メンガーの定理

数学の分野であるグラフ理論において、メンガーの定理は、有限グラフにおいて、最小カットセットのサイズは、任意の頂点のペアの間に見つかる互いに素なパスの最大数に等しいというものです。1927年にカール メンガーによって証明されたこの定理は、グラフの接続性を特徴づけます。この定理は、最大フロー最小カット定理によって一般化されます。これは重み付けされたエッジ バージョンであり、線形計画法の強い双対性定理の特殊なケースです。

メンガーの定理のエッジ接続バージョンは次のとおりです。

G を有限無向グラフとし、xとy を2つの異なる頂点とします。このとき、 xとyの最小エッジカットのサイズ（削除するとxとyが切断されるエッジの最小数）は、 xからyへのエッジが互いに素なペアのパスの最大数に等しくなります。

グラフGの意味は次のようになります。

グラフがk辺接続されている（ k個未満の辺を削除した後も接続されたままである）のは、すべての頂点のペアの間にk個の辺が互いに素なパスがある場合のみです。

メンガーの定理の頂点接続性ステートメントは次のとおりです。

G を有限無向グラフとし、xとy を隣接しない2つの頂点とします。このとき、xとyの最小頂点カットのサイズ（ xとyとは異なる頂点のうち、削除するとxとyが切断される頂点の最小数）は、 xからyへの内部的に互いに素なパスのペアの最大数に等しくなります。

グラフG全体の結果は次のようになります。

グラフがk頂点連結( k個を超える頂点があり、 k個未満の頂点を削除した後も連結されたまま) であるのは、すべての頂点ペアの間に少なくともk 個の内部的に分離したパスがある場合のみです。

エッジバージョンと頂点バージョンの両方におけるこれらすべてのステートメントは、有向グラフ（有向パスを考慮する場合）でも当てはまります。

ほとんどの直接証明では、帰納法で証明できるように、より一般的なステートメントを考慮します。また、いくつかの退化したケースを含む定義を使用するのも便利です。無向グラフに関する次の証明は、パスを有向パスと見なす限り、有向グラフまたはマルチグラフに対して変更なしで機能します。

頂点集合A,B ⊂ G (必ずしも互いに素ではない) について、AB パスは、開始頂点がA 、終了頂点がBで、内部頂点がAにもBにも存在しない、 G内のパスです。 A ∩ Bに頂点が 1 つあり、辺が 0 個のパスも許可されます。サイズkのAB セパレータは、 k 個の頂点 ( AおよびBと交差する場合がある)の集合Sで、 G−SにはABパスが含まれません。サイズkのAB コネクタは、k個の頂点互いに素なABパスの和集合です。

定理: ABセパレータの最小サイズは、ABコネクタの最大サイズに等しくなります。

言い換えると、k −1 個の頂点がAとBを切断しない場合、AからBへのk本の互いに素なパスが存在します。この変形は、上記の頂点接続性のステートメントを意味します。前のセクションのx,y ∈ Gに対して、現在の定理をG −{ x,y }に適用します。ここで、 A = N(x)、B = N(y)はx,yの隣接頂点です。すると、 xとy を切断する頂点の集合はABセパレータと同じものとなり 、独立したxyパスの集合から端の頂点を削除するとABコネクタが得られます。

定理の証明: ^[1] G の辺の数に関する帰納法。辺のないGの場合、最小のABセパレータはA ∩ Bであり、それ自体が単一頂点パスからなる ABコネクタです。

Gが辺e を持つ場合、帰納法によって定理がG−eに対して成立すると仮定できます。G−eにサイズkの最小ABセパレータがある場合、 G−eにサイズkのABコネクタが存在し、したがってGにも存在します。

それ以外の場合、S をG−eのABセパレータでサイズがk未満であるとし、GのすべてのABパスにSの頂点または辺eが含まれるようにします。 Sのサイズはk-1でなければなりません。これは、サイズが小さいと、Sとeのいずれかの端点がGのより良いABセパレータになるためです。G−Sにはe を通るABパスがあります。これは、SだけではGのABセパレータになるには小さすぎるためです。v _{1 を}そのようなパス上のeの前の頂点、v _{2 を}後の頂点とします。すると、 G−S−eでv _{1 は}Aからは到達可能ですがBからは到達できません。一方、v _{2 は}Bからは到達可能ですがAからは到達できません。

ここで、S ₁ = S ∪ {v ₁ }とし、G−e内の最小のAS ₁セパレータTを考えます。v _{2 は}G−S ₁内のAから到達できないため、TもG内のAS ₁セパレータです。次に、T はG内のABセパレータでもあります(すべてのABパスがS ₁と交差するため)。したがって、サイズは少なくともkです。帰納的に、G−eにはサイズがkのAS ₁コネクタC ₁が含まれます。そのサイズのため、その中のパスの終点は正確にS ₁でなければなりません。

同様に、S ₂ = S ∪ {v ₂ }とすると、最小のS ₂ Bセパレータのサイズはkとなり、開始点がまさにS ₂であるパスを持つサイズkのS ₂ BコネクタC ₂が存在します。

さらに、S _{1 は}Gを切断するため、C ₁のすべてのパスはC ₂のすべてのパスと内部的に分離されており、パスを連結することによってGにサイズkのABコネクタを定義できます( Sを通るk−1 個のパスとe=v ₁ v ₂を通る 1 個のパス)。 QED

定理の有向辺バージョンから、他のバージョンが簡単に導き出されます。有向グラフの頂点バージョンを推論するには、各頂点v を2 つの頂点v ₁、v ₂に分割し、すべての入力辺をv ₁に、すべての出力辺をv ₂から、さらにv ₁からv ₂への辺を追加するだけで十分です。定理の有向バージョンからは、無向バージョンが直ちに導き出されます。つまり、無向グラフの各辺を有向辺のペア (二角形) に置き換えるだけで十分です。

有向エッジ版は、その加重版である最大フロー最小カット定理から導かれます。その証明は、最大フローアルゴリズムの正しさの証明となることがよくあります。また、これは、線形計画法のさらに一般的な（強い）双対性定理の特殊なケースでもあります。

有限有向グラフの場合の上記の定式化と同等の定式化は次のようになります。

AとB を有限有向グラフ Gの頂点の集合とします。すると、互いに素なABパスの族Pと、 P内の各パスからちょうど 1 つの頂点だけで構成されるAB分離集合が存在します。

このバージョンでは、定理はケーニッヒの定理からかなり簡単に導かれます。二部グラフでは、カバーの最小サイズはマッチングの最大サイズに等しくなります。

これは次のように行われます。元の有向グラフD内のすべての頂点v を2 つの頂点v'、v''に置き換え、すべての辺uvを辺u'v''に置き換えます。さらに、 AにもBにも属さないすべての頂点vに辺v'v''を含めます。これにより、片側が頂点v'で構成され、もう一方が頂点v''で構成される二部グラフが生成されます。

ケーニッヒの定理を適用すると、一致するMと同じサイズの被覆C が得られる。特に、Mの各辺のちょうど 1 つの端点はCに含まれる。Cに、 Aに含まれるaの頂点a''とBに含まれるbの頂点b'をすべて追加する。Dに含まれる辺uvから成り、 u'v'' がMに属するすべてのABパスの集合をPとする。元のグラフのQ が、 v'とv'' の両方がCに属するすべての頂点vから構成されるとする。 QがAB分離集合であること、族PのすべてのパスにQの頂点が 1 つだけ含まれていること、およびQのすべての頂点がPからのパス上にあることは簡単に確認できる。^[2]

メンガーの定理は無限グラフに対して成り立ち、その文脈ではグラフの頂点または端点である任意の 2 つの要素間の最小カットに適用されます (Halin 1974)。 Ron Aharoniと Eli Berger による次の結果は、もともとPaul Erdősによって提案された予想であり、証明される前はErdős–Menger 予想として知られていました。グラフが有限である場合、これは Menger の定理と同等です。

AとB を（無限の可能性のある）有向グラフ Gの頂点の集合とします。このとき、互いに素なA - Bパスの族Pと、 P内の各パスからちょうど 1 つの頂点で構成される分離集合が存在します。

• ガモイド
• k 頂点連結グラフ
• k辺連結グラフ
• 頂点セパレータ

• カール、メンガー (1927)。 「Zur allgemeinen Kurventheorie」。基金。数学。10：96-115。土井：10.4064/fm-10-1-96-115。
• アハロニ、ロン。バーガー、イーライ (2008)。 「無限グラフのメンジャーの定理」。数学の発明。176 (1): 1-62。arXiv : math/0509397。Bibcode :2009InMat.176....1A。土井：10.1007/s00222-008-0157-3。S2CID  15355399。
• ハリン、R. (1974)。 「無限局所有限グラフに対するメンガーの定理に関するメモ」。ハンブルク大学アブハンドルゲン数学セミナー。40：111-114。土井：10.1007/BF02993589。S2CID  120915644。

• メンガーの定理の証明
• メンガーの定理と最大フロー最小カット