ベルゲの定理

グラフ理論において、ベルゲの定理は、グラフG内のマッチング Mが最大（可能な最大数のエッジを含む）となるのは、Mを持つ増加パス（空き（マッチングされていない）頂点で始まり、そこで終わり、マッチング内のエッジとマッチングに含まれないエッジが交互に現れるパス）がない場合のみであることを述べています。

これは 1957 年にフランスの数学者クロード・ベルジュによって証明されました(ただし、 1891 年にピーターセン、1931 年に ケーニッヒによってすでに観察されていました)。

ベルジュの定理を証明するには、まず補題が必要です。グラフ G を取り、 Mと M ′ を G 内の 2 つのマッチングとします。 G ′を、 MとM ′の対称差、つまり( M - M ′ ) ∪ ( M ′ - M )を取った結果のグラフとします。 G ′ は、次のいずれかの連結成分で構成されます。

1. 孤立した頂点。
2. MとM ′の辺が交互に並ぶ偶数サイクル。
3. MとM ′ の間でエッジが交互に存在し、エンドポイントが異なるパス。

この補題は、 G ′の各頂点が最大 2 本の辺 ( Mから 1 本、 M ′から 1 本) に接続できることを観察することで証明できます。すべての頂点の次数が 2 以下のグラフは、孤立した頂点、サイクル、およびパスのいずれかで構成されます。さらに、 G ′の各パスとサイクルは、MとM ′の間を交互に移動する必要があります。サイクルがこれを実現するには、 MとM ′からの辺の数が等しく、したがって長さが偶数である必要があります。

ここで、ベルジュの定理の逆否定を証明しましょう。GがMより大きいマッチングを持つのは、G が増加パスを持つ場合のみです。明らかに、 Gの増加パスP は、 Mより大きいマッチングM ′ を生成するために使用できます。M ′ をPとMの対称差とします( M ′には、 PとMのどちらか一方にのみ現れるGのエッジが含まれます)。したがって、逆方向が続きます。

順方向では、M ′ をMより大きいG内のマッチングとします。MとM ′の対称差であるD を考えます。D はパスと偶数サイクルで構成されます(前の補題で観察されたように)。M ′ はMより大きいため、D にはM ′からのエッジがMよりも多く含まれるコンポーネントが含まれます。このようなコンポーネントは、 M ′からのエッジで始まり、終わるG内のパスであるため、増加パスです。

M を最大マッチングとし、パス内のエッジがMに含まれるか含まれないかを交互に繰り返す交代チェーンを考えます。交代チェーンがサイクルまたは一致しない頂点から始まる偶数の長さのパスである場合、 MにあるエッジとMにないエッジを交換することで、新しい最大マッチングM ′ を見つけることができます。たとえば、交代チェーンが ( m ₁、n ₁、m ₂、n ₂、...) であり、m _i ∈ Mかつn _i ∉ Mである場合、それらを交換すると、すべてのn _{i が}新しいマッチングの一部になり、すべてのm _{i が}マッチングの一部ではなくなります。

エッジは、最大マッチングに属しているが、すべての最大マッチングに属していない場合は「自由」とみなされます。任意の最大マッチングMにおいて、エッジe が、一致しない頂点から始まる偶数交代パスまたは交代サイクルに属している場合に限り、エッジe は自由です。最初の系により、エッジeがそのような交代チェーンの一部である場合、新しい最大マッチングM ′ が存在する必要があり、e はMまたはM ′のいずれかに存在するため自由になります。逆に、エッジeが自由である場合、e は最大マッチングMの一部ですが、M ′には存在しません。e はMとM ′の両方の一部ではないため、 MとM ′の対称差をとった後も存在する必要があります。MとM ′の対称差により、孤立した頂点、偶数交代サイクル、および交代パスで構成されるグラフが生成されます。これに対して、e が奇数長のパス コンポーネントに属していると仮定します。しかし、このコンポーネントでは、 MとM ′のいずれかがもう一方よりも 1 つ少ないエッジを持つ必要があります。つまり、コンポーネント全体がそのマッチングに関して増加パスになります。元の補題によれば、そのマッチング ( MまたはM ′ ) は最大マッチングにはならず、これはMとM ′ の両方が最大であるという仮定と矛盾します。したがって、 e は奇数長のパス コンポーネントに属することはできないため、交互サイクルまたは偶数長の交互パスのいずれかにある必要があります。

• ベルジュ、クロード(1957 年 9 月 15 日)、「グラフ理論における 2 つの定理」(PDF)、米国科学アカデミー紀要、43 (9): 842–844、Bibcode :1957PNAS...43..842B、doi : 10.1073/pnas.43.9.842、PMC  534337、PMID  16590096。
• ウェスト、ダグラス B. (2001)、グラフ理論入門(第 2 版)、ピアソン エデュケーション社、pp. 109–110、ISBN 81-7808-830-4。
• ベルジュ、クロード（1973）、グラフとハイパーグラフ、ノースホランド出版社、pp. 122-125、ISBN 0-444-10399-6。