Tři domy a tři studně

Tři domy a tři studně[1][2][3] je hlavolam z oboru rekreační matematiky a zároveň úloha z teorie grafů.

Neformální zadání

Jsou dány tři domy a tři studně. Lze od každého z domů vést cestičku ke každé studni, aniž by se tyto cestičky zkřížily?

Jiná znění stejného zadání

Zejména v anglicky mluvícím světě je oblíbené zadání úlohy jako problému inženýrských sítí, respektive problému vody, plynu a elektřiny: Plyn, voda a elektřina se mají zavést z plynárny, vodárny a elektrárny do tří domků tak, aby se nikde roury a kabely nekřížily.[4]

Problém z hlediska teorie grafů

Z hlediska teorie grafů lze úlohu přeformulovat na otázku, zde je úplný bipartitní graf rovinným grafem.

Řešení a varianty

Neumožňuje-li zadání nějaký trik a jedná-li se tedy o výše vyslovený problém existence rovinného nakreslení v rámci teorie grafů, je odpověď záporná (takové propojení neexistuje), neboť v rámci teorie grafů říká Kuratowského věta, že obsahuje-li graf jako podgraf právě , není rovinným.

Řešení na ploše toru

Pokud by zadání nevyžadovalo kreslit graf do roviny, ale na libovolnou plochu, je možné realizovat propojení bez křížení na povrchu toru (neboť je toroidní graf).

V zadání s inženýrskými sítěmi lze realizovat trik, kdy se sice sítě nekříží mimo domky, ale v rámci jednoho domku jsou sítě přivedeny jen k vnějším zdem a jedna ze sítí tak může projít na své cestě do cílového domku skrz jeden z jiných domků, přičemž sítě nekříží (úloha pak ovšem neodpovídá té z teorie grafů).[4]

Nakreslení s jediným křížením

Zadání může být formulováno také jako otázka, jaký je minimální nutný počet křížení. V tom případě je odpověď 1, neboť stačí jediné křížení.

Odkazy

Reference

  1. ŠIŠMA, Pavel. Teorie grafů, 1736–1963. Praha: Prometheus (nakladatelství), 1997. Dostupné online. Kapitola Problém čtyř barev, barvení grafů, rovinné grafy. 
  2. SEDLÁČEK, Jiří. O jednom extrémním rovinném grafu. Časopis pro pěstování matematiky. 1956, roč. 81, čís. 4. Dostupné online. 
  3. ZELINKA, Bohdan. Rovinné grafy. Praha: Mladá fronta, 1977. Dostupné online. Kapitola Tři domy, tři studně a muří noha aneb věta Kuratowského. 
  4. a b ŠIMSA, Jaroslav. Veletucet her, hlavolamů a hádanek. Praha: YMCA, 1939. Dostupné online. Kapitola První tucet hlavolamů. 

Externí odkazy

Média použitá na této stránce

K33 one crossing.svg
The utility graph K3,3 drawn with only a single crossing, showing that its crossing number is one.
Solución en un toroide.png
Autor: Ignacio Zelaya, Licence: CC BY-SA 4.0
Solution to the "Three utility problem", using the surface of a toroid.

Torus plot created with gnuplot: set parametric set hidden3d set view 45 set isosamples 90,40

splot [-pi:pi][-pi:pi] cos(u)*(cos(v)+4), sin(u)*(cos(v)+4), sin(v)