組み合わせ数学

グラフ理論の応用

平面グラフ

グラフGは、頂点がすべて別個の点であり、エッジが単純な曲線であり、2つのエッジが端子以外で互いに交わらないような方法で平面上に表すことができる場合、平面と呼ばれます。たとえば、図4Aに示すように、4つの頂点の完全なグラフであるK ₄は平面です。

2つのグラフは、エッジのサブディビジョンによって同じグラフから両方を取得できる場合、同型であるといいます。たとえば、図4Aと図4Bのグラフは同型です。

K _m、nグラフは、頂点セットを2つのサブセットに分割できるグラフです。1つはm頂点、もう1つはn頂点です。同じサブセットの2つの頂点は隣接していませんが、異なるサブセットの2つの頂点は隣接しています。1930年のポーランドの数学者カジミェシュクラトフスキは、次の有名な定理を証明しました。

グラフGが平面であるための必要かつ十分な条件は、図5に示すK ₅またはK _3,3のいずれかに同型のサブグラフを含まないことです。

グラフGの基本縮約は、Gの新しいグラフG ₁への変換です。つまり、Gの2つの隣接する頂点uとareはG _1の新しい頂点wに置き換えられ、wはG _1のすべての頂点に隣接します。これは、uとυのどちらかがGで隣接しています。グラフG *は、G *が一連の基本縮約によってGから取得できる場合、Gの縮約と呼ばれます。以下は、1937年にドイツの数学者K.ワグナーによる平面グラフの別の特徴です。

グラフが平面であるのは、K ₅またはK _3,3に縮小できない場合のみです。

4色マップの問題

1世紀以上にわたって、4色マップの問題の解決策は、それを試みたすべてのアナリストを回避しました。問題はメビウスの注意を引いたかもしれませんが、それへの最初の書面による言及は、1852年のあるフランシス・ガスリーから彼の兄弟、アウグストゥス・ド・モーガンの学生への手紙であるようです。

問題は平面マップ、つまり単純な閉じた曲線で囲まれた非重複領域への平面の分割に関係します。地理的地図では、経験的に、試行された多くの特別な場合に、領域を色付けするために最大4色が必要であり、共通の境界を共有する2つの領域が常に異なる色で表示されることが観察されています。少なくとも4色が必要な特定のケース。（米国のコロラド州やアリゾナ州など、ある時点でのみ出会う地域は、共通の境界を持つとは見なされません）。この経験的観察の形式化は、いわゆる「4色定理」を構成します。問題は、これがすべての平面マップに当てはまるという主張を証明または反証することです。3色では不十分であることが簡単に示されていますが、5色の十分性は1890年に英国の数学者PJヒーウッドによって証明されました。

1879年、イギリス人のABケンペは4色問題の解決策を提案しました。ヒーウッドはケンペの議論に欠陥があることを示したが、その概念のうちの2つは後の調査で実を結んだ。これらの1つは不可避と呼ばれ、4つの構成が1つもないマップを作成することの不可能性を正しく述べています（これらの構成は、2つの隣接する領域、1つは3つ、1つは4つ、もう1つは5つの領域で構成されます）。2番目の概念、すなわち還元性の概念は、Kempeの有効な証明にちなんで名付けられました。少なくとも5つの色を必要とし、4つ（または3つまたは2つ）の近傍を持つ領域を含むマップがある場合、5つのマップを必要とする必要があります。少数の領域の色。ケンペが隣接する5つの地域を含む地図の縮小可能性を証明しようとしたのは誤りでしたが、1976年に米国のケネスアペルとウォルフガングハーケンによって発表された証明で修正されました。彼らの証拠は、それぞれが500,000もの論理演算を含む1,936の異なるケースの評価を必要とするため、いくつかの批判を集めました。Appel、Haken、およびその共同研究者は、大規模なデジタルコンピューターでこれらの詳細を処理できるようにするプログラムを考案しました。コンピュータがタスクを実行するのに1,000時間以上を要し、結果として得られた正式な証拠は数百ページの長さです。

オイラー周期とケーニヒスベルク橋問題

マルチグラフGは、頂点の空でないセットV（G）およびV（G）の個別の要素の順序付けられていないペアのセットのサブセットE（G）で構成され、各ペアに周波数f≥1が付加されます。周波数f のペア（x ₁、x ₂）がE（G）に属している場合、頂点x ₁とx ₂はfエッジで結合されます。

マルチグラフGのオイラーサイクルは、各エッジが1回だけ現れる閉じたチェーンです。オイラーは、マルチグラフが接続されていて（孤立点を除く）、奇数次の頂点の数が0または2の場合にのみ、マルチグラフがオイラーサイクルを持つことを示しました。

この問題は、最初に次のように発生しました。2つの支流の合流点によって形成されたプレゲル川は、ケーニヒスベルクの町を流れ、クナイプホーフ島の両側を流れています。図6Aに示すように、7つのブリッジがありました。町民は散歩に出かけて、各橋を一度だけ渡ることができるかどうか疑問に思いました。これは、図6Bのマルチグラフのオイラーサイクルを見つけることと同じです。オイラーは、奇数次の頂点が4つあるため、不可能であることを示しました。