耳和耳分解、雙極定向

對(duì)于一個(gè)無(wú)向圖\(G = (V,E)\)，有一個(gè)子圖\(G_1 = (V_1,E_1)\)。若有一條環(huán)或者簡(jiǎn)單鏈\(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\)關(guān)于\(G_1\)的耳，特別的當(dāng)\(L\)是一條簡(jiǎn)單路徑是\(L\)是\(G\)關(guān)于\(G_1\)的開(kāi)耳。

對(duì)于一個(gè)無(wú)向圖\(G\)，若聯(lián)通圖\((G_0,G_1, \cdots \cdots ,G_k)\)滿足：

1. \(G_0\)是一個(gè)簡(jiǎn)單環(huán)，\(G_k = G\)。

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

3. 設(shè)\(G_i = {V_i,E_i}\)，則\(E_i\)\(E_{i - 1}\)組成\(G_{i - 1}\)的一個(gè)耳（開(kāi)耳）。

則稱\((G_0,G_1, \cdots \cdots ,G_k)\)是\(G\)的一個(gè)耳（開(kāi)耳）分解。此處還有一個(gè)性質(zhì)，若一個(gè)圖\(G\)存在耳分解，當(dāng)且僅當(dāng)\(G\)邊雙連通。

給定無(wú)向圖\(G = (V,E)\)和兩個(gè)不同的節(jié)點(diǎn)\(s,t\)，則一下這四個(gè)命題等價(jià)：

1. 在添加\((s,t)\)之后\(G\)點(diǎn)雙聯(lián)通。

2. \(G\)的圓方樹(shù)中所有方點(diǎn)構(gòu)成一條鏈，\(s \to t\)是圓方樹(shù)的一條直徑。

3. 存在一種對(duì)\(G\)的邊進(jìn)行定向的方法，得到一個(gè)有向無(wú)環(huán)圖，且\(s\)入度為零，\(t\)出度為零，其余點(diǎn)出入度都不為零。

4. 存在一個(gè)點(diǎn)的排列\(zhòng)(p_1,p_2, \cdots \cdots ,p_k\)，使得\(p_1 = s,p_k = t\)，且任意前綴和后綴的導(dǎo)出子圖都是聯(lián)通的。

• 《夢(mèng)幻新誅仙》裝備獲取方式大全最新（輕松掌握各種裝備獲取技巧，為你的角色提升實(shí)力）
• 《萬(wàn)靈啟源SSR抽獎(jiǎng)概率揭曉》SSR抽獎(jiǎng)概率究竟是多少呢？（以游戲?yàn)橹�，讓你了解抽�?jiǎng)背后的真相）
• 《龍之谷手游》新手升級(jí)攻略技巧大全最新
• 《最囧大腦》32關(guān)通關(guān)攻略技巧指南（打破困境，激活大腦，輕松通關(guān)）
• 王者榮耀哪個(gè)英雄克制司馬懿？英雄克制攻略技巧！