图论导引 - 第三章 第一节：连通性

图论导引 - 第三章 第一节：连通性

引用

CSDN

1.

https://blog.csdn.net/chan_lay/article/details/143647172

章节概述

第三章（Paths and cycles）主要讲述了路径和循环相关的图论知识，包括四个部分：连通性、欧拉图、哈密顿图、一些相关算法应用。

连通性 Connectivity

通道 walk

给定一个图G，G中的一条通道（或称为“链”）是形如v0v1、v1v2、⋅⋅⋅、vm−1vm的有限边序列，也可记为v0→v1→v2→⋯→vm，其中任意两条连续的边是相邻的或相同的。

• 一条通道确定了一个顶点序列v0,v1,⋅⋅⋅,vm。
• 我们称v0为通道的起始顶点（initial vertex），vm为通道的终止顶点（final vertex），并说这是一条从v0到vm的通道。
• 通道中的边数称为其长度（length）。

迹 trail 和 路径 path

• 所有边都互不相同的通道是一条迹（trail）。
• 此外，如果所有顶点v0,v1,⋯,vm都互不相同（除了v0=vm），那么这条迹就是一条路径（path）。
• 如果v0=vm，则路径或迹是封闭的（closed），并且包含至少一条边的封闭路径是一个圈（cycle）。
• 注意，任何环（loop）或一对多重边都是一个圈。

连通图

当且仅当每对顶点之间都存在一条路径时，图是连通的。

二部图 Bipartite Graph

当且仅当G的每个圈(cycle)都具有偶数长度时，G是二分图。

定理5.1：如果G是一个二分图，那么G的每个圈都具有偶数长度。

证明：

• 因为G是二分图，所以我们可以将其顶点集划分为两个不相交的集合A和B，使得G的每条边都连接A中的一个顶点和B中的一个顶点。
• 设v0→v1→⋯→vm→v0是G中的一个环，并且假设v0在A中。那么v1在B中，v2在A中，依此类推。由于vm必定在B中，所以这个回路的长度肯定是偶数。

简单连通图的边数限制

一个具有n个顶点的简单连通图，当没有回路时边数最少，为n−1条边；当该图是完全图时边数最多，为n(n−1)/2条边。

定理5.2：设G是一个具有n个顶点的简单图。如果G有k个连通分量，那么G的边数m满足n−k≤m≤(n−k)(n−k+1)/2。

证明：

• 证下界：
• 假设每个连通分量Ci中有ni个顶点，图G的总顶点数为n=∑i=1kni
• 一个连通分量中，ni个顶点至少有ni−1条边连接
• k个连通分量，至少有∑i=1k(ni−1)条边，计算∑i=1k(ni−1)=∑i=1kni−k=n−k
• 对于k个连通分量，至少有n−k条边，得证。
• 证上界：
• 为了证明上限，假设G的每个连通分量都是完全图，这样才有可能达到最多的边数。
• 假设有两个连通分量Ci和Cj，分别有ni个和nj个顶点，其中ni≥nj>1。如果我们用具有ni+1个顶点和nj−1个顶点的完全图分别替换Ci和Cj，那么顶点总数保持不变，而边的数量变化为
  { ( ni+1)ni−ni(ni−1)2 } − { nj(nj−1)−(nj−1)(nj−2)2 } = ni−nj+1
• 由于ni−nj+1肯定是一个正数，因此边数在增多。为了让边的数量最大，需要不断增加一个连通分量的顶点，减少另外连通分量的顶点。
• 由此可知，G必须由一个具有n−k+1个顶点的完全图和k−1个孤立顶点组成。
• 具有n−k+1个顶点的完全图的边数为(n−k)(n−k+1)/2，得证。

推论5.3：任何具有n个顶点且边数多于(n−1)(n−2)/2的简单图都是连通的。

证明：

• 把任意一个图G分成包含n−1个顶点的子图和一个顶点n0
• 只需要保证包含n−1个顶点的子图是完全图，再用其余的边连接最后一个顶点n0。
• 顶点个数为n−1的完全图的边数为(n−1)(n−2)/2，那么只要边数多余(n−1)(n−2)/2则整个图G必定是完全图。

断集、割集和桥

• 如何衡量一个连通图的连通性有多强？
• 看看移除多少条边或顶点才能使连通图不连通
• 点连通度、边连通度
• 断集 disconnecting set
• 在连通图G中，一个断集是一组边的集合，移除集合中的这些边会使G不连通。断集是使得图失去连通性的边集。
• 割集 cutset
• 一个断集的任何真子集都不是断集，则称该断集为割集。
• 移除割集中的边总是会留下一个恰好有两个连通分量的图。
• 在上图 5.3 中，{e3,e6,e7,e8}是割集。
• 桥 bridge
• 如果一个割集只有一条边e，我们称e为桥。
• 边连通度λ(G)
• 如果G是连通的，它的边连通度λ(G)是G中最小割集的大小。因此，λ(G)是为使G不连通而需要删除的最少边数。
• 如果λ(G)≥k，那么G是k 边连通的。

分离集和割点

• 分离集 separating set
• 在连通图G中，一个分离集是一组顶点，删除这些顶点会使G不连通；当删除一个顶点时，也会移除与顶点关联的边。
• 割点 cut-vertex
• 如果一个分离集只包含一个顶点v，我们称v为割点。
• 点连通度κ(G)
• 如果G是连通的且不是完全图，它的顶点连通度κ(G)是G中最小分离集的大小。κ(G)是为使G不连通而需要删除的最少顶点数。
• 如果κ(G)≥k，那么G是k连通的。
• 可以证明，如果G是任何连通图，那么κ(G)≤λ(G)。
• 直观理解，一个顶点可能与多条边相关联，删除一个顶点可能会导致与该顶点相连的所有边都失去作用，从而更容易使图变得不连通；而删除一条边只会影响与该边直接相关的两个顶点之间的连接。
• 所以，为了使图不连通，需要删除的顶点数量通常不会超过需要删除的边的数量，即点连通度一般小于等于边连通度。