第9章 习题解答.doc

习题 9.1１．设无向图G有16条边,有3个４度结点,４个3度结点，其余结点的度数均小于3，问：Ｇ中至少有几个结点？解：当其余结点都为2度时，结点数最少根据定理9.1.１列方程：3×4+4×３＋２×ｘ=2×１６解方程得：ｘ=4无向图G中的结点数为:4+3+4＝11所以，G中至少有11个结点2.设无向图G有９个结点，每个结点的度数不是5就是6，证明:Ｇ中至少有5个6度结点或至少有6个5度结点证明:图G中：5度结点数可能为：0,1，2，３,４，５，6，7，8，９6度结点数可能为：9,８,7,6，5,4，3，2,1，0反证法，设６度结点小于５个且5度结点小于6个,则只可能有5个5度结点,4个6度结点（其他情况结点数的和小于9）此时，各结点度数之和为:5×5＋4×6＝25+2４=４9与结点度数之和为偶数(边数两倍）矛盾所以，G中至少有5个6度结点或至少有6个５度结点3.设图G有n个结点，ｎ＋1条边，证明：G中至少有1个结点度数大于等于3.证明：反证法.设G=〈V，Ｅ〉,"v∈V，ｄｅｇ(ｖ)≤2所有结点的度数之和2(n＋１)小于２ｎ即2（n＋１)≤2ｎ，化简后，2≤0,矛盾.所以，G中至少有1个结点度数大于等于3.４.证明在任何有向完全图中.所有结点入度的平方之和等于所有结点的出度平方之和。

证明：设G有ｎ个结点，ai， bi分别是结点vｉ的入度和出度，i=1…n因为是完全图，所以ａi+bi=ｎ-1,=n(n—１)，方法1： 　 　　 　=＝0所以，方法2:= 　 = =5．试证明图9６中（a)和(b)两个图是同构的.证明：设图（ａ)为G=.令g:V®Ｖ′,定义为：ｇ(a)=1,ｇ（b)＝2，g（ｃ）=3,g(ｄ）=４显然,ｇ：Ｖ®V′是双射函数根据双射函数ｇ,Ｅ中的边和E′中的边有如下的对应关系：(a,ｂ)↔（１，2)，(ａ,ｃ）↔（1,3），(ａ．d)↔(1，4），（b，c)↔(２,3）,（c,d）↔（３,4）所以　（a）与（b）同构6．设G1=<Ｖ１，E１>与G２=〈Ｖ2，E2〉是两个无向图,其中：Ｖ１＝ ía，b,ｃ，d，eý，E１=í（a,b），(a，c)，（a，c），（ｂ,c）,(b，ｄ),(d,e)，（ｃ，e),（e,e)ýV2= í1，２，3,4,5ý，Ｅ2＝í(1，2),（1，3)，(1,3)，（2，3）,（２,4)，(4，5），(3,5）,(４，4）ýE1和E２中重复出现的无序对是图中的平行边,如Ｅ1中的（ａ，c）和Ｅ２中的(1,3）都是平行边。

⑴ 试画出Ｇ1和Ｇ２的图形⑵ 证明G1和Ｇ2不同构解：⑴Ｇ1如图９7７所示，G２如图9．７8所示⑵反证法设图G1和G2是同构的，根据同度结点对应的原则：ｃ↔３,e↔4 或c↔４,e↔３.因为，c上关联了４个边，4上关联了3个边,所以，ｃ↔４，e↔3是不可能的.如果c↔3，ｅ↔４，在Ｇ1中与ｅ相邻的结点为d和c,deｇ（d）=２,deｇ(c）=４在G2中与4相邻的结点为2和5，deg(２）=３，deｇ（５)=2，无论怎样对应都不能使用同度结点相对应.所以，这种情况也是不可能的综上所述,G１和Ｇ2不同构.7.设G是n阶自补图,试证明n=4k或ｎ=4k+1，其中k为正整数画出５个结点的自补图.是否有3个结点或6个结点的自补图?证明： 设Ｇ是n阶自补图，则由自补图的定义，Ｇ的边数为ｎ（n－1)×,显然,它应是整数.即n（ｎ-1)×=k.于是有n(n-1）=4ｋ,因为ｎ和n-1是两个相邻数，所以　n=４k或n－１＝4k,即n=４ｋ或ｎ＝4k＋15个结点的自补图如图９79所示因为3和６度不能表示成为n=4k或n=４k+1，所以，没有3个结点或6个结点的自补图设G=<Ｖ,E〉是图，|V｜=n,｜E｜=ｍ，证明：d（G)≤≤D（G）.证明：根据最小度的定义，"ｖÎV，deｇ（v）≥d(G）,所以,2m=≥＝nd（Ｇ）即 nd（Ｇ） ≤２m，整理后得,d(G）≤另一方面,根据最大度的定义，"vÎV，deｇ(ｖ)≤D（Ｇ），与前面推理类似的可得，2m≤nD（G）整理后得,D（G）≥所以, d（G)≤≤D(G)9．设G=＜V，Ｅ>是无向简单图,|V｜=ｎ,n≥3且为奇数,试证明G和中奇度结点个数相等.证明:　令＝〈Ｖ，>， deｇ（ｖ)表示G中结点ｖ的度。

表示中结点v的度 因为ｎ≥3且为奇数，"ｖ∈Ｖ,deg（v）+=ｎ—１,所以，n—1是偶数.故deｇ（v)与同偶或同奇Ｇ与中的奇度结点个数相等习题　9.２1.图G=〈V,Ｅ〉如图9．12所示，求出从a到f的所有初级路.解：从a到f的所有初级路有 　ａｂcf,abcef，ａbef，abecf,aｄebcf，adecf,aｄeｆ.２图G=〈V,E>如图913所示,求出从d出发的所有初级回路解：从ｄ出发的所有初级回路为：dｂaｄ，debad在无向图G中,从结点u到结点v有一条长度为偶数的基本路，从结点v到结点u又有一条长度为奇数的基本路，证明在Ｇ中必有一条长度为奇数的回路.证明：设Cｕｖ是结点u到结点v长度为偶数的基本路.Ｃｖu是结点v到结点u长度为奇数的基本路则由u沿Cuv到达ｖ，再由v沿Cvu到达u,这是一条通过u和ｖ的回路，它的长度是奇数.４．试证明无向图G中恰有两个奇数度的结点,则这两结点间必有一条路证明：反证法设这两个结点间无任何路,它们必属于两个不同的连通分支的(否则，它们之间必有路的)，则这两个连通分支的每一仅有一个奇度结点，与定理9１．１的推论相矛盾所以,这两结点间必有一条路.习题 ９．31．有向图Ｇ如图9。

２０所示.⑴求a到d的最短路和距离⑵求d到a的最短路和距离.⑶判断Ｇ是哪类连通图，是强连通的？是单向(侧)连通的？还是弱连通的?⑷将有向图G略去方向得到无向图,对无向图讨论(1)，(２)两个问题.解：⑴ａ到d的最短路为：aed，距离为ｄ〈a,d〉=2⑵ｄ到a的最短路为deba 　距离为ｄ＜ｄ,ａ＞＝３⑶G是单向连通的和弱连通的,但不是强连通的⑷a到d的最短路为aed 距离为d(a,ｄ）=2 　d到a的最短路为ｄea 距离为ｄ(d,ａ)=２图９.2１是有向图，试求该图的强分图,单向（侧）分图和弱分图解：结点集í１，2，3ý导出子图是该图强分图；结点集í1，２，3，4，5,6ý导出子图是该图的单向分图和弱分图,即该图是它自己的单向分图和弱分图G为无向连通图,有n个结点，m条边，证明m≥n–1对有向图,这个结论对吗？证明:对m归纳证明.当m=0时，由于G是连通图，所以它必为平凡图，ｎ=1,ｎ－1≤ｍ设m=k－1时,结论成立下证m＝k时，结论也成立从Ｇ中删除一条边得G′，　G′可能是连通的,也可能是不连通的⑴当G′是连通图时，G′有n个结点，k—1条边,由归纳假设n–1≤ｋ－1＜ｋ=m,即n–1≤m.⑵当G′是不连通图时,G′有n个结点，ｋ-1条边，设有2个连通分支,分别为:G1=和G2＝。

V1｜+|　V2|=n，| E１｜+| E2|= k—１.由归纳假设有｜　Vｉ｜－1≤| Ei|,ｉ=1，2｜　V1｜＋| V2｜-2≤｜　Ｅ1|+｜ E2|,n–2≤k—1，n–1≤ｋ=ｍ,即ｎ–1≤m.因为强连通图和单向连通图都是弱连通的，所以这个结论也是成立的４.设Ｇ=是一个简单图,|Ｖ｜≤2n,"vÎV，deg（v）≥n,证明Ｇ是连通图.若｜Ｖ|≤2n，＂vÎＶ，deg(ｖ）≥n–1,那么，G是连通图吗？ 为什么？ 证明:（1)先证，＂v，uÎV，deg(ｖ）+ deg（ｕ）≥｜V｜—1时，简单图G=是连通图反证法,设简单图G=不是连通图，至少有两个连通分支,设为G１=,G2＝<Ｖ2，Ｅ２>vÎV1，因为G1是简单图,ｄeg（v）≤|V1｜-1,同理，"uÎＶ2，deg(u）≤|V２|—1,dｅg（ｖ）+ ｄeｇ(u）≤｜Ｖ1|+|V2｜—２＝｜V｜—２＜|V｜-1与条件矛盾.所以,简单图G＝是连通图.(2）再证,|V｜≤2ｎ,"vÎＶ，deg（v)≥ｎ时，Ｇ是连通图.＂v,uÎV，ｄｅｇ（v）+ ｄeg(u）≥２n≥｜V|≥|V｜-１,由（1）,G是连通图。

3)若｜V｜≤2n，”vÎＶ,dｅg（v）≥n–1时，此结论不成立.请看反例令n=1，|V|≤2,"vÎV,deｇ（v)≥0，两个孤立点构成的零图满足此情况,但这样的图是不连通图.５．证明：若图Ｇ是不连通的,则G的补图是连通的证明：因为 G=不连通，故G至少有两个连通分支,设为G1=和G2＝，　 　 "v,ｕ∈V，有下列三种情况： ①u∈V1,v∈Ｖ2 （或ｕ∈V２,v∈Ｖ1) 在G中,因为v,u来自不同的连通分支，所以,它们之间间无边因而,在中，v，ｕ之间必有边.②u∈V1，v∈V1.$w∈Ｖ2，在中,ｕ和w之间有边且　v和ｗ之间也有边,于是通过w,ｖ与u之间有路③ｕ∈Ｖ2，ｖ∈V2可类似②证明之.6．设Ｇ=是一个简单图，|Ｖ|＝ｎ，|E|=ｍ， m>(ｎ-1）(n—2）证明G是连通的.证明：反证法假设Ｇ＝不连通,不妨设G可分成两个连通分支，G1＝和G２=<Ｖ2，E2>则｜ V1｜= n１，|　Ｅ1|= m１,| V2|＝n2，| E２|＝ m2由于ｎ1≥1和n2≥１,有n2≤n-1和ｎ1≤n—１从而　 |E|＝｜　Ｅ1｜＋｜ E2｜≤n１(n1－1)＋ｎ2　（ｎ２-１)≤（n－1)(ｎ1-1）+（n—1)(n2－1) 　　　 　＝(n-1)（n1+n2—2）＝(n—1）(n　－2)这与假设矛盾。

所以G是连通图.7．证明：图G的一条边e不包含在G的回路中当且仅当ｅ是G的割边证明: 设G的一条边e不包含在G的回路中，以下证明e是G的割边删除e，至少连接e的两个结点不连通所以，图不连通，则e是Ｇ的割边设e是G的割边,证明e不包含在G的回路中.反证法，如果e包含在G的某个回路中，删除e，图仍连通，与e是G的割边矛盾.所以命题成立.8令Ｇ是一个至少有三个结点的连通图，下列命题是等价的.⑴G没有桥.⑵G的每二个结点在一条公共的简单回路上⑶G的每一个结点和一条边在一条公共的简单回路上⑷G的每二条边在一条公共的简单回路上⑸对G的每一对结点和每一条边，有一条联结这两个结点而且含有这条边的简单路⑹对Ｇ的每一对结点和每一条边,有一条联结这两个结点而不含有这条边的基本路. ⑺对每三个结点，有一条联结任何两个结点而且含第三个结点的简单路证明：（1）Þ(2）令u,v是G中任意两个结点，下面对u,v的距离d（u，v）作归纳证明①当d(u,v)=1，因为G中没有桥，（u,ｖ)不是桥，G又是连通图，所以,必有一条回路包含(ｕ，v),所以ｕ,v在一个公共的简单回路上②假设当d（u，ｖ)=ｋ时（k≥2),命题成立.考察一条长为ｋ的ｕ到ｖ的一条基本路。

设w是这条路上结点v前面的那个结点，d（u,w)=k-1，由归纳假设u，ｗ两个结点必在G的某个简单回路上该回路由Ｐ1,P2组成，如图9.8０(a)所示因为G中无桥,所以G－（v，w）=Ｇ′（从Ｇ中删除边(v,w））必仍是连通图.因此，u与v之间必。