首页 > 教程 > 耳和耳分解、双极定向

耳和耳分解、双极定向

时间:2024-06-10 | 来源: | 阅读:133

话题:

\(\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\),满足条件

对于一个无向图\(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\),且任意前缀和后缀的导出子图都是联通的。

推荐

最新好玩手游

更多

手游风云榜

更多

资讯阅读

更多


湘ICP备2022002427号-10 湘公网安备:43070202000427号
© 2013~2024 haote.com 好特网