3つのユーティリティ問題
良い記事ですね。詳しくはこちらをクリックしてください。

平面上の3つのユーティリティ問題の図。すべての線はつながっていますが、2本は交差しています。
トムセングラフまたはK3、3{\displaystyle K_{3,3}}

水道・ガス・電気問題としても知られる三公益事業問題は、平面上で3軒の住宅と3つの公益事業会社の間に交差しない接続線を引くことを求める数学パズルです。20世紀初頭にこの問題を提起したヘンリー・デュードニーは、これはすでに古い問題であると記していました。これは不可能なパズルであり、9本の線すべてを交差させずに結ぶことは不可能です。トーラスやメビウスの帯などの非平面上の問題、あるいは他の住宅や公益事業を通過させる接続を可能にする問題は解くことができます。

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

K3、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 ]サム・ロイドも優先権を主張しており、彼の息子は死後に出版した伝記の中で、彼が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 ]。K3、3{\displaystyle K_{3,3}}K3、3{\displaystyle K_{3,3}}

声明

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

3軒の住宅をそれぞれ水道、ガス、電気会社に接続し、各住宅から各会社へ別々の線を引く必要があるとします。9つの線を交差させずに接続する方法はありますか？

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

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

パズルの解答

解決不可能

言葉なしの証明：1軒の家が一時的に削除されます。残りの家とユーティリティを結ぶ線は、平面を3つの領域に分割します。削除された家がどの領域に配置されても、同様に色分けされたユーティリティはその領域の外側にあります。ジョルダン曲線定理により、それらを結ぶ線は、既存の線のいずれかと必ず交差します。

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

の平面埋め込みを見つけることが不可能であることの証明の一つは、ジョルダン曲線定理を用いた事例分析である。[ 16 ]この解決法では、グラフの4閉路に対する頂点の位置の様々な可能性を調べ、それらが全て平面埋め込みと矛盾することを示す。[ 17 ]K3、3{\displaystyle K_{3,3}}

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

ルールを変える

メビウスの帯の解
トーラス上の解
トーラスは最大4つのユーティリティと4つの住宅を収容できる

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

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

ユーティリティグラフのプロパティ

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

剛性

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

その他のグラフ理論的性質

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

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

一般化

1つの交差点の描画K3、3{\displaystyle K_{3,3}}

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

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

参考文献

  1. ^ Gries, David ; Schneider, Fred B. (1993)、「第19章 グラフ理論」、A Logical Approach to Discrete Math、ニューヨーク：Springer、pp.  423– 460、doi：10.1007/978-1-4757-3837-7、ISBN 978-1-4419-2835-1、S2CID  206657798437ページを参照：「はユーティリティグラフとして知られています」。K3、3{\displaystyle K_{3,3}}
  2. ^ a bクルマン、デイヴィッド（1979）「効用問題」、数学雑誌、52（5）：299–302、doi：10.1080/0025570X.1979.11976807、JSTOR 2689782 
  3. ^ a bデュードニー、ヘンリー（1917）、「問題251：水道、ガス、電気」、数学の娯楽、第100巻、トーマス・ネルソン、p. 73、Bibcode：1917Natur.100..302.、doi：10.1038/100302a0、S2CID 10245524 200～201ページに示されている解決策では、他の家の1つに線を通します。
  4. ^デュードニー、ヘンリー（1913年）「Perplexities, with some easy puzzles for beginners」、ストランド・マガジン、第46巻、110ページ
  5. ^ a b cベイネケ、ローウェル；ウィルソン、ロビン（2010）「レンガ工場問題の初期の歴史」、数学インテリジェンサー、32（2）：41– 48、doi：10.1007/s00283-009-9120-4、MR 2657999、S2CID 122588849  
  6. ^ 「パズル」、サクセスフル・ファーミング、第13巻、50ページ、1914年; 「井戸と家のパズル」『ユース・コンパニオン』第90巻第2号392ページ、1916年。
  7. ^ 「32. 噴水パズル」『マジシャンズ・オウン・ブック、あるいは、手品の全技術』、ニューヨーク：ディック・アンド・フィッツジェラルド、1857年、276ページ
  8. ^ロイド、サム(1959)、「82: 喧嘩好きな隣人」、ガードナー、マーティン(編)、サム・ロイドの数学パズル、ドーバー・ブックス、p. 79、ISBN 9780486204987{{citation}}: CS1 メンテナンス: ISBN エラーを無視 (リンク)
  9. ^ a bディクソン, AC (1899)、「特定の変形可能なフレームワークについて」、メッセンジャー・オブ・マスマティクス、29 : 1–21、JFM 30.0622.02 
  10. ^ Henneberg, L. (1908)、「Diegraphische Statik der starren Körper」、Encyklopädie der Mathematischen Wissenschaften、vol. 4、345 ～ 434ページ 特に403ページを参照してください。
  11. ^ Thomsen, Julius (1886 年 7 月)、「DieConstitution des Benzols」(PDF)、Berichte der Deutschen Chemischen Gesellschaft、19 (2): 2944–2950、doi : 10.1002/cber.188601902285
  12. ^ Bollobás, Béla (1998), Modern Graph Theory , Graduate Texts in Mathematics, vol. 184, Springer-Verlag, New York, p. 23, doi : 10.1007/978-1-4612-0619-4 , ISBN 0-387-98488-7、MR  1633290
  13. ^ a bハラリー、フランク（1960）、「グラフ理論の歴史的および直感的な側面」、SIAMレビュー、2（2）：123– 131、Bibcode：1960SIAMR...2..123H、doi：10.1137/1002023、MR 0111698 
  14. ^ a b Bóna, Miklós (2011)、「組合せ論入門：列挙とグラフ理論」、World Scientific、pp.  275– 277、ISBN 9789814335232ボナは275ページでこのパズル（3つの井戸に繋がる3つの家の形）を紹介し、277ページでこれは「交差点のない平面に絵を描く問題と同じである」と書いている。K3、3{\displaystyle K_{3,3}}
  15. ^ Kuratowski、Kazimierz (1930)、「Sur le problème des courbes gauches en topologie」(PDF)、Fundamenta Mathematicae (フランス語)、15 : 271–283、doi : 10.4064/fm-15-1-271-283
  16. ^エアーズ, WL (1938)、「位相幾何学の基本的側面」、アメリカ数学月刊誌、45 (2): 88– 92、doi : 10.1080/00029890.1938.11990773、JSTOR 2304276、MR 1524194  
  17. ^ Trudeau, Richard J. (1993)、「グラフ理論入門」、Dover Books on Mathematics、ニューヨーク：Dover Publications、pp.  68– 70、ISBN 978-0-486-67870-2
  18. ^カプラフ、ジェイ（2001）、つながり：芸術と科学の間の幾何学的架け橋、K＆Eノットアンドエブリシングシリーズ、第25巻、ワールドサイエンティフィック、p.128、ISBN 9789810245863
  19. ^ Harary, F. (1964)、「位相グラフ理論における最近の成果」、Acta Mathematica、15 ( 3– 4): 405– 411、doi : 10.1007/BF01897149、hdl : 2027.42/41775、MR 0166775、S2CID 123170864  ; 409ページを参照。
  20. ^パーカー、マット（2015年）、第四次元で作るもの、やるべきこと：ナルシシズムの数、最適なデートアルゴリズム、少なくとも2種類の無限、その他を巡る数学者の旅、ニューヨーク：ファラー、ストラウス＆ジルー、pp.  180– 181, 191– 192、ISBN 978-0-374-53563-6、MR  3753642
  21. ^ O'Beirne, TH (1961年12月21日)、 「クリスマスのパズルとパラドックス、51：少年、男性、そして英雄たちへ」、ニューサイエンティスト、第12巻、第266号、 751-753ページ 
  22. ^ Larsen, Mogens Esrom (1994)、「私の迷路を誤解すると、私は惨めになるかもしれない」、Guy, Richard K. ; Woodrow, Robert E. (eds.)、 1986年8月、アルバータ州カルガリー大学で開催されたEugène Strens Memorial Conference on Recreational Mathematics and its History held at the University of Calgary, Calgary, Alberta, August 1986、MAA Spectrum、ワシントンD.C.：Mathematical Association of America、pp.  289– 293、ISBN 0-88385-516-X、MR  1303141292ページの図7を参照。
  23. ^ Streinu, Ileana (2005)、「擬似三角測量、剛性、および動作計画」、Discrete & Computational Geometry、34 (4): 587– 635、doi : 10.1007/s00454-005-1184-0、MR 2173930、S2CID 25281202  600ページを参照：「すべてのジェネリック最小剛性グラフが擬似三角分割として埋め込みを持つわけではない。なぜなら、すべてが平面グラフではないからだ。最小の例は」。K3、3{\displaystyle K_{3,3}}
  24. ^ a b Walter, D.; Husty, ML (2007)、「9節リンク機構について、その可能な構成と逆説的可動性の条件」(PDF)、Merlet, Jean-Pierre; Dahan, Marc (編)、第12回世界機構・機械科学会議 (IFToMM 2007)、国際機構・機械科学推進連盟
  25. ^ Tutte, WT (1947)、「立方体グラフの族」、ケンブリッジ哲学協会紀要、43 (4): 459– 474、Bibcode : 1947PCPS...43..459T、doi : 10.1017/s0305004100023720、MR 0021678、S2CID 123505185  
  26. ^ Campbell, SR; Ellingham, MN ; Royle, Gordon F. (1993)、「十分に被覆された立方グラフの特徴づけ」、Journal of Combinatorial Mathematics and Combinatorial Computing、13 : 193– 212、MR 1220613 
  27. ^ Little, Charles HC (1976), 「平面グラフに関する定理」, Casse, Louis RA; Wallis, Walter D. (編), Combinatorial Mathematics IV: Proceedings of the Fourth Australian Conference Held at the University of Adelaide August 27–29, 1975 , Lecture Notes in Mathematics, vol. 560, Springer, pp.  136– 141, doi : 10.1007/BFb0097375 , ISBN 978-3-540-08053-4、MR  0427121
  28. ^ Pach, János ; Sharir, Micha (2009)、「5.1 交差—レンガ工場問題」、組合せ幾何学とそのアルゴリズム的応用：アルカラ講義、数学概説およびモノグラフ、第152巻、アメリカ数学会、pp.  126– 127
「 https://en.wikipedia.org/w/index.php?title=Three_utilities_problem&oldid=1328169407」より取得