Tři domy a tři studně

Tři domy a tři studně 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.

Problém z hlediska teorie grafů

Z hlediska teorie grafů lze úlohu přeformulovat na otázku, zde je úplný bipartitní graf $K_{3,3}$ 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ě $K_{3,3}$, 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ť $K_{3,3}$ 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ů).

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

Externí odkazy

• Obrázky, zvuky či videa k tématu tři domy a tři studně na Wikimedia Commons
  • Lokální šablona odkazuje na jinou kategorii Commons než přiřazená položka Wikidat:
    • Lokální odkaz: Utility graph
    • Wikidata: Three utilities problem