耳和耳分解、双极定向

对于一个无向图\(G = (V,E)\)，有一个子图\(G_1 = (V_1,E_1)\)。若有一条环或者简单链\(L:u_1 \to u_2 \to \cdots \cdots \to u_k\)，满足条件\(u_1,v_k \in V_1\)并且\(u_2,\cdots \cdots,u_k \notin V_1\)，则称之为\(L\)是\(G\)关于\(G_1\)的耳，特别的当\(L\)是一条简单路径是\(L\)是\(G\)关于\(G_1\)的开耳。

对于一个无向图\(G\)，若联通图\((G_0,G_1, \cdots \cdots ,G_k)\)满足：

1. \(G_0\)是一个简单环，\(G_k = G\)。

2. \(G_{i - 1}\)是\(G_i\)的子图。

3. 设\(G_i = {V_i,E_i}\)，则\(E_i\)\(E_{i - 1}\)组成\(G_{i - 1}\)的一个耳（开耳）。

则称\((G_0,G_1, \cdots \cdots ,G_k)\)是\(G\)的一个耳（开耳）分解。此处还有一个性质，若一个图\(G\)存在耳分解，当且仅当\(G\)边双连通。

给定无向图\(G = (V,E)\)和两个不同的节点\(s,t\)，则一下这四个命题等价：

1. 在添加\((s,t)\)之后\(G\)点双联通。

2. \(G\)的圆方树中所有方点构成一条链，\(s \to t\)是圆方树的一条直径。

3. 存在一种对\(G\)的边进行定向的方法，得到一个有向无环图，且\(s\)入度为零，\(t\)出度为零，其余点出入度都不为零。

4. 存在一个点的排列\(p_1,p_2, \cdots \cdots ,p_k\)，使得\(p_1 = s,p_k = t\)，且任意前缀和后缀的导出子图都是联通的。