-路与回路.ppt

7-2 路与回路 在现实世界中，常常要考虑这样的问题：如何从一个图中的给定结点出发，沿着一些边连续移动而达到另一指定结点，这种依次由点和边组成的序列，就形成了路的概念。 一、路 例如 路：v1e2v3e3v2e3v3e4v2e6v5e7v3 迹：v5e8v4e5v2e6v5e7v3e4v2 通路：v4e8v5e6v2e1v1e2v3 圈：v2e1v1e2v3e7v5e6v2 在简单图中一条路v0e1v1e2…envn，由它的结点序列v0，v1，…，vn确定，所以简单图的路，可由其结点序列表示。在有向图中，结点数大于一的—条路亦可由边序列e1e2…en表示。 定理7-2.1的证明 如果从结点vj到vk存在一条路，该路上的结点序列是vj…vi…vk，如果在这条中有l条边，则序列中必有 l+1个结点，若ln-1，则必有结点vs，它在序列中不止出现一次，即必有结点序列vj…vs…vs…vk，在路中去掉从vs到vs的这些边，仍是vj到vk的一条路，但此路比原来的路边数要少，如此重复进行下去，必可得到一条从vj到vk的不多于n-1条边的路。 二、无向图的连通性： 1、连通 2、连通图 定义7-2.3：若图G只有一个连通分支，则称G是连通图。 显然在连通图中，任意两个结点之间必是连通的。 点连通度：是为了产生一个不连通图需要删去的点的最少数目，也称为连通度，记为k(G) 。 即k(G)=min{|V1|| 是G的点割集} 称为图G的点连通度(node-connectivity) 。 (1)若G是平凡图则V1=?，k(G)=0 (2)k(Kn)=n-1 (3)若图存在割点，则k(G)=1 (4)规定非连通图的连通度k(G)=0 4、割边 定义7-2.5 设无向图G =V,E是连通图,若有边集E1?E，使图 G中删除了E1的所有边后，所得到的子图是不连通图，而删除了E1的任何真子集后，所得到的子图仍是连通图，则称E1是G的一个边割集(cut-set of edges) 。若某一条边就构成一个边割集，则称该边为割边或桥。 割边e使图G满足W(G-e)W(G) 。 5、定理7-2.2 对于任何一个图G,有k(G)≤?(G)≤δ(G) 。 证明： 若G不连通，则k(G)=?(G)=0，故上式成立。 若G连通，可分两步证明上式也成立： 1)先证明?(G)≤?(G)： 如果G是平凡图，则?(G)=0≤?(G)， 若G是非平凡图，则因每一结点的所有关联边必含一个边割集，(因?(G)=min{deg(v)|v?V}，设u?V使的deg(u)=δ(G)，与u相关联的?条边必包含一个边割集，至少这?条边删除使图不连通。)故?(G)≤?(G)。 2)再证k(G)≤?(G)： (a)设?(G)=1，即G有一割边，显然这时k(G)=l，上式成立。 (b)设?(G)≥2，则必可删去某?(G)条边，使G不连通，而删去其中?(G)-1条边，它仍是连通的，且有一条桥e=(u，v)。对?(G)-1条边中的每一条边都选取一个不同于u，v的端点，把这些端点删去则必至少删去?(G)-1条边。若这样产生的图是不连通的，则k(G)≤?(G)-1?(G)，若这样产生的图是连通的，则e仍是桥，此时再删去u或v就必产生一个不连通图，故k(G)≤?(G)。由1)和2)得k(G)≤?(G)≤?(G)。 三、有向图的连通性： 1、可达： 在无向图G中，从结点u到v若存在一条路，则称结点u到结点v是可达的。 如果u可达v，它们之间可能不止一条路，在所有这些路中，最短路的长度称为u和v之间的距离（或短程线），记作du,v，它满足下列性质： du,v≥0 du,u =0 du,v + dv,w ≥ du,w 证明：充分性：如G中有一条有向回路，经过每一点至少一次，则G中任意两点u，v∈V，u可以沿着该有向回路的一部分的而到达v，则G是强连通图。 4、定义7-2.7：在简单有向图中，具有强连通性质的最大子图，称为强分图；具有单侧连通性质的最大子图，称为单侧分图；具有弱连通性质的最大子图，称为弱分图。 * * 学习本节要熟悉如下术语(22个)： 路、 路的长度、 迹、 回路、 通路、 圈、 连通、 连通分支、 点割集、 连通图、 割点、 点连通度、 边割集、 边连通度、 割边、 可达、 单侧连通、 强连通、 强分图、 弱连通、 弱分图、 单侧分图 掌握5个定理，一个推论。