在本节中，我们将了解连通性。

连通性是图论的基本概念之一。 我们从路径的正式定义开始。

路径是一系列边，从图形的顶点开始并沿着

图形的边移动，始终连接相邻的顶点对。

根据具体情况，

路径长度可以是路径上的边数，也可以是路径上边的权重之和。

例如在此图中，我们有一条从1到8的路径，长度为4。

相同的路径，但是一个有权值的图，从1到8的路径长度为20。

这是同一图表中从1到8的另一条路径。 在两个顶点之间有多条路径，

我们有兴趣找出具有特定属性的路径。

例如找到最短路径。

图G中从u到v的测地距离或简单距离是G中从u到v的最短路径的长度。

我们不能总是找出图的每两个节点之间的路径。

考虑这个图， 从2到9没有路径。

连通性基本思想是遍历边来实现图顶点之间的可达性。

这可以正式定义并分为五种类型：没有重复的路径，

没有边可以重复的小道，

走在没有限制的地方，

圈是一条封闭的小径，和环是一条封闭的道路。

如果它包含任何循环，我们称它为循环图。 否则我们称之为非循环图。

无向图是每对顶点之间有一条路径。

如果存在A到B以及从B到A的路径，则有向图是强连通，

每当A和B是图的顶点时。 如果图中的每两个顶点之间无直接的路径，

则有向图是弱连通。

哪个图有更强的连通，G1还是G2？

对，G1的联系更紧密。

强连通图可以弱连接，反之不正确。 你知道为什么吗？

这是一个没有连接的图的示例。 如何使它连接？

通过添加5到9之间的边，

使图连通。元素，节点或边的最小数量，

需要删除才能断开连接，图中的其余节点彼此相同，

是研究网络弹性能力的重要手段。

在图中连接的最大子图称为连接组件。注意我们无法将原始图形中的顶点和边

添加到组件中，保持其连通性，因为它是最大子图。

那么很明显，连通图只有一个组件。

因此，让我们看看之前的一个图，看看它有多少组件。

它有两个连接的组件。 图是连通吗？

在该图中，由蓝线分隔的部分不是连通分量。 你知道为什么吗？

如果图是环，则删除环中的边不会影响图的连通性。

因此连通子图包含所有顶点和没有环的最少边数。

寻找循环子图, 追溯到1735年，

瑞士数学家欧拉的柯尼斯堡桥问题。

柯尼斯堡七桥问题是一个古老的难题,

小岛与河的两岸有七条桥连接。在所有桥都只能走一遍的前提下，

如何才能把这个地方所有的桥都走遍？

欧拉意识到的是，地图上的大部分信息对问题的答案没有影响。

通过将每个岸边和岛屿视为一个顶点，并将每个桥作为连接它们的边，

欧拉能够使用右侧可以看到的图进行建模。

欧拉认为没有这样的道路存在。 这个证据只涉及到桥梁的物理排列，

但基本上他证明了图论中的第一个定理。

当且仅当G的每个顶点具有偶数度时，

称图G具有欧拉环。

连通图G具有欧拉轨迹，从节点a到某个其他节点b当且仅当

图G是连通的，且a不等于b，且是两个奇数度的节点。

其中一个重要的图是树。

树的重要性在各个领域的应用是显而易见的。

特别是理论计算机科学和分子进化，

树是没有任何循环的连通图，

或者等价树是连接的非循环图。

还记得非循环意义是什么？

没有循环的图被认为是非循环的或者也可以称为森林。

从定义中可以看出，树必须是一个简单的图，

并且连接每对顶点具有唯一简单路径。

还有其它方法可用于定义树。

非循环图的任何连通子图都是树。 如果在两个顶点之间添加边，

会产生循环并且删除任何边会使图不连通，则图是树。

我们可以列出树的更多属性。

顶点数量大于边数，或者是具有至少两个顶点的树

至少有两个度是1的顶点。

有时我们会得到一个图，但您只需要一种方法来连接节点。

例如具有冗余连接的网络。 在传输数据时，不关心冗余

只需要一种方法将数据发送到目的地。

所以，如果你正在研究路由选择，

你基本上想要将图缩减为树。 树告诉我们如何发送数据。

给定图G，连接G的所有顶点并且是树，

图G的子图称为G的生成树。

图的生成树包含保持图连接的最小边数。

用于构造生成树的算法在

两个方面是非确定性的：顶点u的选择是任意的，

添加到树上的边的选择是任意的。

因此，我们可以为每个图提供多个生成树。

请考虑这个图。 你能找到其中一棵生成树吗？

这是图的一个生成树。

这是同一图的另一个生成树。

Prime的算法和Kruskal的算法通常用于构建生成树。

这些贪婪算法在多项式时间运行。