第10章习题答案

第10章 图

习题10

1.(1)图G的度数列为2、2、3、3、4，则G的边数是多少？

(2)3、3、2、3和5、2、3、1、4能成为图的度数列吗？为什么？

(3)图G有12条边，度数为3的结点有6个，其余结点的度数均小于3，问图G中至多有几个结点？为什么？

解 (1)设G有m条边，由握手定理得2m＝?v?Vd(v)＝2＋2＋3＋3＋4＝14，所以G的边数7条。

(2)由于这两个序列中有奇数个是奇数，由握手定理的推论知，它们都不能成为图的度数列。 (3) 由握手定理得?v?Vd(v)＝2m＝24，度数为3的结点有6个占去18度，还有6度由其它结点占有，

其余结点的度数可为0、1、2，当均为2时所用结点数最少，所以应由3个结点占有这6度，即图G中至多有9个结点。

2.若有n个人，每个人恰有3个朋友，则n必为偶数。

证明 设v1、v2、?、vn表示任给的n个人，以v1、v2、?、vn为结点，当且仅当两人为朋友时其对

n应的结点之间连一条边，这样得到一个简单图G。由握手定理知?k?1d(vk)＝3n必为偶数，从而n必为偶数。

3.判断下列各非负整数列哪些是可图化的？哪些是可简单图化的？ (1)(1，1，1，2，3)。 (2)(2，2，2，2，2)。 (3)(3，3，3，3)。 (4)(1，2，3，4，5)。 (5)(1，3，3，3)。

解 由于非负整数列d＝(d1，d2，…，dn)是可图化的当且仅当?di≡0(mod 2)，所以(1)、(2)、

i?1n(3)、(5)能构成无向图的度数列。

(1)、(2)、(3)是可简单图化的。其对应的无向简单图如图所示。

(5)是不可简单图化的。若不然，存在无向图G以为1，3，3，3度数列，不妨设G中结点为v1、v2、

v3、v4，且d(v1)＝1，d(v2)＝d(v3)＝d(v4)＝3。而v1只能与v2、v3、v4之一相邻，设v1与v2相邻，于

是d(v3)＝d(v4)＝3不成立，矛盾。

1

第10章 图

4.试证明图10-48中的两个无向图是不同构的。

证明 因为两图中都有4个3度结点，左图中每个3度结点均与2个2度结点邻接，而右图中每个3度结点均只与1个2度结点邻接，所以这两个无向图是不同构的。

5.在图同构意义下，试画出具有三个结点的所有简单有向图。

解 具有三个结点的所有非同构的简单有向图共16个，如图所示，其中(8)?(16)为其生成子图。

(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)(11)(12)(13)(14)(15)(16)6.给定无向完全图G＝，且|V|＝4。在图同构意义下，试求： (1)G的所有子图。 (2)G的所有生成子图。

解 (1)G的所有子图如图所示。 (2)图(8)?(18)是G的所有生成子图。

(7)(8)(9)(10)(11)(12)(1)(2)(3)(4)(5)(6)

7.(1)试给出一个五个结点的自补图。

(13)(14)(15)(16)(17)(18) 2

第10章 图

(2)是否有三个结点或六个结点的自补图。

(3)一个图是自补图，则其对应的完全图的边数必是偶数。 (4)一个自补图的结点数必是4k或4k＋1。

解 (1)五个结点的图G与它的补图G如图所示。对G与G建立双射：v1?v1，v2?v2，v3?v3，v4?v4，

v5?v5。显然这两个图保持相应点边之间的对应的关联关系，故G?G。因此，G是五个结点的自补图。

(3)设图G是自补图，有m条

（1）G（2)G边，G对应的完全图的边数

为s，则G对应的补图G的边数为s－m。因为G?G，故边数相等，即有m＝s－m，s＝2m，因此G对应的完全图的边数s为偶数。

(2)由(3)知，自补图对应的完全图的边数为偶数。n个结点的完全图Kn的边数为n(n－1)，当n＝3

21或n＝6时，Kn的边数为奇数，因此不存在三个结点或六个结点的自补图。

(4)设G为n阶自补图，则需n(n－1)能被2整除，因此n必为4k或4k＋1形式。

218.一个n(n≥2)阶无向简单图G中，n为奇数，已知G中有r个奇数度结点，问G的补图G中有几个奇数度结点？

解 由G的补图G的定义可知，G∪G为Kn，由于n为奇数，所以Kn中各顶点的度数n－1为偶数。对于图G的任意结点v，应有v也是G的顶点，且dG(v)＋dG(v)＝dKdG(v)和d(v)奇偶性相同，因此若

Gn(v)＝n－1，由于n－1为偶数，所以

G中有r个奇数度结点，则G中也有r个奇数度结点。

9.画出4阶无向完全图K4的所有非同构的生成子图，并指出自补图来。 解 下图中的11个图是K4的全部的非同构的生成子图，其中(7)为自补图。 10.

3

设图G中有9

第10章 图

个结点，每个结点的度不是5就是6。试证明G中至少有5个6度结点或至少有6个5度结点。

证明 由握手定理的推论可知，G中5度结点数只能是0、2、4、6、8五种情况（此时6度结点数分别为9、7、5、3、1）。以上五种情况都满足至少5个6度结点或至少6个5度结点的情况。

11.证明3度正则图必有偶数个结点。

n证明 设G为任一3度正则图，有n个结点v1、v2、?、vn，则所有结点度数之和?d(vi)＝3n。若n

i?1为奇数，则3n也为奇数，与握手定理矛盾。故n为偶数。

12.设G为至少有两个结点的简单图，证明：G中至少有两个结点度数相同。

证明 若G中孤立结点的个数大于2，结论显然成立。若G中有1个孤立结点，则G中至少有3个结点，因而不考虑孤立结点，就是说G中每个结点的度数都大于等于1。又因为G为简单图，所以每个结点的度数都小于等于n-1。因而G中结点的度的取值只能是1，2，?，n-1这n个数。由抽屉原理可知，取n-1个值的n个结点的度至少有两个是相同的。

13.给定无向图G＝如图10-49所示，试求： (1)从a到d的所有基本路。 (2)从a到d的所有简单路。

(3)长度分别是最小和最大的基本回路。 (4)长度分别是最小和最大的简单回路。 (5)从a到d的距离。

(6)?(G)、?(G)、?(G)、?(G)分别是多少？

解 (1)从a到d的所有基本路共有10条：abd，abcd，abed，abced，abecd，afed，afecd，afebd，afebcd，afecbd。

(2)从a到d的所有简单路共有14条：除（1）中的10条外还有abcebd，abecbd，afebced，afecbed。 (3)长度最小的基本回路共4个：bceb，bdeb，cdec，bcdb。长度最大的基本回路共1个：abdcefa。 (4)长度最小的简单回路共4个：bceb，bdeb，cdec，bcdb。长度最大的简单回路2个：abcebdefa，afebcedba。 (5)从a到d的距离为2。

(6)?(G)＝2，?(G)＝2，?(G)＝2，?(G)＝4。 14.给定有向图G＝如图10-50所示，试求： (1)各结点的出度、入度和度。 (2)从a到d的所有基本路和简单路。 (3)所有基本回路和简单回路。

解 (1)d(a)＝2，d(a)＝1，d(b)＝1，d(b)＝2，d(c)＝1，d(c)＝1，d(d)＝2，d(d)＝2，d(e)＝1，d(e)＝1。

(2)从a到d的基本路2条：ad，abd。从a到d的简单路5条：ad，abd，adcbd，adead，adeabd。 (3)基本回路共3个abdea，adea，bdcb.简单回路共4个：abdea，adea，bdcb，adcbdea。

4

-+

-+

-+

-+

-+

第10章 图

15.(1)若无向图G中只有两个奇数度结点，则这两个结点一定是连通的。 (2)若有向图G中只有两个奇数度结点，它们一个可达另一个结点或互相可达吗？

证明 (1)设无向图G中只有两个奇数度结点u和v。从u开始构造一条回路，即从u出发经关联结点

u的边e1到达结点u1，若d(u1)为偶数，则必可由u1再经关联u1的边e2到达结点u2，如此继续下去，每条边

只取一次，直到另一个奇数度结点为止，由于图G中只有两个奇数度结点，故该结点或是u或是v。如果是v，那么从u到v的一条路就构造好了。如果仍是u，该回路上每个结点都关联偶数条边，而d(u)是奇数，所以至少还有一条边关联结点u的边不在该回路上。继续从u出发，沿着该边到达另一个结点u?，依次下

1去直到另一个奇数度结点停下。这样经过有限次后必可到达结点v，这就是一条从u到v的路。

(2)若有向图G中只有两个奇数度结点，它们一个可达另一个结点或互相可达不一定成立。下面有向图中，只有两个奇数度结点u和v，u和v之间都不可达。

16.若无向图G是不连通的，证明G的补图G是连通的。

证明 设无向图G是不连通的，其k个连通分支为G1、G2、?、Gk。任取结点u、v∈G，若u和v不在图G的同一个连通分支中，则[u，v]不是图G的边，因而[u，v]是图G的边；若u和v在图G的同一个连通分支中，不妨设其在连通分支Gi（1≤i≤k）中，在不同于Gi的另一连通分支上取一结点w，则[u，

wuwv]和[w，v]都不是图G的边，，因而[u，w]和[w，v]都是G的边。综上可知，不管那种情况，u和v都是可达的。由u和v的任意性可知，G是连通的。

17.完成定理10.11的证明。

证明 充分性：若连通图G中存在结点u和w，使得连接u和w的每条路都经过e，则在子图G－{e}中u和w必不可达，故e是G的割边。

必要性：若e是G的割边，则G－{e}至少有两个连通分支G1＝和G2＝。任取u∈V1，w∈V2，因为G连通，故在G中必有连接u和w的路?，但u、w在G－{e}中不可达，因此?必通过e，即u和w之间的任意路必经过e。

18.完成定理10.16的证明。

证明 先证任一结点至少位于一个单向分图中。

任给一结点v，若v是孤立结点，则含v的平凡图即为单向分图。若v不是孤立结点，则必有一个结点u，使得u与v有一弧e与它们联结。此时若有单向分图G1??V1,E1?，|V1|≥3，使u，v∈V1，且e∈E1，那么结论成立；若不存在这样的G1，则由u，v和e就构成一个单向分图。因此，任何结点至少位于一个单向分图中。

其次证明，任何一条弧至少位于一个单向分图中。

任给一弧e，其关联的结点u和v。若存在一单向分图G1??V1,E1?，|V1|≥3，使u，v∈V1，且e∈E1，那么结论成立。否则，u，v和e就构成一个单向分图。综上可知，任一弧至少位于一个单向分

5

第10章 图

图中。

19.完成定理10.17的证明。

证明 显然任一结点和任一弧都位于一个弱分图中。

假设有一结点v位于两个不同的弱分图G1??V1,E1?和G2??V2,E2?中，即v∈V1∩V2。由于略去弧的方向后，V1中所有结点与v可达，V2中所有结点也与v可达，故V1与V2中所有结点可达，这与G1和G2为弱分图矛盾，故任一结点不可能包含于不同的弱分图中，即任一结点能且只能位于一个弱分图中。

假设一弧e位于两个不同的弱分图中，该弧e所关联的两个结点也位于两个不同的弱分图中，这是不可能的，因此任一弧也只能位于一个弱分图中。

20.给出3个4阶有向简单图D1、D2、D3，使得D1为强连通图；D2为单向连通图但不是强连通图；D3

是弱连通图但不是单向连通图，当然更不是强连通图。

解

图中得（a）为强连

（a） （b） （c）通图；（b）为单向连通

图但不是强连通图；（c）是弱连通图但不是单向连通图，当然更不是强连通图。

21.一个有向图D是单向连通图，当且仅当它有一条经过每一个结点的路。 证明 充分性。

给定有向图D＝，如果D有一条经过每一个结点的路为v1v2e1v2e2?vn?1en?1vn，这时V＝{v1，

，?，vn?1，vn}，E＝{e1，e2，?，en?1}?E，边ei（1≤i≤n－1）以vi为起点，以vi?1为终点。任给

elvl?1两个结点vl、vm∈V，不妨设l＜m，则vl必要性。

对结点数v进行归纳。

?em?1vm就是从结点vl到vm的路，故D是单向连通的。

当v＝1或2时，单向连通图显然有一条经过每一个结点的路。 设v＝k时，有一条经过每一个结点的路v1所经过结点的次序，显然k≤p。

当v＝k＋1时，取一结点u，在图中删去结点u，使D－{u}还是单向连通图。根据归纳假设，D－{u}有一条经过每一个结点的路v1i＋1，则必有tv2v2?vp，其中结点可能有重复，这条路的下标只表示该路

?vp。令i＝max{s|vs到u有路}，j＝min{s|u到vs有路}。假如j＞

满足i＜t＜j。由于图D是单向连通的，vt与u之间必有路。如果该路是从vt到u，则与i＝max{s|vs到u有路}矛盾。如果该路是从u到vt，则与j＝min{s|u到vs有路}矛盾。故而j＞i＋1不可能，只能是j≤i＋1。当j＝i＋1时，有经过每个结点的路v1v2?vi?u?vi?1vi?2?vp。当j≤i时，有

6

第10章 图

经过每个结点的路v1v2?vj?vi?u?vj?vivi?1?vp。

22.设e为图G＝中的一条边，?(G)为G的连通分支数，证明?(G)≤?(G－e)≤?(G)＋1。 证明 设e为图G的第个连通分支Gi的一条边。

若e不是Gi的割边，则Gi－e仍然连通，因而G的连通分支数不变，即

?(G)＝?(G－e) （1）

若e是Gi的割边，则Gi－e有且仅有两个连通分支，因而G－e比G多一个支连通分支，即

?(G)＋1＝?(G－e) （2）

由（1）和（2）可得?(G)≤?(G－e)≤?(G)＋1。

23.设G是n阶无向简单图，有m条边，p个连通分支，证明n－p≤m≤(n－p)(n－p＋1)/2。 证明 （1）首先证明n－p≤m。对边数m做归纳法。m＝0时，G为零图，p＝n，n－p＝0，此时结论显然成立。

设m＜k（k≥1）时结论成立，要证m≥3时结论成立。在G中找一个边割集，不妨设这个边割集中的边为e1，e2，?，el（l≥1），设G1＝G－{e1，e2，?，el}，则G1的连通分支数为p＋1，边数为m1＝m－l（l≥1），由归纳假设得n－（p＋1）≤m－l＝m－1，于是n－p≤m。

（2）再证m≤(n－p)(n－p＋1)/2。为证明此不等式，不妨设G的各连通分支都是完全图，因为在这种情况下边数最多。而在l－1个连通分支都是完全图的情况下，又以p－1个为K1（平面图），一个n－p＋1阶完全图Kn?p?1时边数最多，此时的边数为(n－p)(n－p＋1)/2。为此只需证明下面事实：设Kn和Knji是G的两个连通分支（ni≥nj≥1）。用Kn?1和Knj?1分别代替Kn和Knj，所得图的结点数和连通分支数

ii没变，但边数增加了。证明如下：

(

12ni(ni＋1)＋(nj－1)(nj－2))－(

2112ni(ni－1)＋

12nj(nj－1))＝ni－nj＋1＞0

综上所述就证明了结论。

24.设G＝为非平凡有向图，若对V的任一非空子集S，G中起始结点在S中，终止结点在V－S中的有向边都至少有k条，则称G是k条边连通的。证明：非平凡有向图G是强连通?它是1边连通的。

证明 必要性。设G是强连通的，此时若从S到V－S没有有向边，则S中的任一结点u到V－S中的任一结点v均没有有向路，从而与G是强连通的矛盾。所以从S到V－S至少有一条有向边。故G是1边连通的。

充分性。设G是1边连通的。任意u、v∈V，{u}到V－{u}至少有一条边，设为uu1，而{u，u1}到V－{u，u1}至少有一条边uu2或u1u2。无论那种情况都有从u到u2的有向路。因G中结点有限，所以通过如上递归地求解，一定有u到v的有向路。故G是强连通的。

25.证明在n个结点的连通图G中，至少有n－1条边。

证明 不妨设G是无向连通图（若G为有向图，可略去边的方向讨论对应的无向图）。

设G中结点为v1、v2、?、vn。由连通性，必存在与v1相邻的结点，不妨设它为v2（否则可重新编号），

7

第10章 图

连接v1和v2，得边e1，还是由连通性，在v3、v4、?、vn中必存在与v1或v2相邻的结点，不妨设为v3，将其连接得边e2，续行此法，vn必与v1、v2、?、vn?1中的某个结点相邻，得新边en?1，由此可见G中至少有n－1条边。

26.试给出|V|＝n，|E|＝(n－1)(n－2)的简单无向图G＝是不连通的例子。

21解 下图满足条件但不连通。

27.一个n阶连通图G最少有几个割点？最多有几个割点？

解 一个n阶连通图G为树时割点最少，只有一个；为完全图时割点最多，有n－1个。 28.求完全图Kn中任两点之间长为k的路的数目。

解 设E为元素全为1的n阶矩阵，I为阶单位矩阵，于是Kn的邻接矩阵为A＝E－I。Kn中长度为k的路的数目由决定Ak。

由于A＝(E－I)＝?E(?I)kk

kk?iiCkk＝(?1)kI?E?i?1(?1)k?ini?1Cki＝(?1)kI?1n[(n?1)?(?1)]Ekk

i?0所以，aij(k)1?kkk(?1)?[(n?1)?(?1)]??n??1kk?[(n?1)?(?1)]?n?i?ji?j。

29.有向图D如图10-51所示： (1)求D的邻接矩阵A。

(2)D中v1到v4长度为4的路有多少？ (3)D中v1到自身长度为3的回路有多少？ (4)D中长度为4的路数为多少？其中有几条回路？ (5)D中长度小于等于4的路有多少？其中有多少条回路？ (6)D是哪类连通图？

解 (1) 求D的邻接矩阵为：

?1??0A??0??0?200011010??0??1?0??

且有

?1??0??0??0?200030101??1??0?01???1??03A??0??0?200041013??1??0??04A? ??10???00???200060104??1??0?1??A2

8

第10章 图

(4)(2)由A4中a14?4可知，D中v1到v4长度为4的路有4条，分别为：e1e1e4e6、e4e6e7e6、e1e2e5e6、

e1e3e5e6。

?1可知，D中v1到自身长度为3的回路只有1条，为e1e1e144(3)(3)由A3中a11。

(4)(4)D中长度为4的路总数为??aiji?1j?1?16，其中对角元素之和为3，说明长度为4的回路为3条。

(5)D中长度小于等于4的路总数为A、A2、A3、A4中全体元素之和：7＋10＋13＋16＝46，其中回路数为：1＋3＋1＋3＝8。

?4??0??0??0?8000142228??2??2?2??(6)由B4?A?A?A?A234可知，D是单向连通图。

30.有向图G如图10-52所示，试求： (1)求G的邻接矩阵A。

(2)求出A2、A3和A4，v1到v4长度为1、2、3和4的路有多少？

(3)求出ATA和AAT，说明ATA和AAT中的第(2，2)元素和第(2，3)元素的意义。 (4)求出可达矩阵P。 (5)求出强分图。

解 (1)求G的邻接矩阵为：

?0??0A??0??0?101101001??1??1?0??v4v1v3v2图10-52

(2)由于

?0??0??0??0?121010111??1??1?1???0??03A??0??0?212212102??2??2?1???0??0??0??0?343121223??3??3?2??A2 A4

所以v1到v4长度为1、2、3和4的路的个数分别为1、1、2、3。 (3)由于

?0??0TAA??0??0?030201110??2??2??1T? AA??12???13???121021221??0?? 1?1??再由定理10.19可知，所以ATA的第(2，2)元素为3，表明那些边以v2为终结点且具有不同始结点的

9

第10章 图

数目为3，其第(2，3)元素为0，表明那些边既以v2为终结点又以v3为终结点，并且具有相同始结点的数目为0。AAT中的第(2，2)元素为2，表明那些边以v2为始结点且具有不同终结点的数目为2，其第(2，3)元素为1，表明那些边既以v2为始结点又以v3为始结点，并且具有相同终结点的数目为1。

?0??0??0??0?101101001??1??1?0???0?0+??0??0?121010111??1??1?1???0?0+??0??0?212212102??2??2?1???0?0+??0??0?343121223??0??3??0???30???02???777444431??7??7?4??(4)因为B4?A?A?A?A234，所以

求可达矩阵为

?0??0P??0??0?111??111??。 111?111???0??0??0??0?111111111??0??1??1?∧?11???11???011101110??1??1?1???0?0＝??0??0?011101110??1??1?1??(5)因为P?PT，所以{v1}，{v2，v3，v4}构成G的强分图。

31.画一个无向欧拉图，使它具有： (1)偶数个顶点，偶数条边。 (2)奇数个顶点，奇数条边。 (3)偶数个顶点，奇数条边。 (4)奇数个顶点，偶数条边。

解 (1)n（n为偶数，且n≥2）阶圈都是偶数个顶点，偶数条边的无向欧拉图。 (2)n（n为奇数，且n≥1）阶圈都是奇数个顶点，奇数条边的无向欧拉图。

(3)在(1)中的圈上任选一个顶点，在此顶点处加一个环，所得图为偶数个顶点，奇数条边无向欧拉图。 (4)在(3)中的圈上任选一个顶点，在此顶点处加一个环，所得图为奇数个顶点，偶数条边无向欧拉图。 32.画一个无向图，使它是： (1)既是欧拉图，又是哈密尔顿图。 (2)是欧拉图，但不是哈密尔顿图。 (3)是哈密尔顿图，但不是欧拉图。 (4)既不是欧拉图，也不是哈密尔顿图。

解 (1)n（n≥3）阶圈，它们都是欧拉图，又是哈密尔顿图。

(2)给定k（k≥2）个长度大于等于3的初级回路，即圈C1，C2?，Ck。将C1中某个顶点和C2中的某个顶点重合，但边不重合，C2中某个顶点和C3中的某个顶点重合，但边不重合，续行此法，直到将Ck?1中某个顶点和Ck中的某个顶点重合，但边不重合，设最后得到的连通图为G，则G是欧拉图，但不是哈密尔顿图。

(3)在n（n≥4）阶圈中，找两个不相邻的顶点，在它们之间加一条边，所得图是哈密尔顿图，但不是欧拉图。

10

第10章 图

(4)在(2)中的图中，设存在长度大于等于4的圈，比如C1，在C1中找，两个不相邻的顶点，在它们之间加一条边，然后按照（2）的方法构造图G，则G既不是欧拉图，也不是哈密尔顿图。

33.(1)n为何值时，无向完全图Kn是欧拉图？n为何值时，Kn仅存在欧拉路而不存在欧拉回路？ (2)什么样的完全二部图是欧拉图？ (3)n为何值时，轮图Wn为欧拉图？

解 (1)一般情况下，我们不考虑K1。n（n≥2）为奇数时，无向完全图Kn是欧拉图。Kn各结点的度均为n－1，若使Kn为偶拉图，n－1必为偶数，因而必n为奇数。K2仅存在欧拉路而不存在欧拉回路。

(2)设Kr,s为完全二部图，当r、s均为偶数时，Kr,s为欧拉图。

(3)设Wn（n≥4）为轮图，在Wn中，有n－1个结点的度数为3，因而对于任何取值的n（n≥4），轮图Wn都不是欧拉图。

34.证明：完全图K9中至少存在彼此无公共边的两条哈密尔顿回路和一条哈密尔顿通路。

证明 设C1为K9中一条哈密尔顿回路。令G1为K9删除C1中全部边之后的图，则G1中每个结点的度均为6。由定理10.26可知G1仍是哈密尔顿图，因而存在G1中的哈密尔顿回路C2（显然C2也是K9中的哈密尔顿回路，并且C1与C2无公共边）。再L设G2为G1中删除C2中的全部边后所得图，G2为4正则图。由定理10.26可知G2具有哈密尔顿通路。设L为G2中的一条存在哈密尔顿通路，显然C1、C2、L无公共边。

事实上，可以证明在K9中存在4条边不重的哈密尔顿回路。

可以证明：在K3中存在一条边不重合的哈密尔顿回路，K5中存在两条边不重合的哈密尔顿回路，K7

中存在3条边不重合的哈密尔顿回路，一般情况下，K2k+1(k≥1)中最多可存在条边不重合的哈密尔顿回路。

35.已知a、b、c、d、e、f、g 7个人中，a会讲英语；b会讲英语和汉语；c会讲英语、意大利语和俄语；d会讲汉语和日语；e会讲意大利语和德语；f会讲俄语、日语和法语；g会讲德语和法语。能否将他们的座位安排在圆桌旁，使得每个人都能与他身边的人交谈？

解 用a、b、c、d、e、f、g 7个结点代表7个人，若两人能交谈（会讲同一种语言），就在代表它们的结点之间连无向边，所得无向图如下图（1），此图中存在哈密尔顿回路：，如图（2）粗边所示，于是按图（3）所示的顺序安排座位即可。

36.证明：对于每个竞赛图D，至多改变一条边的方向后就可以变成哈密尔顿图。 证明 由定理10.26可知D中存在哈密尔顿通路，设D为n（n≥3）阶竞赛图，v1哈密尔顿通路，若边在D中，则v1v2v2?vn为中的一条

?vnv1为D中一条哈密尔顿回路，故D为哈密尔顿图。否则

边在D中，将改变方向得到边，于是D就变成了哈密尔顿图。

11

第10章 图

237.给定简单无向图G＝，且|V|＝m，|E|＝n。试证：若n≥Cm?1＋2，则G是哈密尔顿图。

22证明 若n≥Cm?1＋2，则2n≥m－3m＋6 （1）。

若存在两个不相邻结点u、v使得d(u)＋d(v)＜m，则有2n＝?d(w)＜m＋(m－2)(m－3)＋m＝m2

w?V－3m＋6，与（1）矛盾。所以，对于G中任意两个不相邻结点u、v都有d(u)＋d(v)≥m。由定理10.26可知，G是哈密尔顿图。

38.设G是无向连通图，证明：若G中有割点或割边，则G不是哈密尔顿图。

证明 若G中有割点v，则G－{v}中至少有两个连通分支，从而?(G－{v})＞|{v}|，由定理10.25可知，G不是哈密尔顿图。

若G中有割边e，当G只有两个结点时，显然G不是哈密尔顿图。当G的结点数多余2时，从G中删除割边e之后至少有两个连通分支，其中一个连通分支含有割边e的一个端点v且其结点个数大于1，于是

?(G－{v})＞|{v}|，由定理10.25可知，G不是哈密尔顿图。

39.某次会议有20人参加，其中每个人都至少有10个朋友，这20人围一圆桌入席，要想使与每个人相邻的两位都是朋友是否可能？根据什么？

解 可能。依题意，若用结点代表人，两人是朋友时相应结点之间连一条边，则得到一个无向图G＝，该题转化为求哈密尔顿回路问题。

由于对任意u、v∈V，有d(u)＋d(v)≥10＋10＝20，根据定理10.26，G为哈密尔顿图，G中存在哈密尔顿回路，按此回路各点位置入席即为所求。

40.设G是具有k(k＞0)个奇数度结点的无向连通图，证明G中边不重合的简单通路的最小数目是它们包含G的全部边。

证明 由握手定理的推论可知，k是偶数。对k做归纳法。 (1)当k＝2时，由定理10.22可知，G中存在偶拉路，结论得证。 (2)设k≤2r（r≥2）时结论成立，要证k为2r＋2时结论成立。

设v1，v2为G中任意二奇度结点，由G的连通性可知，从v1到v2存在路径P0，删除P0上的全部边，得连通分支G1，G2，?，Gs。这些连通分支共含2r个奇度结点，设Gi中含ri个奇度结点，则2ri≤2r（1

sk2，

≤r≤s），且?2ri＝2r。由归纳假设可知，Gi中存在ri条边不重合的简单通路，它们含Gi中的所有边。于

i?1是G中共含1＋r1＋r2＋?＋rs＝1＋r＝

k2条边不重合的简单通路，它们含G中的全部边。

41.甲、乙、丙、丁四位教师，分配他们教数学、物理，电工和计算机原理四门课。甲能教物理和电工，乙能教数学和计算机原理，丙能教数学、物理和电工，丁只能教电工，对他们的工作怎样分配？

解 设.甲、乙、丙、丁四位教师分别用v1、v2、v3、v4表示，V1＝{v1，v2，v3，v4}，数学、物理，电工和计算机原理四门课分别用u1、

u1u2u3u4u2、u3、u4表示，V2＝{u1，u2，u3，

12 v1v2v3v4第10章 图

u4}。若vi能教uj，令∈E。所作图G＝，则G为二部图，如下图所示。易证满足“相

异性条件”，且|V1|＝|V2|，所以，存在V1到V2的完全匹配。图中粗线所示就是其一种分配方案。

42.某杂志发表了7个征求答案的题目，当从读者寄来的解答中挑选每题的两个解答时，编者发现所有14个选出来的解答恰好是7个读者提出来的，而且每个人正好提出了两个答案。试证明：编辑可以这样发表每道题的一个解答，使得在发表的解答中，这7个读者每个人都恰有一个解答。

解 7个位读者分别用v1、v2、?、v7表示，V1＝{v1，v2，?，v7}，7个题目分别用u1、u2、?、u7表示V2＝{u1，u2，?，u7}。若vi为uj做解答，令∈E。所作图G＝，则G为二部图。由已知条件可知V1中每个结点关联两条边，中每个结点也关联两条边，即G满足t＝2的“t条件”，所以存在V1到V2的完备匹配，又因为|V1|＝|V2|，因而对于任意的V1到V2的完备匹配M，不存在M-非饱和点，故M也是完全匹配。即使得7个题目的7个解答分别由7个读者给出是办得到的。

43.给定二部图G＝，且|V1∪V2|＝m，|E|＝n，证明n≤m/4。 证明 设|V1|＝m1，则|V2|＝m－m1，于是n≤m1(m－m1)＝m1m－m12。因为(m22

m2?m1)2?0，即

4?mm1?m12，所以n≤m/4。

2

44.设G是面数r小于12的简单平面图，G中每个结点的度数至少为3。 (1)证明G中存在至多由4条边围成的面。

(2)给出一个例子说明，若G中的面数为12，且每个结点的度至少为3，则(1)的结论不成立。 证明 1)不妨设G是连通的，否则可以对它的每个连通分支进行讨论（因为每个连通分支均满足条件）。因而由偶拉公式有

n－m＋r＝2， （1）

又由已知条件得r＜12且n≤m， （2）

32将（2）其代入（1）得2＜m－m＋12，m＜30。 （3）

32若所有的面均至少由5条边围成，则

5r≤2m，r≤m， （4）

52将（2）、（4）代入（1）得

2≤m－m＋m，m≥30。 （5）

3522 13

第10章 图

（3）与（5）是矛盾的，因而必存在至多由4条边围成的面。

2)十二面体图有12个面，每个结点均为3度，每个面由5条边围成，并没有4条边围成的面。 45.把平面分成?个区域，每两个区域都相邻，问?最大为几？

解 在每个区域放一个结点，当两区域相邻时就在相应的两个结点之间连一条线，如此构造了一个平面图且是完全图K?，而最大的平面完全图为K4，所以?最大为4。

46.设简单平面图G中结点数n＝7,边数m＝15，证明G是连通的。

证明 反证法。设G为非连通的，具有k≥2个连通分支G1,G2,?,Gk。设Gi的结点数为ni，边数为

mi，i＝1，2，?，k。

若存在nj＝1，则k必为2，因为只有此时G为一个平凡图并上一个K6才能使其边数为15，可是K6不是平凡图，这矛盾于G为平面图这个事实，所以不存在nj＝1。

若存在nj＝2，Gj中至少有一条边（因为G为简单图），另外5个结点构成K5时边数最多，但充其量为10条边，这与G有15条边矛盾。

综上所述，ni必大于等于3，i＝1，2，?，k。由定理10.37可知，mi≤3（ni－2）＝3ni－6，i＝1，2，?，k。求和得

m≤3n－6k （1）

将n＝7,m＝15代入（1）得15≤21－6k，于是k≤1，这与k≥2矛盾。 至此证明了G必为连通图。

47.设G是边数m小于30的简单平面图，试证明G中存在结点v使得d(v)≤4。

解 不妨设G是连通的，否则因为它的每个连通分支的边数都应小于30，因此可对它的每个连通分支进行讨论，所以可设G是连通的。

若G中无回路，则G必为树，结论显然成立。若G中有回路，由于G为简单图，因而G中每个面至少由3个边围成，由定理10.37有m≤3n－6。

n下面用反证法证明结论。若不然，G中所有结点的度数均大于等于5，由握手定理可知2m＝?k?1d(vk)≥

5n，所以n≤m，将其代入m≤3n－6得m≤3×m－6，于是m≥30，与m＜30矛盾，所以一定存在结

5522点v使得d(v)≤4。

48.设G为有k(k≥2)个连通分支的平面图，G的平面图的每个面至少由f(f≥3)条边围成，则m≤

ff?2(n－k－1)。

解 设G的各面的边界长度之和为T。G的每条边在计算T时，均提供2，又因为G的平面图G? 的每个面至少由f条边围成，所以fr≤T＝2m。又因为r＝k＋1＋m－n，将其代入fr≤2m得f(k＋1＋m－n)≤2m，整理得m≤

ff?2(n－k－1)。

14

第10章 图

49.证明：平面图G的对偶图G*是欧拉图?G中每个面的次数均为偶数。

*证明 显然G*是连通图，设v*为G*的任一结点，由于R由偶数边围成，所以d(v*)v位于G的面R中，

为偶数，由v*的任意性可知，G*是欧拉图。

50.在由6个结点，12条边构成的连通平面图G中，每个面由几条边围成？为什么？

解 每个面由3条边围成。因图中结点数和边数分别为n＝6，m＝12。根据欧拉公式n－m＋r＝2得r＝8。

又因为?d(vi)＝2m＝24，而简单连通平面图的每个面至少由3条边围成，所以G中每个面由3条边围成。

51.给定连通简单平面图G＝，且|V|＝6，|E|＝12。证明：对任意f∈F，d(f)＝3。 证明 由偶拉公式得|V|－|E|＋|F|＝2，所以|F|＝2－|V|＋|E|＝8，又由定理10.31得?d(f)＝

f?F2|E|＝24。若存在f∈F，使得d(f)＞3，则3|F|＜2|E|＝24，于是|F|＜8，与|F|＝8矛盾。故对任意f∈F，d(f)＝3。

52.证明：不存在具有5个面，每两个面都共享一条公共边的平面图G。

证明 若存在这样的平面图G，设G的对偶图为G*，则G*也是平面图。由于G有5个面，所以G*具有5个结点。设v*为G*的任一结点，设它位于G的面R中。由于R与其余4个面均有公共边，所以v*与其余面中的结点均相邻，于是d(v*)＝4，而且G*为简单图，所以G*必为K5，可是K5为非平面图，这与G*为平面图矛盾。

53.已知一棵无向树T有三个3度结点，一个2度结点，其余的都是1度结点。 (1)T中有几个1度结点？

(2)试画出两棵满足上述度数要求的非同构的无向树。

解 (1)设T中有x个1度结点，则T中结点数n＝3＋1＋x，T中边数m＝3＋1＋x－1＝3＋x。T中各结点度数之和?d(vi)＝3×3＋2×1＋1×x＝11＋x。由握手定理得11＋x＝2m＝6＋2x，于是x＝5。所以T

i?1n中有5个1度结点。

(2)下图中所示的两棵树均满足要求，但它们是不同构的。

54.一棵无向树T有ni个度数为i的结点，i＝2，3，?，k，问有多少个1度结点？

15

第10章 图

解 (1)利用公式TE(vi)?max{TE(vj)??ij}求得各结点的最早完成时间为：

vj?Pree(vi)TE(v1)＝0

TE(v2)＝max{0＋3}＝3 TE(v3)＝max{3＋0，0＋2}＝3 TE(v4)＝max{0＋4，3＋2}＝5 TE(v5)＝max{3＋4，3＋4}＝7 TE(v6)＝max{3＋4，7＋0}＝7 TE(v7)＝max{5＋5，7＋3}＝10 TE(v8)＝max{7＋3，10＋1}＝11 TE(v9)＝max{7＋6，11＋1}＝13

(2)利用公式TL(vi)?minvj?Succ(vi){TL(vj)??ij}求得各结点的最晚完成时间为：

TL(v9)＝13

TL(v8)＝min{13－1}＝12 TL(v7)＝min{12－1}＝11 TL(v6)＝min{12－3}＝9 TL(v5)＝min{13－6，9－0}＝7 TL(v4)＝min{11－5}＝6

TL(v3)＝min{9－4，6－2，7－4}＝3 TL(v2)＝min{7－4，3－0}＝3 TL(v1)＝min{3－3，3－2，6－4}＝0

(3)利用公式TL(vi)－TE(vi)求得各结点的缓冲时间为：

TS(v1)＝TS(v2)＝TS(v3)＝TS(v5)＝TS(v9)＝0 TS(v4)＝6－5＝1 TS(v6)＝9－7＝2 TS(v7)＝11－10＝1 TS(v8)＝12－11＝1

21

第10章 图

于是，所求关键路径为v1v2v5v9，v1v2v3v5v9。

22

本文来源：https://www.bwwdw.com/article/jui5.html