小编点评

这段文字似乎是由两部分组成，第一部分是关于无向图的耳分解概念及其性质，第二部分是关于双极定向的概念及其性质。下面是对这两部分的解释和总结： ### 无向图的耳分解 - **耳与耳的分解**：在一个无向图 \(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, u_k \notin V_1\)，则称 \(L\) 是 \(G\) 关于 \(G_1\) 的耳。特别地，当 \(L\) 是一条简单路径时，它被称为 \(G\) 的开耳。 - **性质**：如果一个图 \(G\) 存在耳分解，则意味着 \(G\) 是边双连通的。 ### 双极定向 - **双极定向的定义**：给定一个无向图 \(G = (V,E)\) 和两个不同的节点 \(s,t\)，则以下四个命题等价： - 在添加 \((s,t)\) 之后 \(G\) 点双联通。 - \(G\) 的圆方树（认为圆方树是一个特殊的图，其中每个节点都有一个入度和出度都为1的相邻节点）中所有方点构成一条链，\(s \\to t\) 是圆方树的一条直径。 - 存在对 \(G\) 的边进行定向的方法，得到一个有向无环图，且 \(s\) 入度为零，\(t\) 出度为零，其余点出入度都不为零。 - 存在一个点的排列 \(p_1,p_2, \\cdots \\cdots ,p_k\\)，使得 \(p_1 = s,p_k = t\)，且任意前缀和后缀的导出子图都是联通的。 综上所述，这段内容主要介绍了图论中的两个重要概念：耳分解和双极定向。耳分解描述了一个图中耳（作为子图的环或简单链）如何与整个图相关联的性质，而双极定向则提供了一种在图中添加特定节点并确保新图的性质的方法。这两个概念在图论的算法设计和理解复杂网络结构中有着广泛的应用。

正文

\(\text{1 }\) 耳和耳分解

\(\text{1.1 }\) 耳和耳分解

对于一个无向图 \(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\) 边双连通。

\(\text{1.2 }\) 双极定向

给定无向图 \(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\)，且任意前缀和后缀的导出子图都是联通的。