切边、切顶点定义说明
Cut edge, cut vertex definition clarification
正在寻找一个简单问题的一些定义说明。考虑图表：
A---B 其中 A 和 B 是顶点，它们之间只有一条边。它们之间的边是否会被视为 "cut edge" 因为它的删除会断开图形？或者 "cut edge" 是否需要增加 连接的 组件的数量，而不仅仅是组件？
是的，它是切边。让我们更深入地了解一下定义。
切边的定义：
In graph theory, a bridge, isthmus, cut-edge, or cut arc is an edge of a graph whose deletion increases its number of connected components.
请参阅 Wikipedia 与切边相关的文章。
连通分量的定义：
In graph theory, a connected component (or just component) of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the supergraph.
请参阅 Wikipedia 与连接组件相关的文章。
另一种定义连通分量的方法涉及在顶点上定义的等价关系的等价类图的。在无向图中，如果存在从 u 到 v 的路径，则可以从顶点 u 到达顶点 v。在此定义中， 单个顶点被视为长度为零的路径，同一个顶点在一条路径中可能出现不止一次。可达性是一个等价关系，因为：
- 它是自反的：从任何顶点到它自己都有一条长度为零的平凡路径。
- 是对称的：如果有一条从u到v的路径，相同的边组成一条从v到u的路径。
- 是传递的：如果有一条从u到v的路径和一条从v到w的路径，这两条路径可以拼接在一起形成一条从u到v的路径w.
连通分量就是由这个关系的等价类形成的导出子图。
结论：
没有任何连接的单个顶点是基于自反性的连接组件。您的图在去除边之前有 1 个连通分量，在没有边的情况下有 2 个连通分量，因此您的边是切边。
正在寻找一个简单问题的一些定义说明。考虑图表： A---B 其中 A 和 B 是顶点，它们之间只有一条边。它们之间的边是否会被视为 "cut edge" 因为它的删除会断开图形？或者 "cut edge" 是否需要增加 连接的 组件的数量，而不仅仅是组件？
是的，它是切边。让我们更深入地了解一下定义。
切边的定义：
In graph theory, a bridge, isthmus, cut-edge, or cut arc is an edge of a graph whose deletion increases its number of connected components.
请参阅 Wikipedia 与切边相关的文章。
连通分量的定义：
In graph theory, a connected component (or just component) of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the supergraph.
请参阅 Wikipedia 与连接组件相关的文章。
另一种定义连通分量的方法涉及在顶点上定义的等价关系的等价类图的。在无向图中，如果存在从 u 到 v 的路径，则可以从顶点 u 到达顶点 v。在此定义中， 单个顶点被视为长度为零的路径，同一个顶点在一条路径中可能出现不止一次。可达性是一个等价关系，因为：
- 它是自反的：从任何顶点到它自己都有一条长度为零的平凡路径。
- 是对称的：如果有一条从u到v的路径，相同的边组成一条从v到u的路径。
- 是传递的：如果有一条从u到v的路径和一条从v到w的路径，这两条路径可以拼接在一起形成一条从u到v的路径w.
连通分量就是由这个关系的等价类形成的导出子图。
结论： 没有任何连接的单个顶点是基于自反性的连接组件。您的图在去除边之前有 1 个连通分量，在没有边的情况下有 2 个连通分量，因此您的边是切边。