第4讲 生成树

树，割集，最小树定义：连通无圈的图称树，平凡图称为平凡树。若非连通图的每一连通分支都是树，则称其为森林。设T=(V,E)是一棵树.vV，若d(v)=1,则称v为T的悬挂点，若d(v)≥2,则称v为分支点。·6个顶点的树···································树的等价定义定理2.1设G=(V,E)是一图，|V|=n，|E|=m。则以下命题是等价的。(1)G是树（连通，无圈）(2)G的每对顶点之间有唯一的一条路(3)G连通且m=n-1(4)G无圈且m=n-1(5)G无圈,在G的任一对顶点上加一新边后产生圈(6)G连通，但删去任何一边后不再连通。证明：可以按照(1)(2)(3)(4)(5)(6)(1)的次序来证明。Vv2-22d(v)证：设G是非平凡树，则对所有v∈V,有d(v)≥1。由定理1.1，知由此推出至少有两个顶点v，使d(v)=1。推论2.1.1每棵非平凡树至少有两个度为l的顶点。定义：称e∈E是G的割边，若ω(G-e)＞ω(G)。·······uvwx·图中粗线所表示的边为割边割边（cutedge）•定义：如果在图G中删去一条边e后，图G的连通分支增加，则称此边e为图G的割边。•等价说法：图G中的割边e为满足于ω（G-e）ω（G）的边e。•G-e是什么？ω（G）是什么？关于割边的结论•定理：e为图G的割边的充要条件是e不包含在图G的任何一个圈中。•证明？•定理：连通图G是树的充要条件是图G的每一条边均是割边。割点（cutvertex）•定义：如果在图G中去掉一个顶点v和与它关联的所有边后，图G的连通分支增加，则称此顶点v为图G的割点。•等价说法：图G中的割点v为满足于ω（G-v）ω（G）的顶点v。•G-v是什么？ω（G）是什么？关于割点的结论•定理：v为图G的割点的充要条件是G中存在与v不同的两个顶点u和w，使得图G所有的uw路都通过v。•证明？•定理：树G中的每个d(v)1的顶点（非悬挂点）均是割点。余树•余树的定义：设T为G的生成树，则G-E（T）称为G中生成树T的余树，记作•定理：T为G的生成树，e是T的余树中任一边，则T+e包含唯一的圈。•图G的基本圈个数：ℇ-ν+1TT·······uvwx·········uvwx··图G图G的生成树T·······uvwx··T的余树割集•割集的定义：连通图G的一个边集BE（G），如果它是使得G-B不连通的极小边集，则称B为G的割集。•例：图的割集2.2割集定义：连通图G的一个边集BE(G)，如果它是使G-B不连通的极小边集，则称B为G的割集。···v1v2v5v4·e1e7e2e5e4e3e6··v3v6e8e9图Ge10···v1v2v5v4·e2e5e4e6e9G1=G-B1B1={e1,e3,e7,e10}·v3e8·v6下图中，B1是割集定理2.6设B为连通图G的割集，则ω(G-B)=2证：用反证法。设B为连通图G的割集，且ω(G-B)≥3，将B中任一边e添回到G-B中，一条边只能使两分支连接，故G-B+e仍是不连通的，而B-e是B的真子集，这与B为极小边集矛盾，故ω(G-B)=2。*割边为只含一条边的割集。记号：对V的子集V1和V2，用[V1,V2]表示一个端点在V1中另一个端点在V2中的所有边的集。定义：若S⊂V，记，则边集称为G中的割。S/VS]SS[，···v1v2v5v4·e1e2e3··v3v6e9e10假设S={v1,v2,v3}则={v4,v5,v6}S}e,e,e,e,e{]SS[87654，e7e5e4e6e8•在连通图G中移去一个割后，必然使分支数增加。当分支数增加1时此割即为割集。•在G中移去一割集B就使G-B成为两个分支G1和G2。设V(G1)=S则得，故割集是割。•从G移去一个割，一般来说可使G增加的分支数大于1。]S,S[BSS/)G(V)G(V2定义：设连通图G=(V,E),T为G的一个生成树，E(T)={e1,e2,…,eγ-1}对任何ei∈E(T),含有G的唯一割集Bi,i=1,2,…,γ-1,称割集B1,B2,…,Bγ-1为G中关于生成树T的基本割集。ieT生成树(spanningtree)•定义：如果T是图G的一个生成子图而且又是一个树图，则称T为图G的一个生成树。•例：如何求生成树？•例：求下图的所有非同构生成树？生成树有关结论•定理：图G有生成树的充要条件是图G连通。•证明？•推论1：若图G连通，则ℇ≥ν-1•推论2：T是连通图G的生成树的充要条件是T为G的有ν-1条边的连通生成子图。•图G的生成树T是G的极小连通生成子图，也是G的极大无圈生成子图。•极小子图？极大子图？最小生成树•定义：在赋权图G的所有生成树中，各边权数之和最小的生成树，称为最小生成树。例：某市6单位经过A铺设煤气管道问题：距离ABCDEFA01.33.24.33.83.7B1.303.543.13.9C3.23.502.82.61D4.342.802.12.7E3.83.12.62.102.4F3.73.912.72.40求最小生成树的避圈法•避圈法(Kruskal算法)：将图中所有边按权数从小到大排序，每步从未选的非环边中选择一条权数最小的边，但不能构成圈，直到得到n-1条边为止，n为图的顶点数。例：避圈法求最小生成树v6v4v3v2v1v5621554344避圈法求解结果v6v4v3v2v1v514235求最小生成树的破圈法•破圈法：在图中任找一圈，去掉该圈上权数最大的边，直到不再含有圈为止，便得到最小生成树。例：破圈法求最小生成树v6v4v3v2v1v5v7343110728354(1)(2)(3)(4)(5)破圈法求解结果v6v4v3v2v1v5v7331723作业•复习：割边，割点，生成树，割集的基本概念•预习：第三章连通度•作业本：习题2.1，习题2.2，习题2.4，习题2.11，习题2.12，习题2.15，习题2.25:补充要求求出所有最小生成树。谢谢！再见！