メンガーの定理

メンガーの定理：グラフの連結性と辺、点の切断

メンガーの定理は、グラフ理論において、グラフの連結性を測る上で極めて重要な定理です。1927年、カール・メンガーによって発見され、その後、様々な分野に応用されています。この定理は、2つの頂点間の連結性を、辺や頂点を削除することで切断する最小の辺や頂点の数と、それら2つの頂点を結ぶ独立した経路の最大数との関係を明らかにしています。

辺連結度版

まず、辺連結度版について説明します。これは、グラフ上の2つの頂点xとyを繋ぐ辺を切断することで、xとyを分離する最小の辺の数を考えます。この数を「最小辺カット」と呼びます。一方、xとyを繋ぐ複数の経路のうち、どの2つの経路も共通の辺を持たない経路の最大数を「辺独立経路の最大数」と呼びます。メンガーの定理（辺連結度版）は、これらの量が等しいことを主張します。

言い換えると、xとyを分離するために必要な最小の辺の数は、xとyを互いに独立に接続する経路の最大数と一致します。これは直感的には理解しづらいかもしれませんが、例えば、橋で結ばれた島を考えた場合、島を分離するために必要な橋の本数は、島同士を独立に繋ぐ橋の最大数と等しくなります。

点連結度版

次に、点連結度版について説明します。これは、辺連結度版と同様に、グラフ上の2つの頂点xとyを分離することを考えますが、今度は辺ではなく、頂点を削除することで分離することを考えます。この時、xとyを分離するために削除する必要のある最小の頂点の数を「最小点カット」と呼びます。一方、xとyを繋ぐ複数の経路のうち、どの2つの経路も共通の頂点を持たない経路の最大数を「頂点独立経路の最大数」と呼びます。メンガーの定理（点連結度版）は、これらの量が等しいことを主張します。

これは、辺連結度版と同様に、xとyを分離するために必要な最小の頂点の数が、xとyを互いに独立に接続する経路の最大数と等しいことを示しています。

無限グラフへの拡張

初期のメンガーの定理は有限グラフを対象としていましたが、その後、ポール・エルデシュの予想に基づき、無限グラフに対しても成立することが証明されました。これは、有限グラフの場合よりもはるかに複雑な証明を必要としますが、グラフ理論の基礎となる重要な結果です。

最大フロー最小カット定理との関係

辺連結度版のメンガーの定理は、ネットワークフロー理論における最大フロー最小カット定理へと一般化されます。最大フロー最小カット定理は、ネットワークにおける最大流量と、ネットワークを切断するための最小容量の関係を示す定理であり、オペレーションズリサーチやコンピュータサイエンスなど、様々な分野で応用されています。メンガーの定理は、この重要な定理の基礎となる重要な概念を提供しています。

まとめ

メンガーの定理は、グラフ理論における基本的な定理であり、グラフの連結性を理解する上で重要な役割を果たしています。辺連結度版と点連結度版の両方が存在し、有限グラフだけでなく無限グラフにも拡張されています。また、最大フロー最小カット定理など、他の重要な定理との関連も深く、現代数学、特に離散数学において重要な位置を占めています。

もう一度検索