下载文档原格式
第九章 图9.1设},,,,{y x w v u V =，画出图),(E V G =，其中：（1）)},(),,(),,(),,(),,{(y x y v w v x u v u E =（2）)},(),,(),,(),,(),,{(y x y w x w w v v u E =再求各个顶点的度数。
解（1）见图9.1(a )。
其中顶点u 的度数是2，顶点v 的度数是3，顶点x 的度数是2，顶点y 的度数是2，顶点w 的度数是1。
图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）证明一个自互补图一定只有k 4或14+k 个顶点（k 为整数）。
解（1）(a) (b)图9.3 习题3图 （2）因为n 个顶点的无向完全图有)1(21-n n 条边，所以自互补图有)1(41-n n 条边，因此，k n 4=或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.1设},,,,{y x w v u V =，画出图),(E V G =，其中：（1）)},(),,(),,(),,(),,{(y x y v w v x u v u E =（2）)},(),,(),,(),,(),,{(y x y w x w w v v u E =再求各个顶点的度数。
解（1）见图9.1(a )。
其中顶点u 的度数是2，顶点v 的度数是3，顶点x 的度数是2，顶点y 的度数是2，顶点w 的度数是1。
图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）证明一个自互补图一定只有k 4或14+k 个顶点（k 为整数）。
解（1）(a) (b)图9.3 习题3图 （2）因为n 个顶点的无向完全图有)1(21-n n 条边，所以自互补图有)1(41-n n 条边，因此，k n 4=或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,...,,v v v 代表这207个人，建立顶点集},...,,{20721v v v V =,对于其中的任意两个人)(,j i v v j i ≠，若j i v v 和握了手，则E v v j i ∈},{，得到边集E ，则有一个无向图)(E V G ，=。
若每一个人仅和其余5个人握过手，则5)(=i v d ，而此时图G 的奇数度的顶点是207个，即是奇数个，产生矛盾。
因此至少有一个人i v ，6)(≥i v d 。
9.8证明一个无向图的奇数度的顶点一定有偶数个。
证明设)(E V G ，=是一个无向图。
})(|{1是奇数v d V v V ∈=，})(|{2是偶数v d V v V ∈=，显然},{21V V 是V 的一个划分。
所以∑∑∑∈∈∈+=21)()()(V v V v V v v d v d v d ，而2()v V d v ∈∑是一个偶数，所以1()v V d v ∈∑=()v V d v ∈∑－2()v V d v ∈∑，其中||2)(E v d Vv =∑∈也是一个偶数，偶数减去偶数仍然是偶数，故1()v V d v ∈∑是偶数。
9.9 设 δ，∆分别是图)(E V G ，=中顶点的最小度数和最大度数。
n |V |=，m |E |=，证明δ≤2m n≤∆。
证明因为∑∈=V v i i m v 2)d e g (，对任意的V v i ∈，有∆≤≤)d e g (i v δ，于是∆⋅≤≤⋅∑n v n i v i )deg(δ，即∆⋅≤≤⋅n m n 2δ，所以∆≤≤nm 2δ。
9.10证明由多于或等于2个人的人群，至少有二个人在这群人中朋友数相同。
证明设n v v v ,...,,21代表这)2(≥n n 个人，建立顶点集},...,,{21n v v v V =，对于其中的任意两个人)(,j i v v j i ≠，若j i v v 和是朋友，则E v v j i ∈},{，得到边集E ，则有一个无向图)(E V G ，=。
由于每个顶点仅仅能够与另外的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 )(E V G ，=是一个简单无向图，若2)|)(|1|(|21-->V V |E |，则G 是连通图。
证明反证法。
假设G 不连通，不妨设G 可分成两个不相连通的子图1G 和2G ，并假设它们中的顶点个数分别为1n 和2n ，当然21||n n V +=，因为1≥i n ，所以0)1)(1(21≥--n n ，从而有012121≤--+n n n n 。
)(212)1(2)1(||2122212211n n n n n n n n E --+=-+-≤ ))(2)((212121221n n n n n n +--+= ))22)(22||3|(|2121212--+++-=n n n n V V ))1(22||3|(|2121212--+++-=n n n n V V )2|)(|1|(|21)2||3|(|212--=+-≤V V V V 这与假设相矛盾，因此G 是连通的。
9.12 )(E V G ，=是一个简单图，试证明若G 不连通，则G 的补图G 一定连通。
证明若>=<E V G ,是不连通的，则G 可分为n 个连通分支),(11E V G =，),(222E V G =，),(,n n n E V G = 。
由于任意两个连通分支)(,j i G G j i ≠之间不连通，因此两个顶点子集i V 与j V 之间的所有连线都在图G 的补图G 中。
任取两个顶点v u ,，则存在两种情况：（a ）v u ,分别属于两个不同顶点子集i V 与j V 。
由上可知，G 包含边),(v u ，故u 和v 在G 中是连通的。
（b ）v u ,属于同一个顶点子集i V 。
可在另一个顶点子集j V 中取一个顶点w ，由上可知，边),(w u 及边),(w v 均在G 中，故邻接边),(w u 和),(v w 组成的路连接顶点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个人中，任意两个都能交谈。
图9.7 习题13图9.14（1d ，2d ，…n d ）是一个非负整数的n 元数组，若存在一个n 个顶点的简单无向图，使得其顶点的度数分别是1d ，2d ，…n d ，则称这个n 元数组是可图的。
证明（1）(4，3，2，2，1)是可图的。
（2）（3，3，3，1）是不可图的。
（3）不失一般性设n d d d ， ≥≥21证明：（1d ，2d ，…n d ）是可图的当且仅当（12-d ,13-d ，…，11-d d ，111-+d d ，21+d d ，…,n d ）是可图的。
证明（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 ，…n d ）是可图的，则（12-d ,13-d ，…，11-d d ，111-+d d ，21+d d ，…,n d ）是可图的。
设（1d ，2d ，…n d ）构成图G 的顶点为n v v v ,...,,21，且i i d v d =)(，可有以下两种情况：(a )若1v 关联的边正好是,,...,,1131211+d v v v v v v 则去掉这些边所得之图，即为所要求的图。
(b )若1v 关联的边中，有},...,,{11312111+∉d j v v v v v v v v ，即,11+>d j 令1)}(|min{1)}(|max{110110+≤∉=+>∈=d G E v v i i d G E v v j j j j则有)(01G E v v j ∈，当0j j >时，)(1G E v v j ∉；)(01G E v v i ∉，当0i i <时，)(1G E v v i ∈。
其线图如图9.9所示。
考察与顶点0i v 相邻接的0i d 个顶点，其中必有一个顶点k v 与0j v 不相邻接，否则就会产生100+≥i j d d 的矛盾。
图9.9 习题14(3)图 图9.10 习题14(3)图作图},{},{'001001j k i k i j v v v v v v v v G G +-=,即得图9.10。
于是'G 仍是无向无自回路的线图，且有与G 相同的度序列，只是'G 的0j 减少了，0i 增大了。
这个过程重复地做下去，总可得到与（a ）相同的情况。
因此，必要性得证。
再证充分性。
若（12-d ,13-d ，…，11-d d ，111-+d d ，21+d d ，…,n d ）是可图的，则（1d ，2d ，…n d ）也是可构成图的。
设前者所构成的图为G ，顶点为n v v v ,,,32 ，且顶点的次数为n i d d v d d i d v d i i i i ≤<+=+≤≤-=1,)(;12,1)(11时，G 中增加一个新顶点1v ，使1v 与121,...,+d v v 相邻接，所得新图的顶点度序列为（1d ，2d ，…n d ）。
