图论树与割集

• 生成树的构造方法： 破圈法，避圈法 ¾ 破圈法定理的证明也为我们提供了一种构造生 成树的方法，即每次去掉回路的任一条边，到 不再含有回路为止。这种方法称为破圈法.
¾ 避圈法在G中任找一条边e1，然后找一条不与 e1形成回路的边e2，再找一条不与边集合 (e1,e2)形成回路的边e3，如此继续下去使找 的边都不与已找到的边集合形成回路，直到 过程不能进行下去为止，则所有找到的边集 合{e1,e2,e3,...,em}构成的图就是G的一棵生 成树。
定义3.4 设T是图G的一棵生成树，由T的树枝和一条 弦构成的回路称为对应于这条弦的基本回路，基本 回路的集合，称为基本回路集。 b
b e1 e7 e6 f a c a e9 e5 e d e (a) e4 d f e8 e2 c e3
如左图是右图的一棵生成树则 对应于弦e1的基本回路是C(e1)＝{e1,e6,e7} 对应于弦e2的基本回路是C(e2)＝{e2,e7,e8} 对应于弦e4的基本回路是C(e4)＝{e4,e3,e8,e9} 对应于弦e5基本回路是C(e5)＝{e5 e6 e9} 树T的基本回路集是C＝{C(e1)C(e2)C(e3)C(e4)}
平凡树
•
定理3.1 具有n个结点m条边的无向图T是树， 当且仅当下列条件之一成立。
1. T无回路且m＝n一1 2. T连通且m＝n一1 3. 任意两结点之间必然存在且仅存在一条基本路 径(n≥2) 4. 无回路，如在任意两结点之间添上一条边，得 到一个且仅一个基本回路。(n ≥ 2) 5. 图连通，但去掉任一条边图将不连通。
1) T无回路且m＝n一1 (证明树的定义<=>条件(1)) 必要性(=>)设T是树。现对结点进行归纳证明 m＝n一1。 当n＝1时，m＝0，公式成立。设n=k时公式成立， 即m＝k-1，考察n=k+1的情况，即增加了一个结点。设 为v，下面证明结点v仅与原k个结点中的一个结点连接. 如不然。不与k个结点中的任一结点连接，则v是孤 点，与树是连通的定义不符。 如果v与k个结点中连接的点不止一个，不妨设两个点 v1与v2都与v连接，即与v关联的边有两条(v,v1)及 (v,v2)，因为v1与v2是原来k个点中的任意两个点，它 们原来是连通的，这样v1与v2将通过与v关联的这两条 边形成回路，与树无回路矛盾，因此，增加一个点一 定增加也只能增加一条边，故公式m=n-1成立。
• 定理3．4 任何一棵有两个以上结点的树至 少有两片树叶。 证：已知 m = n −1又 ∑ deg(v ) = 2m = 2n − 2 因树 是连通的， 没有次数为0的结点（孤点）。 如果树没有一片树叶（即任一结点的次数都 ∑ deg(v ) ≥ 2n 与 ∑deg(v ) =2n−2 大于等于2）则 矛盾， 如果树只有一片叶，则
不包含在回路中时，e才是割边。
定理3.3
无向树T的所有分枝点均为割点。
证：设v是T的任一分枝点，则deg(v)＞1,所 以存在与v邻接的不同的结点u与w,因此uvw则 是T中u到w的唯一一条通路，若在T中去掉v及 其关联边后，u与w将不连通,按定义，v是割点。
如果去掉一个结点v及与v关连的边，图将不连通， 则称结点v为图的割点。
充分性(<=)设条件(1)成立，只要证明图连通，根据 定义,即得T是一棵树。 【反证法】 设图不连通而是分成了K个连通分支 T1,T2,...,Tk, 每一分图的结点数和边数用ni和mi表 示(1≤i ≤ k)，则 k k
n=
∑n
i =1
i
m=
∑m
i =1
i
因每一个分图都是连通的而且无回路，根据树的定义 知每个分图都是一棵树，应有mi＝ni一1．故
d
最小生成树 最小生成树很有实际应用价值.例如结点是 城市名,边的权表示两个城市间的距离, 从一个城市出发走遍各个城市,如何选择 最优的旅行路线.又如城市间的通信网络 问题,如何布线,使得总的线路长度最短. 例如:右图所示 2 v2 D D v3 3 5 1 2.求最小生成树算法 7 1 2 7 v1 D 8 v8 D D v5 3 D v4 ---Kruskal算法: 4 3 4 6 2 4 v7 D D v6 (避圈法) 6
③ 设T是G的一棵生成树，B是G的任一回路，不失一般性， B包含边的集合写成 {e , e ,..., e , e ,..., e }
i1 i2 ij ij +1 im
其中 eik 是弦 (k = 1,2,..., j ) , eir (r = j + 1,2,..., m) 是树枝, 则含有上面这些弦的基本回路可以写成 Ci1 , Ci 2 ,..., Cij B' = Ci1 ⊕ Ci 2 ⊕ ... ⊕ Cij 设 因此B’只含弦 e i1 , e i 2 ,..., e ij 不再含其他的弦，而B也只 含这些弦， 所以 B ⊕ B'将不再含有弦而只含有树枝，但是我们知道回路 的环和仍是回路或者是回路的边不重并集,因此只含树枝而 不含弦是不可能的，只能有 B ⊕ B ' = φ 成立， 即 B = B' = C ⊕ C ⊕ ... ⊕ C
4)无回路，如在任意两结点之间添上一条
边，得到一个且仅一个基本回路。(n ≥ 2) 必要性：设T是树．故无回路，由(3)已证任 意两点vi与vj之间有且只有一条基本路 径，故添上一条边(vi,vj)，只能得到唯 一的一条基本回路，故条件(4)成立。 充分性：设条件(4)成立，因而图无回路， 往证明图是连通的，若图不连通，则存在 两点，这两点之间不存在路径，则在这两 点之间添上一条边就不可能得到一个回路 与条件矛盾。
m=
∑ m = ∑ (n − 1) = n − k
i i i =1 i =1
k
k
如k≥2 ,则m=n-k<n-1与题设矛盾，所以图是连通 的，即图T是树。
2) T连通且m＝n一1
必要件：设T是树，则T连通且由(1)已证m=n-1， 故条件(2)成立。 充分性：设条件(2)成立，只要证明图无回路即符 合树的定义。 现对n用归纳证明，当n＝1或2时，显然图无回 路，命题成立。设n＝k时图无回路，这时边的数目 为m’=k-1现考察n=k+1时的情况，增加了一个结 点，设为v,此时边的数目为m=k,比m’多了一条边， 这条边的一个端点必然是v(否则v无关联达成为孤 点，与图是连通的相矛盾)另一个端点是原来k个结 点中的某一结点，由于原来k个点是无回路的，现 在增加的这条边也不可能通过结点v构成回路，即 m＝k+1 时图也无回路，按定义图T是树.
n i i =1
n
n
i
i
i =1
1 i=
∑ deg(v ) ≥ 2(n −1) +1 = 2n −1
i i =1
n
仍然矛盾，故至少有两片树叶。 • 定义 由不相连的树组成的图称为森林。
生 成 树
• 生成树 若无向图G的生成子图T是一棵树， 则称T为图G的生成树。
图中(b)，(c)，(d) 等是图(a)的生成树。
定理3.6 设G是一连通无向图，则 ① G的任一回路至少含一条基本回路的弦. ② 所有基本回路的环和不为空集，即
⊕C
i =1
kiΒιβλιοθήκη ≠ φ , k = N (G ) = m − n + 1
③ G的任一回路均可写成是若干个基本回路 的环和。
证： ① 如果有一回路不含任何基本回路的弦，即 回路中的边全是树枝，它们一定包含在生 成树中，但生成树是没有回路的，所以回 路中至少有一条边不是树枝而是弦。 ② 因为每一基本回路只有一条弦，不同的基 本回路含有不同的弦，根据环和的性质， 所有基本回路的环和不可能是空集。
定理3．5 一个连通图至少有一棵生成树。 证： 如果连通图G无回路，根据的定义，则G本身就是 一棵生成树。 如果连通图G有回路，去掉回路的任一条边得到生 成子图G1，显然G1仍然是连通的，如果G1不含回 路，则G1就是G的生成树，否则又可去掉回路的任 一条边得到另一个生成子图，只要生成图还有回 路，就去掉回路的一条边，由于图的有限性，最 后一定得到不含回路的生成子图T，由于每次去掉 回路的一条边，并不破坏图的连通性，所以T是G 的生成树。
|S|=n-1, 说明是树 最后S={a1, a2, a3,… ,an}
边按升序排序:边(vi, vj)记成eij e34 e23 e38 e17 边 e28 权
e24
e45 3 e12 7
e57 3 e18 8
e16 4
1 1 2 2 2 3 e35 e46 e67 e58 边 e78 e56 4 5 6 6 7 权 4 2 v2 D D v3 3 5 1 1 7 2 7 v1 D 8 v8 D D v5 3 D v4 4 3 4 2 v2 D 6 2 4 v7 D D v6 1 6 v1 D v8 D 4 2 v7 D
Kruskal算法: 设G是有n个结点,m条边(m≥n-1)的连通 图. S=Φ i=0 j=1 将所有边按照权升序排序: e1, e2, e3,… ,em S=S∪{ai} j=j+1 ai=ej i=i+1 N |S|=n-1 Y 输出S N 取ej使得 S∪{ ej}有回路? Y j=j+1 停
树与割集
无 向 树 生 成 树 有向树 有向树的应用 图的中心和中位点 图的连通性 习题
树是一种特殊的图, 它是图论中重要的概 念之一, 它有着广泛的应用.在计算机科学中 有如判定树、语法树、分类树、搜索树、目 录树等等.
无
向
树
• 定义 一个连通且不含回路的无向图称为无向树，简称树。 常用符号T(m,n)表示一棵树，其中n表示树的结点数，m表 示树的边数(树枝数)。次数为1的结点称为树的树叶次数大 于1的结点称为树的分枝点，边称为树枝。只有一个结点的 树称为平凡树，它的次数为0(无树枝)，如图中的(d)就是一 棵平凡树。