耳分解

耳分解

耳分解是一種對圖的分解方法。圖論的定義就是一條極大的路徑,路徑內部(不包括端點)的度均為2。耳分解就是將圖分解為一個環和若干個耳。

基本介紹

  • 中文名:耳分解 
  • 外文名:Ear Decomposition
  • 所屬學科圖論
定義,中文定義,英文定義,性質,充分性,必要性,

定義

中文定義

耳指的是內部點度數均為2的極大路徑。
耳分解指的是將圖分解為一個環和若干個耳的組合。

英文定義

An ear of a graph G is a maximal path whose internal vertices have degree 2 in G.
An ear decomposition of G is a decomposition
such that
is a cycle and
for i ≥ 1 is an ear of
.

性質

一個圖G是2-連通的(2-connected)若且唯若圖存在一個耳分解。
引理1:對於一個2-連通圖,至少存在一個環。
引理2:對於每一個有多於3個頂點的2-連通圖,每一對邊都存在一個環將它們連線。
引理3:如果一個圖是2-連通的,那么通過對G中的邊進行細分(subdividing)得到的圖G‘仍然是2-連通的。

充分性

由引理1,圖G中可以找到一個環。取任意一個環C作為
如果
,那么至少存在
中的一條邊uv∉
。根據引理2,我們在
中任取一條邊xy,那么存在一個環連線xy與uv。通過uv沿著環順勢針、逆時針分別尋找與
最近的兩個交點z與w。將z-u-v-w作為耳加入分解中。重複操作,所有邊必然都能被加入耳分解中。

必要性

環是2-連通圖的,對於每一個耳
首先連線耳
的兩個端點,此時仍然是2-連通圖的。然後對這條邊進行細分至路徑的長度,引理3保證了此時圖仍然是2-連通圖。
重複操作,直到將所有耳都加到環上,得到的圖是2-連通的。

相關詞條

熱門詞條

聯絡我們