离散数学 课件 6.2 路与回路

CHAPTER06图论6.2路与回路PATHSANDCIRCUITSINGRAPHTHEORY目录CONTENTS01路和回路的概念定义、示例与连通性02删除边和删除点割点、割边与连通度03有向图的连通性强连通、单侧连通与弱连通6.2.1路和回路的概念定义6.13：路、回路、迹、通路、圈定义：给定图G=<V,E>，结点和边的交替序列v1

e1

v2

e2…envn，

称为联接v1

到vn

的路(Path)。路(Path)最基础的定义。图中由顶点和边交替构成的序列，用于描述从起点到终点的连接关系。回路(Cycle)闭合的“路”。当一条路的起点\(v_1\)与终点\(v_n\)为同一个结点时，该条路被称为回路。迹(Trail)强调边的不重复性。若一条路中包含的所有边都互不相同，无论顶点是否重复，这样的路被称作“迹”。通路(Path)强调点的不重复性。若一条路中包含的所有顶点都互不相同，这样的路被称作“通路”，也常直接称为“路径”。圈(Circuit)闭合的“通路”。即除了起点和终点重合外，其他所有顶点均不相同的闭合路径。路、迹、通路、圈示例路(Walk)|最宽泛的概念，边和点均可重复示例：a→e₁→b→e₄→c→e₂→a→e₁→b→e₅→d迹(Trail)|边不可重复，点可重复示例：a→e₁→b→e₄→c→e₂→a→e₃→d通路(Path)|结点不可重复，边自然也不可重复示例：a→e₁→b→e₄→c→e₆→d圈(Cycle)|特殊的闭合通路，起点与终点相同示例：a→e₁→b→e₄→c→e₆→d→e₃→a图论结构示例：图中的边与点构成不同的连接方式定理6.5：最短路径的边数限制定理内容在一个具有n个结点的图中，如果从结点vᵢ到结点vⱼ存在一条路，则从结点vᵢ到结点vⱼ必存在一条不多于n-1条边的路。证明思路如果一条路的边数l>n-1，那么根据“鸽巢原理”，该路径上包含的l+1个结点中必有重复的结点出现。我们可以不断移除重复结点之间的回路（即环），从而缩短路径的总长度，直到路径上的边数不超过n-1为止。定义6.14&6.15：连通性与连通图定义6.14连通性与连通分支在无向图G=<V,E>中，若从结点u到结点v存在一条路，称结点u和v是连通的。利用连通性对结点集V作划分，得到的子图称为连通分支。定义6.15连通图若图G的连通分支数W(G)=1，即图中所有的结点都在同一个连通分支中，就称图G是一个连通图。注：连通分支数W(G)是图论中衡量图连通程度的一个基本指标。核心结论“连通图”的定义本质上保证了：在连通图中，任意两个不同的结点之间一定存在通路，即任意两结点之间一定是连通的。连通图与非连通图示例图(a)：连通图连通分支数为1，图中所有的顶点都属于同一个连通分量，任意两点之间都存在路径相连，构成一个整体。图(b)：非连通图连通分支数为3，图被分割为三个互不连通的子图。不同连通分支上的顶点之间不存在路径，是独立的部分。例题6.5：摆渡问题(FerryProblem)问题描述一个人带着一只狼、一只羊和一捆草要渡河。人一次只能运送一个“乘客”。如果人不在，狼要吃羊，羊要吃草。问人如何安排摆渡，才能让所有东西都安全过河？图论建模思路将河左岸允许出现的安全状态视为图的“结点”。若一种状态通过一次合法摆渡变为另一种状态，则在两结点间连一条“边”。问题转化为：在图中寻找一条以“人、狼、羊、草”为起点，以“空”（左岸无物）为终点的简单路径。摆渡问题的解决方案问题转化：状态图视角摆渡问题本质上是一个图论问题：在状态图中寻找一条以初始状态“人、狼、羊、草”为起点，以最终状态“空（所有人/物都到达对岸）”为终点的简单路径。解决方案A：先带狼过河1.人带羊过河→人返回→带狼过河→放下狼并带回羊

2.人带草过河→人返回→最后带羊过河解决方案B：先带草过河1.人带羊过河→人返回→带草过河→放下草并带回羊

2.人带狼过河→人返回→最后带羊过河6.2.2删除边和删除点基本概念对于连通图，删除图中的点或边，可能会改变图的结构，从而影响图的连通性，甚至导致连通图变为非连通图。删除结点v(VertexDeletion)将图中的顶点v移除，同时删除与v关联的所有边。这种操作通常会移除图中的一个“枢纽”节点，对图的连通性影响较大。删除边e(EdgeDeletion)仅将图中的特定边e从图中移除，而保留边的两个端点。这是一种相对温和的操作，但如果该边是“桥”（割边），则会导致图分裂。图示：原图（左）与删除操作后的结果对比定义6.16：点割集、割点、点连通度点割集(VertexCutSet)设无向图G=<V,E>为连通图，若删除图中的一个顶点集合后，图变得不连通，且该集合在所有满足条件的集合中元素数量最少，则称该集合为点割集。割点(CutVertex)如果一个点割集中仅包含一个顶点，那么这个特殊的顶点就被称为割点。删除割点后，连通图会分裂成两个或多个不连通的子图。点连通度(VertexConnectivity)点连通度记为k(G)，它是图G的最小点割集的顶点数量。它反映了一个连通图的连通程度：k(G)越大，图越难被破坏连通性。性质一：存在割点的连通图若连通图G中存在割点，则图G的点连通度为1，即k(G)=1。性质二：完全图Kn对于n阶完全图，任意两个顶点都相邻，必须删除n-1个顶点才能使其不连通，故k(Kn)=n−1。例题6.6：点割集与割点示例图(a)分析•点割集：集合V={l}

是图的一个点割集。•割点：顶点l

被称为“割点”，因为删除它会导致图不连通。•点连通度：图的点连通度k(G)=1。图(b)分析•关键割点：图中顶点v2

和v6

均为割点。•影响：移除这两个顶点中的任意一个，都会将原图分割为两个或更多互不连通的子图，是维持整体连通性的核心节点定义6.17：边割集、割边、边连通度边割集(EdgeCutSet)设无向图G=<V,E>为连通图，若删除某一边集后，图变为不连通，且该边集是满足此条件的最小集合，则称为**边割集**。割边(Bridge)如果一个边割集中仅含有一条边，则这条边被称为“割边”，也常被形象地称作“桥”。边连通度λ(G)对于连通图G，其所有边割集中，元素个数最小的边割集的大小，被定义为图G的边连通度，记作λ(G)。性质01：割边与边连通度如果一个连通图G中存在割边，则其边连通度λ(G)=1。反之，如果λ(G)=1，则图中必含有割边。性质02：完全图的边连通度对于n阶完全图Kn，任意两点间都有边相连，其边连通度为λ(Kn)=n−1。这意味着需要切断连接任意一个顶点的所有边，才能使图不连通。边割集与割边示例单点边割集(割边/桥)•边子集E={m}

构成一个边割集，且边m是一条割边（Bridge）。•该图的边连通度λ(G)=1，说明其连通性较低，删除一条边即可导致图不连通。多点边割集•边子集V1={e,s}，V2={t,l}

均是图的边割集。•这表明，在图论中，边割集既可以是单条边，也可以是多条边的集合，它们共同决定了图的连通性。定理6.6：连通度的不等式定理内容：k(G)≤λ(G)≤δ(G)（点连通度≤边连通度≤最小度）

λ(G)≤δ(G)设顶点v是图G的一个最小度结点，即d(v)=δ(G)。删除与v关联的所有δ(G)

条边后，顶点v将成为孤立点，图G不再连通。因此，图的边连通度λ(G)

不超过δ(G)。k(G)≤λ(G)设S是图G的一个最小边割集，即|S|=λ(G)。删除S中的边后，图被分为两个不连通的子图G1和G2。通过在G1中选择S的所有端点并将其删除，也能使图断开，且删除的点数不会超过边数。因此点连通度k(G)不超过边连通度λ(G)。例题6.7：国际会议翻译问题问题描述有小组成员{a,b,c,d,e,f,g}，每位成员掌握不同的语言种类。试判断：他们中间任何两个人是否都能进行对话（必要时可通过其他人翻译）？建模思路：图论转化将每个人抽象为图中的一个顶点；若两个人掌握同一种语言，则在对应的两个顶点之间连一条边。此时，原问题等价于判断构建出的图是否为一个连通图。最终结论经检验，该图为连通图。因此，必要时通过他人的翻译协助，小组内任何两个人都可以实现对话交流。图：小组成员语言互通关系图示意注：顶点为参会者，连线表示语言互通例题6.8：网络可靠性分析💡问题描述：为了使n个站点之间的连接在部分链路或节点故障时不容易被破坏，应如何构造一个可靠的网络拓扑图？图(a)：高可靠性网络点连通度k(G)=4，边连通度λ(G)=4。

网络结构中无割点，容错能力强，需要破坏大量的点或边才会导致网络瘫痪，是更优的选择。图(b)：低可靠性网络点连通度k(G)=1，边连通度λ(G)=3。

存在关键的割点v，若该站点失效，网络将被分割成互不连通的部分，从而导致整体瘫痪，风险极高。6.2.3有向图的连通性定义6.18：强连通、单侧连通、弱连通强连通(StronglyConnected)在简单有向图G中，若对于任意两个结点u,v，均满足u可达v且v可达u，则称图G是强连通的。单侧连通(UnilaterallyConnected)在简单有向图G中，若对于任意两个结点u,v，至少满足u可达v或v可达u其中之一，则称图G是单侧连通的。弱连通(WeaklyConnected)在简单有向图G中，如果去掉所有边的方向后，得到的无向图是连通的，则称图G是弱连通的。包含关系：强连通⫋单侧连通⫋弱连通（强连通图一定是单侧连通图；单侧连通图一定是弱连通图）有向图连通性示例图(a)·强连通图在有向图中，若任意两个顶点之间都能相互到达，则称该图为强连通图。它是连通性最强的一种类型。图(b)·单侧连通图若有向图中任意两个顶点，至少存在一个方向的通路（例如：顶点a可达顶点b，但顶点b不可达顶点a），则称为单侧连通图。图(c)·弱连通图若将有向图的所有边的方向去掉，转化为无向图后是连通的，但作为有向图本身并不满足强连通或单侧连通的条件，则称为弱连通图。定理6.8：强连通的充要条件定理内容Statement一个有向图G是强连通的，当且仅当G中有一个回路，它至少包含G中所有结点一次。充分性Sufficiency若存在一个包含所有结点的回路，则图中任意两个结点都可以沿着这个回路互相到达，因此图满足强连通的定义。必要性Necessity若图是强连通的，则任意两结点相互可达。通过依次从任意起点出发访问所有结点并连接路径，可以构造出一条包含所有结点的回路。定义6.19：强分图、单侧分图、弱分图强分图StrongComponent在简单有向图G中，具有强连通性质的最大子图。单侧分图UnilateralComponent在简单有向图G中，具有单侧连通性质的最大子图。弱分图WeakComponent在简单有向图G中，具有弱