离散数学_十章-图 ( 1 ):图的相关定义

简介: 离散数学_十章-图 ( 1 ):图的相关定义

图是一种非线性的数据结构,也是由顶点和连接顶点的边构成的离散结构


根据图中的边是否有方向、相同顶点对之间是否可以有多条边相连以及是否允许存在自环,图可以分为多种不同的类型。


通过运用各种图模型,图可以用来建模应用问题


本章将介绍图论的基本概念,还将给出许多不同的图模型。为了求解能够用图研究的多种问题,我们将介绍许多不同的图的算法,还将研究这些算法的复杂度。


1. 图的定义


图 G = (V , E) 由 顶点(或结点)的非空集V 和 边集E 构成,每条边有一个或两个顶点与它相连,这样的顶点称为边的端点。边连接它的端点。


顶点集比边集更重要,在图中加一条边,需要加的顶点数:0或1或2


顶点集:Vertex Set 👉 V

边集:Edge Set 👉 E


2. 有限图 和 无限图


顶点集V 为无限集或有无限条边的图称为无限图


顶点集和边集都为有限集的图称为有限图


// 我们目前只考虑有限图


3. 多重边、多重图


一个计算机网络可能在两个数据中心之间有多重链接,如图2所示。

为这样的网络建模,需要有多条边连接同一对顶点的图。

→ 存在多重边连接同―对顶点的图称为多重图。


当有m条不同的边与相同的无序顶点对相关联时,我们也说 {u,v} 是一条多重度为m的边。可以认为这个边集是边 {u,v} 的m个不同副本。


注: {u,v} 中的 u 和 v 表示的是两个顶点;{u,v}表示的是这两点间的边


通俗来说,多重图就是存在某两点间有不止一条边的图


4. 简单图 和 伪图


简单图

每条边都连接两个不同的顶点 且 没有两条不同的边连接一对相同顶点的图称为简单图。


通俗来说,简单图即:没有自回路、没有多重边的图

或者说 不是伪图的图是简单图


伪图

包含环或存在多重边连接同一对顶点或同一个顶点的图,称为伪图


注:在简单图中,每条边都与一对无序的顶点相关联,而且没有其他的边和这条边相关联。因此,在简单图中,当有一条边与{u,v}相关联时,也可以说{u,v}是该图的一条边,这不会产生误解。


5. 有向图 、无向图 、混合图


无向图:所有边都没有方向的图。如上面的图2

有向图:所有边都有方向的图。有向图的边也叫箭弧。

混合图:既包含有向边又包含无向边的图。


有向图 (V , E) 由一个非空顶点集V和一个有向边(或弧)集E组成。


每条有向边与一个顶点有序对(代表起点、终点)相关联。我们称与有序对(u,v)相关联的有向边开始于u,结束于v


5.1 简单有向图

当对一个无向图的每一条边都赋予方向后,就得到了一个有向图。


当一个有向图不包含环和多重有向边时,就称为简单有向图。因为在简单有向图中,每个顶点有序对(u,u)之间最多有一条边和它们相连,如果在图中,(u,v)之间存在一条边,则称(u,v)为边


5.2 多重有向边 → 有向多重图

在某些计算机网络中,两个数据中心之间可能有多重的通信链路,如图5所示。


可以用包含从一个顶点指向第二个 (也许是同一个) 顶点的多重有向边的有向图来对这样的网络建模,我们称这样的图为有向多重图。当m条有向边中的每一条都与顶点有序对(u,v)相关联时,我们称(u,v)是一条多重度为m的边


表1 图术语


类型

允许多重边

允许环

简单图

无向

多重图

无向

伪图

无向

简单有向图

有向

有向多重图

有向

混合图

有向 和 无向 都有

相关文章
|
机器学习/深度学习 数据建模 定位技术
【数据结构】图的基本概念—无/有向图、权和网、完全图、路径与回路
【数据结构】图的基本概念—无/有向图、权和网、完全图、路径与回路
5240 0
【数据结构】图的基本概念—无/有向图、权和网、完全图、路径与回路
|
机器学习/深度学习 图计算 图形学
同构图、异构图、属性图、非显式图
同构图(Homogeneous Graph)、异构图(Heterogeneous Graph)、属性图(Property Graph)和非显式图(Graph Constructed from Non-relational Data)。 (1)同构图:
3214 0
同构图、异构图、属性图、非显式图
|
前端开发 Android开发 iOS开发
react native 实现图片预览 图片保存 react-native-image-zoom-viewer
图片 预览,和保存 功能 应该是很常见的APP 功能 。实现起来也很简单。 这里用到的组件是:https://github.com/ascoders/react-native-image-viewer 看下新效果图: [图片上传中.
6791 0
|
11月前
|
安全 JavaScript Java
SpringBoot解决跨域最佳实践
本文介绍了跨域问题的起因及最佳实践,重点讲解了SpringBoot中如何利用`CorsFilter`解决跨域问题。首先解释了由于浏览器的同源策略限制导致的跨域现象,然后提出了在服务端入口处解决跨域问题的建议,最后详细展示了三种SpringBoot中配置跨域的方法:使用默认配置、自定义配置规则以及通过配置文件管理跨域设置,以适应不同的应用场景。
534 5
|
SQL 数据库 索引
SQL中COUNT函数结合条件使用的技巧与方法
在SQL查询中,COUNT函数是一个非常常用的聚合函数,用于计算表中满足特定条件的记录数
2194 5
|
存储 关系型数据库 MySQL
InnoDB 引擎技术文档
【7月更文挑战第6天】InnoDB 是 MySQL 数据库中最常用的关系型数据库存储引擎,自 MySQL 5.5 版本以来成为默认存储引擎。它支持事务处理、行级锁定、外键约束以及崩溃恢复能力,特别适合于高并发、高可靠性的应用场景。InnoDB 引擎还提供了对大容量数据的支持,通过聚簇索引实现数据和索引的紧密集成,优化了查询性能。
275 0
|
10月前
|
SQL 关系型数据库 MySQL
MySQL进阶突击系列(04)事务隔离级别、AICD、CAP、BASE原则一直搞不懂? | 看这篇就够了
本文详细介绍了数据库事务的四大特性(AICD原则),包括原子性、隔离性、一致性和持久性,并深入探讨了事务并发问题与隔离级别。同时,文章还讲解了分布式系统中的CAP理论及其不可能三角关系,以及BASE原则在分布式系统设计中的应用。通过具体案例和图解,帮助读者理解事务处理的核心概念和最佳实践,为应对相关技术面试提供了全面的知识准备。
|
11月前
|
缓存 监控 安全
“您与此网站建立的连接不安全”一招解决
当浏览器提示“您与此网站建立的连接不安全”时,通常表示该网站未使用HTTPS加密链接。解决方法包括:购买并安装SSL证书,强制HTTPS重定向,监控证书有效期,以及全面检查内容来源。普通用户可尝试更新浏览器、清除缓存和Cookies,或使用其他浏览器访问。但根本解决需网站管理员操作。
|
机器学习/深度学习 算法 数据可视化
统计建模——模型——python为例
统计建模——模型——python为例
742 0
|
消息中间件 存储 监控
Kraft模式下Kafka脚本的使用
【9月更文挑战第9天】在Kraft模式下,使用Kafka脚本涉及以下几个关键步骤:启动Zookeeper和Kafka服务、创建主题、发送与消费消息、查看主题列表及描述主题详情。通过指定配置文件与相关参数,如`--replication-factor`和`--partitions`,可以灵活管理主题。此外,确保根据实际需求调整配置文件中的参数,并监控日志以维持最佳性能与及时问题处理。
470 8