数学 › グラフ理論 › 連結度とネットワークフロー

Menger の定理

定理 5.4（「連結度とネットワークフロー」§5） ・ ✓公理まで証明済み

本文で読む（証明と前後の説明）→

閉包の状態

✓ 公理まで証明済み

証明が使う定理を 前提 としてたどると、Rikai の中の証明だけで定義・公理（物理では基本仮定）までつながっています（前提の定理類 16 件、定義なども含めて 18 件）。

印の意味: ✓公理まで証明済み ・ △証明あり（閉包未完）・ ※主張のみ。テーマごとの集計は 閉包の状況。

前提をたどる 証明が使う定理・定義（直接 3 件）

▸ を開くと、その項目の証明が使う前提が出ます。深い先は各項目のページでたどれます。

• 整数性定理✓定理 4.9・連結度とネットワークフロー

  • 増加すると流量が増える✓補題 4.5・連結度とネットワークフロー
  • 流量はどのカットでも測れる✓補題 4.3・連結度とネットワークフロー
  • 増加道が無ければ流量と等しい容量のカットがある✓補題 4.6・連結度とネットワークフロー

    • 流量はどのカットでも測れる✓補題 4.3・連結度とネットワークフロー
• 0-1 フローは道に分解できる✓補題 5.2・連結度とネットワークフロー

  • 数学的帰納法の原理✓定理 3.2・証明の技術

    • 背理法の正当性✓命題 6.2・証明の技術
    • 整列性公理 3.1・証明の技術
  • 流量はどのカットでも測れる✓補題 4.3・連結度とネットワークフロー
• 最大フロー最小カット定理✓定理 4.8・連結度とネットワークフロー

  • 最大フローの存在✓補題 4.7・連結度とネットワークフロー

    • ハイネ・ボレルの定理✓定理 5.2・コンパクト性

      • 閉直方体はコンパクト✓補題 5.1・コンパクト性 この先をたどる →
      • コンパクト空間の閉部分集合はコンパクト✓定理 4.1・コンパクト性 この先をたどる →
      • ハウスドルフ空間定義 2.1・コンパクト性
      • ハウスドルフ空間ではコンパクト集合と外部の点が分離できる✓定理 4.2・コンパクト性 この先をたどる →
      • 部分空間のコンパクト性の判定✓補題 3.3・コンパクト性
    • 最大値・最小値の定理✓系 6.2・コンパクト性

      • コンパクト集合の連続像はコンパクト✓定理 6.1・コンパクト性 この先をたどる →
      • ハイネ・ボレルの定理✓定理 5.2・コンパクト性（上で展開済み）
  • 増加すると流量が増える✓補題 4.5・連結度とネットワークフロー
  • 増加道が無ければ流量と等しい容量のカットがある✓補題 4.6・連結度とネットワークフロー（上で展開済み）

これを使っている定理 証明で参照している 2 件

• Menger の定理の大域版✓系 5.5・連結度とネットワークフロー
• Menger の定理から König と Hall が従う✓命題 6.1・連結度とネットワークフロー

関連するノック 1 問

• グラフ理論 第 21 問