图论讲义2连通性

图论与网络流理论（Graph Theory and Network Flow Theory）讲授：高随祥中科院研究生院专业基础课学时/学分：60/3本课程适合基础数学、应用数学、计算数学、运筹学与控制论、概率论与数理统计各专业的硕士学位研究生作为专业基础课，也可供物理学、化学、天文学、地学、生物科学、计算机科学与技术、计算机软件、管理科学与工程以及通信、信号等学科专业的硕士研究生选修。

主要讲授图论与网络流理论的基本概念、方法和定理，介绍该领域重要的问题以及典型的算法，展示图论与网络流模型及方法的广泛应用。

为学习者将来从事有关方面的理论研究打下基础，也为进行应用性研究提供一种有力的工具。

内容提要第一章 图的基本概念图的基本概念；二部图及其性质；图的同构；关联矩阵与邻接矩阵。

路、圈与连通图；最短路问题。

树及其基本性质；生成树；最小生成树。

第二章 图的连通性割点、割边和块；边连通与点连通；连通度；Whitney定理；可靠通信网络的设计。

第三章 匹配问题匹配与最大匹配；完美匹配；二部图的最大匹配；指派问题与最大权匹配。

第四章 欧拉图与哈密尔顿图欧拉图；中国邮递员问题；哈密尔顿图；旅行商问题。

第五章 支配集、独立集、覆盖集与团支配集、点独立集、点覆盖集、边覆盖集与团的概念及其求法。

第六章图的着色问题点着色；边着色；平面图；四色猜想；色多项式；色数的应用。

第七章网络流理论有向图；网络与网络流的基本概念；最大流最小割定理；求最大流的标号算法；最小费用流问题；最小费用最大流；网络流理论的应用。

主要参考书[1] J.A. Bondy and U.S. Murty, Graph theory with applications, 1976, 有中译本（吴望名等译）。

[2] B.Bollobas, Modern graph theory (现代图论)，科学出版社，2001。

[3] 蒋长浩，图论与网络流，中国林业出版社，2001。

连通性（二）道路连通性与连通性类似的概念是道路连通性，它同样可以看作是人的直观的一种数学化，但在某些特殊的例子上他似乎又与人的直观不太类似，本节我们介绍道路连通性的定义以及基本性质并证明：拓扑学家的正弦曲线不是道路连通的.设与为空间的两点, 中从到的一条道路 (path) 是指从实直线的某一个闭区间到的一个连续映射 , 使得和 . 如果空间中每一对点都能用中的一条道路连接, 则称是道路连通的 (path connected).道路连通必然连通.假设道路连通但不是连通的，那么我们有的一个分割：.而取中的两点,构造道路,那么是连通的，因此必然全含于或,这与分别在或者中是矛盾的.注意到：道路是映射，而非函数的像，但是由于我们无法画出函数，因此有函数的像加箭头表示.习惯上，我们会令为.若,我们把这样的道路称为环路或者闭路.1.中的凸集是道路连通的.(凸集的定义.)2.穿孔欧式空间是道路连通的.道路连通集的像还是道路连通的.证明：设是道路连通集，是其像.那么对于任意的存在使得：,又因为道路连通，因此村子啊使得,所以：是中的一条道路.由于的任意性.命题得证.这说明连通性是拓扑不变性质，在连续映射下可以保持自然可以在同胚下保持.设和是道路连通的，证明是道路连通的.设是乘积空间中任意两点，我们要构造从到的连续映射使得.首先由于是连通的，因此存在使得他们是中的道路，并且有：,那么我们有：连续映射的复合还是连续映射，因此道路连通.作为道路连通的结束，我们来证明拓扑学家的正弦曲线不是道路连通的.拓扑学家的正弦曲线是连通的但不是道路连通的.前一部分我们已经证明过了，现在我们证明后半部分.我们仍然采用前边的记号：,为整个图像记为，我们假设是中的一条道路，且,是中任何一点.由于是图的闭集因此是闭集，那么是闭集，因此有最大元,因此将中的点都除了之外都映在了中，我们不妨令，,其中,,但是我们可以证明不连续.可以取,使得从而得到不连续.(我们可按照以下方式选取 : 对于给定的 , 选取满足的使得 . 那么由介值定理知, 存在满足的使得 .)。

图论_连通_连通分量 强连通图 : 强连通分量就是本⾝ 有向图 ---> ⾮强连通图 : 多个强连通分量图---> 连通图 : 连通分量就是本⾝ ⽆向图 ---> ⾮连通图 : 多个连通分量路径 : 顾名思义.路径长度 : 路径上边的数量.路径 : 顾名思义.路径长度 : 路径上边的数量.连通 : ⽆向图顶点A可以到顶点B,则称A,B连通.强连通 : 有向图中，两个顶点间⾄少存在⼀条互相可达路径，则两个顶点强连通连通图 : 图中任意两点都连通的图.强连通图 : 有向图的任意两点都强连通.连通分量 : ⽆向图的极⼤连通⼦图称为连通分量.连通图只有⼀个连通分量,即⾃⾝强连通分量: 强连通图有向图的极⼤强连通⼦图.强连通图的强连通分量只有⼀个,即强连通图本⾝.基图 : 将有向图的所有边替换成⽆向边形成的图.弱连通图 : 基图是连通图的有向图.(即,连通的有向图)求图的连通分量的⽬的，是为了确定从图中的⼀个顶点是否能到达图中的另⼀个顶点，也就是说，图中任意两个顶点之间是否有路径可达。

求强连通分量有多种算法.我⽤的Tarjan算法. 复杂度O(V+E)这两个博客写得不错:https:///reddest/p/5932153.htmlhttps:///shadowland/p/5872257.htmlint dfn[16]; // 时间戳int dfn_num = 0; // 时间int low[16]; // 节点u所能访问到的最⼩时间戳int inSt[16]; // 节点u是否在栈中.int st[16];int top = 0;// 我们维护的信息.int col[16]; // 给节点染⾊, 同⼀个连通块的节点应该是同⼀个颜⾊的.int col_num = 0; // 颜⾊值.int size[16]; // 每个颜⾊值所拥有的块数./*第⼀步: 访问当前节点的所有⼦节点: ⼦节点有三种第⼀种: 未访问过的, 我们对它进⾏访问, 同时设置它的时间戳dfn[u]和low[u]为++ndfn_num,以及进栈.第⼆种: 访问过的,并且在栈中,我们直接更新我们当前节点的low[] --> 注意应该⽤low[u] 和 dfn[v]⽐较.第三种: 访问过的,并且不在栈中的, 我们直接跳过.因为这个时候,所以它已经染⾊了,属于⼀个连通块了.第⼆步: 如果dfn[u] == low[u] 说明已经找到⼀个连通块了.这时候我们要将栈顶元素弹出,直到当前节点. 记得也要修改inSt, 同时维护我们需要的信息.*/void Tarjan(int u) {int v, i;dfn[u] = low[u] = ++dfn_num; //添加时间戳.st[++top] = u; // 进栈inSt[u] = true; // 标⽰在栈for (i=head[u]; i; i=edge[i].lst) {v = edge[i].to;if (!dfn[v]) {Tarjan(v);low[u] = min(low[u], low[v]);} else if (inSt[v]) {low[u] = min(low[u], dfn[v]);}}if (dfn[u] == low[u]) {col_num++;do {inSt[st[top]] = false;col[st[top]] = col_num;size[col_num]++;} while (st[top--] != u);}}View Code加上2个板⼦题./problem/1332/题⽬很简单: 要你求出最⼤的强连通块,如果有多个则输出字典序最⼩的⼀个.#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int maxn = 5e4+500;struct Edge {int lst;int to;}edge[maxn<<1];int head[maxn];int qsz = 1;inline void add(int u, int v) {edge[qsz].lst = head[u];edge[qsz].to = v;head[u] = qsz++;}int dfn[maxn]; // 时间戳int dfn_num = 0; // 时间int low[maxn]; // 节点u所能访问到的最⼩时间戳int inSt[maxn]; // 节点u是否在栈中.int st[maxn];int top = 0;// 我们维护的信息.int col[maxn]; // 给节点染⾊, 同⼀个连通块的节点应该是同⼀个颜⾊的.int col_num = 0; // 颜⾊值.int size[maxn]; // 每个颜⾊值所拥有的块数.int id[maxn];void Tarjan(int u) {int v, i;dfn[u] = low[u] = ++dfn_num; //添加时间戳.st[++top] = u; // 进栈inSt[u] = true; // 标⽰在栈for (i=head[u]; i; i=edge[i].lst) {v = edge[i].to;if (!dfn[v]) {Tarjan(v);low[u] = min(low[u], low[v]);} else if (inSt[v]) {low[u] = min(low[u], dfn[v]);}}if (dfn[u] == low[u]) {col_num++;id[col_num] = u;do {inSt[st[top]] = false;col[st[top]] = col_num;size[col_num]++;id[col_num] = min(id[col_num], st[top]);} while (st[top--] != u);}}int main(){memset(id, 0x3f, sizeof(id));int n, i, u, v, m, t;scanf("%d%d", &n, &m);for (i=1; i<=m; ++i) {scanf("%d%d%d", &u, &v, &t);add(u, v);if (t==2) add(v, u);}for (i=1; i<=n; ++i)if (!dfn[i]) Tarjan(i);int mm = 0, tcol = -1;for (i=1; i<=col_num; ++i)if (mm < size[i]) {mm = size[i];tcol = i;} else if (m == size[i]) {if (id[tcol] > id[i])tcol = i;}// printf("%d \n", tcol);printf("%d\n", mm);for (i=1; i<=n; ++i)if (col[i] == tcol) printf("%d ", i);printf("\n");return0;}View Codehttps:///problem/HYSBZ-1051题⽬: 求出所有⽜都欢迎的⽜的个数. 我们可以把所有连通块求出,然后把⼀个连通块看成⼀个点,即缩点. 然后找到出度为零的点(连通块), 如果有且只有⼀个,那么连通块的点数就是答案,否则答案为零.#include <cstdio>#include <algorithm>using namespace std;struct Edge {int lst;int to;}edge[50500];int head[10100];int qsz = 1;inline void add(int u, int v) {edge[qsz].lst = head[u];edge[qsz].to = v;head[u] = qsz++;}int dfn[10100]; // 时间戳int dfn_num = 0; // 时间int low[10100]; // 节点u所能访问到的最⼩时间戳int inSt[10100]; // 节点u是否在栈中.int st[10100];int top = 0;// 我们维护的信息.int col[10100]; // 给节点染⾊, 同⼀个连通块的节点应该是同⼀个颜⾊的.int col_num = 0; // 颜⾊值.int size[10100]; // 每个颜⾊值所拥有的块数./*第⼀步: 访问当前节点的所有⼦节点: ⼦节点有三种第⼀种: 未访问过的, 我们对它进⾏访问, 同时设置它的时间戳dfn[u]和low[u]为++ndfn_num,以及进栈.第⼆种: 访问过的,并且在栈中,我们直接更新我们当前节点的low[] --> 注意应该⽤low[u] 和 dfn[v]⽐较. 第三种: 访问过的,并且不在栈中的, 我们直接跳过.因为这个时候,所以它已经染⾊了,属于⼀个连通块了. 第⼆步: 如果dfn[u] == low[u] 说明已经找到⼀个连通块了.这时候我们要将栈顶元素弹出,直到当前节点. 记得也要修改inSt, 同时维护我们需要的信息.*/void Tarjan(int u) {int v, i;dfn[u] = low[u] = ++dfn_num; //添加时间戳.st[++top] = u; // 进栈inSt[u] = true; // 标⽰在栈for (i=head[u]; i; i=edge[i].lst) {v = edge[i].to;if (!dfn[v]) {Tarjan(v);low[u] = min(low[u], low[v]);} else if (inSt[v]) {low[u] = min(low[u], dfn[v]);}}if (dfn[u] == low[u]) {col_num++;do {inSt[st[top]] = false;col[st[top]] = col_num;size[col_num]++;} while (st[top--] != u);}}bool ou[10010];int main(){// freopen("E:\\input.txt", "r", stdin);int n, i, j, u, v, m;scanf("%d%d", &n, &m);for (i=1; i<=m; ++i) {scanf("%d%d", &u, &v);add(u, v);}for (i=1; i<=n; ++i)if (!dfn[i])Tarjan(i);// 缩点操作int cnt = 0, res = 0;for (i=1; i<=n; ++i) {if (ou[col[i]]) continue;for (j=head[i]; j; j=edge[j].lst) {v = edge[j].to;if (col[i] != col[v]) {ou[col[i]] = true;break;}}}for (i=1; i<=col_num; ++i) {if (!ou[i]) {res = size[i];cnt++;}if (cnt > 1) {res = 0;break;}}printf("%d\n", res);return0;}View Code。

图的连通性检测方法图论是数学的一个分支，研究图形结构以及图形之间的关系。

在图论中，连通性是一个重要的概念，用于描述图中的节点或顶点之间是否存在路径相连。

连通性检测方法是用来确定一个图是否是连通图的方法。

本文将介绍几种常用的图的连通性检测方法。

一、深度优先搜索（DFS）深度优先搜索是一种常用的图遍历算法，也可以用来检测图的连通性。

该方法从图中的一个顶点开始，沿着一条路径尽可能深的搜索，直到到达无法继续搜索的节点，然后回溯到上一个节点，继续搜索其他路径。

具体步骤如下：1. 选择一个起始节点作为根节点。

2. 遍历该节点的邻接节点，并标记为已访问。

3. 递归的访问未访问过的邻接节点，直到所有节点都被访问过。

4. 如果所有节点都被访问过，则图是连通的；否则，图是不连通的。

DFS算法的时间复杂度为O(V+E)，其中V是节点数，E是边数。

二、广度优先搜索（BFS）广度优先搜索也是一种常用的图遍历算法，同样可以用来检测图的连通性。

该方法从图中的一个顶点开始，先访问其所有邻接节点，然后再依次访问它们的邻接节点。

具体步骤如下：1. 选择一个起始节点作为根节点。

2. 将该节点加入一个队列中。

3. 从队列中取出一个节点，并标记为已访问。

4. 遍历该节点的邻接节点，将未访问过的节点加入队列中。

5. 重复步骤3和步骤4，直到队列为空。

6. 如果所有节点都被访问过，则图是连通的；否则，图是不连通的。

BFS算法的时间复杂度同样为O(V+E)。

三、并查集并查集是一种数据结构，常用于解决图的连通性问题。

它可以高效地合并集合和判断元素是否属于同一个集合。

具体步骤如下：1. 初始化并查集，每个节点都是一个独立的集合。

2. 遍历图中的每条边，将边的两个节点合并到同一个集合中。

3. 判断图是否连通的方法是查找两个节点是否属于同一个集合。

并查集的时间复杂度为O(V+E)。

四、最小生成树最小生成树是指一个连通图的生成树，其所有边的权值之和最小。

三、连通性3.1 连通性和Whitmey定理定义V’真包含于V(G)，G[V(G)-V’]不连通，而G是连通图，则称V’是G的顶剖分集。

最小顶剖分集中顶的个数，记成κ(G)，叫做G的连通度；规定κ(Kv)=υ-1；κ(不连通图)= κ(平凡图)=0。

由一个顶组成的顶剖分集叫割顶。

没有割顶的图叫做块，G中的成块的极大子图叫做G的块。

定义E’包含于E(G)，G为连通图，而G-E’(从G中删除E’中的边)不连通，则称E’为G的边剖分集，若G中已无边剖分集E″，使得|E″|<|E’|,则称|E’|为G的边连通度，记成κ’(G)。

|E’|=1时，E’中的边叫做桥。

规定κ’(不连通图)=0，κ’(Kv)= υ-1。

定义κ(G)>=k时，G叫做k连通图；κ’(G)>=k时，G称为k边连通图。

k连通图，当k>1时，也是k-1连通图。

k边连通图，当k>1时，也是k-1边连通图。

上面就是顶连通与边连通的概念，好象不指明的就是指顶连通了。

定理1 κ(G)=<κ’(G)=<δ(可以复习一下第一章的1.2：δ=min{d(v i)})证：设d(v)=δ，则删除与v边关联的δ条边后，G变不连通图，所以这δ条边形成一个边剖分集，故最小边剖分集边数不超过δ，即κ’(G)=<δ。

下证κ=<κ’。

分情形讨论之。

若G中无桥，则有κ’>=2条边，移去它们之后，G变成不连通图。

于是删除这κ’条中的κ’-1条后，G变成有桥的图。

设此桥为e=uv，我们对于上述κ’-1条删去的每条边上，选取一个端点，删除这些(不超过κ’-1个)端点，若G变得不边能，则κ=<κ’-1；若仍连通，则再删去u或v，即可使G变得不连通，于是κ=<κ’。

证毕。

这个定理很好理解，图论中的一些定理常以这种“友好”的面目出现。

下面就是Whitmey定理定理2(Whitney,1932) υ>=3的图是2连通图的充要条件是任二顶共圈(在一个圈上)。