第九章 图

第九章 图 9.1设},,,,{yxwvuV，画出图),(EVG，其中： （1）)},(),,(),,(),,(),,{(yxyvwvxuvuE （2）)},(),,(),,(),,(),,{(yxywxwwvvuE 再求各个顶点的度数。 解 （1）见图9.1(a)。其中顶点u的度数是2，顶点v的度数是3，顶点x的度数是2，顶点y的度数是2，顶点w的度数是1。

u x y v

w (a)

u y w x v

(b) 图9.1 习题1图 （2）见图9.1(b)。其中顶点u的度数是1，顶点v的度数是2，顶点x的度数是2，顶点y的度数是2，顶点w的度数是3。 9.2 设G是具有4个顶点的完全图。 （1）画出图G。 （2）画出G的所有互不同构的生成子图？ 解 （1）如图9.2(1)所示。

图9.2(1) 习题2图 （2） 如图9.6(2)所示 ﹒ ﹒

﹒ ﹒ ﹒

﹒ ﹒

﹒

图9.2(2) 习题2图 9.3 一个无向简单图，如果同构于它的补图，则称这个图为自互补图。 （1）试画出五个顶点的自互补图。 （2）证明一个自互补图一定只有k4或14k个顶点（k为整数）。 解 （1）

v1 v1

v2 v3 v4 v5 v2 v5

v3 v4

G G

(a) (b) 图9.3 习题3图 （2）因为n个顶点的无向完全图有)1(21nn条边，所以自互补图有)1(41nn条边，因此，kn4或14k。 9.4 画出两个不同构的简单无向图。每一个图都仅有6个顶点，且每个顶点都均是3度，并指出这两个图为什么不同构。 解

图9.4 习题9.4图 9.5 证明任意两个同构的无向图，一定有一个同样的顶点度序列。顶点度序列是一组按大小排列的正整数。每一个数对应某一个顶点的度数。 证明 两个同构的无向图，度数相同的顶点数目一定相同，这样才能够建立起顶点之间的一一对应关系，进而建立起边的对应关系。所以，任意二个同构的无向图，一定有一个同样的顶点度序列。 9.6图9.6中所给的图(a)与图(b)是否同构？为什么？

(a) (b) 图9.6 习题6图 解 左图9.2（a）中次数为4的点，与3个度数为1，一个度数为2的顶点相邻接，右图9.2（b）中度数为4的点，却与3个度数为1，一个度数为3的顶点相邻接。因此两图之间不存在同构映射，从而不同构。 9.7有207个人在一起欢聚。若已知每个人至少和5个人握了手，则至少有一个人不止和5个人握手。 证明

设20721,...,,vvv代表这207个人，建立顶点集},...,,{20721vvvV,对于其中的任意两个人

)(,jivvji，若jivv和握了手，则Evvji},{，得到边集E，则有一个无向图)(EVG，。

若每一个人仅和其余5个人握过手，则5)(ivd，而此时图G的奇数度的顶点是207个，即是奇数个，产生矛盾。因此至少有一个人iv，6)(ivd。 9.8证明一个无向图的奇数度的顶点一定有偶数个。 证明

设)(EVG，是一个无向图。})(|{1是奇数vdVvV，})(|{2是偶数vdVvV，

显然},{21VV是V的一个划分。所以21)()()(VvVvVvvdvdvd，而2()vVdv是一个偶数，

所以1()vVdv=()vVdv－2()vVdv，其中||2)(EvdVv也是一个偶数，偶数减去偶数仍然是偶数，故1()vVdv是偶数。 9.9 设 ，分别是图)(EVG，中顶点的最小度数和最大度数。n|V|，m|E|，证明≤2mn≤。

证明 因为Vviimv2)deg(，对任意的Vvi，有)deg(iv，于是nvnivi)deg(，即nmn2，所以nm2。

9.10证明由多于或等于2个人的人群，至少有二个人在这群人中朋友数相同。 证明

设nvvv,...,,21代表这)2(nn个人，建立顶点集},...,,{21nvvvV，对于其中的任意两

个人)(,jivvji，若jivv和是朋友，则Evvji},{，得到边集E，则有一个无向图)(EVG，。由于每个顶点仅仅能够与另外的1n个顶点邻接，所以每个顶点的度数

1n。因此，在G中顶点可能出现的度数是0，1，2，…, 1n。由于度数是0的顶点是

孤立顶点，而度数为1n的顶点一定邻接其它1n个顶点的，所以在G中度数为0和度数为1n的顶点不可能同时出现。因此，在G中可以出现的顶点的度数应该分成以下两种情况：

(1) 0,1,2,„, 2n (2) 1,2,3,„, 1n 上述两种情况最多有1n种不同的度数。根据鸽巢原理，至少有两个顶点具有相同的度数。故由多于或等于2个人的人群，至少有二个人在这群人中朋友数相同。

9.11 )(EVG，是一个简单无向图，若2)|)(|1|(|21VV|E|，则G是连通图。 证明 反证法。假设G不连通，不妨设G可分成两个不相连通的子图1G和2G，并假设它们中

的顶点个数分别为1n和2n，当然21||nnV，因为1in，所以0)1)(1(21nn，从而有012121nnnn。

)(212)1(2)1(||2122212211nnnnnnnnE ))(2)((212121221nnnnnn ))22)(22||3|(|2121212nnnnVV ))1(22||3|(|2121212nnnnVV )2|)(|1|(|21)2||3|(|212VVVV 这与假设相矛盾，因此G是连通的。 9.12 )(EVG，是一个简单图，试证明若G不连通，则G的补图G一定连通。 证明 若EVG,是不连通的，则G可分为n个连通分支),(11EVG，),(222EVG，),(,nnnEVG。由于任意两个连通分支)(,jiGGji之间不连通，因此两个顶点子集iV与

jV之间的所有连线都在图G的补图G中。任取两个顶点vu,，则存在两种情况：

（a）vu,分别属于两个不同顶点子集iV与jV。由上可知，G包含边),(vu，故u和v在G中是连通的。

（b）vu,属于同一个顶点子集iV。可在另一个顶点子集jV中取一个顶点w，由上可知，边),(wu及边),(wv均在G中，故邻接边),(wu和),(vw组成的路连接顶点u和v，即u和v在G中也是连通的。因此，当图G不连通时，G一定连通。

9.13已知关于人员a，b，c，d，e，f和g的下述事实： (a) 说英语； (b) 说英语和西班牙语； (c) 说英语，意大利语和俄语； (d) 说日语和西班牙语； (e) 说德语和意大利语；

(f) 说法语，日语和俄语； (g) 说法语和德语。 试问：上述七个人中是否任意两人都能交谈（如果必要，可由其余五人所组成的译员链帮忙），为什么？ 解

以a，b，c，d，e，f和g为顶点，如能讲同一语言则作一边，得图9.7，图9.7是连通的，所以这7个人中，任意两个都能交谈。

a b d f

c e g 图9.7 习题13图 9.14（1d，2d，„nd）是一个非负整数的n元数组，若存在一个n个顶点的简单无向图，使

得其顶点的度数分别是1d，2d，„nd，则称这个n元数组是可图的。证明 （1）(4，3，2，2，1)是可图的。 （2）（3，3，3，1）是不可图的。

（3）不失一般性设nddd，21证明：（1d，2d，„nd）是可图的当且仅当

（12d,13d，„，11dd，111dd，21dd，…,nd）是可图的。 证明 （1）其构成图如图9.8所示。

图9.8 习题14(1)图 （2）（3，3，3，1）说明4阶无自回路的图中有3个顶点的度数为3，一个顶点的度数为1，而当有3个顶点的度数为3时，说明这3个顶点与其余各个顶点相邻接，这是，另一个顶点度数也应为3。与题设相矛盾，所以（3，3，3，1）是不可图的。

（3）先证明必要性。若 （1d，2d，„nd）是可图的，则（12d,13d，„，11dd，

111dd，21dd，…,nd）是可图的。

设（1d，2d，„nd）构成图G的顶点为nvvv,...,,21，且iidvd)(，可有以下两种情况： (a)若1v关联的边正好是,,...,,1131211dvvvvvv则去掉这些边所得之图，即为所要求的图。 (b)若1v关联的边中，有},...,,{11312111djvvvvvvvv，即,11dj令

1)}(|min{1)}(|max{110110dGEvviidGEvvjjjj

则有)(01GEvvj，当0jj时，)(1GEvvj；)(01GEvvi，当0ii时，)(1GEvvi。 其线图如图9.9所示。考察与顶点0iv相邻接的0id个顶点，其中必有一个顶点kv与0jv不相邻接，否则就会产生100ijdd的矛盾。