离散数学习题解答-（)————————————————————————————————作者：————————————————————————————————日期：ﻩ第七章图7.1 图的基本知识定义８.8设图G＝<V，Ｅ，Ψ >(１）Ｇ－e表示对G作删除边e的运算，Ｇ－e =<Ｖ,E’，Ψ’>，其中E’＝Ｅ-｛ｅ｝,Ψ’= Ψ↑E’。

（2）G-v表示对G作删除顶点v的运算，G－ｖ= <V’,Ｅ’,Ψ’>，其中V’= V-{v}，E’＝E-{e |e以v为端点}，Ψ’＝Ψ↑E’。

（３）边e切割运算。

设Ｇ中Ψ (e) =(u,v)，对G作边ｅ切割得G’＝<Ｖ’，E’，Ψ’>，其中，Ｖ’＝V⋃{v’｝,E’= (E-｛e}）⋃{e１,ｅ2}，Ψ’= （Ψ-{<e,(u,ｖ)>})⋃{<e1, (u,ｖ’）＞,<e2,(v’,v）>}(４)顶点v贯通运算。

设Ｇ中顶点ｖ恰为边e1,ｅ２的端点,且Ψ (e1) ＝(u,v)，Ψ（e2) =（ｗ，v)。

对G作顶点ｖ贯通得G’=<V’，E’，Ψ’>,其中V’=V-｛ｖ},Ｅ’＝(E－｛e1,ｅ2｝)⋃{e}, Ψ’=( Ψ－{<ｅ1,(u,v)>，<e2，(w，v）＞})⋃{＜e, (u,ｗ)>}。

切割与贯通是互逆的,两者常被称为同胚运算。

定义8.９设G1＝<V１，E1,Ψ1>,Ｇ2=<V2，E2，Ψ2>为两个图，称Ｇ1与G２同构(isomorphic),如果存在双射ｆ:Ｖ1→V2,双射g：E1→Ｅ２，使得对每一边ｅ∈Ｅ1, Ψ1(ｅ)＝(u,ｖ）（或<u,ｖ>)当且仅当Ψ2（g(e)) = (f(u），f(v))(或＜f（u)，ｆ(v)>) 当限于讨论简单图时,可以用顶点的偶对表示边,即当Ψ(e)＝(ｕ,v)时，边e用(u,v)来表示。

这时两图同构的条件可以简化为(u,v)∈Ｅ1当且仅当(ｆ（u),ｆ（v))∈E２习题解答练习7．11、想一想,一只昆虫是否可能从立方体的一个顶点出发，沿着棱爬行、它爬行过每条梭一次且仅一次,并且最终回到原地?为什么？解不可能。

可将立方体的一个顶点看作图的一个顶点,把立方体的棱看作图的边,那么该图的四个顶点都是三度的，因此不可能从一个顶点出发,遍历所有的边一次且仅一次，并且最终回到原顶点。

2、请设想一张图，它的64个顶点表示国际象棋棋盘的64个方格,顶点间的边表示:在这两个顶点表示的方格之间可以进行“马步”的行走。

试指出其顶点有哪几类(依其度分类),每类各有多少个顶点。

解其顶点有5类:二度顶点合计4个，三度顶点合计8个,四度顶点,合计20个,六度顶点，合计16个顶点，八度顶点, 合计1６个顶点。

2 3 4 4 4 4 3 23 4 6 6 6 6 4 34 6 8 ８8 8 ６44 6 8 8 8 8 6 4４6 8 8 8 8 6 44 ６8 8 8 8 6 ４3 4 ６6 ６6 ４3 2 3 4 4 4 4 3 23、（ｌ)证明:ｎ个顶点的简单图中不会有多于2)1(-nn条边。

(2）n个顶点的有向完全图中恰有2n条边。

证(l）n个顶点的简单完全图的边数总和为2)1(12)2()1(-=+++-+-n nnn(２）n个顶点的有向完全图的边数总和为2nnnnnnn=⨯=++++４、证明：在任何n （n≥２）个顶点的简单图G中，至少有两个顶点具有相同的度。

证如果Ｇ有两个孤立顶点，那么它们便是具有相同的度的两个顶点。

如果G恰有一个孤立顶点，那么我们可对有n –1 个顶点但没有孤立顶点的G’(它由G 删除孤立顶点后得到)作下列讨论。

不妨设G没有孤立顶点,那么G 的n个顶点的度数应是:1，2，3,…，n–１这n–１种可能之一，因此必定有两个顶点具有相同的度。

５、图8．10是一个迷宫,其中数字表示通道、和死胡同(包括目标) 。

请用一个图来表示这个迷宫(用结点表示通道、和死胡同(包括目标)),用边表示它们之间的可直接到达关系。

图8．10 解6、在晚会上有n 个人,他们各自与自己相识的人握一次手。

已知每人与别人握手的次数都是奇数，问n 是奇数还是偶数。

为什么？解 ｎ是偶数。

用ｎ个顶点表示ｎ个人，顶点间的一条边表示一次握手，可构成一个无向图。

若n 是奇数,那么该图的顶点度数之和为奇数（奇数个奇数的和）,这是不可能的，因此ｎ是偶数。

7、n 个城市间有m 条相互连接的直达公路。

证明：当2)2)(1(-->n n m 时，人们便能通过这些公路在任何两个城市间旅行。

证 用n 个顶点表示n 个城市,顶点间的边表示直达公路，据题意需证这n 个城市的公路网络所构成的图G 是连通的。

反设G 不连通,那么可设G 由两个不相关的子图(没有任何边关联分别在两个子图中的顶点)G1,Ｇ2组成，分别有n 1,n 2个顶点，从而,n = n 1+ｎ2,n 1 ≥1，n ２ ≥1。

由于各子图的边数不超过2)1(-i i n n (见练习８．l 之3)，因此G 的边数m 满足： ))1()1((21)1(2122111-+-=-≤∑=n n n n n n m k i i i))1)(1()1)(1((2121--+--=n n n n )2)(1(21)2)(1(2121--=-+-=n n n n n2 1 1831745 20 21 16与已知2)2)(1(-->n n m 矛盾，故图G 是连通的。

（本题是定理8.8的特例，当然也可以应用这一定理和它的证明方法来解题。

）*8、(1）证明：序列(7，6,5，４,3,３， ２),（6,5,5，4,3，2，２）以及(6,6，５，4，3,3，1）都不是简单图的度序列。

（2）若自然数序列（d １,d ２,…,d n ）满足d 1>d 2>…＞ｄn ，那么当它为一简单图的度序列时必有 （a ）∑=ni id1为偶数;(b)对任一k ，1≤k ≤ｎ ,∑=ki id1≤ k （k-1）＋∑+=nk i id k 1),min(。

证(1)由于7个顶点的简单图中不可能有7度的顶点，因此序列（７，6，5,4，3,3， 2）不是简单图的度序列。

序列(６,5，5,4，３，2，2)中有三个奇数,因此它不是简单图的度序列。

序列(6,6,5，４,3，3，1）中有两个6,若它是简单图的度序列,那么应有两个顶点是6度顶点,于是它们都要与其它所有顶点邻接，该图就不会有一度的顶点,与序列中末尾的1冲突。

故（6，6,5,4,３,3,１)也不是简单图的度序列。

证(２)∑=ni id1为偶数是显然的。

考虑图中的k 个顶点（ｋ=1,２,…,n)，这k 个顶点的生成子图的度数总和 ≤ k （k-１),而其余n –k 个顶点v ｋ+1,ｖk+2, …,v ｎ, 可使 v 1,v 2, …,ｖｋ增加的度数不会超过∑+=nk i id k 1),min(因此我们有∑=ki id1≤ ｋ（k －1)＋∑+=nk i id k 1),min(。

9、画出图８．1１中图的补图及它的一个生成子图。

图８.11解 补图 生成子图1０、一个简单图,如果同构于它的补，则该图称为自补图。

(１）给出一个4个顶点的自补图。

(2)给出一个5个顶点的自补图。

(3）是否有3个顶点或６个顶点的自补图?（４）证明一个自补图一定有4k 或4k ＋1个顶点（k 为正整数)。

解 (1)4个顶点的自补图： （2）５个顶点的自补图：(3)没有。

（4)证 设Ｇ为自补图,有ｎ 个顶点。

我们已知n 个顶点的完全图有 2)1(-n n 条边，因此Ｇ应恰有4)1(-n n 条边。

故或者n 是4的整数倍,或者n –１是４的整数倍，即图G 一定有４k 或4k+1个顶点（k 为正整数）。

1１、(l)证明图 ８.12中(a ）与（b ）同构。

(a ） (b) 图8.1２(2)给出所有不同构的4个结点的简单图的图示。

(l ）证 在图（a)图(ｂ)间建立双射hv A Ｂ D Ｉ J Ｃ E Ｇ H F ｈ(v)α β δ ι η χ φ ϕκγ可逐一验证 （不赘)(u,v)∈E （a)当且仅当 (h(u),h （v))∈E(b)（2)所有不同构的4个结点的简单图的图示有如下１１个：A α βD C B7.2 路径、回路及连通性习题解答练习7．21、证明定理8．５。

证设n个顶点的图G中,有从v到v的闭路径,表示为(ｖ,v1,v2,…,v k,v)如果ｖ,ｖ1,v2,…,ｖk中没有相同顶点(因而不多于n个),那么它便是一条从v到v的长度不大于ｎ的回路。

如果v,v1，ｖ2，…,v k中有相同顶点v i＝v j，例如(v,v1，…，vｉ,…, v j, v j＋1，…,v k,ｖ)那么删除ｖi到ｖｊ的闭路径,得到（v,v1,…, vｉ, ｖj＋1,…,ｖk,ｖ）仍然为从v到v的闭路径。

如此不断删除闭路径内相同顶点构成的闭路径,最终必可得到一条从ｖ到v的长度不大于n的回路。

2、证明:在简单无向图G中，从结点u到结点v,如果既有奇数长度的通路又有偶数长度的通路，那么Ｇ中必有一奇数长度的回路。

证设G中,从结点u到结点v的奇数长度的通路为O ,偶数长度的通路为E。

对O和E的除结点u和v的相交结点的数目归纳ｋ。

k＝０,那么Ｏ和E恰好构成G的奇数长度的回路。

设奇数长度的通路与偶数长度的通路的相交结点的数目少于k时，命题成立。

设图Ｇ中，从结点u到结点v的奇数长度的通路与偶数长度的通路有k个相交结点，如图所示:u 12 …k考虑结点u到结点ｋ,如果从结点u到结点ｋ,既有奇数长度的通路又有偶数长度的通路，那么据归纳假设,其中有一奇数长度的回路,因而G中必有一奇数长度的回路。

如果从结点u到结点k的两条通路均为偶数长度，或均为奇数长度，那么结点ｋ到结点v必然既有奇数长度的通路又有偶数长度的通路，因而构成一奇数长度的回路。

3、证明：若简单无向图G是不连通的,那么G¯必定是连通的。

证设简单无向图G是不连通的,那么G由两个不相关的子图(没有任何边关联分别在两个子图中的顶点)G1,G2组成，分别有顶点，u1，u２，…,ｕｋ和v1，v2,…,v l。

由于边（u i ,v j ）均不在Ｇ中(i=１，2,…,ｋ, j ＝1,2,…，ｌ)因此（u i ,ｖj )全部在G ¯中,从而G ¯是连通的。

4、有向图可用于表示关系，图８.18表示的二元关系是传递的吗?说说如何由有向图判定关系的传递性。

求图8.18表示的二元关系的传递闭包,说说构作有向图传递闭包的方法。

图8.１8解 图8.18表示的二元关系不是传递的。

有向图表示的关系是传递的,当且仅当对图中任意两个结点u,v,如果有从u 到ｖ的路径，则必有从ｕ到v 的边。