离散数学_十章-图 ( 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 图术语


类型

允许多重边

允许环

简单图

无向

多重图

无向

伪图

无向

简单有向图

有向

有向多重图

有向

混合图

有向 和 无向 都有

相关文章
|
7月前
|
存储 测试技术 开发工具
软考中的UML图、数据流图等二十余种示例
软考中的UML图、数据流图等二十余种示例
595 0
|
机器学习/深度学习 图计算 图形学
同构图、异构图、属性图、非显式图
同构图(Homogeneous Graph)、异构图(Heterogeneous Graph)、属性图(Property Graph)和非显式图(Graph Constructed from Non-relational Data)。 (1)同构图:
1996 0
同构图、异构图、属性图、非显式图
|
7月前
|
算法 Python
传统流程图和N-S(又称盒图或NS图)结构流程图
传统流程图和N-S(又称盒图或NS图)结构流程图
868 2
|
7月前
|
机器学习/深度学习 数据可视化 PyTorch
基于TorchViz详解计算图(附代码)
基于TorchViz详解计算图(附代码)
265 0
|
7月前
|
存储 搜索推荐 Java
图计算中的顶点和边是什么?请解释其概念和作用。
图计算中的顶点和边是什么?请解释其概念和作用。
190 0
|
算法 测试技术 uml
【UML图】行为图
【UML图】行为图
|
Java uml
【UML图】实现图
【UML图】实现图
|
Java
离散数学_十章-图 ( 3 ):由旧图构造新图
离散数学_十章-图 ( 3 ):由旧图构造新图
147 0
离散数学_十章-图 ( 2 ):图的术语和几种特殊的图(一)
离散数学_十章-图 ( 2 ):图的术语和几种特殊的图(一)
121 0
|
机器学习/深度学习
离散数学_十章-图 ( 2 ):图的术语和几种特殊的图(二)
离散数学_十章-图 ( 2 ):图的术语和几种特殊的图(二)
2515 0