P5776 题解 & 图的耳分解

Purslane · 2024-06-26 14:32:29 · 题解

Solution

本题是无向图最小权耳分解板子题。略微记录一些耳分解相关内容。

定义无向图 G=(V,E) 对其导出子图 G'=(V',E') 存在耳，当前仅当可以找到一组顶点 (x_1,x_2,\dots,x_{t-1},x_t)，其中 x_1,x_t \in V，\{x_2,x_3,\dots,x_{t-1}\} = V / V'，且 \forall 1 \le i \le t-1，x_i 和 x_{i+1} 有边，且除了 x_1 和 x_t 外这组顶点两两不同。这样的一组顶点称为 G 对 G' 的耳，如果 x_1 \neq x_t 称为 G 对 G' 的开耳。

直观地看，就像 G' 外面挂了一个“耳朵”形成了 G。定义并不关注 V / V' 和 V' 之间的连边情况，也就是完全图任何点集是他的一个耳。

对于有向图，也容易定义他的“耳”，只要确定边的方向一定即可。

定义无向图的耳分解为：

取无向图 G 的若干个导出子图 G_0=(V_0,E_0)，G_1 = (V_1,E_1)，\dots，G_t=(V_t,E_t)。

其中 G_t=G，V_0 \subset V_1 \subset \cdots \subset V_t；G_0 存在哈密顿回路（就是能形成一个环），且 \forall 1 \le i \le t，G_i 对 G_{i-1} 的耳存在。

这样的耳构成的集合称为无向图的耳分解。

特别的，如果每个耳都是开耳，称为无向图的开耳分解。

同样容易定义有向图的耳分解。

无向图的耳分解实际上刻画了图的双连通性。