内容发布更新时间 : 2024/12/24 8:03:55星期一 下面是文章的全部内容请认真阅读。

蒇习 题 1

螁1. 证明在n阶连通图中 （1）

（2） 薁至少有n-1条边。 （3） （4） （5） （6）

蝿如果边数大于n-1，则至少有一条闭通道。 如恰有n-1条边，则至少有一个奇度点。

袅

袄证明 (1) 若对?v?V(G),有d(v)?2,则：2m=?d(v)?2n ? m?n?n-1,矛盾！ 若G中有1度顶点，对顶点数n作数学归纳。 当n=2时，G显然至少有一条边，结论成立。 设当n=k时，结论成立，

薀

袆

蚇

当n=k+1时，设d(v)=1，则G-v是k阶连通图，因此至少有k-1条边，所以G至少有k条边。

蚀(2) 考虑v1?v2???vn的途径，若该途径是一条路，则长为n-1,但图G的边数大于n-1,因此存在vi,vj,使得viadgvj,这样，vi?vi+1???vj并上vivj构成一条闭通道；若该途径是一条非路，易知，图G有闭通道。

芇(3) 若不然，对?v?V(G),有d(v)?2,则：2m=?d(v)?2n ? m?n?n-1,与已知矛盾！ 2.

3. 肅设G是n阶完全图，试问

（1）

（2） 莂有多少条闭通道？ （3）

（4） 螀包含G中某边e的闭通道有多少？ （5）

（6） 螈任意两点间有多少条路？

薃

螇 答 (1) (n-2)! (2) (n-1)!/2 (3) 1+(n-2)+(n-2)(n-3)+(n-2)(n-3)(n-4)+…+(n-2)…1. 4.

5. 莅证明图1-27中的两图不同构：

芄证明 容易观察出两图中的点与边的邻接关系各不相同，因此，两图不同构。 6.

袀

图

7. 羀

羆膄证明图1-28中的两图是同构的

证明 将图1-28的两图顶点标号为如下的(a)与(b)图 作映射f : f(vi)?ui (1? i ? 10) 容易证明，对?vivj?E((a)),有f(vivj)? uiuj?E((b)) (1? i ? 10, 1?j? 10 )

羂

肀

由图的同构定义知，图1-27的两个图是同构的。 8.

9. 蒄证明：四个顶点的非同构简单图有11个。

蚁证明 蚆 膀 m=0 肇 1 膆 2 螄 3 膀 4 蒈 5 薄6 蒃 艿 衿 芆 节 荿 芀

螄由于四个顶点的简单图至多6条边，因此上表已经穷举了所有情形，由上表知：四个顶点的非同构简单图有11个。

10.

11. 芅设G是具有m条边的n阶简单图。证明：m =????当且仅当G是完全图。

葿证明 必要性 若G为非完全图，则? v?V(G),有d(v)? n-1 ? ? d(v) ? n(n-1) ? 2m?n(n-1)

莇?n??2?? m ? n(n-1)/2=????, 与已知矛盾！?

?n??2?

?n?蒆 充分性 若G为完全图，则 2m=? d(v) =n(n-1) ? m= ??。 ?2???12.

13. 肄证明：（1）m(Kl,n) = ln，

?n2?蕿（2）若G是具有m条边的n阶简单偶图，则m ? ?4?。

??

螈证明 (1) Kl,n的总度数为2ln,所以，m(Kl,n) = ln。

膈(2) 设G的两个顶点子集所含顶点数分别为n1与n2,G的边数为m,可建立如下的二

袃次规划：

虿m=n1n2

腿s.t n1+n2=n

蚅n1?1, n2? 1

薁当n为偶数时，n1=n2=n/2时，m取最大值：m=n2/4

当n为奇数时，取n1=(n+1)/2, n2=(n-1)/2时，m取最大值：m=(n2-1)/4

蝿

?n2?蕿所以，m ? ?4?。

??14.

15. 莇设△和δ是简单图G的最大度和最小度，则δ≤2m / n≤△。 蚄证明 16.

17. 蝿证明：若k正则偶图具有二分类V= V1∪V2，则 | V1| = |V2|。

螆 证明 由于G为k正则偶图，所以，k? V1 ? =m = k? V2 ? ? ?V1?= ?V2 ?。 18.

19. 袅证明：由两人或更多个人组成的人群中，总有两人在该人群中恰好有相同的朋友

数。

证明 将人用图的顶点表示，图的两顶点邻接当且仅当人群中的两人相认识，于是，问题转化为：证明在任意一个简单图中必有一对度数相等的顶点。

衿 若图G为连通单图，则对?v?V(G),有1?d(v)?n-1,因此，n个顶点中必存在两个顶点，其度数相同；若G为非连通图，设G1为阶数n1的连通分支，则?v?V(G1),有1?d(v)?n1-1，于是在G1中必存在两个顶点，其度数相同。

20.

21. 膇证明：序列 (7,6,5,4,3,3,2) 和 (6,6,5,4,3,3,1) 不是图序列。

蒃