图 论
• 图——基本概念
– 图、路与连通、最短路、有向图、图的矩阵
• Euler图与Hamilton图 • 树
– 树、生成树、有向树
• 平面图 图的着色
– 平面图、对偶图、顶点着色、面着色
• 网络 匹配 独立集
树
• 树的概念 • 生成树 • 有向树
树
• 定义1 连通无回路的图称为树，树中度为 1的点称为树叶，度大于1的点称为分枝点 或内点，每个连通分支均为树的图称为森 林。
Kruskal算法
(1)选取G的一边e1，使w(e1)＝min{w(e)|e∈E}，令E1 ＝｛e1｝ (2)若已选出Ei＝｛e1，…，ei｝，那么，从E－Ei中 e 选取一边ei＋1，使 (Ⅰ)Ei∪｛ei＋1｝的导出子图中不含回路； (Ⅱ)w(ei＋1)＝min{w(e)|e∈E－Ei , Ei∪{e}的导 出子图无回路} (3)若ei＋1存在，令Ei＋1＝Ei∪｛ei＋1｝，i＋1→i，转 (2)，若ei＋1不存在，则停止。
• 定理２ 任意一棵非平凡树 T 中，至少有 两片树叶。
• • •
作业 证明 非平凡树中最长路的起点和终点 均为树叶。 证明 一棵树恰有２片树叶，则此树为 路。
生成树
• 定义1 若图G的生成子图T是树，则称T为 G的生成树。
• 定理1 G是连通图当且仅当G有生成树。
• 权图G中带权最小的生成树称为最小生成树 • Kruskal算法 • 输入：简单连通图G ，权函数w 。 • 输出：最小生成树T
(a)
b1
b2
(b)
b3
• 定义４ 设u是有根树T的一个顶点，Vu是u 及其子孙构成的顶点集，Vu的导出子图称为 T的以u为根的子树。 • 定
1
2
3
4
(a)
(b)
• 定义６ 在有序树中，如果每个顶点v都满 足ｄ＋(v)≤m，则称该有序树为m叉树，如果 每个顶点v都满足ｄ＋(v)＝m，称该有序树为 正则m叉树。 • 一类重要的m叉树是二叉树和正则二叉树。 左儿子、右儿子，左子树、右子树。
c5
• 定理1 设T是一棵有根树，r是T的根，则r 到其余每个顶点恰有一条有向路。
• 有根树的画法 • 定义３ 儿子，父亲，兄弟，子孙，祖先； 从根到某一顶点的路长称为该顶点的路长 或层数，从根到树叶的最大层数，称为有 r 根树的高。
a
a1
a1 a2
v 11
v 22
…
…
…
图 3.2
…
b1
b2
b3
有向树
• 定义1 设D是一个有向图，如果在不考虑 弧的方向时D是一棵树(即D的底图是一棵树) 则称D为一棵有向树。 • 定义２ 若一棵有向树中恰有一个顶点的 入度为０，其余所有顶点的入度均为1，则 称该有向树为有根树(或树形图)，入度为０ 的顶点称为根。
a b1 b2
c1
(a)
c2
c3
(b)
c4
(a)
(b)
• 定理1 设图T是有n个顶点、ε条边的非平凡图， 则下列各条等价。 (1) T是树。 (2) T中无回路，且ε＝n－1。 (3) T连通，且ε＝n－1。 (4) T中无回路，且在T的任意两个不相邻点之间 添加一边恰得一条回路。 (5) T连通，删去任一边则不连通。 (6) T的任意两个不同顶点之间恰有一条路。
• 上面的算法能执行吗？ • 会终止吗？ • 每次执行结果一样不一样？
• 定理２ Kruskal算法得到的图T*是最小生 成树。 • 证明:
（1）T*是生成树。 （2） E(T*) ＝｛e1，…，en-1｝，若T*不是最小 生成树，设T1是最小生成树，则T*中必有边不 在T1中，设ek是第一条不在T1中的边……
• 定理２ 在正则m叉树中，分枝点数i与树 叶数l满足 (m－1)i＝l－1。
• 定理３ 设T是正则m叉树，I表示分枝点的 路长总和，L表示树叶的路长总和，i是分枝 点数，则 L＝(m－1)I＋mi。
• •
作业 对非平凡正则m叉数的分枝点数i施行归纳 法，以证明定理２。