离散数学7.2路与回路.pptVIP

* 7.2 路 与 回 路 7.2.1 路与回路 7.2.2 图的连通性 7.2.1 路 与 回 路 定义 7.2.1 给定图G＝〈V ,E〉, 设v0, v1, … , vk∈V， e1，e2，…，ek∈E， 其中ei是关联于结点vi-1和vi的边， 称交替序列v0e1v1e2…ekvk为连接v0到vk的路， v0和vk分别称为路的起点与终点。路中边的数目k称作路的长度。 当v0=vk时,这条路称为回路。 在简单图中一条路v0e1v1e2…ekvk由它的结点序列v0v1…vk确定,所以简单图的路,可表示为v0v1…vk 。如图7.1.1表示的简单图中， 路ae1be4ce5d可写成abcd。 定义 7.2.2 设μ＝v0e1v1e2…ekvk是图G中连接v0到vk的路。 1)若e1， e2， …， ek都不相同， 则称路μ为迹； 2)若v0， v1， …， vk都不相同， 则称路μ为通路； 3)长度大于２的闭的通路（即除v0＝vk外， 其余结 点均不相同的路）μ称作圈。 图7.1.1 例如在图 7.2.1中， 有连接v5到v3的路v5e8v4e5v2e6v5e7v3， 这也是一条迹； 路v1e1v2 e3v3是一条通路； 路v1e1v2e3v3e4v2e1v1是一条回路， 但不是圈； 路v1e1v2e3v3e2v1是一条回路， 也是圈。 下面我们利用通路的概念解决一个古老的著名问题。 图 7.2.1 【例7.2.1】（渡河问题） 一个摆渡人， 要把一只狼、 一只羊和一捆干草运过河去， 河上有一只木船， 每次除了人以外， 只能带一样东西。 另外， 如果人不在旁时， 狼就要吃羊， 羊就要吃干草。 问这人怎样才能把它们运过河去？ 【游戏】 解 用Ｆ表示摆渡人， W表示狼， Ｓ表示羊， Ｈ表示干草。 解: 用F表示摆渡人， W表示狼， S表示羊， H表示干草。 若用FWSH表示人和其它３样东西在河的左岸的状态。 这样在左岸全部可能出现的状态为以下16种： FWSH FWS FWH FSH WSH FW FS FH WS WH SH F W S H φ 这里φ表示左岸是空集， 即人、 狼、 羊、 干草都已运到右岸去了。 根据题意检查一下就可以知道， 这16种情况中有６种情况是不允许出现的。 它们是： WSH、 FW、 FH、 WS、 SH、 F。 如FH表示人和干草在左岸， 而狼和羊在右岸， 这当然是不行的。 因此， 允许出现的情况只有10种。 我们构造一个图， 它的结点就是这10种状态。 若一种状态可以转移到另一种状态， 就在表示它们的两结点间连一条边， 这样就画出图7.2.2 。 本题就转化为找结点FWSH 到结点φ的通路。 从图中得到两条这样的通路， 即有两种渡河方案。 图 7.2.2 定义 7.2.2 在图G中， 若结点vi到vj有路连接（这时称vi和vj是连通的）， 其中长度最短的路的长度称为vi到vj 的距离， 用符号d(vi,vj)表示。若从vi到vj不存在路径,则d(vi,vj)=∞。 例如在图7.2.1中， ｄ（v1， v4）＝２。 注意:在有向图中,d(vi,vj)不一定等于d(vj,vi),但一般地满足以下性质: (1) d(vi,vj)≥0; (2) d(vi,vi)=0; (3) d(vi,vj)+d(vj,vk)≥d(vi,vk)。 定理 7.2.1 设G是具有n个结点的图， 如果从结点v1到另一结点v2存在一条路， 则从结点v1到v2必存在一条路长度不大于n－1的通路。 证明:假定从v1