耳和耳分解、雙極定向

對(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\)，滿(mǎn)足條件\(u_1,v_k \in V_1\)并且\(u_2,\cdots \cdots,u_k \notin V_1\)，則稱(chēng)之為\(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)\)滿(mǎn)足：

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)耳）。

則稱(chēng)\((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)通的。

• 《暗喻幻想：ReFantazio》尤法社群等級(jí)提升作用介紹
• 【長(zhǎng)城守望】新服開(kāi)啟！沖榜就送非遺城磚
• 《寶可夢(mèng)大集結(jié)》路卡利歐技能圖鑒
• 《塞爾達(dá)傳說(shuō) 智慧的再現(xiàn)》螺旋甜味冰沙怎么制作
• 《仙劍世界》黑蜘蛛森林寶箱開(kāi)啟方法