アルゴリズムグラフの耳分解 2.3 連結性 (グラフ) 駆け足で読む B.コルテ/J.フィーゲンの 組合せと最適化-理論とアルゴリズム

グラフがある。それは、次のようにできているとみなせるとする。

１つの閉路がある。これをG0とする。その閉路と１点のみを共有する閉路か、その閉路と２点のみをい共有するパスがある。このG0＋閉路またはパスをG1とする。このG1|G0(G1からG0をのぞいた部分グラフを耳と呼ぶ)。G1に耳をつけ、それをG2とし、さらにG2に耳をつけ、G3とし、、、というような構成にできるグラフがあって、それを１つの閉路とそれに順番に付け加わった耳とに分けるようなわけ型を耳分解(ear-decomposition)という。

耳がすべてパスであって、閉路でないときの耳分解をプロパー(proper)な耳分解と呼ぶ。

無向グラフが２−連結であるための必要十分条件は、プロパーな耳分解を持つことである。

ただし、k-連結である、とは、任意のk-1個の点を除去してもそのグラフが連結であることを言う。たとえば、1-連結であるとは、橋(関節点)を持つような連結グラフである。2−連結であるとは、うまく2個の点を選んで取り去ると、連結でないグラフに分けられるようなグラフである。

掲載図のオリジナルはこちら