003路径、连通图、连通分量.ppt

一个顶点是可达的； 有向图是弱连通的，有向边被看作无向边时是连通的。
连通图 不连通图 强连通图 单向ቤተ መጻሕፍቲ ባይዱ通图 弱连通图
第18讲 路径、回路及连通性
-9-
连通分支
定义：在无向图G中，若至少存在两个节点是不可达的，则 G是不连通的；如果G是不连通的，G’是G的子图，G’是连 通的，并且不存在G的真子图G’’，使G’’是连通的，且G’’ 以G’为真子图， 则称G’是G的一个极大连通子图，或称是 G的一个连通分支
PowerPoint Template_Sub
1 图的基础知识 2 路径、回路及连通性 3 欧拉图与哈密顿图 4 图的矩阵表示
《离散数学》第18讲 路径、回路及连通性 Page 112 to 117
拟路径及长度
定义：图G的顶点v1到顶点vl的拟路径是指以下顶点与边的序列： v1 , e1, v2, e2, v3, …, vl-1, el-1, vl v1 ,v2 ,v3 ,… ,vl-1 ,vl为G的顶点，e1 ,e2 ,… ,el-1 为G的边 ei( i= 1,2, … ,l-1 )以vi及vi+1为端点 对有向图G，ei以vi为起点，以vi+1为终点
称有向图G是单向连通的，如果G的任何两个顶点中， 至少从一个顶点到另一个顶点是可达的；
称有向图G是弱连通的，如果G的有向边被看作无向 边时是连通的。
第18讲 路径、回路及连通性
-8-
连通
u到v是可达的，如果有一条u到v的路径，或者u =v。 无向图是连通的，任何两个顶点u到v都是可达的。 有向图是强连通，任何两个顶点都是相互可达的； 有向图是单向连通的，任何两个顶点中，至少从一个顶点到另
然后重复上述讨论，直至没有边重复出现、没有顶点重 复出现，从而得到从u到v的路径和长度不超过n – 1的通 路。

ar Cows
给定一个有向图，求有多少个顶点是由任何顶 点出发都可达的。
顶点数<= 10,000,边数 <= 50,000
有用的定理:
有向无环图中唯一出度为0的点，一定可 以由任何点出发均可达(由于无环，所 以从任何点出发往前走，必然终止于 一个出度为0的点)
ACM2186: 解题思路
有向图的强连通分支
定义
在有向图G中，如果任意两个不同的顶点 相互可达，则称该有向图是强连通的。 有向图G的极大强连通子图称为G的强连 通分支。
转置图的定义：将有向图G中的每一条 边反向形成的图称为G的转置GT。（注 意到原图和GT的强连通分支是一样的）
Korasaju算法
procedure Strongly_Connected_Components(G);
学习并没有结束，希望继续努力
Thanks for listening, this course is expected to bring you value and help 为方便学习与使用课件内容，课件可以在下载后自由编辑
ACM1236: 解题思路
1. 求出所有强连通分量
2. 每个强连通分量缩成一点，则形成一个有 向无环图DAG。
3. DAG上面有多少个入度为0的顶点，问题1的 答案就是多少
ACM1236: 解题思路
在DAG上要加几条边，才能使得DAG变成强连通 的，问题2的答案就是多少
加边的方法：
要为每个入度为0的点添加入边，为每个出度 为0的点添加出边
end; 证明参考：
(a)为有向图G， 其中的阴影部分 是G的强连通分 支，对每个顶点 都标出了其发现 时刻与完成时刻 ，黑色边为深度 优先搜索的树 枝；

二叉树的性质
二叉树具有五种基本形态，即空二叉树、只有一个根节点的二叉树、只有左子树或右子 树的二叉树、以及左右子树均有的二叉树。此外，二叉树还具有一些重要性质，如二叉
树的第i层最多有2^(i-1)个节点（i>=1），深度为k的二叉树最多有2^k-1个节点 （k>=1）等。
二叉树的遍历算法
先序遍历
先访问根节点，然后遍 历左子树，最后遍历右
05
图论基础及图的存储结构
图论基础概念介绍
图的基本概念
由顶点（Vertex）和边（Edge）组成的数 据结构，表示对象及其之间的关系。
图的遍历
通过某种方式访问图中所有顶点的过程， 常见的遍历算法有深度优先遍历（DFS）和 广度优先遍历（BFS）。
有向图与无向图
根据边是否有方向，图可分为有向图和无 向图。
时间复杂度
平均时间复杂度和最坏时 间复杂度均为O(n)。
适用场景
适用于数据量较小或数据 无序的情况。
查找算法设计之二分查找法
算法思想
在有序数组中，取中间元素与目标元素比较，若相等则查找成功；若目标元素小于中间元素， 则在左半部分继续查找；若目标元素大于中间元素，则在右半部分继续查找。
时间复杂度
平均时间复杂度和最坏时间复杂度均为O(log n)。
连通图与连通分量
在无向图中，任意两个顶点之间都存在路 径，则称该图是连通图；否则，称该图的 极大连通子图为连通分量。
顶点的度
在无向图中，顶点的度是与该顶点相关联 的边的数目；在有向图中，顶点的度分为 入度和出度。
图的存储结构之邻接矩阵法
邻接矩阵表示法
用一个二维数组表示图中顶点之 间的关系，若顶点i与顶点j之间 存在一条边，则数组元素值为1

离散数学中的图的连通性与欧拉路径问题图论是离散数学中的一个重要分支，研究对象是图。

图是由一组顶点和连接这些顶点的边组成的数学结构。

在图论中，连通性和欧拉路径问题是两个基本概念，对于理解和解决图相关的问题具有重要意义。

一、连通性在图论中，连通性是指图中任意两个顶点之间存在一条路径。

如果一个图中任意两个顶点都是连通的，则称该图是连通图；如果一个图不是连通图，那么它可以被分解为多个连通的子图，这些子图称为连通分量。

连通性在实际应用中具有广泛的应用。

例如，在社交网络中，连通性可以用来判断两个人之间是否存在关系链；在计算机网络中，连通性可以用来判断网络中的主机之间是否可以进行通信。

二、欧拉路径问题欧拉路径问题是图论中的一个经典问题，它要求找出一条路径，经过图中每条边一次且仅一次。

如果存在这样的路径，则称图具有欧拉路径。

欧拉路径问题有两种情况：1. 欧拉回路：如果存在一条路径，从起点出发，经过图中每条边恰好一次后回到起点，则称该图具有欧拉回路。

2. 半欧拉路径：如果存在一条路径，从起点出发，经过图中每条边恰好一次后到达终点，但不回到起点，则称该图具有半欧拉路径。

欧拉路径问题的解决方法有欧拉定理和深度优先搜索算法。

欧拉定理指出，一个连通图具有欧拉回路的充分必要条件是每个顶点的度数都是偶数；一个连通图具有半欧拉路径的充分必要条件是除了起点和终点外，其它顶点的度数都是偶数。

深度优先搜索算法（DFS）是一种用来遍历图或树的算法，它可以用来解决欧拉路径问题。

DFS从起点开始遍历图，当遍历到某个顶点时，选择一个未访问过的邻接顶点进行继续遍历，直到无法继续遍历为止。

通过DFS算法，可以找到图中的欧拉路径。

三、总结离散数学中的图的连通性与欧拉路径问题是图论中的两个基本概念。

连通性用来描述图中顶点之间的连接情况，欧拉路径问题则是要找出一条路径，经过图中每条边一次且仅一次。

这两个概念在实际应用中具有广泛的应用，对于理解和解决图相关的问题具有重要意义。

Bellman-Ford算法
总结词
Bellman-Ford算法是一种用于查找带权图中单源最短路径的算法。
详细描述
Bellman-Ford算法的基本思想是从源节点开始，通过不断更新节点之间的距离，逐步找到从源节点到 其他节点的最短路径。该算法可以处理带有负权重的边，并且在图中存在负权重环的情况下也能正确 处理。
THANKS
感谢观看
Floyd-Warshall算法
总结词
Floyd-Warshall算法是一种用于查找所有节点对之间最短路 径的动态规划算法。
详细描述
Floyd-Warshall算法的基本思想是通过动态规划的方式，逐 步构建最短路径矩阵。该算法首先初始化一个距离矩阵，然 后通过一系列的转移操作，逐步更新距离矩阵，直到找到所 有节点对之间的最短路径。
欧拉回路
总结词
欧拉回路是指一个路径的起点和终点是同一点，且经过图中的每条边且仅经过 一次的路径，并且该路径闭合。
详细描述
欧拉回路是欧拉路径的一种特殊情况，它不仅满足欧拉路径的所有条件，而且 起点和终点是同一点，形成一个闭合的路径。在图论中，欧拉回路具有重要的 应用价值。
欧拉回路的判定
总结词
判断一个图是否存在欧拉回路是一个NP 难问题，目前没有已知的多项式时间复 杂度的算法。
连通度
总结词
连通度是描述图中任意两点之间可达性的度量，表示图中节点之间的连接紧密程度。
详细描述
在图论中，连通度是衡量图连通性的一个重要参数。对于一个无向图，连通度通常用K表示，表 示图中任意两点之间是否存在路径。对于有向图，连通度分为入度和出度，分别表示从一个节 点到另一个节点是否存在路径和从另一个节点到这个节点是否存在路径。

06
总结与展望
总结连通分量计算的重要性和应用场景
连通分量计算是图论中的基本问题，对于理解图的结构和性质至关重 要。
连通分量计算在社交网络分析、网页排名、图像分割等领域有着广泛 的应用。
连通分量计算可以帮助我们更好地理解数据的分布和关联，从而为实 际问题提供有效的解决方案。
未来，随着图数据的不断增加，连通分量计算的重要性和应用场景将 会更加广泛。
计算连通分量：使用 networkx库的
connected_compon ents函数
输出结果：将计算 结果打印或保存到 文件中
05
连通分量计算的应用
在社交网络分析中的应用
社交网络中的连通分量：表 示社交网络中相互连接的用 户群体
连通分量的应用：分析社交 网络的结构和特性，例如找 出核心用户群、检测社交网 络中的社区结构等
添加标题
顶点表：存储图中所有顶点的信息，如顶点编号 、顶点名称等
添加标题
边表：存储图中所有边的信息，如起始顶点、终 止顶点、边的权重等
添加标题
邻接表表示法的优点：易于实现图的基本操作， 如添加顶点、删除顶点、添加边、删除边等
添加标题
邻接表表示法的缺点：占用空间较大，不适合表 示稀疏图
添加标题
Python实现图的连通分量计算时，可以使用邻接 表表示法来存储图结构，方便地进行图的遍历和 操作。
在交通运输网络中的应用
计算图的连通分量可以帮助我们理解交通运输网络的结构
通过计算连通分量，可以找出交通网络的关键节点和关键路径
在交通网络优化中，连通分量的计算可以帮助我们找到最优的交通路 线
连通分量的计算还可以帮助我们预测交通网络的拥堵情况，并采取相 应的措施进行缓解

// 对v的尚未访问的邻接顶点w递归调用DFS
} // DFS
4
对于无向图，这个算法可以遍历到v顶点所在的连通 分量中的所有顶点，而与v顶点不在一个连通分量中的 所有顶点遍历不到；
对于有向图可以遍历到起始顶点v能够到达的所有顶 点。
若希望遍历到图中的所有顶点，就需要在上述深度优 先遍历算法的基础上，增加对每个顶点访问状态的检 测。
14
7.4 图的连通性
1.求无向图的生成树（或生成森林）
生成树：是一个极小连通子图，它含有图中全部顶点， 但只有n-1条边。
生成森林：由若干棵生成树组成，含全部顶点，但构 成这些树的边是最少的。 （对有向或无向图均 适用）
思考1：若对连通图进行遍历，得到的是什么？ 一个极小连通子图，即图的生成树！
2、非连通图的深度优先搜索遍历
步骤：
• 访问起始点 v及图中所有和v有路径相通的顶点。
• 如果图中尚有顶点未被访问，则以该顶点为起始点， 进行深度优先搜索遍历。重复上述过程，直至所有
顶点都已被访问。
5
0
1
例2:
a
b
6
g
2
3
4
5
c
d
e
f
7
8
h
k
012345678
访问标志: FT FT F TF TF TF TF FT FT T
• 如果使用邻接矩阵，则BFS对于每一个被访问到的顶点， 都要循环检测矩阵中的整整一行（ n 个元素），总的时 间代价为O(n2)。
DFS与BFS之比较： （设图中有 n 个顶点，e 条边）
• 空间复杂度相同，都是O(n)(借用堆栈或队列装n个 顶点）；
• 时间复杂度只与存储结构（邻接矩阵或邻接表）有 关，而与搜索路径无关。

第07章_图c ppt课件
7.4 图的连通性
连通图：在路无径向, 则图称中顶, 若点从v1与顶v点2是v1连到通顶的点。v2有如
果图中任意一对顶点都是连通的, 则 称此图是连通图。 非连通图的极大连通子图叫做连通 分量。
强连通图：在有向图中, 若对于每一对顶点vi和vj,
都存在一条从vi到vj和从vj到vi的路径, 则称此图是强连通图。
18
7
c
16 e 8
3
g
d
27
21
f
所得生成树权值和
= 14+8+3+5+16+21 = 67
一般情况下所添加的顶点应满足下列 条件: 在生成树的构造过程中，图中 n 个 顶点分属两个集合：已落在生成树上的 顶点集 U 和尚未落在生成树上的顶点集 V-U ，则应在所有连通U中顶点和V-U中 顶点的边中选取权值最小的边。
//新顶点并入U后重新选择最小边
if (G.arc[k][j].adj<closedge[j].lowcost) closedge[j]={G.vexs[k], G.arcs[k][j].adj};
}//for i }//MiniSpanTree
取图中任意一个顶点 v 作为生成树的根， 之后往生成树上添加新的顶点 w。在添加 的顶点 w 和已经在生成树上的顶点v 之间 必定存在一条边，并且该边的权值在所有 连通顶点 v 和 w 之间的边中取值最小。之 后继续往生成树上添加顶点，直至生成树 上含有 n-1 个顶点为止。
例如:
a 19
b5
14 12
// 此时closedge[k].lowcost = // MIN{closedge[vi].lowcost | closedge[vi].lowcost>0, vi ∈V-U.

第18页/共26页
7.2.3 图的连通度
定义7-2.4 设无向图G =<V,E>是连通图,若有结点集V1V,使图 G中删除了 V1的所有结点后,所得到的子图是不连通图,而删除了V1的任何真子集后,所
得到的子图仍是连通图,则称V1是G的一个点割集(cut-set of nodes) 。
k(G)=min{|V1|| 是G的点割集} 称为图G的点连通度(nodeconnectivity) 。
现对G的每一条边e＝(u1,u2)，若u1,u2都在 V1上 ，则存 在两条 路P1与P2分别 连接u与 u1和u与u2， 且P1、 P2的长 度均为 偶数， 闭路P1∪P2∪ {e}的 长度为 奇数， 则不难 看出G中 有一条 长为奇 数的圈 ，矛盾 。同样 u1和u2不能同 时含在 V2中。 故e的 两个端 点分别 在V1和 V2中。 因此G是二分 图。
G 定理7.2.1 非平凡图 是二分图当且仅当 中不含长为奇数的回路。
G
证明 必要性是明显的。
充分性：不妨设G中每一对顶点之间有路连接（否则
只需考虑G的每个每一对顶点之间有路连接的极大子
图）。任取G的一个顶点u，由G的假设，对G的每个顶
点v，在G中存在u-v路。现利用u对G的顶点进行分类。
设
第24页/共26页
3 v1e1v2e5v5e6v4e4v2e5v5e7v6
…………
初级通路 简单通路 复杂通路
7.2.1 路
例1、(2)
图(2)中过 v2 的回路 (从 v2 到 v2 )有：
第7页/共26页
1 v2e4v4e3v3e2v2
长度3
2 v2e5v5e6v4e3v3e2v2
长度4
3 v2e4v4e3v3e2v2e5v5e6v4e3v3e2v2 长度7

图论_连通_连通分量 强连通图 : 强连通分量就是本⾝ 有向图 ---> ⾮强连通图 : 多个强连通分量图---> 连通图 : 连通分量就是本⾝ ⽆向图 ---> ⾮连通图 : 多个连通分量路径 : 顾名思义.路径长度 : 路径上边的数量.路径 : 顾名思义.路径长度 : 路径上边的数量.连通 : ⽆向图顶点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。

在离散数学中，图是研究的重要对象之一。

图由节点和连边组成，可以用来描述许多实际问题，比如社交网络、交通网络等等。

在图的研究中，连通分量和最小生成树是两个重要的概念。

首先，我们来介绍连通分量。

在一个图中，如果任意两个节点之间存在路径，那么这个图被称为是连通的。

如果一个连通图的任意两个节点之间不存在路径，并且如果将其中的任何一个节点移除后，剩下的子图也不再连通，那么这个图的连通部分被称为是连通分量。

连通分量可以将一个复杂的图分割为若干个互不相交的子图，每个子图都是一个连通图。

连通分量在许多应用中有着重要的意义。

例如，在社交网络中，每个人可以看做是一个节点，而他们之间的关系可以用边来表示。

如果某个社交圈的人之间相互认识，那么他们就属于同一个连通分量。

通过分析连通分量，可以了解社交网络中的人际关系、信息传递等情况。

另一个重要的概念是最小生成树。

最小生成树是指一个连通图的最小权重的生成树，其中每个节点都连接在一起，并且总权重达到最小。

生成树是保留了原图中部分边的子图，该子图包含了原图的所有节点，但是其中的边数比原图少一。

最小生成树则是在所有生成树中权重最小的一种。

最小生成树可以用来优化资源分配、路径规划等问题。

最小生成树的算法有很多种，其中一种常用的算法是Prim算法。

Prim算法从一个起始节点开始，逐步扩展生成树的边。

每次选择与已经生成的树相连的边中权重最小的边。

然后，继续选择与生成树相连的边中权重最小的边，直到生成树包含了所有的节点。

另一个常用的算法是Kruskal算法。

Kruskal算法从边的权重最小的边开始，依次将未加入生成树中且不会形成环的边加入生成树中。

然后，继续选择权重次小的边，直到生成树包含了所有的节点。

最小生成树可以用来解决一些实际问题。

例如，在一个城市的交通网络中，每个路口可以看成是一个节点，而道路可以看成是边。

通过最小生成树算法，可以找到将所有路口连接起来的最短路径，从而优化城市交通的规划。

占用空间较少。 邻接矩阵的空间？ 邻接链表的空间？
很多有价值的应用场景中，都是大规模的稀疏图。
16 ／50
2017年春季 通信网络理论基础
n vs m
假定图G(V, E)具有n个顶点，m条边。【一般我们都假定是 没有平行边和自环的所谓“简单图”】
如果G是无向图，m和n什么关系？ 如果G是有向图呢？
Variations(2/3)
How about this: there are odd number of vertices whose degree is odd?
IMPOSSIBLE
• Theorem: 顶点度数之和必 为偶数；且为边数的2倍。 • Corollary: 奇数度顶点的数 目必为偶数。
3 ／50
2017年春季 通信网络理论基础
关于边 基本术语 (关于一顶点)
边
• 也称为弧(arc)， 链路(link)。
• 边与两个顶点有 关(head和tail)。
顶点
• 也称为节点/ 结点(node)。
自环(loop点)间关系
• 如果一条边的头 和尾都是同一个顶 点，则称为自环。
点边关系
关联
与顶点u直接相连 的边与u关联；反 之，u也与这些边 关联(Incident)。
循环开始时，从边界点集合中选择一个顶点进行探索。 循环结束前，将新扩展的边界点纳入集合。
注意：BFS和DFS选择边界点的策略不同。
维护边界点集合的方式如何影响选择策略？
BFS用队列(FIFO)；DFS用堆栈(LIFO)。
23 ／50
2017年春季 通信网络理论基础
图搜索伪码
BFS( G, s )
// B=所有边界点构成的集合 B.EnQueue(s); WHILE B非空

PowerPoint Template_Sub
1 图的基础知识 2 路径、回路及连通性 3 欧拉图与哈密顿图 4 图的矩阵表示
《离散数学》第18讲 路径、回路及连通性 Page 112 to 117
拟路径及长度
定义：图G的顶点v1到顶点vl的拟路径是指以下顶点与边的序列： v1 , e1, v2, e2, v3, …, vl-1, el-1, vl v1 ,v2 ,v3 ,… ,vl-1 ,vl为G的顶点，e1 ,e2 ,… ,el-1 为G的边 ei( i= 1,2, … ,l-1 )以vi及vi+1为端点 对有向图G，ei以vi为起点，以vi+1为终点
证明：若G为不连通图或单一孤立结点的图，那么据定义知:
χ(G) = λ(G) = 0≤δ(G) 。 若G为完全图Kn，那么χ(G) = λ(G) = δ(G) = n – 1 。 对其它情况：先证λ(G) ≤δ(G)。 由于度数最小的那个结点上关联的所有边被删除后，G显然不 再连通，因而λ(G)至多是δ(G)，即λ(G) ≤δ(G)。
证明：充分性是显然的。 必要性：设顶点v是简单连通图G的割点，如果不存在两个 顶点v1，v2，使v1到v2的通路都经过顶点v，那么对任意两 个顶点v1，v2，都有一条通路不经过顶点v，因而删除顶点v 不能使G不连通，与v是简单连通图G的割点矛盾。故G中必 存在两个顶点v1，v2，使v1到v2的通路都经过顶点v 。
第18讲 路径、回路及连通性
-20-
边连通度
定义：λ(G)称为图G的边连通度，定义如下：
0
当G非连通图时
(G) 0
当G为一孤立结点时
min{ S : S为G的割集} 否则
v1
v4 v2
v5 v7

第七章
12
权、网、子图
在图的边或弧中给出相关的数，称
15 A 9
为权。 权可以代表一个顶点到另一个顶
11
点的距离、耗费等。带权的图通常称作 B 7 21
E
网。
3 C2F
假设有两个图G=(V,{VR}) 和 图 G=(V,{VR}), 如果 VV且 VRVR, 则称 G 为 G 的子图。
B B
C
A E
第七章
11
完全图、稀疏图、稠密图
假设图中有 n 个顶点，e 条边，则: ❖ 含有 n(n-1)/2 条边的无向图称作完全图; （无向图中边的取 值范围为0～n(n-1)／2） ❖ 含有 n(n-1) 条弧的有向图称作 有向完全图; （有向图中边 的取值范围为0～n(n-1)）
❖ 若边或弧的个数 e<n*logn，则称作稀疏图，否则称作稠密 图。（当n很大时,n2>> n*log n）
❖ 生成树是对连通图而言的； ❖ 是连通图的极小连通子图； ❖ 包含图中的所有顶点； ❖ 有且仅有n-1条边。
B A
F
C D
E
第七章
19
7.2 图的存储结构
一、数组表示法(邻接矩阵) 二、邻接表存储表示 三、有向图的十字链表存储表示 四、无向图的邻接多重表存储表示
第七章
20
一、数组表示法(邻接矩阵)
由顶点集和边集构成的图称作无向图（Undigraph）。
例如: G2=(V2, {R2})
B
C
V2={A, B, C, D, E, F} R2={(A,B), (A,E),
(B,E), (B,F),
(C,D), (C,F) ,
A
D