文档介绍：****题 1
1. 证明在n阶连通图中
至少有n-1条边。
如果边数大于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,与已知矛盾!
设G是n阶完全图,试问
有多少条闭通道?
包含G中某边e的闭通道有多少?
任意两点间有多少条路?
答(1) (n-2)! (2) (n-1)!/2 (3) 1+(n-2)+(n-2)(n-3)+(n-2)(n-3)(n-4)+…+(n-2)…1.
证明图1-27中的两图不同构:
图1-27
证明容易观察出两图中的点与边的邻接关系各不相同,因此,两图不同构。
证明图1-28中的两图是同构的
图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的两个图是同构的。
证明:四个顶点的非同构简单图有11个。
证明
m=0
1
2
3
4
5
6
由于四个顶点的简单图至多6条边,因此上表已经穷举了所有情形,由上表知:四个顶点的非同构简单图有11个。
设G是具有m条边的n阶简单图。证明:m =当且仅当G是完全图。
证明必要性若G为非完全图,则$ vÎV(G),有d(v)< n-1 Þ å d(v) < n(n-1) Þ 2m<n(n-1)
Þ m < n(n-1)/2=, 与已知矛盾!
充分性若G为完全图,则 2m=å d(v) =n(n-1) Þ m= 。
证明:(1)m(Kl,n) = ln,
(2)若G是具有m条边的n阶简单偶图,则m £ 。
证明(1) Kl,n的总度数为2ln,所以,m(Kl,n) = ln。
(2) 设G的两个顶点子集所含顶点数分别为n1与n2,G的边数为m,可建立如下的二
次规划:
m=n1n2
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
所以,m £ 。
设△和δ是简单图G的最大度和最小度,则δ≤2m / n≤△。
证明
证明:若k正则偶图具有二分类V= V1∪V2,则| V1| = |V2|。
证明由于G为k正则偶图,所以,k| V1 |