《离散数学(图论)课后总结.doc》由会员分享，可在线阅读，更多相关《离散数学(图论)课后总结.doc（4页珍藏版）》请在金锄头文库上搜索。
1、第八章 图论例1、下面哪些数的序列,可能是一个图的度数序列?如果可能,请试画出它的图. 哪些可能不是简单图?a) (1,2,3,4,5) b) (2,2,2,2,2) c) (1,2,3,2,4) d) (1,1,1,1,4) e) (1,2, 2,4,5) 解:a)不是, 因为有三个数字是奇数. b) c) d)是. e) 不是简单图,因为它有5个结点, 有一个结点度为5, 必然有环或平行边.例2、已知无向简单图G中,有10条边,4个3度结点,其余结点的度均小于或等于2,问G中至少有多少个结点?为什么?解:已知边数|E|=10, deg(v)=2|E|=20其中有4个3度结点, 余下结点度之
2、和为: 20-34=8因为G是简单图, 其余每个结点度数2, 所以至少还有4个结点.所以G中至少有8个结点.强连通、单侧连通和弱连通 在简单有向图G中,如果任何两个结点间相互可达, 则称G是强连通. 如果任何一对结点间, 至少有一个结点到另一个结点可达, 则称G是单侧连通. 如果将G看成无向图后(即把有向边看成无向边)是连通的,则称G是弱连通.在简单有向图中,具有强连通的最大子图,称为强分图.具有单侧连通的最大子图,称为单侧分图. 具有弱连通的最大子图,称为弱分图.注：我每次都会被各种分图弄糊涂！考试时要注意啊，千万不要错了利用可达性矩阵求强分图，注意初等矩阵变换的知识不要忘了！令图G=, 集
3、合SiV Si=V-Si , 令|V|=n Si=u|从u0到u的最短路已求出 Si=u|从u0到u的最短路未求出Dijkstra算法:(求从u0到各点u的最短路长)第一步. 置初值: d(u0,u0)=0 d(u0,v)= (其中v u0) i=0 S0=u0 S0=V-S0 , 第二步.若 i=n-1 则停. 否则转第三步第三步. 对每个uSi 计算 d(u0,u)=mind(u0,u), d(u0,ui)+c(ui,u) ui Si计算 mind(u0,u)uSi并用ui+1记下达到该最小值的那个结点u 置Si+1 =Siui+1 i=i+1 Si=V-Si , 转第二步.例3、求最短路
4、解：例.求右图中从v1到v6的最短路1.置初值: u0=v1 d(u0,u0)=0 d(u0,v2)=d(u0,v3)=d(u0,v4)=d(u0,v5)=d(u0,v6)=2.3. i=0 S0=v1 S0=v2,v3,v4,v5,v6 d(u0,v2)=mind(u0,v2), d(u0,u0)+c(u0,v2)=min,0+3=3 d(u0,v3)=mind(u0,v3),d(u0,u0)+c(u0,v3)=min,0+= d(u0,v4)=mind(u0,v4), d(u0,u0)+c(u0,v4)=min,0+5=5 d(u0,v5)=mind(u0,v5),d(u0,u0)+c(u
5、0,v5)=min,0+= d(u0,v6)=mind(u0,v6),d(u0,u0)+c(u0,v6)=min,0+= min3,5, ,=3 ui+1 =u1=v2 , 实际已求出d(u0,v2)=3, 路是u0v2i=1 S1=v1, v2 S1=v3,v4,v5,v6 u1=v2 d(u0,u1)=3 d(u0,v3)=mind(u0,v3),d(u0,u1)+c(u1,v3)=min,3+6=9 d(u0,v4)=mind(u0,v4), d(u0,u1)+c(u1,v4)=min5,3+1=4 d(u0,v5)=mind(u0,v5),d(u0,u1)+c(u1,v5)=min,3
6、+= d(u0,v6)=mind(u0,v6),d(u0,u1)+c(u1,v6)=min,3+= min9,4,=4 ui+1 =u2=v4 , 实际已求出d(u0,v4)=4, 路是u0v2v4 i=2 S2=v1, v2 ,v4 S2=v3,v5,v6 u2=v4 d(u0,u2)=4d(u0,v3)=mind(u0,v3), d(u0,u2)+c(u2,v3)=min9 ,4+3=7d(u0,v5)=mind(u0,v5), d(u0,u2)+c(u2,v5)=min,4+1=5d(u0,v6)=mind(u0,v6), d(u0,u2)+c(u2,v6)=min,4+= min7,5
7、,=5 ui+1 =u3=v5 , 实际已求出d(u0,v5)=5, 路是u0v2v4 v5i=3 S3=v1, v2 ,v4 ,v5 S3=v3,v6 u3=v5 d(u0,u3)=5 d(u0,v3)=mind(u0,v3),d(u0,u3)+c(u3,v3)=min7 ,5+3=7 d(u0,v6)=mind(u0,v6),d(u0,u3)+c(u3,v6)=min,5+6=11 min7,11=7 ui+1 =u4=v3 , 实际已求出d(u0,v3)=7, 路是u0v2v4 v3i=4 S3=v1, v2 ,v4 ,v5, v3 S3=v6 u4=v3 d(u0,u4)=7d(u0,
8、v6)=mind(u0,v6),d(u0,u4)+c(u4,v6)=min11,7+3=10 min10=10 ui+1 =u5=v6 , 实际已求出d(u0,v6)=10, 路是u0v2v4 v3 v6i=5 (n-1) 时 算法停止.例4、求关键路径。例如, 求右图的关键路径(1)求各个结点的最早完成时间: 计算时，从前向后逐个结点计算。TE(v1)=0TE(v2)=max0+1=1 (v1 v2的先驱结点)TE(v3)=max0+2 ,1+0=2 (v1v2 v3的先驱结点)TE(v4)=max0+3,2+2=4 (v1v3 v4的先驱结点)TE(v5)=max1+3,4+4=8 (v2
9、v4 v5的先驱结点) TE(v6)=max2+4,8+1=9 (v3v5 v6的先驱结点) TE(v7)=max1+4,2+4=6 (v2v3 v7的先驱结点) TE(v8)=max9+1,6+6=12 (v6v7 v8的先驱结点)(2)求各个结点的最晚完成时间: 计算时，从后向前逐个结点计算。TL(v8)=TE(v8)=12TL(v7)=min12-6=6 (v8)TL(v6)=min 12-1=11 (v8)TL(v5)=min 11-1=10 (v6)TL(v4)=min 10-4=6 (v5) TL(v3)=min 6-2, 11-4, 6-4=2 (v4v6v7) TL(v2)=m
10、in 2-0, 10-3, 6-4=2 (v3v5v7) TL(v1)=min 2-1, 2-2, 6-3=0 (v2v3v4)(3)求各个结点的缓冲时间 TS(vi)=TL(vi)-TE(vi)viv1v2V3V4V5V6V7V8TL(Vi)02261011612TE(Vi)012489612TS(Vi)01022200关键路径为: v1v3v7v8例5、设G是结点数n3的简单图，若边数m(1/2)(n-1)(n-2)+2，证明G中存在汉密尔顿回路。证明：假设G不存在汉密尔顿回路(不是H图)，由H图充分条件判定定理可知，G中必存在结 点u1、u2,使得deg(u1)+deg(u2)n-1，即
11、关联这两个结点的边数最多为n-1。 在图Gu1,u2中：结点数为n2, 边数(1/2)(n-2)(n-3) G中边数 m(1/2)(n-2)(n-3)+(n-1) (1/2)(n-2)(n-3)+n=(1/2)(n2-5n+6)+n =(1/2)(n2-5n+6+2n) =(1/2)(n2-3n+6) =(1/2)(n2-3n+2)+4= (1/2)(n2-3n+2)+2 = (1/2)(n-1)(n-2)+2 与已知矛盾，所以G中存在汉密尔顿回路。例6、平面图的欧拉公式是d=m-n+2 (r=e-v+2)?简单平面图G中至少有一个结点的度小于几？解：由欧拉公式 v-e+r=2，所以r=e-v
12、+2 (d=m-n+2 )成立。简单平面图G中至少存在一个结点的度数小于6。 因为如果图G的结点数v6时，所有结点的度均小于等于5。结论显然成立。 当v7时，若所有结点的度均 6时，则由定理8-1.1得 2e=deg(vi)6v ，所以推出 e3v。而由定理8-7.2(必要条件) 设G是有v 个结点、e条边的连通简单平面图, 若v3, 则 e3v-6.所以不可能所有结点的度均大于等于6。即G中至少存在一个结点的度数小于6。例7、证明在n4的极大平面图中，每个结点的度都大于等于3。证明：因为结点数n3的简单平面图为极大平面图的充 分且必要条件是，每个面的次数均为3。所以G中任何回路的长度均大于或等于3。于是任结点u，与u相邻接的结点都在某个回路C上，且此回路的长度必大于等于3，所以deg(u)3。图论这一章，还有点割集，边割集，点连通度，边连通度，完全关联矩阵等知识点，你可能还不熟，（应该不是考试的重点）注意及时复习啊！想一下，还有一周左右的时间就要考试了。 3
