割边

更新时间：2023-12-26 10:24

假设有连通图G，e是其中一条边，如果G-e是不连通的，则边e是图G的一条割边。此情形下，G-e必包含两个连通分支。

定义

假设有连通图G，e是其中一条边，如果G-e是不连通的，则边e是图G的一条割边。此情形下，G-e必包含两个连通分支。

我们可以用下边的例子说明：

对于该连通图，割边有V3V4，V4V5两个；其他边均不是割边。

连通图

若对图G中每对不同的顶点都存在某条过这两个点的同类，则称图G是连通的。

如下边的例子：

图1，图2都是连通的；图3和图4都是不连通的。

完全图

若图G的任意两个点都是邻接的（及存在一条边将这两个点连接起来），则称G是完全图。

如下图3中：

图1不连通；图2，图3是连通的，但不完全；图4是完全图。