树17平面图及图着色

《树17平面图及图着色》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、16.树16.1无向树及其性质定义16.1:连通且无回路的无向图称为无向树。用T表示,T中次数为1的点称为树叶,次数大于1的结点称为分支点或内部结点。非连通图的每个连通分支是树的无向图称为森林。116.树16.1无向树及其性质图中v1到v6都是树叶其他结点是内部结点v1v4v3v6v5v2216.树16.1无向树及其性质定理16.1:无向图T是树,当且仅当以下命题之一成立。<1>T是连通且无回路<2>T无回路且m=n-1,其中

2、V

3、=n,

4、E

5、=m<3>T连通且m=n-1<4>T无回路,但增加一边后得到且仅得一个圈<5>T连通,但删去任一边后就不连通<6>每一对结点间有且仅有一条路径

6、。316.树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时成立。416.树16.1无向树及其性质(2)T无回路且m=n-1(3)T连通且m=n-1只要证明连通即可,反证如T不连通,设T的连通分支数为k,k>1,每个连通分支是树,点数为n1,n2,…nk边数则由（2）知为n1-1,n2-1,…nk-1∴

7、m=n1+n2+…+nk-k=n-k

8、(u,v)如果删掉e仍连通u到v另有一条路,则原来就有回路。v1vu616.树16.1无向树及其性质(5)(6)反证如果两结点间有两条通路,则该图必有回路则删去回路上的一边T仍是连通的与(5)矛盾。(6)(1)任两点间均有路,则T是连通的,反证如T是有回路的,则必存在两点,使该两点间有两条路,与（6）矛盾。716.树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

9、,则k≥2。816.树16.1无向树及其性质例：设T=是树,如

10、V

11、=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。916.树16.2生成树定义16.3:设T是无向图G的子图并且为树，则称T为G的树。若无向图G的生成子图是一棵树,则称这棵树为G的生成树或支撑树,设G的一棵生成树为T,则T中的边称为树枝,在G中而不在T中的边称弦,所有弦的集合称为生成树T的余树。e3e2e4e6e5e

12、7e8e9e1e10e1e3e9e8e6e2e9e4e7e5e2e101016.树16.2生成树定理16.3:无向图G具有生成树当且仅当G是连通图。证明:充分性，如果G无回路,则G本身就是它的生成树,如G有回路,则在回路上任取一条边并去掉后仍是连通的,如G仍有回路,则继续在该回路上去掉一条边,直到图中无回路为止,此时该图就是G的一棵生成树。1116.树16.2生成树推论1设G为n阶m条边的无向连通图，则m≥n-1推论2设G是n阶m条边的无向连通图，T为G的生成树，则T的余树中含有m-n+1条边推论3设T是连通图G的一棵生成树，T为T的余树，C为G中任意一个圈，则E(T)∩E(C)不为

13、空。定理16.4设T为无向连通图G中一棵生成树，e为T的任意一条弦，则T∪e中含G中只含一条弦其余边均为树枝的圈，而且不同的弦对应的圈也不同。1216.树16.2生成树一般如果G有n个点m条边连通,则m≥n-1,因为G的生成树有n-1条边，则G要删除m-(n-1)条边。破坏了m-(n-1)个回路，必成G的一棵生成树,这是”破圈法”。也可以从m条边中选取n-1条边并使它不含有回路,这是”避圈法”。定义16.3此m-(n-1)个基本回路称为图G的关于树T的基本