ブリッジ（グラフ理論）

グラフ理論において、ブリッジ、地峡、カットエッジ、またはカットアークは、グラフのエッジであり、これを削除すると、グラフの連結成分の数が増加する。^[1]同様に、エッジがブリッジとなるのは、どのサイクルにも含まれていない場合のみである。連結グラフの場合、ブリッジはカットを一意に決定できる。グラフにブリッジが含まれていない場合、そのグラフはブリッジレスまたは地峡フリーであると言われる。

このタイプのブリッジは、グラフ理論における「ブリッジ」の無関係な意味、つまり、指定された頂点のサブセットによってグラフの残りの部分から分離されたサブグラフとは区別する必要があります。グラフ理論の用語集のブリッジを参照してください。

ノードを持つグラフには最大でブリッジを含めることができます。これは、エッジを追加すると必ずサイクルが作成されるためです。正確に 個のブリッジを持つグラフはまさに木であり、すべてのエッジがブリッジであるグラフはまさに森です。 ${\displaystyle n}$${\displaystyle n-1}$${\displaystyle n-1}$

すべての無向グラフには、頂点間に同値関係があり、それによれば、2 つの頂点を接続する辺が互いに素なパスがある場合、それらの頂点は互いに関連している。(すべての頂点は、長さが 0 の 2 つのパスを介して自分自身と関連しており、これらのパスは同一であるが、辺が素である。) この関係の同値類は2 辺連結成分と呼ばれ、グラフのブリッジは、端点が異なる成分に属する辺とまったく同じである。グラフのブリッジ ブロック ツリーには、すべての非自明な成分に対応する頂点と、すべてのブリッジに対応する辺がある。^[2]

ブリッジは、他の頂点のペア間のすべてのパスに属する頂点である、連結頂点の概念と密接に関連しています。ブリッジの 2 つの端点は、次数が 1 でない限り連結頂点ですが、ブリッジ以外の辺が 2 つの連結頂点を端点として持つことも可能です。ブリッジのないグラフが 2 辺接続されているのと同様に、連結頂点のないグラフは2 頂点接続されています。

立方体グラフでは、すべてのカット頂点は少なくとも 1 つのブリッジの終点です。

ブリッジレスグラフは、ブリッジを持たないグラフです。同等の条件は、グラフの各連結成分がオープンイヤー分解を持つこと、^[3]、各連結成分が2辺連結であること、または（ロビンズの定理により）すべての連結成分が強い配向を持つことです。^[3]

橋に関する重要な未解決問題として、シーモアとシェケレス（1978年と1979年、それぞれ独立）によるサイクル二重被覆予想がある。これは、橋のないグラフには、各辺がちょうど2回含まれる単純サイクルの多重集合が存在するというものである。^[4]

グラフ内のブリッジを見つけるための最初の線形時間アルゴリズム（辺の数に比例）は、1974年にロバート・タージャンによって記述されました。 ^[5]このアルゴリズムは、以下のステップを実行します。

• 広がる森を見つける${\displaystyle G}$
• スパニングフォレストからルートフォレスト を作成する${\displaystyle F}$
• フォレストを事前順序でトラバースし、ノードに番号を付けます。フォレスト内の親ノードの番号は、子ノードの番号よりも小さくなります。${\displaystyle F}$
• 事前順序の各ノード（事前順序番号を使用して各ノードを示す） に対して、次の操作を実行します。${\displaystyle v}$
  • このノードのフォレスト子孫の数を、その子の子孫の合計に 1 を加えて計算します。${\displaystyle ND(v)}$
  • 最後のエッジを除くすべてのエッジが をルートとするサブツリー内にあるパスによってから到達可能な最低の事前順序ラベルを計算します。これは、 の事前順序ラベル、の子ノードにおけるの値、に属さないエッジによってから到達可能なノードの事前順序ラベルで構成されるセットの最小値です。${\displaystyle L(v)}$${\displaystyle v}$${\displaystyle v}$${\displaystyle v}$${\displaystyle L(w)}$${\displaystyle v}$${\displaystyle v}$${\displaystyle F}$
  • 同様に、最後のエッジを除くすべてのエッジが をルートとするサブツリー内にとどまるパスによって到達可能な最高の事前順序ラベル を計算します。これは、 の事前順序ラベル、の子ノードにおけるの値、に属さないエッジによってから到達可能なノードの事前順序ラベルで構成されるセットの最大値です。${\displaystyle H(v)}$${\displaystyle v}$${\displaystyle v}$${\displaystyle H(w)}$${\displaystyle v}$${\displaystyle v}$${\displaystyle F}$
  • 親ノードを持つ各ノードについて、 の場合、からへのエッジはブリッジです。${\displaystyle w}$${\displaystyle v}$${\displaystyle L(w)=w}$${\displaystyle H(w)<w+ND(w)}$${\displaystyle v}$${\displaystyle w}$

非常に単純なブリッジ検出アルゴリズム^[6]は、チェーン分解を使用します。チェーン分解を使用すると、グラフのすべてのブリッジを計算できるだけでなく、Gのすべてのカット頂点(およびGのブロックカットツリー)を読み取ることができ、2 辺と 2 頂点の接続性をテストするための一般的なフレームワークが得られます (これは、線形時間の 3 辺と 3 頂点の接続性のテストに拡張されます)。

連鎖分解は、 GのDFS 木Tに依存する特別な ear 分解であり、非常に簡単に計算できます。すべての頂点を未訪問としてマークします。昇順のDFS番号 1... nの各頂点vについて、 vに接続するすべてのバックエッジ (つまり、 DFS 木にないすべてのエッジ) をトラバースし、ツリーエッジのパスをたどってTのルートに戻り、訪問済みとしてマークされている最初の頂点で停止します。このようなトラバース中、トラバースされたすべての頂点は訪問済みとしてマークされます。したがって、トラバースは遅くともvで停止し、 v から始まる有向パスまたはサイクルを形成します。このパスまたはサイクルを連鎖と呼びます。この手順で見つかったi番目の連鎖はC _iと呼ばれます。C =C ₁、C ₂、...はGの連鎖分解です。

以下の特徴付けにより、Gのすべてのブリッジを含む、Gのいくつかの特性をCから効率的に読み取ることができます。^[6] Cを単純連結グラフG=(V,E)の連鎖分解とします。

1. Gが 2 辺連結であるためには、 C内のチェーンがE を分割する必要があります。
2. Gのエッジeがブリッジとなるのは、e がCのどのチェーンにも含まれていない場合のみです。
3. Gが 2 辺連結である場合、 C はear 分解です。
4. Gが 2 頂点連結であるためには、G の最小次数が 2 であり、C _{1 が}C内の唯一の閉路である必要があります。
5. 2辺連結グラフGの頂点vは、 v がC - C ₁の閉路の最初の頂点である場合に限り、カット頂点となります。
6. Gが 2 頂点連結である場合、 C はオープン イヤー分解です。

• 二重連結成分
• カット（グラフ理論）