树平面图及图着色.ppt

16.树 16.1无向树及其性质 定义16.1:连通且无回路的无向图称为无向树。用T表示,T中次数为1的点称为树叶,次数大于1的结点称为分支点或内部结点。非连通图的每个连通分支是树的无向图称为森林。 16.树 16.1无向树及其性质 图中v1到v6都是树叶 其他结点是内部结点 16.树 16.1无向树及其性质 定理16. 1: 无向图T是树,当且仅当以下命题之一成立。 1??T是连通且无回路 2??T无回路且m=n-1,其中|V|=n,|E|=m 3??T连通且m=n-1 4? T无回路,但增加一边后得到且仅得一个圈 5? T连通,但删去任一边后就不连通 6? 每一对结点间有且仅有一条路径。 16.树 16.1无向树及其性质 证明: (1) T是连通且无回路?（2）T无回路且m=n-1 当n=2时,连通无回路则m=1,满足m=n-1 设n=k时结论成立。 当n=k+1时,因T连通无回路,所以至少有一点的度数为1,在T中删去该点及相关联的边得到k个结点的连通且无回路的图,由归纳假设知它有k-1条边,故n=k+1时有k条边,故结论在n=k+1时成立。 16.树 16.1无向树及其性质 (2) T无回路且m=n-1 ?(3) ?T连通且m=n-1 只要证明连通即可, 反证如T不连通,设T的连通分支数为k,k1,每个连通分支是树,点数为n1,n2,…nk 边数则由（2）知为n1-1,n2-1,… nk-1 ∴m=n1+n2+…+nk-k=n-kn-1矛盾,故T是连通的。 (3)?(4)T无回路,但增加一边后得到且仅得一个圈 由归纳法可以证明T是无回路的（略） 任取两点u,v∈V因T连通故uv间有一条路P。将uv两点间加一条边则必构成回路,如uv 16.树 16.1无向树及其性质 若两点间一条边构成两个回路u…v1…v和u…v2…v则原来的图就有回路u…v1…v…v2…u。 (4) T无回路,但增加一边后得到且仅得一个圈? (5) T连通,但删去任一边后就不连通 任取两结点u,v∈V,加上边(u,v)就构成回路uv…v1…u则原来u到v之间就有一条通路u…v1…v T中任取一条边e∈E,e=(u,v) 如果删掉e仍连通u到v另有 一条路,则原来就有回路。 16.树 16.1无向树及其性质 (5)?(6)反证如果两结点间有两条通路,则该图必有回路则删去回路上的一边T仍是连通的与(5)矛盾。 (6)?(1)任两点间均有路,则T是连通的, 反证如T是有回路的,则必存在两点,使该两点间有两条路,与（6）矛盾。 16.树 16.1无向树及其性质 定理16.2: 设T是n阶非平凡的无向树,则T至少存在两个叶(n≥2时)。 证明：因T连通则?v∈T，deg(v)≥1设T有k个一度点,其它点度数均大于等于2，则2m=∑deg(vi)≥k+2(n-k)=2n-k 因m=n-1,∴2（n-1）≥2n-k,则k≥2。 16.树 16.1无向树及其性质 例：设T=V,E是树,如|V|=20,树叶共有8个,其它点的度数均≤3,问：2度点和3度点各有多少？ 解: 设2度点为x个,则3度点为20-8-X。 因2m=∑deg(vi)而m=n-1 ∴2×(20-1)=1×8+2x+3(20-8-x) 解为x=6,则3度点共有20-8-6=6。 16.树 16.2生成树 定义16. 3:设T是无向图G的子图并且为树，则称T为G的树。若无向图G的生成子图是一棵树,则称这棵树为G的生成树或支撑树,设G的一棵生成树为T,则T中的边称为树枝,在G中而不在T中的边称弦,所有弦的集合称为生成树T的余树。 16.树