第二章图论基础

目录第一章图的基本概念 (1)二路和连通性 (3)第二章树 (3)第三章图的连通度 (4)第四章欧拉图与哈密尔顿图 (5)一，欧拉图 (5)二．哈密尔顿图 (6)第五章匹配与因子分解 (9)一．匹配 (9)二．偶图的覆盖于匹配 (10)三．因子分解 (11)第六章平面图 (14)二．对偶图 (16)三．平面图的判定 (17)四．平面性算法 (20)第七章图的着色 (24)一．边着色 (24)二．顶点着色 (25)第九章有向图 (30)二有向树 (30)第一章图的基本概念1.点集与边集均为有限集合的图称为有限图。

2.只有一个顶点而无边的图称为平凡图。

3.边集为空的图称为空图。

4.既没有环也没有重边的图称为简单图。

5.其他所有的图都称为复合图。

6.具有二分类（X, Y）的偶图（或二部图）：是指该图的点集可以分解为两个（非空）子集X 和Y ，使得每条边的一个端点在X 中，另一个端点在Y 中。

7.完全偶图：是指具有二分类（X, Y）的简单偶图，其中X的每个顶点与Y 的每个顶点相连，若|X|=m，|Y|=n，则这样的偶图记为Km,n8. 定理1 若n 阶图G 是自补的（即），则n = 0, 1（mod 4）9. 图G 的顶点的最小度。

10. 图G 的顶点的最大度。

11. k-正则图: 每个点的度均为 k 的简单图。

例如,完全图和完全偶图Kn,n 均是正则图。

12. 推论1 任意图中，奇点的个数为偶数。

13.14. 频序列：定理4 一个简单图G 的n 个点的度数不能互不相同。

15. 定理5 一个n 阶图G 相和它的补图有相同的频序列。

16.17.18. 对称差：G1△G2 = (G1∪G2) - (G1∩G2) = (G1-G2)∪(G2-G1)19. 定义： 联图 在不相交的G1和G2的并图G1+G2中，把G1的每个顶点和G2的每个顶点连接起来所得到的图称为G1和G2的联图，记为G1∨G220. 积图：积图 设G1= (V1, E1)，G2 = (V2, E2)，对点集V = V1×V2中的任意两个点u =(u1,u2)和v = (v1,v2)，当(u1 = v1和 u2 adj v2) 或 (u2 = v2 和 u1 adj v1) 时就把 u 和 v 连接起来所得到的图G 称为G1和G2积图。

end;
end;
end;
End； 15
End； End；
以上dfs(i)的时间复杂度为O（n*n）。 对于一个非连通图，调用一次dfs(i)，即按深度优先顺序依次访问了顶点i所在的（强）连通分支，所以 只要在主程序中加上：for i:=1 to n do {深度优先搜索每一个未被访问过的顶点}
if not Visited（I) then dfs(i);
Begin
访问顶点i；Visited[i]:=true;顶点i入队q；
while 队列q非空 do
begin
从队列q中取出队首元素v；
for j:=1 to n do
begin
if (not Visited[j]) and (a[v,j]=1) then
begin
时间：O（n*n）
访问顶点j；Visited[j]:=true;顶点j入队q
强连通分支：一个有向图的强连通分支定义为该图的最大的强连通子图， 右图含有两个强连通分支，一个是1和2构成的一个子图，一个是3独立构 成的一个子图。
7
图论算法与实现
一、图论基础知识
3、图的存储结构（n阶e条边）：
8
图论算法与实现
一、图论基础知识
4、图的遍历： 从图中某一顶点出发系统地访问图中所有顶点，使每个顶点恰好
11
图论算法与实现
一、图论基础知识
4、图的遍历： 图的宽（广）度优先遍历：类似于树的按层次遍历。从图中某个顶点V0出 发，访问此顶点，然后依次访问与V0邻接的、未被访问过的所有顶点，然 后再分别从这些顶点出发进行广度优先遍历，直到图中所有被访问过的顶 点的相邻顶点都被访问到。若此时图中还有顶点尚未被访问，则另选图中 一个未被访问过的顶点作为起点，重复上述过程，直到图中所有顶点都被 访问到为止。

0° ≤ β < 360°
判断点与多边形位置关系的铅垂线内点算法 判断点与多边形位置关系的铅垂线内点算法
(适用于带孔多边形 适用于带孔多边形) 适用于带孔多边形
基本思想:从待判别点引铅垂线， 基本思想:从待判别点引铅垂线，由该铅垂线 注意：是一条射线）与多边形交点个数的奇 （注意：是一条射线）与多边形交点个数的奇 偶性来判断点是否在多边形内 来判断点是否在多边形内。 偶性来判断点是否在多边形内。 若交点个数为奇数，点在多边形内； 若交点个数为奇数，点在多边形内； 若交点个数为偶数，则该点在多边形外。 若交点个数为偶数，则该点在究的重点问题是求线与面的相交。 线面关系研究的重点问题是求线与面的相交。 求线与面的相交 线段与多边形交线的算法 ：
第一步，求多边形的最小投影矩形。 第一步，求多边形的最小投影矩形。 第二步， 第二步，判断线段是否有端点在该最小投影矩形 若不在，结论为“线段与多边形相离” 中。若不在，结论为“线段与多边形相离”，算 法结束；否则，执行第三步。 法结束；否则，执行第三步。 第三步，顺次判断线段与多边形各边是否有交点， 第三步，顺次判断线段与多边形各边是否有交点， 若有交点，则求出并保存交点坐标。 若有交点，则求出并保存交点坐标。 第四步，对交点坐标排序：计算各交点与线段一 第四步，对交点坐标排序：计算各交点与线段一 端点的距离 的距离， 端点的距离，然后按照距离由小到大对交点编号 排序。 排序。 第五步，按规律连接各个交点， 第五步，按规律连接各个交点，得到位于多边形内部的 连接各个交点 交线。 交线。
判断点线侧位关系的意义？ 判断点线侧位关系的意义？
1.2 点、线关系的判别方法 点线关系判别的目的之一是确定点是否在线上。 点线关系判别的目的之一是确定点是否在线上。

定义2.2.2 如果在图G中去掉一个顶点（自然同 时去掉与该顶点相关联的所有边）后图的分 支数增加，则称该顶点为G的割点。
定理2.2.1 当且仅当G的一条边e不包含在G 的 圈中时，e才是割边。
u x
e
v
Hale Waihona Puke yCG推论2.2.1 当且仅当连通图G的每一条边均为 割边时，G才是一棵树。
对割边有下面的等价命题：
推论2.1.3 设G的边数为q，顶点数为p,如果 G无圈且q=p-1，则G是一棵树。
推论2.1.4 在树中至少存在两个度为1的顶点。
关于树有下列的等价命题：
（1）G是一棵树 （2）G的任意两个顶点由唯一道路联结 （3）G是连通的，且q=p-1 （4）G是无圈的，且q=p-1 （5）G无圈，且若G的任意两个不邻接的顶点 联一条边e，则G+e中恰有一个圈。
A directed graph is Eulerian if it is connected and can be decomposed into arc-disjoint directed cycles.
An undirected graph is traversable if it is connected and at most two vertices in the graph are of odd degree
条包含G的所有边的闭链； ❖ （4）两个欧拉图的环和仍是欧拉图。
理定3.1.2和推论3.1.1反映了图的一 个重要性质，即图的连绘性。一个连 绘的图是指这个图可以用一笔画成而 没有重复的笔划。换句话说就是在这 个图中存在一条能过每条边的链。
3.3 哈密顿图
1856 年 hamilton 周游世界的游戏，十 二面体，有20个顶点，三十条边，十二 个面