资源描述：
《离散数学(图论)课后总结》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
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中至少有多少个结点?为什么?解:已知边数
2、E
3、=10,∑deg(v)=2
4、E
5、=20其中有
6、4个3度结点,余下结点度之和为:20-3×4=8因为G是简单图,其余每个结点度数≤2,所以至少还有4个结点.所以G中至少有8个结点.强连通、单侧连通和弱连通在简单有向图G中,如果任何两个结点间相互可达,则称G是强连通.如果任何一对结点间,至少有一个结点到另一个结点可达,则称G是单侧连通.如果将G看成无向图后(即把有向边看成无向边)是连通的,则称G是弱连通.在简单有向图中,具有强连通的最大子图,称为强分图.具有单侧连通的最大子图,称为单侧分图.具有弱连通的最大子图,称为弱分图.注：我每次都会被各种分图弄糊涂！！考试时要注意啊，
7、千万不要错了利用可达性矩阵求强分图，注意初等矩阵变换的知识不要忘了！！令图G=,集合SiÍVSi’=V-Si,令
8、V
9、=nSi={u
10、从u0到u的最短路已求出}Si’={u’
11、从u0到u’的最短路未求出}Dijkstra算法:(求从u0到各点u的最短路长)第一步.置初值:d(u0,u0)=0d(u0,v)=∞(其中v≠u0)i=0S0={u0}S0’=V-S0,第二步.若i=n-1则停.否则转第三步第三步.对每个u’∈Si’计算d(u0,u’)=min{d(u0,u’),d(u0,ui)+c(ui,u’)}ui
12、∈Si计算min{d(u0,u’)}u’∈Si’并用ui+1记下达到该最小值的那个结点u’置Si+1=Si∪{ui+1}i=i+1Si’=V-Si,转第二步.例3、求最短路解：例.求右图中从v1到v6的最短路1.置初值:u0=v1d(u0,u0)=0d(u0,v2)=d(u0,v3)=d(u0,v4)=d(u0,v5)=d(u0,v6)=∞2.3.i=0S0={v1}S0’={v2,v3,v4,v5,v6}d(u0,v2)=min{d(u0,v2),d(u0,u0)+c(u0,v2)}=min{∞,0+3}=3d(u0,v3
13、)=min{d(u0,v3),d(u0,u0)+c(u0,v3)}=min{∞,0+∞}=∞4d(u0,v4)=min{d(u0,v4),d(u0,u0)+c(u0,v4)}=min{∞,0+5}=5d(u0,v5)=min{d(u0,v5),d(u0,u0)+c(u0,v5)}=min{∞,0+∞}=∞d(u0,v6)=min{d(u0,v6),d(u0,u0)+c(u0,v6)}=min{∞,0+∞}=∞min{3,∞,5,∞,∞}=3ui+1=u1=v2,实际已求出d(u0,v2)=3,路是u0v2i=1S1={v1,
14、v2}S1’={v3,v4,v5,v6}u1=v2d(u0,u1)=3d(u0,v3)=min{d(u0,v3),d(u0,u1)+c(u1,v3)}=min{∞,3+6}=9d(u0,v4)=min{d(u0,v4),d(u0,u1)+c(u1,v4)}=min{5,3+1}=4d(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,∞,∞}=4ui+1
15、=u2=v4,实际已求出d(u0,v4)=4,路是u0v2v4i=2S2={v1,v2,v4}S2’={v3,v5,v6}u2=v4d(u0,u2)=4d(u0,v3)=min{d(u0,v3),d(u0,u2)+c(u2,v3)}=min{9,4+3}=7d(u0,v5)=min{d(u0,v5),d(u0,u2)+c(u2,v5)}=min{∞,4+1}=5d(u0,v6)=min{d(u0,v6),d(u0,u2)+c(u2,v6)}=min{∞,4+∞}=∞min{7,5,∞}=5ui+1=u3=v5,实际已求出d(
16、u0,v5)=5,路是u0v2v4v5i=3S3={v1,v2,v4,v5}S3’={v3,v6}u3=v5d(u0,u3)=5d(u0,v3)=min{d(u0,v3),d(u0,u3)+c(u3,v3)}=min{7,5+3}=7d(u0,v6)=min{d(u0,v6),d(u0,u
