Domy a studny

Problém tří domů a tří studní je klasická matematická hádanka : položte neprotínající se cesty od každé ze tří studní ke každému ze tří domů . Formulace problému je připisována Eulerovi . V moderní literatuře se někdy vyskytuje v následující podobě: je možné položit potrubí (objímky) ze tří zdrojů - dodávky elektřiny, plynu a dodávky vody (" voda, plyn, elektřina ") do každého ze tří domů bez přejezd v letadle .

Hádanka nemá řešení: topologická teorie grafů, která studuje vnoření grafů do ploch , dává zápornou odpověď na otázku možnosti zobrazení odpovídajícího grafu v rovině bez křížení hran.

Kompletní bipartitní graf představující problém se nazývá „ domy a studny “, „ graf užitku “ , Thomsenův graf [1] . $K_{{3,3}}$

Formalizace

Z hlediska teorie grafů se problém redukuje na otázku rovinnosti úplného bipartitního grafu . Tento graf je ekvivalentní cirkulujícímu grafu . Kazimir Kuratovsky v roce 1930 dokázal, že je neplanární, a proto problém nemá řešení [2] . $K_{{3,3}}$ $Ci_6(1;3)$ $K_{{3,3}}$

Jedním z důkazů nemožnosti najít ploché zapuštění je případová studie, která pomocí Jordanova teorému uvažuje o různých možnostech umístění vrcholů vzhledem k cyklům délky 4 a ukazuje, že jsou neslučitelné s požadavkem rovinnosti [3]. . Lze také ukázat, že pro jakýkoli bipartitní rovinný graf bez mostů s vrcholy a hranami , zkombinujeme-li Eulerův vzorec (zde počet ploch rovinného grafu) s pozorováním, že počet ploch nepřesahuje polovinu počtu ploch hrany (protože každá plocha má alespoň čtyři hrany a každá hrana patří právě dvěma plochám). Navíc v grafu : a , který porušuje nerovnost, takže tento graf nemůže být rovinný. $K_{{3,3}}$ $n$ $m$ $m \leqslant 2n - 4$ $n - m + f = 2$ $F$ $K_{{3,3}}$ $m = 9$ $2n - 4 = 8$

Neřešitelnost problému vyplývá přímo z každé z následujících důležitých vět o rovinných grafech: Kuratowského věta , podle níž rovinnými grafy jsou právě ty grafy, které neobsahují podgrafy homeomorfní k úplnému grafu , a Wagnerova věta , že rovinné grafy jsou přesné. , ty grafy, které neobsahují buď , nebo jako vedlejší , obsahují tento výsledek. $K_{{3,3}}$ $K_{5}$ $K_{{3,3}}$ $K_{5}$

Vlastnosti K 3,3

Graf je stejně jako všechny ostatní kompletní bipartitní grafy dobře pokrytý , což znamená, že všechny největší nezávislé množiny v tomto grafu mají stejnou velikost. V tomto grafu jsou pouze dvě největší nezávislé množiny - to jsou části bipartitního grafu a je zřejmé, že jsou si rovny. je jedním ze sedmi 3-běžných 3-spojených dobře pokrytých grafů [4] . $K_{{3,3}}$ $K_{{3,3}}$

Graf je lamanovský , což znamená, že tvoří minimální strukturální tuhost , když je zasazen do roviny (s průsečíky). Toto je příklad minimálního Lamanova grafu, zatímco jiný neplanární graf není minimálně rigidní. $K_{{3,3}}$ $K_{5}$

Variace a zobecnění

$K_{{3,3}}$ je toroidní , což znamená , že může být zabudováno do torusu . Ekvivalentní tvrzení je, že rod grafu je roven jedné, což znamená, že nemůže být vložen do povrchu s rodem menším než jedna. Povrch s rodem jedna je ekvivalentní torusu . $K_{{3,3}}$
- Zejména hlavolam o domech a studnách má řešení na povrchu hrnku (takové hrnky jsou dokonce k vidění v prodeji).

Zarankiewiczův problém , také známý jako problém cihelny Pal Turan , si klade obecnější otázku – najít vzorec pro minimální počet křížení v kresbě úplného bipartitního grafu v závislosti na číslechadvou částech grafu. Graflze nakreslit pouze s jedním křížením, ale ne s nulou, takže jeho počet křížení je jedna. Úkol souvisí s tím, že za války Turan pracoval v cihelně a z každé pece do každého skladu vedla úzkokolejka. Posouvat vozíky podél přejezdů je obtížné, proto problém: jak zmenšit přejezdy. $K_{{a,b}}$ $A$ $b$ $K_{{3,3}}$

Poznámky

↑ W. G. Brown. Na grafech, které neobsahují Thomsenův graf // Canadian Mathematical Bulletin. - 1966. - T. 9 . — S. 281–285 . - doi : 10.4153/CMB-1966-036-2 .
↑ Výsledek je důsledkem obecnějšího faktu stanoveného Kuratovským - Kuratovského věta ; V ruskojazyčné literatuře se tvrdí, že důkaz této skutečnosti poprvé našel Pontrjagin v roce 1927, ale nebyl včas publikován.
↑ Richard J. Trudeau. Úvod do teorie grafů. - Opravená, rozšířená republika .. - New York: Dover Pub., 1993. - s. 68–70. - ISBN 978-0-486-67870-2 .
↑ S. R. Campbell, M. N. Ellingham, Gordon F. Royle. Charakterizace dobře pokrytých kubických grafů // Journal of Combinatorial Mathematics and Combinatorial Computing. - 1993. - T. 13 . — S. 193–212 .

Odkazy

Weisstein, Eric W. Graf užitečnosti (anglicky) na webu Wolfram MathWorld .
The Utilities Puzzle // Archimedes-lab.org
3 Pomůcky Puzzle // cut-the-uzel
Jim Loy. Důkaz, že Impossible Puzzle is Impossible. Archivováno z originálu 20. ledna 2007.