图论基础可参考上一篇《图的基本知识总结》
特殊图
可看JosonLe’ notes排版更好
- <a href='#1'>欧拉图
- <a href='#2'>哈密尔顿图
- <a href='#3'>二部图（二分图）
- <a href='#4'>平面图
- <a href='#5'>多边形图、对偶图</a>
可参考文章:
欧拉图
先定义一下欧拉路径(有称欧拉链)和欧拉闭路（有称欧拉圈）：
1. 欧拉路径，包含图G中所有边的简单开路径。通俗的说,把所有的边遍历且仅遍历一次的通路，不会回到出发点。
2. 欧拉闭路，包含所有边的简单闭路径(简单回路)。同上含所有边、不经过重复边、但回到出发点
欧拉闭路
欧拉路径
- 规定平凡图是欧拉图
- 含有欧拉路径的图叫做半欧拉图
- 若G是==连通无向图==，则
- 每个节点都是偶结点，则G是欧拉图
- 由1)，当且仅当G有欧拉闭路，则G是欧拉图
- 由1)、2)当且仅当G仅有两个奇结点V1、V2，则存在由V1到V2的欧拉路径。（形象的看，V1到V2再加上一条边就能由欧拉路径构成了欧拉回路，奇结点也变成偶了）
- 若G是==连通有向图==，则
- 每个节点入度等于出度，则G是欧拉有向图
- 若G是弱连通有向图，当且仅当G有欧拉闭路，则G是欧拉有向图
- 类似无向图，当且仅当弱联通有相同G有两个节点V1、V2，有
$d_{G}^{+}(V1)=d_{G}^{-}(V1)+1 , d_{G}^{-}(V2)=d_{G}^{+}(V2)+1$,除此之外的结点入度等于出度，则由V1到V2存在一条欧拉路径(+是出度-是入度)
如上公式，简书不支持插入公式
-
若G1、G2是欧拉图且可运算，则G1同或G2也是欧拉图（用处不大
-
一笔画问题：欧拉路径或欧拉图就能一笔画完。
图(b)欧拉有向图，图(c)欧拉路径
哈密尔顿图
具有哈密尔顿回路的图叫做哈密尔顿图，==哈密尔顿回路==：经过所有顶点且仅经过一次的回路，只谈无向图，有向图没意义
同理可得哈密尔顿路径，同上只是不回到出发点
如图
-
完全图必定是哈密尔顿图
-
充分条件：
-
无向简单图G，n个结点，每一对结点度数之和大于等于n-1，则G中含有一条哈密尔顿路；若每一对不相邻结点度数之和大于等于n，则G是一个哈密尔顿图
哈密尔顿图，但不满足如上充分条件
-
-
必要条件：---------->用来判断某些图是否是哈密尔顿图
- 哈密尔顿图G的结点集V（G）任一非空子集s，都有
$w(G-s)\leqslant \left | s \right |$,$w(G-s)$指G删去s中的点后，图的连通分支数，|s|是点集s顶点的个数
如上公式
- 哈密尔顿图G的结点集V（G）任一非空子集s，都有
-
由必要条件可知，哈密尔顿图不含割点
二部图
无向图G点集V可划分为{V1，V2}，使得V1中每个节点都不与V2中结点相邻，则称G为二部图
可知二部图：
- 没有回路
-
或回路长度为偶数
如图，右图是左图另一形式
完全二部图：V1,V2是简单二部图G的互补结点子集，V1中每个点与V2中每个点相邻。可以记作$K_{m,n}$,边数m*n，上图也是完全二部图，$K_{3,3}$
如上公式
二部图匹配问题
- 匹配
- 极大匹配
- 最大匹配:包含边数最多的那个匹配就是图G的最大匹配
求二部图的最大匹配可以使用最大流（maximal flow）或匈牙利算法（Hungarian algorithm）
- 匹配数：最大匹配包含的边数
- 最大匹配一定是极大匹配，但极大匹配不一定是最大匹配
- 无向图中可以有多个极大匹配和最大匹配
- 完美匹配:如果一个最大匹配中所有的点都有边与之相连，没有未覆盖点，则这个最大匹配就是完美匹配。
未覆盖点的定义是：图G的一个顶点Vi，如果Vi不与任何一条属于匹配M的边相连，则成Vi是一个未覆盖点
太晚了，可以看我的笔记（开头连接），不想写了。。。
网友评论