《图论》5-8章-习题课.pptVIP

1.平面图G的对偶G*同构于G时，称G为自对偶图。证明：G=(V,E)为自对偶图时，有m=2n?2。这里n=|V|，m=|E|。;1.平面图G的对偶G*同构于G时，称G为自对偶图。证明：G=(V,E)为自对偶图时，有m=2n?2。这里n=|V|，m=|E|。

提示：欧拉公式：n?m+d=2

对偶性：d=n*

同构性：n*=n

联立解得。;2.证明：Perterson图不是平面图。;2.证明：Perterson图不是平面图。;《图论》4-8章习题课;3.设G是边数m小于30的简单平面图，证明G中存在节点v，deg(v)?4。;3.设G是边数m小于30的简单平面图，证明G中存在节点v，deg(v)?4。

证明：不妨设G是连通的。若G是一棵树，结论显然成立。设G中有回路。反证：若G中所有结点的度均大于等于5，则2m?5n。联立m?3n?6得m?30，矛盾。;4.设简单平面图G中结点数n=7，边数m=15。证明G是连通的。;4.设简单平面图G中结点数n=7，边数m=15。证明G是连通的。

证明：反证。设G不连通，有k个连通分支G1,G2,…,Gk，Gi对应结点数和边数分别为ni和mi。不存在1阶的连通分支，否则G只能由平凡图加上K6才能构成m=15，而K6是不可平面的。也不存在2阶的连通分支K2，否则G最多由K2加上K5也只能构成m=1015。因此任意连通分支的阶必大于等于3。由mi?3ni?6，对全部连通分支求和得m?3n?6k。将n=7,m=15代入得k?1。;5.将平面分成x个区域，且使得任意两个区域都相邻，问x最大是多少？;5.将平面分成x个区域，且使得任意两个区域都相邻，问x最大是多少？

证明：上述分法得到平面图G，设其对偶为G*。可知G*的任意两个顶点都邻接，即G*是一个完全图。又G*是一个平面图，故最多G*为K4。即x的最大值是4。;6.设G是连通的平面图，证明：G为二部图当且仅当G的对偶图为欧拉图。;6.设G是连通的平面图，证明：G为二部图当且仅当G的对偶图为欧拉图。

证明：设G的对偶为G*，则G*是连通的。必要性：G为二部图，则G中无奇数长度回路，故G*中无奇数度顶点，因此G*是一个欧拉图。充分性：G*是一个欧拉图，则G*中无奇数度顶点，故G中无奇数长度回路，因此G为一个二部图。;7.证明：k色图G中至少有k(k?1)/2条边。;7.证明：k色图G中至少有k(k?1)/2条边。

证明：按G的一个k正常着色方案划分G的顶点为k个集合V1,V2,…,Vk。则任给i,j，i?j，在Vi和Vj之间必有边相连，否则给Vi和Vj的顶点染上相同颜色，可以得到G的一个k?1正常着色方案，与G的色数是k矛盾。将Vi用一个结点ui取代，得到一个k阶完全图，其边数恰为k(k?1)/2。;8.色数的图解求法：如图，求其色数?(G)。;《图论》4-8章习题课;9-1.色数多项式的图解求法：加边法。如图，求其色数多项式。;《图论》4-8章习题课;9-2.色数多项式的图解求法：减边法。如图，求其色数多项式。;《图论》4-8章习题课;10.如图是一份PCB板设计图，孔位x1~x9,y1~y3已经确定，联结边（导通）e1~e9。问至少要分成几层板才能实现。;10.解：PCB要求将设计图P中发生交叉的边分配到不同的层面。若将同层的边染以相同颜色，问题转化为求最少颜色数。构造图G如下：以顶点vi标示图P的边ei，G的两个顶点vi,vj邻接当且仅当P中的两条边ei,ej。;10.易得G的色数为3，即至少需要3层板。给出G的一种染色方案，相应可以得到P的一种铺板方案。;10.P的一种3层铺板方案。;11.点独立集与点覆盖的相关关系。

[定理6-3-2]设图G=(V,E)无孤立点，C?V，则：C为G的一个点覆盖?V-C为G的一个独立集。

[推论1]G如上所述，C?V，则：C为G的