离散数学_十章-图 ( 2 ):图的术语和几种特殊的图(二)

简介: 离散数学_十章-图 ( 2 ):图的术语和几种特殊的图(二)

5. 定理:入度的和 = 出度的和 = 边数


带有向边的图有许多性质是不依赖于边的方向的。


因此,忽略这些方向经常是有用处的。忽略边的方向后得到的无向图称为基本无向图。带有向边的图与它的基本无向图有相同的边数。


6. 几种特殊的图


6.1 完全图 Kn

完全图:n个顶点的完全图记作Kn,是在每对不同顶点之间都恰有一条边的简单图


非完全图:至少有一对不同的顶点不存在边相连的简单图


含n个顶点的完全图的边数:n · (n - 1)/2,即C2n


为什么K~n~表示完全图呢? 一些消息来源称,这个符号中的字母K代表德语单词komplett,但完全图的德文名称vollständigerGraph不包含字母K,其他来源则表示符号表示KazimierzKuratowski图论


6.2 圈图 Cn

圈图:圈图Cn(n ≥3 )是由n个顶点v1,v2,···,vn以及边{v1,v2},{v2,v3},···,{vn-1,vn},{vn,v1}组成的


Cn,C表示circle嘛


含n个顶点的圈图的边数:n



6.3 轮图 Wn

轮图:当给圈图Cn(n ≥3 ),添加另一个顶点,并把这个新顶点与Cn中的n个顶点逐个连接时,就得到轮图Wn

注意,轮图Wn的下标n是轮圈上的顶点数,不是总顶点数(总顶点数是n+1,加上中心的那个顶点)


Wn,W表示wheel(轮)嘛


含n个顶点的轮图的边数:2 ·(n - 1)



6.4 n立方体图 Qn

n立方体图:n立方体图记作Qn,是用顶点表示2n个长度为n 的比特串的图。


注意,两个顶点相邻 iff 它们所表示的比特串恰恰有一位不同。


含n个顶点的n立方体图的边数:2n



7. 二分图


定义:若把简单图G的顶点集分成两个不相交的非空集合V1和 V2, 使得图中的每一条边都连接V1中一个顶点和V2中的一个顶点(因此G中没有一条边会连接V1中两个顶点或V2中两个顶点),则G称为二分图。


当此条件成立时称(V1,V2)为G的顶点集的一个二部划分。


7.1 判断一个图是否为二分图的定理

定理:一个简单图是二分图 iff 能够对图中的每个顶点赋予两种不同的颜色,并使得没有两个相邻的顶点被赋予相同的颜色。


例题:

例1:说明C6是二分图


🔴解:


C6是二分图,因为它的顶点集被分成两个集合V1 = { v1, v3, v5}和V1 = { v2, v4, v6},C6的每一条边都连接V1中的一个顶点和V2中的一个顶点



例2:说明K3不是二分图


🔴解:


若把K3内顶点集分成两个不相交的集合,则两个集合之一必然包含两个顶点。假如这个图是二分图,那么这两个顶点就不能用边连接,但是在K3中每一个顶点都有边连接到其他每个顶点。


上面这两个例题当然也可以直接用染色法,很容易判断


7.2 完全二分图

完全二分图 Km,n 是顶点集划分成分别含有 m 和 n 个顶点的两个子集的图,并且两个顶点之间有边 iff 一个顶点属于第一个子集,而另一个顶点属于第二个子集。

相关文章
|
7月前
|
存储 测试技术 开发工具
软考中的UML图、数据流图等二十余种示例
软考中的UML图、数据流图等二十余种示例
595 0
|
机器学习/深度学习 算法 数据挖掘
图神经网络02-图与图学习(下)
图神经网络02-图与图学习(下)
484 0
图神经网络02-图与图学习(下)
|
算法 容器
图压实算法
## 一、定义 将一个原本较为稀疏的图布局,进行压实操作,从而提高画布空间利用率,便于用户理解。 ## 二、适用场景 1. 图面积最小化:即移除多余的空间,将稀疏图变为紧密图。 1. 布局编译:从符号布局生成蒙版布局,电路板。 1. 重新设计:自动清除违反设计规则的情况。 1. 重新缩放:将蒙版级别的布局从一种技术转换到另一种。 在实际场景中,通常用于电路板的排版中。
290 0
图压实算法
|
Java uml
【UML图】实现图
【UML图】实现图
|
算法 测试技术 uml
【UML图】行为图
【UML图】行为图
离散数学_十章-图 ( 2 ):图的术语和几种特殊的图(一)
离散数学_十章-图 ( 2 ):图的术语和几种特殊的图(一)
121 0
|
算法 数据中心
离散数学_十章-图 ( 1 ):图的相关定义
离散数学_十章-图 ( 1 ):图的相关定义
179 0
|
机器学习/深度学习
离散数学_十章-图 ( 4 ):图的表示和图的同构
离散数学_十章-图 ( 4 ):图的表示和图的同构
297 0
|
Java
离散数学_十章-图 ( 3 ):由旧图构造新图
离散数学_十章-图 ( 3 ):由旧图构造新图
147 0