图论术语
块(Block),图论中重要概念,是某一图中不含割点(cut-vertex)的极大连通子图。每一个图都可以被分割为一个或多个块。
定义
中文定义
块是一个图中没有割点的极大连通子图
英文定义
A block of a graph G is maximal connected subgraph of G that has no cut-vertex.
If G itself is connected and has no cut-vertex, then G is a block.
性质
1、同一个图中的两个块最多只能共享一个顶点,并且这个顶点必定是一个割点(cut-vertex)。
2、如果一个块包含多于两个顶点,那么这个块必定是2-连通的(2-connected)。
3、图G的块-割点图(The block-cutpoint graph)是一个二部图,一部分由割点组成,另一部分由块组成,它们之间存在边当且仅当割点是块的一部分。如果图G是连通的,那么它的块-割点图是一棵
图的块划分方法
输入:一个连通图G
输出:图G的块划分
主要思想:建立图G的DFS树T,如果识别出了一个块就将其从T上删除;保持一个顶点为ACTIVE状态
初始化:选择一个根节点x∈V(G);将x设为ACTIVE;设置T={x}
步骤:将当前状态为ACTIVE的点记作v
(1)如果v存在一个没有访问过的边vw:
1.1 如果w∉V(T),那就将边vw加入树T,将vw标记为已访问,将w设为ACTIVE;
1.2 如果w∈V(T),那说明w是v祖先,将vw标记为已访问。
(2)如果v的所有边都已经访问过了:
2.1 如果v≠x,并且选择v的父亲节点w,将w设为ACTIVE。在当前情况下,如果以v为根节点的T的子树T‘中不存在一条边连接到w的任意先祖,那么V(T‘)∪{w}就是一个块,将其记录并将T‘删除;
2.2 如果v=x,那么所有点都已经访问过了,算法终止。
参考资料
最新修订时间:2021-12-02 11:15
目录
概述
定义
性质
参考资料