当前位置:文档之家› 离散数学图论

离散数学图论

握手定理应用
无向图G有16条边,3个4度顶点,4个3度顶点,其余顶 点度数均小于3,问G的阶数n为几? 解 设除3度与4度顶点外,还有x个顶点v1, v2, …, vx, 则 d(vi) 2,i =1, 2, …, x, 应用握手定理,得不等式 32=2m= Σd(vi)3*4+4*3+2x 得 x 4, 阶数 n 4+3+4=11.
14
1
实例
有向图D如图所示,求D的邻接矩阵 A与 A2, A3, A4. 问D 中长度 为1, 2, 3, 4的通路各有多少条?其中回路分别有多少条?
2
实例求解
1 2 A 1 1 1 4 3 3 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 0 1 0 0 0 1 0 A
8
例题
已知无向树T中有1个3度顶点,2个2度顶点,其余顶点全是树 叶,试求树叶数. 解 设有x片树叶,于是 n = 1+2+x = 3+x, 先依树的性质m=n1, 再根据握手定理: 2m = 2(n1) = 2(2+x) = 13+22+x, 解出x = 3,故T有3片树叶.
9
例题
已知无向树T有5片树叶,2度与3度顶点各1个,其余顶 点的度数均为4,求T的阶数n. 解 设T的阶数为n, 则边数为n1,4度顶点的个数为n7. 由握手定理得 2m = 2(n1) = 51+21+31+4(n7) 解出n = 8,4度顶点为1个.
2
1 3 2 2
0 0 0 0 0 0 0 0
0 0 1 0 0 0 1
A
3
1 5 4 A 4 4
答: D中长度小于等于4的通路为50条,其中有8条是回路.
5
练习
用至少两种方法证明下图不是哈密顿图. 方法一. 取 V1 = {a, c, e, h, j, l},则 p(GV1) = 7 > |V1| = 6 故已知图下图不是哈密顿图. 方法二. G为二部图,互补顶点子集 V1 = {a, c, e, h, j, l}, V2 = {b, d, f, g, i, k, m}, |V1| = 6 7 = |V2|. 故已知图下图不是哈密顿图. 方法三. 此图中,n = 13,m = 21. 由于h, l, j 均为4度顶点,a, c, e为3度顶点, 且它们关联边互不相同. 而在哈密顿回路上,每个顶点准确地关联两条边, 于是可能用的边至多有21(32+31) = 12<n. 故已知图下图不是哈密顿图.
12
欧拉公式
证明欧拉公式:nm+r=2,其中 n为连通平面图G的阶数, m为G中边的条数,r为G中面的个数。 证:对边数m做归纳法。 m=0时,G为平凡图,结论显然为真. 假设m=k(k0)时结论为真,证明m=k+1时结论亦真. (1) 若G中无圈,则G为树,删除一片树叶, 则阶数与边数皆减1,依归纳假设, (n1)(m1)+r=2, 从而欧拉公式成立. (2)否则,在某一个圈上删除一条边, 此时边数与面数皆减1, 依归纳假设,n(m1)+(r1)=2, 从而欧拉公式亦成立. 13 综合(1)(2),m=k+1时结论恒真. 依归纳原理,欧拉公式得证.
练习
设G是连通的简单的平面图,面数r<12,(G)3. 证明G中存在次数4的面. r=12时,上述结论成立吗(无需证明)? 解:假设G中不存在次数4的面, 设G的阶数、边数、面数分别为n, m, r, 则由欧拉公式得 2m 5r = 5 (2+mn) ① 由于(G)3有 2m 3n ② 由①与②得 2m10+5m5n,10+3m≤5n≤10m/3, 于是 m30 ③ 又依欧拉公式及已知得 r=2+mn <12 ④ 由④及②得 m<30 ⑤ ③与⑤矛盾,故G中必存在次数4的面. r=12时,正十二面体就是上述结论的一个反例.
3
实例
有向图D如图所示,求D的邻接矩阵 A与 A2, A3, A4. 问D 中长度 小于等于4的通路为多少条?其中有多少条回路?
4
实例求解
1 2 A 1 1 1 4 3 3 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 0 1 0 0 0 1 0 A
2
1 3 2 2
0 0 0 0 0 0 0 0
0 0 1 0 0 0 1 0
0 1 0 1 0 1 0 1
A
3
1 5 4 A 4 4
答:D中长度为1的通路为8条,其中有1条是回路. D中长度为2的通路为11条,其中有3条是回路. D中长度为3和4的通路分别为14和17条,回路分别为1与3条.
7
证明思路
设G=<V,E>是n阶m条边的无向图,G 中任意两个顶点之间存在 惟一的路径,证明 G 中无回路且 m=n1. 证明:假设G中有回路,则回路上任意两点之间的路径不惟一 , 故G 中无回路. 对n用归纳法证明m=n1. n=1正确. 设nk时正确,证n=k+1时也正确. 取G中边e,Ge有且仅有两个连通分支G1,G2 , nik, 由归纳假设得mi=ni1, i=1,2. 于是,m=m1+m2+1=n1+n22+1=n1.
10
练习
设n阶非平凡的无向树T中,(T) k 1. 证明T至少有k片树叶. 证 用反证法. 假设T有s片树叶,s < k, 下面利用握手定理及树的性质m = n1推出矛盾. 由于(T) k,故存在v0,d(v0) k. 于是,
2 m 2 n 2 d ( v ) 2 ( n s 1) k s
i 1 i n
2n 2 2n 2s 2 k s
由此解出s k,这与s < k矛盾.
11
练习
设T 是正则2叉树,T 有t 片树叶,证明T的阶数 n=2t1. 证法一. 利用正则2叉树的定义及树的性质有: (1) n = t+i (i为分支点数) (2) n = m+1 (m为T的边数) (3) m = 2i (正则2叉树定义) 由(2)、(3)得 i =(n1)/2 ,代入(1)得n = 2t1. 证法二. T的树根为2度顶点,所有内点为3度顶点,树叶为1度顶点, 利用握手定理及树的性质有: (1) 2m = 2+3(i1)+t (i为分支点数) (2) n = m+1 = i+t 由(1) 和(2) 可解出n = 2t1.
6
练习
某次国际会议8人参加,已知每人至少与其余7人中的4人 有共同语言,问服务员能否将他们安排在同一张圆桌就座, 使得每个人都与两边的人交谈? 解 做无向图G=<V,E>, 其中V={v| v为与会者}, E={(u,v) | u,vV且u与v有共同语言,且u v}. 易知G为简单图且vV, d(v)4, 于是,u,vV, 有d(u)+d(v) 8, 由定理15.7 的推论可知G为哈密顿图. 服务员在G中找一条哈密顿回路C, 按C中相邻关系安排座位即可.
相关主题