5.2 通路，回路和图的连通性

我们类比上一小节中提到的简单图的概念引入简单通路和简单回路。

简单来说就是通路中所以边互不相同。

有边重复出现的通路称为复杂通路，有边重复出现的回路称为复杂回路。

初级通路（回路）在简单通路（回路）的基础上加了一条结点互不相同的限制。
注意：
初级回路中所说的结点互不相同是不包括起始点和终点的。毕竟人家是回路嘛。

就是说都存在不故意绕弯路的通路（回路）

下边我们来说图的连通性：
连通图顾名思义：

易得：
连通是自反，对称，传递的。所以其是等价关系。

例题：

有以下定理：

因为对于每一个连通分支都是一个n阶图。而对于每一个n阶图来说，其边数都是小于等于n-1。

简单来说就是找分割图的方法。每一个点割集中都没有冗余的元素。
当一个点就可以将其分割时我们称其为割点。
对于由多个点组成的点割集来说，只有将这些点同时去除才能将图分割。

eg：

在这个图里，{$v_1$v1​,$v_6$v6​}不是点割集。因为$v_6$v6​已经是割点了。
{$e_3$e3​,$e_4$e4​,$e_5$e5​}也不是边割集，因为{$e_3$e3​,$e_4$e4​}已经是边割集了。

若$D$D是一个有向图

• 略去$D$D中各边方向后所得无向图是连通图，则称$D$D是弱连通图，简称连通图。
• 若$D$D中任意两顶点至少一个可达另一个，则称$D$D是单向连通图。
• 若$D$D中任何一对顶点都是相互可达的，则称$D$D是强连通图。

练习1：

练习2：


练习3：