数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究图的割集和割顶
是否能够从一个顶点遍历到图中的另一个顶点取决于图的连接方式。连通性是图论中的一个基本概念。连通性定义了图是连通的还是不连通的。
连通性
如果每对顶点之间都存在一条路径，则称该图是连通的。从每个顶点到任何其他顶点，都应该存在一些路径可以遍历。这称为图的连通性。具有多个不连通顶点和边的图称为不连通图。
割顶
设 'G' 为一个连通图。如果 'G-V'（从 'G' 中删除 'V'）导致一个不连通图，则顶点 V ∈ G 称为 'G' 的割顶。从图中移除一个割顶会将其分成两个或多个图。
注意 - 删除割顶可能会使图变得不连通。
一个连通图 'G' 最多可以有 (n–2) 个割顶。
示例
在下图中，顶点 'e' 和 'c' 是割顶。
通过移除 'e' 或 'c'，该图将变成一个不连通图。
如果没有 'g'，则顶点 'c' 和顶点 'h' 以及许多其他顶点之间没有路径。因此，它是一个不连通图，其割顶为 'e'。类似地，'c' 也是上图的割顶。
割边（桥）
设 'G' 为一个连通图。如果 'G-e' 导致一个不连通图，则边 'e' ∈ G 称为割边。
如果从图中移除一条边会导致两个或多个图，则该边称为割边。
示例
在下图中，割边为 [(c, e)]
从图中移除边 (c, e) 后，它将变成一个不连通图。
在上图中，移除边 (c, e) 将图分成两部分，这实际上是一个不连通图。因此，边 (c, e) 是该图的割边。
注意 - 设 'G' 为一个具有 'n' 个顶点的连通图，则
边 e ∈ G 是割边当且仅当边 'e' 不属于 G 中的任何环。
可能的割边最大数量为 'n-1'。
只要存在割边，也一定存在割顶，因为割边的至少一个顶点是割顶。
如果存在割顶，则割边可能存在也可能不存在。
图的割集
设 'G'= (V, E) 为一个连通图。如果从 G 中删除 E' 中的所有边使 G 不连通，则 E 的子集 E' 称为 G 的割集。
如果从图中删除一定数量的边使其不连通，则这些被删除的边称为该图的割集。
示例
看一下下图。它的割集是 E1 = {e1, e3, e5, e8}。
从图中移除割集 E1 后，它将显示如下 -
同样，还有其他可以使图不连通的割集 -
- E3 = {e9} - 图中最小的割集。
- E4 = {e3, e4, e5}
35K+ 浏览量
