今北産業pedia

グラフ理論において、グラフがハミルトン閉路を持つための十分条件を与える定理。

頂点数が3以上で、隣接しない任意の2頂点の次数の和が頂点数以上であれば閉路が存在する。

巡回セールスマン問題などの組合せ最適化問題に関連する、重要な基礎理論である。

グラフが平面上に交差なく描けるための必要十分条件を与えるグラフ理論の定理。

完全グラフK5または完全二部グラフK3,3をマイナーとして含まないことが条件。

カジミェシュ・クラトフスキによって1930年に証明された。

グラフのマイナー関係による順序において、無限の反鎖が存在しないという定理。

任意のグラフの無限集合には、一方が他方のマイナーとなるペアが必ず含まれる。

ロバートソンとシーモアによる膨大な証明により、グラフ理論の最高峰の一つとされる。

二部グラフにおいて、最大マッチングのサイズは最小頂点被覆のサイズに等しいという定理。

組合せ最適化における「最大流最小カット」の概念とも深く関連している。

デネス・ケーニヒによって1931年に証明された。

グラフが完全マッチングを持つための必要十分条件を与えるグラフ理論の定理。

任意の頂点集合を取り除いた際の、奇数個の頂点を持つ連結成分の数を評価する。

マッチング理論の基礎であり、ネットワークの構造解析などに広く応用される。

グラフ理論において、ハミルトン閉路が存在するための十分条件を与える定理。

頂点数nが3以上のグラフで、各頂点の次数がn/2以上なら閉路が存在する。

ネットワークの巡回経路の存在を判定する際の基本的な指標となる。

グラフ理論において、橋を持たない3-正則グラフは完全マッチングを持つという定理。

どの頂点からも3本の辺が出ているグラフが、頂点を余らせずペアにできることを示す。

デンマークの数学者ジュリウス・ピーターセンによって1891年に証明された。

任意の平面グラフは、すべての辺を直線として平面上に描画できるという定理。

曲線を使わずに交差なしでグラフを描けることを示し、グラフ描画理論の基礎となった。

1948年にイシュトヴァン・ファーリらによって独立に証明された。

ネットワークフロー問題において、始点から終点への最大流量を求める手法。

増加道（余裕のある経路）を繰り返し探し、流量を更新し続けることで最適解を得る。

最大流最小カット定理に基づき、通信網や輸送経路の最適化に広く応用されている。

グラフの彩色数に関する定理で、最大次数をΔとしたとき、彩色数は高々Δである。

完全グラフと奇サイクルという2つの例外を除き、Δ色あれば隣接頂点を塗り分けられる。

グラフ理論における頂点彩色の限界を明示した、基本的かつ重要な成果。