《路与回路》PPT课件

《《路与回路》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、离散数学DiscreteMathematics课程回顾图的定义：结点集、边集、图的分类、点和边的关联、点与点的相邻、边与边的邻接、孤立结点、零图、平凡图、环、平行边点的度数：度数、出度、入度、最大度、最小度、握手定理、相关定理特殊的图：多重图、简单图、完全图、补图、子图、生成子图、图的同构第七章图论第2讲7—2路与回路7-2路与回路在实际应用中，比如在市内乘出租车去参观一个博览会，一定要司机选一条最短的路。到博览会后，最好选一条这样的路径，使得每个展台都参观一次后，再回到原来存包处。这就是路与回路的问题。学习本节要熟悉如下术语（22个）：路、路的长度、迹、回路、通路、圈、连通、连通分

2、支、点割集、连通图、割点、点连通度、边割集、边连通度、割边、可达、单侧连通、强连通、强分图、弱连通、弱分图、单侧分图掌握5个定理，一个推论。一、路定义7-2.1给定图G=,设v0,v1,…,vnV，e1,…,enE,其中ei是关联于结点vi-1,vi的边，交替序列v0e1v1e2…envn称为结点v0到vn的路（拟路径Pseudopath）。v0和vn分别称为路的起点和终点，边的数目n称作路的长度。当v0=vn时，这条路称作回路（闭路径closedwalk）。若一条路中所有的边e1,…,en均不相同,称作迹（路径walk）。若一条路中所有的结点v0,v1,…,vn均不相

3、同,称作通路（Path）。闭的通路,即除v0=vn之外，其余结点均不相同的路，称作圈（回路circuit）。注：通路都是迹，迹不都是通路。（没有重复结点亦没有重复边）在简单图中一条路v0e1v1e2…envn，由它的结点序列v0v1…vn确定，所以简单图的路，可由其结点序列表示。在有向图中，结点数大于1的一条路亦可由边序列e1e2…en表示。路长度：边的数目n。结点数=边数+1回路(closedwalk):当v0=vn时v0e1v1e2…vi-1eivi…envn结点数=边数图7-2.1例路：v1e2v3e3v2e3v3e4v2e6v5e7v3迹：v5e8v4e5v2e6v5e7v3

4、e4v2通路：v4e8v5e6v2e1v1e2v3圈：v2e1v1e2v3e7v5e6v2v1v2v3v4v5e1e2e3e4e5e6e7e8v1v2v3v4v5e1e2e3e4e5e6e7e8v2v1v2v3v4v5e1e2e3e4e5e6e7e8v1v2v3v4v5e1e2e3e4e5e6e7e8从v1到v3的一条路，长度为6从v5到v2的一条迹，长度为5从v4到v3的一条通路，长度为4从v2到v2的一条圈，长度为4定理7-2.1在一个具有n个结点的图中，如果从结点vj到结点vk存在一条路，则从结点vj到结点vk必存在一条不多于n-1条边的路。证明思路：多于n-1条边的路中必有重

5、复出现的结点，反复删去夹在两个重复结点之间的边之后，剩余的边数不会超过n-1条边。定理7-2.1示例:VsVkVjVsVsVkVjVjVk定理7-2.1的证明如果从结点vj到vk存在一条路，该路上的结点序列是vj…vi…vk，如果在这条路中有L条边，则序列中必有L+1个结点，若L>n-1，则必有结点vs，它在序列中不止出现一次，即必有结点序列vj…vs…vs…vk，在路中去掉从vs到vs的这些边，仍是vj到vk的一条路，但此路比原来的路边数要少，如此重复进行下去，必可得到一条从vj到vk的不多于n-1条边的路。定理7-2.1的推论在一个具有n个结点的图中，如果从结点vj到结点vk

6、存在一条路，则从结点vj到结点vk必存在一条边数小于n的通路。如在图7-2.1中有5个结点。v1到v3的一条路为：v1e2v3e3v2e3v3e4v2e6v5e7v3此路中有6条边，去掉e3有路v1e2v3e4v2e6v5e7v3有4条边。v1到v3最短的路为v1e2v3二、无向图的连通性1、连通定义7-2.2在无向图G中，如果从结点u和结点v之间若存在一条路，则称结点u和结点v是连通的（connected）。注：（1）对于所有v∈V，规定结点到自身是连通的。（2）由定义不难看出，无向图中结点之间的连通关系R={

7、u,v∈V且u与v连通}是自反的，对称的，传递的，因而R是V

8、上的等价关系。结点之间的连通性是结点集V上的等价关系，对应该等价关系，必可将作出一个划分，把V分成非空子集V1,V2,…,Vm,使得两个结点vj和vk是连通的，当且仅当它们属于同一个Vi。把子图G(V1),G(V2),…,G(Vm)称为图G的连通分支（connectedcomponents）,图G的连通分支数记为W(G)。例:W(G)=3G见281页图7-2.2练习1：下图中连通分支数目？练习2：下图中连通分支数目？2645132、连通图定义7