耳和耳分解、雙極定向

對于一個無向圖\(G = (V,E)\)，有一個子圖\(G_1 = (V_1,E_1)\)。若有一條環(huá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\)的耳，特別的當\(L\)是一條簡單路徑是\(L\)是\(G\)關(guān)于\(G_1\)的開耳。

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

1. \(G_0\)是一個簡單環(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_0,G_1, \cdots \cdots ,G_k)\)是\(G\)的一個耳（開耳）分解。此處還有一個性質(zhì)，若一個圖\(G\)存在耳分解，當且僅當\(G\)邊雙連通。

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

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

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

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

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

• 《魔獸世界》懷舊服 從入門到精通指南
• 萬道仙訣游戲技巧與攻略大全最新指南
• 火柴人小游戲最新版攻略全講解
• 捕獵魂獸游戲攻略技巧大全最新：斗羅大陸全面指南
• 養(yǎng)蠱傳奇游戲攻略大全