Tekst źródłowy strony Domki i studnie

[[Plik:Water gaz electricity Dudeney.jpg|thumb|Ilustracja zagadki z książki ''{{j|en|Amusements in mathematics}}''{{odn|Dudeney|1917}}]]
'''Domki i studnie'''{{odn|Jaszuńska|2011}} – zagadka matematyczna, której współczesna wersja może mieć następujące brzmienie:
{{Cytat
 |treść = Na kartce (płaszczyźnie) są 3 domki i 3 firmy (doprowadzające wodę, prąd i gaz). Bez użycia trzeciego wymiaru i bez przechodzenia przez domki ani przez firmy, doprowadź wodę, prąd i gaz do każdego domku, tak aby linie się nie przecięły.
 |autor = Marta Bilska
 |źródło = Korepetycje z Martą<ref>{{Cytuj |autor = Marta Bilska |tytuł = Rozwiązanie zagadki o trzech domkach |praca = Korepetycje z Martą |opublikowany = [[YouTube]] |data = 16 lutego 2016 |data dostępu = 2018-04-24 |język = pl |url = https://www.youtube.com/watch?v=XwOvF_fGF00}}</ref>
 |styl = środek
}}

Formalnie łamigłówka odpowiada na pytanie czy pełny [[graf dwudzielny]] <math>K_{3,3}</math> jest [[Graf płaski|płaski]]{{odn|Jaszuńska|2011}}.

== Historia ==
Przegląd historii zagadki podał David E. Kullman w 1979 stwierdzając, że większość publikacji na temat tego problemu określa go jako „starożytny”{{odn|Kullman|1979|s=299}}. Najwcześniejszą wersję, którą odnalazł Kullman, opublikował Henry Ernest Dudeney w 1917{{odn|Dudeney|1917}}. Tę samą zagadkę Dudeney opublikował wcześniej w 1913 w ''[[The Strand Magazine]]'' podkreślając, że jest ona bardzo stara, lecz ją uwspółcześnił dzięki zastosowaniu „wody, gazu i elektryczności”{{odn|Dudeney|1913}}.

W innych starych wersjach zagadki należało wytyczyć ścieżki od trzech domów do trzech studni<ref>{{Cytuj |tytuł = Puzzle |url = https://books.google.com/books?id=yLSTwH0pINIC&q=%22three+houses+and+three+wells%22&dq=%22three+houses+and+three+wells%22&hl=en&sa=X&ved=0ahUKEwiS-aHrteXNAhVD9mMKHYXNBWo4FBDoAQg2MAY |czasopismo = Successful Farming |data = 1914 |wolumin = 13 |s = 50 |język = en}}</ref>, kościoła, knajpy i studni<ref>{{cytuj |url = http://www.mini.pw.edu.pl/~tomtracz/md/md_grafy_w_13.pdf |tytuł = Wykład 13. Grafy planarne |data dostępu = 2020-02-08}}</ref> lub gołębnika, studni i [[Bróg|brogu]]<ref>{{Cytuj |autor = Jerzy Mioduszewski |tytuł = Wykłady z topologii. Topologia przestrzeni euklidesowych |miejsce = Katowice |wydawca = Wydawnictwo Uniwersytetu Śląskiego |data = 1994 |s = 33 |kropka=za [[Hugo Steinhaus]], ''[[Kalejdoskop matematyczny]]'', 1956, s. 261.}}</ref>.

Zagadka stała się motywacją w [[Teoria grafów|teorii grafów]] nad wprowadzeniem pojęcia [[Graf planarny|grafu planarnego]]<ref>{{Cytuj |autor = Sudev Naduvath |tytuł = Lecture notes on graph teory |rozdział = 7. Planar Graphs |wydawca = Centre for Studies in Discrete Mathematics |miejsce = Thrissur, India |data = 2017 |isbn = 9789352911479 |s = 81 |url = https://books.google.pl/books?id=Mg5DDwAAQBAJ&pg=PA81&lpg=PA81 |język = en}}</ref>.

== Rozwiązanie ==
[[Plik:Biclique K 3 3.svg|thumb|150px|Graf <math>K_{3,3}</math>]]
Nie istnieje rozwiązanie pozwalające na wyznaczenie dziewięciu połączeń, w którym linie by się nie przecinały{{odn|Jaszuńska|2011}}. Treść zagadki sprowadza się do utworzenia pełnego [[graf dwudzielny|dwudzielnego grafu]] <math>K_{3,3}</math>{{odn|Jaszuńska|2011}}. Dowód nierozwiązywalności zagadki sprowadza się do wykazania, że <math>K_{3,3}</math> nie jest [[Graf planarny|planarny]]{{odn|Jaszuńska|2011}}. Ów graf wraz z <math>K_5</math> są elementarnymi grafami nieplanarnymi{{odn|Jaszuńska|2011}}. W 1930 [[Kazimierz Kuratowski]] opublikował [[Twierdzenie Kuratowskiego|twierdzenie]], w którym stwierdził, że graf jest planarny jeśli nie zawiera w sobie <math>K_{3,3}</math> lub <math>K_5</math>{{odn|Kuratowski|1930}}.

{{Clear}}

== Inne powierzchnie ==
Możliwość rozrysowania grafu bez przecięć zależy od rozmaitości topologicznej, na której jest on umieszczany{{odn|Sydow}}. Takim przykładem jest [[Torus (matematyka)|torus]], na którym graf <math>K_{3,3}</math> można narysować bez przecinających się linii{{odn|Sydow}}.
[[Plik:Solución en un toroide.png|thumb|center|250px|Rozwiązanie zagadki na torusie]]

== Przypisy ==
{{Przypisy}}

== Bibliografia ==
* {{Cytuj |autor = Joanna Jaszuńska |tytuł = Domki i studnie |czasopismo = Delta |numer = 8 |data = sierpień 2011 |s = 25 |url = https://deltami.edu.pl/2011/08/domki-i-studnie/ |język = pl |odn = tak}}
* {{Cytuj |autor = David E. Kullman |tytuł = The Utilities Problem |czasopismo = Mathematics Magazine |wolumin = 52 |numer = 5 |data = listopad 1979 |język = en |s = 299–302 |jstor = 2689782 |odn = tak}}
* {{Cytuj |autor = Henry Ernest Dudeney |rozdział = 251. – Water, gas and electricity |tytuł = Amusements in mathematics |data = 1917 |s = 73 |url = https://archive.org/stream/amusementsinmath00dude#page/72/mode/2up |odn = tak}}
* {{Cytuj |autor = Henry Dudeney |tytuł = Perplexities, with some easy puzzles for beginners |czasopismo = [[The Strand Magazine]] |data = 1913 |wolumin = 46 |s = 110 |url = https://archive.org/stream/TheStrandMagazineAnIllustratedMonthly/TheStrandMagazine1913bVol.XlviJul-dec#page/n119/mode/2up |odn = tak}}
* {{Cytuj |autor = [[Kazimierz Kuratowski]] |data = 1930 |url = http://matwbn.icm.edu.pl/ksiazki/fm/fm15/fm15126.pdf |tytuł = Sur le problème des courbes gauches en topologie |czasopismo = Fund. Math. |wolumin = 15 |s = 271–283 |język = fr |odn = tak}}
* {{Cytuj |rozdział = Inne powierzchnie |autor = Marcin Sydow |tytuł = Grafy i Zastosowania. 7: Planarność |url = http://users.pja.edu.pl/~msyd/giz/planarnosc7.pdf |s = 17 |odn = tak}}

== Linki zewnętrzne ==
* {{Cytuj |url = https://www.youtube.com/watch?v=xBkTIp6ajAg |tytuł = Planar Graphs |praca = Numberphile |opublikowany = [[YouTube]] |data = 11 listopada 2019 |data dostępu = 2019-11-12 |język = en}}
* {{MathWorld | adres=UtilityGraph | tytuł=Utility Graph | data dostępu=2020-12-17}}

{{Kontrola autorytatywna}}

[[Kategoria:Topologiczna teoria grafów]]
[[Kategoria:Rozrywka matematyczna]]
[[Kategoria:Zagadki]]