离散数学【11. 图】

图的基本概念

顶点v：非空顶点集

边e：边集，弧集

无向图(v1，v2)，其中e3和e2称为平行边或多重边

有向图<v1，v2>，其中v4叫做孤立点

底图：有向图将有向边改为无向边得到的无向图

结点与边之间的关系

1. 邻接点：同一条边的两个端点
2. 孤立点：没有边与之关联的结点
3. 邻接边：关联同一个结点的两条边
4. 孤立边：不与任何边相邻接的边
5. 自回路(环)：关联同一个结点的一条边(v,v)或者<v,v>
6. 平行边(多重边)：关联同一对结点的多条边，两结点间相互平行的边的条数称为该平行边的重数

图的分类

1. 零图：有n个顶点，0条边
2. 平凡图：有1个顶点，0条边
3. 多重图：含有平行边的图
4. 线图：非多重图
5. 简单图：不含平行边和自回环的图
6. 完全图Kn：任意两个结点之间都邻接的简单图（n个结点）
7. 二部图Kn,m：一部分n个结点m条边，另一部分m个结点n条边的简单图

结点的度

关联：点与边

邻接：点与点、边与边

最大度：各个结点中的最大度

最小度：各个结点中的最小度

有向图的度：出度+入度（环有两个度，孤立点没有度）

握手定理：任意图 中 所有顶点的度数之和 = 边数×2

奇结点：度数为奇数的结点

偶结点：度数为偶数的结点

推论：因为度数肯定是偶数，所有每个图必须有偶数个奇结点

k度正则图：每个结点的度数都等于k的无向图

无向完全图Kn：每个顶点的度数都是n-1，一共有n(n-1)/2条边

图的同构

判断两个图是否同构：两个图的点集一一对应，边与边也是一一对应，邻接关系也是一样的，如果是有向图，那方向也要保持一致。

同构的性质：

1. 图之间的同构关系具有自反性、对称性、传递性
2. 相同的结点数
3. 相同的边数
4. 度数相同的结点数目相同
5. 有相同重数的边数相同

图的同构判定算法：

1. 关联度序列法
2. 黄金分割关联度序列法

子图和补图

子图：顶点集和边集都包含于图；

真子图：顶点集和边集都包含于图，并且不能与图相同；

生成子图：顶点集和图必须一致，边集都包含于图；

顶点集导出子图：顶点集都包含于图，边就是这些顶点可能连接的边；

边集导出子图：边集都包含于图，由边所引出的顶点；

G`是G的补图：

1. 相同的顶点集
2. 边集不相交
3. 互为补图
4. 边总数=n(n-1)/2 = G`的边集+G的边集

路径与回路

路径：从起点到终点（V0e1V1e1...emVm）

通路：开路、闭路

回路（闭路，圈）：起点=终点

简单(回)路：无向图中边互不相同的路

基本(回)路：无向图中顶点互不相同的路（任何结点到自身都有长度为0的基本路），每条基本路必定是简单路。

无向图的连通性

连通：两个顶点之间存在路径

连通图：图中任意两个顶点都是连通的

结点自身：不是邻接除非有环，但是连通的

连通分支：图是一个连通图就是它自己w(G) = 1，图是一个分离图，顶点集可以按照等价关系划分。

连通分支的个数：w(G) = n

删除顶点和边

删除顶点集（G-S）：图G中删除顶点集S，将G中删除点，以及点所连接的边；

删除边集（G-T）：图G中删除边集T，将G中删除边；

点割集(不唯一)：图G是连通图，删除顶点集V，就不是连通图了(分离图)；

割点(不唯一)：图G是连通图，只删除顶点V，就不是连通图了(分离图)；

点连通度k(G)：G不是完全图，图的全部点割集中包含点最少的点割集；分离图k(G)=0，存在割点的连通图k(G)=1；

边割集：图G是连通图，删除边集E，就不是连通图了；

割边：图G是连通图，只删除边e，就不是连通图了(分离图)；

边连通度入(G)：G不是平凡图，图的全部边割集中包含边最少的边割集；分离图入(G)=0，存在割边的连通图入(G)=1；

对于任何一个无向图G，k(G)≤k(G)≤最小度

有向图的连通性

单向可达：两个点之间存在一条有向路（自反性、传递性）

单向连通：图中任意两个点至少存在一边单向可达

双向可达：两个顶点双向可达，是一个等价关系

无向图的连通性关系：连通图、分离图

有向图的连通性关系：强连通图(回路) => 单向连通(通路) => 弱连通图 => 分离图

强分图：G`是G的子图，G`是强连通图，G`增加G中其他任意的点或边就不再是强连通；

单向分图：

弱分图：

无向欧拉通路：无向图中只存在0个或者2个奇度结点

有向欧拉通路：是每条边经过且仅经过一次的通路

判断是有向欧拉通路的充分必要条件：

1. 有向图中有两个顶点的出度与入度不相等，其中一个出度比入度多1，另一个的入度比出度多1；
2. 所有顶点都是出度=入度

判断是有向欧拉回路的充分必要条件：

1. 所有顶点都是出度=入度

哈密顿通路：每个顶点经过且仅经过一次的通路；

判断是哈密顿通路的充分条件：n阶无向简单图，存在两个顶点不连接，两个顶点的度数之和≥n-1；

判断不是哈密顿回路的必要条件(满足一定不是，不满足不一定是)：

1. 有割点或桥的图一定不是哈密顿图（推论）
2. 连通分支数 ≤ 删掉的顶点数

判断是哈密顿回路的充分条件：（n阶无向简单图G中）

1. 顶点v与顶点u不邻接，d(v)+d(u) ≥ n（奥尔定理）
2. 最小度 ≥ n/2（狄拉克定理）
3. 图的闭包是一个无向完全图，那原图就是哈密顿图

无向完全图Kn一定是哈密顿图

图的闭包C：连接任意两个度数之和≥n且不邻接的顶点（加边）