導入
「水、ガス、電気の謎」とも呼ばれる「三家の謎」は、トポロジーまたはグラフ理論の定理を分析に使用する数学ゲームです。この問題には解決策がありません。ジョルジュ・ペレックは、1978 年に著書『 I remember 』の中で彼の言葉を引用しています。 「私は小学 3 年生だったと思いますが、パイプが互いに交差しないように 3 軒の家に水、ガス、電気を供給するために何時間も費やしたことを覚えています (解決策はありません)。私たちが 2 次元空間にいる限り、これはケーニヒスベルクの橋や地図の色付けのような、トポロジーの基本的な例の 1 つです。) »
この謎は、1917 年にデュドニー閣下によって著書『数学における娯楽』ですでに提起されていました。彼は、「丘と同じくらい古い謎が6つあり、それらは絶えず再現されている」と述べています。記事にあるのは、彼が「水道、ガス、電気」と呼んでいるものの 1 つです。これはガードナー氏によって広められ、彼の『数学ゲームの 6 冊の本』で紹介されました。
解決策が存在しないことを証明するには 2 つのアプローチがあります。 1 つ目は、ジョーダンの定理を使用しており、平面にループを描く場合、ループの補部分、つまり平面の描かれていない部分は、円弧で接続された 2 つの要素で構成され、1 つは有界 (ループ)、もう 1 つはそうでない (ループの外部)。 2 番目のアプローチはより一般的で、平面グラフにオイラーの公式を使用します。これは、Kuratowski として知られる平面グラフの重要定理の実証のステップです。
ステートメント
この謎は物語の形式で次のように表現されます。
「 3 軒の住宅からなる分譲地には、水道、ガス、電気を完備しなければなりません。安全上の理由から、規制によりパイプを横断することは禁止されています。どのように行うべきですか? »
物語には多くのバリエーションがあります。たとえば、次のようなことがわかります。 「彼は… 3 台の車を持っており、駐車スペース 1、2、または 3 に駐車できる必要があります。彼は、各車をそれぞれの場所に接続するルート (つまり、合計9 つの別々の場所) を描きたいと考えています。道路）により、各車両がこれらの場所のいずれかに移動できるようになりますが、衝突を避けるために、これらの経路は（部分的であっても）いかなる場合でも交差したり、混乱したりしてはなりません。これらの通路は、駐車場や車の後ろを通ることができ、どんな形状であっても構いませんが、駐車スペース（もちろん他の車両も）を横切ってはなりません。」
この問題は抽象的にグラフとして見ることもできるため、数学的に研究することができます。グラフはノードと呼ばれる一連の点で構成されており、その一部はリンクによって接続されています。パズルの場合、2 つのノード セットがあります。集合M は3 つの家 (反対側の図の青) の 3 つのノードを持ち、集合F はガス供給、水道、電気 (赤)の 3 つのノードを持ちます。反対側の図）。この謎では、2 つのリンクが交差しないように、 MとFの各ノード間にリンクが存在する必要があります。これらのリンクを配置する可能な方法は、反対側の図に緑色のリンクで示されています。 m個の要素のセットのすべてのノードがn 個の要素のセットのすべてのノードに接続されている必要があるグラフは、完全な 2 部グラフと呼ばれ、 K m,nで示されます。 2 つのリンクが交差しないグラフは、平面と呼ばれます。疑問は次のとおりです: K 3.3 は平面グラフですか?