3つのユーティリティの問題

トムセングラフまたは${\displaystyle K_{3,3}}$

3ユーティリティ問題、または水道、ガス、電気問題として知られる古典的な数学パズルは、平面上で3つの家と3つのユーティリティ会社の間に交差しない接続を引くことを求めるものです。20世紀初頭にこの問題を提起したとき、ヘンリー・デュドニーは、これはすでに古い問題であると書きました。これは不可能なパズルです。9本の線すべてを交差せずに接続することは不可能です。トーラスやメビウスの帯などの非平面上の問題のバージョン、または接続が他の家やユーティリティを通過することを許可するバージョンの問題は解くことができます。

このパズルは、頂点が家屋や公共施設を表し、辺がそれらの接続を表す完全二部グラフ が平面にグラフ埋め込みを持つかどうかを問うことによって、位相グラフ理論の問題として形式化できます。パズルが不可能であることは、 が平面グラフではないという事実に対応しています。この不可能性の証明は複数知られており、平面グラフを 2 つの禁制部分グラフ (そのうちの 1 つ) によって特徴付けるクラトフスキーの定理の証明の一部を形成します。完全二部グラフの描画における交差数を最小化する問題は、トゥランのレンガ工場問題として知られており、 の最小交差数は 1 です。 ${\displaystyle K_{3,3}}$${\displaystyle K_{3,3}}$${\displaystyle K_{3,3}}$${\displaystyle K_{3,3}}$

${\displaystyle K_{3,3}}$は6つの頂点と9つの辺を持つグラフで、問題に関連してユーティリティグラフと呼ばれることが多い。 ^[1] 19世紀の化学者ジュリアス・トムセンにちなんでトムセングラフとも呼ばれる。これはよく覆われたグラフであり、最小の三角形のない立方体グラフであり、最小の非平面極小剛性グラフである。

3 ユーティリティ問題の歴史については、Kullman (1979) がレビューしています。彼は、この問題に関するほとんどの出版物で、この問題は「非常に古い」と特徴づけられていると述べています。^[2] Kullman が発見した最も古い出版物では、Henry Dudeney  (1917) がこの問題を「水、ガス、電気」と名付けています。しかし、Dudeney は、この問題は「非常に古い...電気照明やガスよりもずっと古い」と述べています。^[3] Dudeney は、 1913 年にThe Strand Magazineで同じパズルを発表しました。^[4]競合する優先権の主張はSam Loydにあり、彼の息子は、この問題を 1900 年に発表したと死後の伝記で引用しています。^[5]

この問題の別の初期バージョンでは、3 つの家を 3 つの井戸につなぐという問題が出題された。^[6]これは、3 つの家と 3 つの噴水が関係する別の (そして解ける) パズルにも同様に述べられており、3 つの噴水と 1 つの家はすべて長方形の壁に接している。このパズルでも交差しない接続が必要であるが、これは現代のナンバーリンクパズルのように、指定された 3 組の家と井戸または噴水の間だけに限られる。^[7]ロイドのパズル「口論する隣人」も同様に、3 つの家を 3 つの門に 3 つの交差しない経路でつなぐ (ユーティリティ問題のように 9 つではなく)。1 つの家と 3 つの門は長方形の庭の壁にあり、その庭には他の 2 つの家がある。^[8]

このグラフは、3つの効用問題だけでなく、19世紀後半から20世紀初頭にかけての初期の文献にも登場しており、構造剛性に関する初期の研究^{[9] [10]}や、化学グラフ理論の分野では、ジュリアス・トムセンが1886年に当時は不確定だったベンゼンの構造についてこのグラフを提案した^[11]。トムセンの研究に敬意を表して、このグラフはトムセングラフと呼ばれることもある^{[12] 。}${\displaystyle K_{3,3}}$${\displaystyle K_{3,3}}$

3 つの効用問題は次のように述べることができます。

3 軒の住宅をそれぞれ水道会社、ガス会社、電気会社に接続し、各住宅から各会社に別々の線を引く必要があるとします。9 つの接続すべてを、線が交差することなく行う方法はあるでしょうか。

この問題は、実際の工学的状況では存在しない制約を課す抽象的な数学パズルである。その数学的形式化は、グラフの面への埋め込みを研究する位相グラフ理論の分野の一部である。このパズルの重要な部分であるが、パズルの非公式な言葉遣いでは明示的に述べられないことが多いのは、家、会社、線がすべて平面の位相を持つ2次元面上に配置されなければならないこと、および線が他の建物を通過してはならないことである。これは、家や会社の図面を示し、同じ図面上に線として接続を描くように要求することで強制されることがある。^{[13] [14]}

より正式なグラフ理論の用語で言えば、問題は完全な二部グラフ が平面グラフであるかどうかを問うものである。このグラフには、3つの部分集合の2つの部分集合に6つの頂点があり、1つの頂点が各家、もう1つの頂点が各ユーティリティである。9つの辺があり、家とユーティリティのペアごとに1辺、またはより抽象的には、一方の部分集合の頂点ともう一方の部分集合の頂点のペアごとに1辺がある。平面グラフは平面上で交差することなく描くことができるグラフであり、そのような描画が見つかれば、3つのユーティリティのパズルは解決する。^{[13] [14]}${\displaystyle K_{3,3}}$

通常（平らな2次元平面上）に提示される効用パズルの解答は「いいえ」です。つまり、9つの接続をすべて、どの線も交差させずに作成する方法はありません。言い換えると、グラフは平面ではありません。カジミエシュ・クラトフスキは1930年にグラフは非平面であると述べており、^[15]そこから、この問題には解答がないことがわかります。しかし、クルマン（1979）は、「興味深いことに、クラトフスキは[ ]が非平面であるという詳細な証明を発表しませんでした」と述べています。^[2]${\displaystyle K_{3,3}}$${\displaystyle K_{3,3}}$${\displaystyle K_{3,3}}$

の平面埋め込みを見つけることが不可能であることの証明の1つは、ジョルダン曲線定理を含む事例分析を使用する。^[16]この解決法では、グラフの4サイクルに対する頂点の位置のさまざまな可能性を調べ、それらがすべて平面埋め込みと矛盾していることを示しています。^[17]${\displaystyle K_{3,3}}$

あるいは、頂点と辺を持つ任意のブリッジレス 二部平面グラフが を持つことを、オイラーの公式(ここでは平面埋め込みの面の数) と、面の数は最大で辺の数の半分であるという観察 (各面の周りの頂点は家とユーティリティの間で交互にならなければならないため、各面は少なくとも 4 つの辺を持ち、各辺はちょうど 2 つの面に属している) を組み合わせることによって示すことも可能です。ユーティリティ グラフでは であり、したがってユーティリティ グラフでは は真ではありません。この不等式を満たさないため、ユーティリティ グラフは平面ではありません。^[18]${\displaystyle V}$${\displaystyle E}$${\displaystyle E\leq 2V-4}$ ${\displaystyle V-E+F=2}$${\displaystyle F}$${\displaystyle E=9}$${\displaystyle 2V-4=8}$${\displaystyle E\leq 2V-4}$

${\displaystyle K_{3,3}}$はトーラスグラフであり、種数1の面であるトーラス上に交差することなく埋め込むことができる。 ^{[19]これらの埋め込みは、家や会社が平面ではなく}コーヒーマグなどの表面に描かれたバージョンのパズルを解きます。 ^[20]トーラス上には、4つの家と4つのユーティリティを持つバージョンのパズルを解くのに十分な自由度もあります。^{[21] [5]同様に、3つのユーティリティのパズルが透明素材のシート上に提示されている場合、シートをねじって接着し、}メビウスの帯を形成した後に解くことができます。^[22]

ヘンリー・デュドニーが提案した、パズルのルールを変えて解けるようにするもう一つの方法は、公共設備の配線が、接続している家や公共設備以外の家や設備を通過できるようにすることである。^[3]

効用パズル以外にも、剛性理論、ケージと十分に被覆されたグラフの分類、グラフ交差数の研究、グラフマイナーの理論など、他のいくつかの数学的な文脈で同じグラフが登場します。 ${\displaystyle K_{3,3}}$

ユーティリティ グラフはラマン グラフです。つまり、平面上の頂点の配置のほとんどすべてにおいて、平面全体の剛体運動以外ですべての辺の長さを保存しながら頂点を連続的に動かす方法はなく、また、その全域のサブグラフのいずれも同じ剛体特性を持ちません。これは非平面ラマン グラフの最小の例です。^[23]最小限の剛体グラフであるにもかかわらず、頂点の特別な配置による非剛体埋め込みがあります。^{[9] [24]}一般位置埋め込みの場合、同じ辺の長さを持つすべての可能な配置を記述する多項式方程式の次数は 16 です。つまり、一般に同じ長さの配置は最大 16 個あります。この方程式の解の最大 8 つが実現可能な配置を記述する辺の長さのシステムを見つけることが可能です。^[24]${\displaystyle K_{3,3}}$

${\displaystyle K_{3,3}}$は三角形のないグラフで、すべての頂点にはちょうど3つの隣接頂点があります（立方体グラフ）。このようなグラフの中では、これが最小のグラフです。したがって、これは（3,4）ケージであり、頂点ごとに3つの隣接頂点を持ち、最短閉路の長さが4である最小のグラフです。^[25]

他の完全な二部グラフと同様に、これは十分に被覆されたグラフであり、すべての最大独立集合は同じサイズであることを意味します。このグラフでは、2つの最大独立集合のみが二分割の両側にあり、サイズが等しくなります。は、わずか7つの3正則3連結の十分に被覆されたグラフの1つです。 ^[26]${\displaystyle K_{3,3}}$

平面グラフの2つの重要な特徴付け、すなわち、平面グラフは も完全グラフも部分として含まないグラフであるというクラトフスキーの定理と、平面グラフは もマイナーも含まないグラフであるというワグナーの定理は、 の非平面性を利用し、一般化している。 [ ^27]${\displaystyle K_{3,3}}$ ${\displaystyle K_{5}}$${\displaystyle K_{3,3}}$${\displaystyle K_{5}}$${\displaystyle K_{3,3}}$

パル・トゥランの「レンガ工場問題」は、より一般的には、頂点の数と二分グラフの両側における完全な二部グラフの描画における交差数の最小値を求める式を求めている。効用グラフは、交差が1 つだけのグラフを描くことはできるが、交差が 0 のグラフを描くことはできないため、交差数は 1 である。^{[5] [28]} ${\displaystyle K_{a,b}}$${\displaystyle a}$${\displaystyle b}$${\displaystyle K_{3,3}}$

• Cut-the-knotの 3 つのユーティリティ パズル
• Archimedes-lab.orgでユーティリティ パズルが説明され、「解決」されました
• ワイスタイン、エリック W.、「ユーティリティ グラフ」、MathWorld