ロビンズの定理

グラフ理論において、ハーバート・ロビンス (1939)にちなんで名付けられたロビンスの定理は、強い向きを持つグラフはまさに2 辺連結グラフであると述べている。つまり、無向グラフGの各辺の方向を選択して、Gが連結でブリッジがない場合に限り、すべての頂点から他のすべての頂点へのパスを持つ有向グラフにすることができる。

強い方向性を持つグラフに対するロビンズの特徴付けは、このタスクのためにロビンズが導入したツールである ear decomposition を使用して証明できます。

グラフにブリッジがある場合、ブリッジにどの方向が選択されても、ブリッジの 2 つのエンドポイントの一方から他方へのパスが存在しないため、強く方向付けることはできません。

反対に、連結されたブリッジレス グラフはすべて強く方向付けられることを示す必要があります。ロビンズが証明したように、このようなグラフはすべて、「耳」と呼ばれるサブグラフのシーケンスに分割されます。このシーケンスの最初のサブグラフはサイクルで、後続の各サブグラフはパスであり、2 つのパスのエンドポイントは両方ともシーケンスの前の耳に属します。(2 つのパスのエンドポイントが等しい場合、サブグラフはサイクルになります。) 各耳内のエッジを方向付けて、有向サイクルまたは有向パスを形成すると、グラフ全体の強く連結された方向付けが実現します。^[1]

Boesch & Tindell (1980) による混合グラフへのロビンズの定理の拡張では、G が一部の辺が有向で他の辺が無向であるグラフであり、Gがすべての頂点から他のすべての頂点への辺の向きを考慮したパスを含む場合、Gのブリッジではない無向辺はGの接続性を変更することなく有向にできることが示されています。特に、ブリッジのない無向グラフは、すべての頂点のペア間のパスの存在を維持しながら辺を1つずつ有向にする貪欲アルゴリズムによって、強く接続された有向グラフにすることができます。このようなアルゴリズムでは、追加の向きの決定ができ​​ない状況に陥ることは不可能です。

与えられた橋のない無向グラフの強い向きは、グラフの深さ優先探索を実行し、深さ優先探索木内のすべての辺を木の根から離して向きを変え、残りのすべての辺（深さ優先探索木で祖先と子孫を必ず接続する必要がある）を子孫から祖先に向けることで、線形時間で見つけることができます。^[2]このアルゴリズムは、深さ優先探索を実行するのが難しいため、並列コンピュータには適していませんが、並列モデルで効率的に問題を解決する代替アルゴリズムが利用可能です。 ^[3]並列アルゴリズムは、混合グラフの強く接続された向きを見つけるためにも知られています。^[4]

ロビンズはもともと、都市の一方通行の設計への応用を研究の動機としていた。別の応用は、構造剛性、つまりグリッドブレース理論に見られる。この理論は、柔軟なジョイントで接続された剛性ロッドから構成される正方形グリッドを、グリッドの対角線上にクロスブレースとしてロッドまたはワイヤを追加することで剛性にする問題に関する。追加されたロッドのセットは、関連する無向グラフが接続されている場合はグリッドを剛性にし、さらにブリッジがない場合には二重にブレースされる（どのエッジも削除されても剛性は維持される）。同様に、追加されたワイヤのセット（接続するポイント間の距離を縮めるために曲げることはできるが、拡張することはできない）は、関連する有向グラフが強く接続されている場合はグリッドを剛性にする。^[5]したがって、この応用のためにロビンズの定理を再解釈すると、二重にブレースされた構造は、ロッドをワイヤに置き換えても剛性を維持できる構造とまったく同じである。