第9章 习题解答习题 9.11.设无向图G有16条边，有3个4度结点，4个3度结点，其余结点的度数均小于3，问：G中至少有几个结点？解：当其余结点都为2度时，结点数最少根据定理9.1.1列方程：3×4+4×3+2×x=2×16解方程得：x=4无向图G中的结点数为：4+3+4=11所以，G中至少有11个结点2.设无向图G有9个结点，每个结点的度数不是5就是6，证明：G中至少有5个6度结点或至少有6个5度结点证明：图G中：5度结点数可能为：0，1，2，3，4，5，6，7，8，96度结点数可能为：9，8，7，6，5，4，3，2，1，0反证法，设6度结点小于5个且5度结点小于6个，则只可能有5个5度结点，4个6度结点(其他情况结点数的和小于9)此时，各结点度数之和为：5×5+4×6=25+24=49与结点度数之和为偶数(边数两倍)矛盾所以，G中至少有5个6度结点或至少有6个5度结点3.设图G有n个结点，n＋1条边，证明：G中至少有1个结点度数大于等于3证明：反证法设G=，"v∈V，deg(v)≤2所有结点的度数之和2(n+1)小于2n即2(n+1)≤2n，化简后，2≤0，矛盾所以，G中至少有1个结点度数大于等于3。
4.证明在任何有向完全图中所有结点入度的平方之和等于所有结点的出度平方之和证明：设G有n个结点，ai, bi分别是结点vi的入度和出度，i=1…n因为是完全图，所以ai+bi=n-1，=n(n-1)，方法1： ==0所以，方法2：= = =5.试证明图9.6中(a)和(b)两个图是同构的 证明：设图(a)为G=，图(b)为G′=令g：V®V′，定义为：g(a)=1，g(b)=2，g(c)=3，g(d)=4显然，g：V®V′是双射函数根据双射函数g，E中的边和E′中的边有如下的对应关系：(a,b)↔(1,2)，(a,c)↔(1,3)，(a.d)↔(1,4)，(b,c)↔(2,3)，(c,d)↔(3,4)所以 (a)与(b)同构6.设G1=与G2=是两个无向图，其中：V1= ía,b,c,d,eý，E1=í(a,b),(a,c),(a,c),(b,c),(b,d),(d,e),(c,e),(e,e)ýV2= í1,2,3,4,5ý，E2=í(1,2),(1,3),(1,3),(2,3),(2,4),(4,5),(3,5),(4,4)ýE1和E2中重复出现的无序对是图中的平行边，如E1中的(a,c)和E2中的(1,3)都是平行边。
⑴ 试画出G1和G2的图形⑵ 证明G1和G2不同构解：⑴G1如图9.77所示，G2如图9.78所示⑵反证法设图G1和G2是同构的，根据同度结点对应的原则：c↔3，e↔4 或c↔4，e↔3因为，c上关联了4个边，4上关联了3个边，所以，c↔4，e↔3是不可能的如果c↔3，e↔4，在G1中与e相邻的结点为d和c，deg(d)=2，deg(c)=4在G2中与4相邻的结点为2和5，deg(2)=3，deg(5)=2，无论怎样对应都不能使用同度结点相对应所以，这种情况也是不可能的综上所述，G1和G2不同构7.设G是n阶自补图，试证明n=4k或n=4k＋1，其中k为正整数画出5个结点的自补图是否有3个结点或6个结点的自补图？证明: 设G是n阶自补图，则由自补图的定义，G的边数为n(n-1)×，显然，它应是整数即n(n-1)×=k于是有n(n-1)=4k，因为n和n-1是两个相邻数，所以 n=4k或n-1=4k，即n=4k或n=4k+15个结点的自补图如图9.79所示因为3和6度不能表示成为n=4k或n=4k＋1，所以，没有3个结点或6个结点的自补图8.设G=是图，|V|=n，|E|=m，证明：d(G)≤≤D(G)。
证明：根据最小度的定义，"vÎV，deg(v)≥d(G)，所以，2m=≥=nd(G)即 nd(G) ≤2m，整理后得，d(G)≤另一方面，根据最大度的定义，"vÎV，deg(v)≤D(G)，与前面推理类似的可得，2m≤nD(G)整理后得，D(G)≥所以， d(G)≤≤D(G)9.设G=是无向简单图，|V|=n，n≥3且为奇数，试证明G和中奇度结点个数相等证明: 令=， deg(v)表示G中结点v的度表示中结点v的度 因为n≥3且为奇数，"v∈V，deg(v)+=n-1，所以，n-1是偶数故deg(v)与同偶或同奇G与中的奇度结点个数相等习题 9.21.图G=如图9.12所示，求出从a到f的所有初级路解：从a到f的所有初级路有 abcf，abcef，abef，abecf，adebcf，adecf，adef2.图G=如图9.13所示，求出从d出发的所有初级回路解：从d出发的所有初级回路为：dbad，debad3.在无向图G中，从结点u到结点v有一条长度为偶数的基本路，从结点v到结点u又有一条长度为奇数的基本路，证明在G中必有一条长度为奇数的回路证明：设Cuv是结点u到结点v长度为偶数的基本路。
Cvu是结点v到结点u长度为奇数的基本路则由u沿Cuv到达v，再由v沿Cvu到达u，这是一条通过u和v的回路，它的长度是奇数4.试证明无向图G中恰有两个奇数度的结点，则这两结点间必有一条路证明：反证法设这两个结点间无任何路，它们必属于两个不同的连通分支的(否则，它们之间必有路的)，则这两个连通分支的每一仅有一个奇度结点，与定理9.1.1的推论相矛盾所以，这两结点间必有一条路习题 9.31.有向图G如图9.20所示⑴求a到d的最短路和距离⑵求d到a的最短路和距离⑶判断G是哪类连通图，是强连通的？是单向(侧)连通的？还是弱连通的？⑷将有向图G略去方向得到无向图，对无向图讨论(1)，(2)两个问题解：⑴a到d的最短路为：aed，距离为d=2⑵d到a的最短路为deba 距离为d=3⑶G是单向连通的和弱连通的，但不是强连通的⑷a到d的最短路为aed 距离为d(a,d)=2 d到a的最短路为dea 距离为d(d,a)=22.图9.21是有向图，试求该图的强分图，单向(侧)分图和弱分图解：结点集í1,2,3ý导出子图是该图强分图；结点集í1,2,3,4,5,6ý导出子图是该图的单向分图和弱分图，即该图是它自己的单向分图和弱分图。
3.G为无向连通图，有n个结点，m条边，证明m≥n–1对有向图，这个结论对吗?证明：对m归纳证明当m=0时，由于G是连通图，所以它必为平凡图，n=1，n-1≤m设m=k-1时，结论成立下证m=k时，结论也成立从G中删除一条边得G′, G′可能是连通的，也可能是不连通的⑴当G′是连通图时，G′有n个结点，k-1条边，由归纳假设n–1≤k-1＜k=m，即n–1≤m⑵当G′是不连通图时，G′有n个结点，k-1条边，设有2个连通分支，分别为：G1=和G2= V1|+| V2|=n，| E1|+| E2|= k-1由归纳假设有| Vi|－1≤| Ei|，i=1,2 V1|+| V2|-2≤| E1|+| E2|，n–2≤k-1，n–1≤k=m，即n–1≤m因为强连通图和单向连通图都是弱连通的，所以这个结论也是成立的4.设G=是一个简单图，|V|≤2n，"vÎV，deg(v)≥n，证明G是连通图若|V|≤2n，"vÎV，deg(v)≥n–1，那么，G是连通图吗? 为什么? 证明：(1)先证，"v,uÎV，deg(v)+ deg(u)≥|V|-1时，简单图G=是连通图。
反证法，设简单图G=不是连通图，至少有两个连通分支，设为G1=，G2="vÎV1，因为G1是简单图，deg(v)≤|V1|-1，同理，"uÎV2，deg(u)≤|V2|-1，deg(v)+ deg(u)≤|V1|+|V2|-2=|V|-2＜|V|-1与条件矛盾所以，简单图G=是连通图2)再证，|V|≤2n，"vÎV，deg(v)≥n时，G是连通图"v,uÎV，deg(v)+ deg(u)≥2n≥|V|≥|V|-1，由(1)，G是连通图3)若|V|≤2n，"vÎV，deg(v)≥n–1时，此结论不成立请看反例令n=1，|V|≤2，"vÎV，deg(v)≥0，两个孤立点构成的零图满足此情况，但这样的图是不连通图5.证明：若图G是不连通的，则G的补图是连通的证明:因为 G=不连通,故G至少有两个连通分支,设为G1=和G2=, "v,u∈V，有下列三种情况： ①u∈V1，v∈V2 (或u∈V2，v∈V1) 在G中，因为v，u来自不同的连通分支，所以，它们之间间无边因而，在中，v，u之间必有边②u∈V1，v∈V1。
w∈V2，在中，u和w之间有边且 v和w之间也有边，于是通过w，v与u之间有路③u∈V2，v∈V2可类似②证明之6.设G=是一个简单图，|V|=n，|E|=m， m＞(n—1)(n—2)证明G是连通的证明：反证法假设G=不连通，不妨设G可分成两个连通分支，G1=和G2=则| V1|= n1，| E1|= m1，| V2|=n2，| E2|= m2由于n1≥1和n2≥1，有n2≤n-1和n1≤n-1从而 |E|=| E1|+| E2|≤n1(n1-1)＋n2 (n2-1)≤(n-1)(n1-1)＋(n-1)(n2-1) ＝(n-1)(n1＋n2-2)=(n-1)(n -2)这与假设矛盾所以G是连通图7.证明：图G的一条边e不包含在G的回路中当且仅当e是G的割边证明: 设G的一条边e不包含在G的回路中，以下证明e是G的割边删除e，至少连接e的两个结点不连通所以，图不连通，则e是G的割边设e是G的割边，证明e不包含在G的回路中反证法，如果e包含在G的某个回路中，删除e，图仍连通，与e是G的割边矛盾所以命题成立8.令G是一个至少有三个结点的连通图，下列命题是等价的。
⑴G没有桥⑵G的每二个结点在一条公共的简单回路上⑶G的每一个结点和一条边在一条公共的简单回路上⑷G的每二条边在一条公共的简单回路上⑸对G的每一对结点和每一条边，有一条联结这两个结点而且含有这条边的简单路⑹对G的每一对结点和每一条边，有一条联结这两个结点而不含有这条边的基本路 ⑺对每三个结点，有一条联结任何两个结点而且含第三个结点的简单路证明：(1)Þ(2)令u,v是G中任意两个结点，下面对u,v的距离d(u,v)作归纳证明①当d(u,v)=1，因为G中没有桥，(u,v)不是桥，G又是连。