离散数学(图论)课后总结.docVIP

图论 例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度结点, 余下结点度之和为: 20-3×4=8 因为G是简单图, 其余每个结点度数≤2, 所以至少还有4个结点.所以G中至少有8个结点. 强连通、单侧连通和弱连通 在简单有向图G中,如果任何两个结点间相互可达, 则称G是强连通. 如果任何一对结点间, 至少有一个结点到另一个结点可达, 则称G是单侧连通. 如果将G看成无向图后(即把有向边看成无向边)是连通的,则称G是弱连通. 在简单有向图中,具有强连通的最大子图,称为强分图.具有单侧连通的最大子图,称为单侧分图. 具有弱连通的最大子图,称为弱分图. 注：我每次都会被各种分图弄糊涂！！考试时要注意啊，千万不要错了 利用可达性矩阵求强分图，注意初等矩阵变换的知识不要忘了！！ 令图G=V,E,W, 集合SiíV 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 则停. 否则转第三步 第三步. 对每个u’∈Si’ 计算 d(u0,u’)=min{d(u0,u’), d(u0,ui)+c(ui,u’)} ui ∈Si计算 min{d(u0,u’)}u’∈Si’ 并用ui+1记下达到该最小值的那个结点u’ 置Si+1 =Si∪{ui+1} i=i+1 Si’=V-Si , 转第二步. i=1 S1={v1, v2} S1’={v3,v4,v5,v6} u1=v2 d(u0,u1)=3 d(u0,v3)=min{d(u0,v3),d(u0,u1)+c(u1,v3)}=min{∞,3+6}=9 d(u0,v4)=min{d(u0,v4), d(u0,u1)+c(u1,v4)}=min{5,3+1}=4 d(u0,v5)=min{d(u0,v5),d(u0,u1)+c(u1,v5)}=min{∞,3+∞}=∞ d(u0,v6)=min{d(u0,v6),d(u0,u1)+c(u1,v6)}=min{∞,3+∞}=∞ min{9,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)=4 d(u0,v3)=min{d(u0,v3), d(u0,u2)+c(u2,v3)}=min{9 ,4+3}=7 d(u0,v5)=min{d(u0,v5), d(u0,u2)+c(u2,v5)}=min{∞,4+1}=5 d(u0,v6)=min{d(u0,v6), d(u0,u2)+c(u2,v6)}=min{∞,4+∞}=∞ min{7,5,∞}=5 ui+1 =u3=v5 , 实际已求出d(u0,v5)=5, 路是u0v2v4 v5 i=3 S3={v1, v2 ,v4 ,v5} S3’={v3,v6} u3=v5 d(u0,u3)=5 d(u0,v3)=min{d(u0,v3),d(u0,u3)+c(u3,v3)}=min{7 ,5+3}=7 d(u0,v6)=min{d(u0,v6),d(u0,u3)+c(u3,v6)}=min{∞,5+6}=11 min{7,11}=7 ui+1 =u4=v3 ,