Problem z trzema narzędziami - Three utilities problem

Problem trzech mediów. Czy każdy dom może być podłączony do każdego narzędzia bez przecinania się linii połączeniowych?
W samolocie potrzebne jest jedno przejście

Klasyczna zagadka matematyczna znana jako problem trzech narzędzi ; problem z trzema domkami lub czasem z wodą, gazem i elektrycznością można określić następująco:

Załóżmy, że w samolocie (lub kuli) są trzy domki i każdy z nich musi być podłączony do firmy wodociągowej, gazowej i elektrycznej. Bez korzystania z trzeciego wymiaru lub wysyłania jakichkolwiek połączeń przez inną firmę lub domek, czy istnieje sposób na wykonanie wszystkich dziewięciu połączeń bez przecinania się żadnej z linii?

Problemem jest abstrakcyjna zagadka matematyczna, która narzuca ograniczenia, które nie istniałyby w praktycznej sytuacji inżynierskiej. Jest częścią matematycznej dziedzinie topologicznej teorii wykres , który bada się osadzanie na wykresach na powierzchni . Ujmując bardziej formalnie teorię grafów , problem dotyczy tego, czy pełny dwudzielny graf K 3,3 jest planarny . Ten wykres jest często nazywany wykresem użyteczności w odniesieniu do problemu; nazywano go również wykresem Thomsena .

Historia

Przegląd historii problemu trzech mediów przedstawia Kullman (1979) . Twierdzi, że większość opublikowanych odniesień do problemu określa go jako „bardzo stary”. W najwcześniejszej publikacji znalezionej przez Kullmana, Henry Dudeney  ( 1917 ) nazwał ją „wodą, gazem i elektrycznością”. Jednak Dudeney twierdzi, że problem jest „stary jak wzgórza ... znacznie starszy niż oświetlenie elektryczne , a nawet gaz ”. Dudeney opublikował również tę samą łamigłówkę wcześniej, w The Strand Magazine w 1913 roku.

Inna wczesna wersja problemu polega na podłączeniu trzech domów do trzech studni. Jest to podobne do innej (i możliwej do rozwiązania) łamigłówki, która również obejmuje trzy domy i trzy fontanny, przy czym wszystkie trzy fontanny i jeden dom dotykają prostokątnej ściany; łamigłówka ponownie polega na tworzeniu nieprzekraczających się połączeń, ale tylko między trzema wyznaczonymi parami domów i studni lub fontann, jak w nowoczesnych łamigłówkach numberlink .

Matematycznie, problem ten może być sformułowane rysunków wykresu z całkowitym dwuczęściowego wykresie K 3,3 . Ten wykres pojawia się wcześnie w Hennebergu (1908) . Ma sześć wierzchołków podzielonych na dwa podzbiory po trzy wierzchołki i dziewięć krawędzi, po jednej na każdy z dziewięciu sposobów łączenia wierzchołka z jednego podzbioru z wierzchołkiem z drugiego podzbioru. Problem trzech narzędzi polega na tym, czy ten wykres jest grafem planarnym .

Rozwiązanie

Wykres użyteczności, znany również jako wykres Thomsena lub K 3,3
Dowód bez słów : jeden dom zostaje tymczasowo usunięty. Linie łączące pozostałe domy z mediami dzielą samolot na trzy regiony, zacieniowane na żółto, czerwono i niebiesko. Niezależnie od regionu, w którym znajduje się usunięty dom, narzędzie o podobnym kolorze znajduje się poza regionem. Krzywa Jordana stwierdza, że linia łącząca je musi przecinać jeden z istniejących linii.

Jak to zwykle się przedstawia (na płaskiej dwuwymiarowej płaszczyźnie), rozwiązanie zagadki użytkowej brzmi „nie”: nie ma możliwości wykonania wszystkich dziewięciu połączeń bez przecinania się linii. Innymi słowy, wykres K 3,3 nie jest płaski. Kazimierz Kuratowski stwierdził w 1930 r., Że K 3,3 jest niepłaski, z czego wynika, że ​​problem nie ma rozwiązania. Kullman stwierdza jednak, że „Co ciekawe, Kuratowski nie opublikował szczegółowego dowodu, że [ K 3,3 jest] niepłaski”.

Jeden dowód na niemożność znalezienia płaskiego osadzenia K 3,3 wykorzystuje analizę przypadku obejmującą twierdzenie o krzywej Jordana . W tym rozwiązaniu rozpatruje się różne możliwości lokalizacji wierzchołków w odniesieniu do 4 cykli wykresu i pokazuje, że wszystkie są niespójne z osadzaniem planarnym.

Alternatywnie, można wykazać, że każdy bezmostkowy dwustronny graf planarny z wierzchołkami V i krawędziami E ma E ≤ 2 V - 4 , łącząc wzór Eulera V - E + F = 2 (gdzie F jest liczbą ścian płaskiego osadzenia ) z obserwacją, że liczba ścian wynosi co najwyżej połowę liczby krawędzi (wierzchołki wokół każdej ściany muszą być naprzemiennie rozmieszczone między domami i obiektami użyteczności publicznej, więc każda ściana ma co najmniej cztery krawędzie, a każda krawędź należy dokładnie do dwóch ścian). Na wykresie użyteczności E  = 9 i 2 V  - 4 = 8 , naruszając tę ​​nierówność, więc wykres użyteczności nie może być płaski.

Uogólnienia

K 3,3 wylosowany tylko z jednym skrzyżowaniem.
Rozwiązanie problemu z trzema narzędziami w torusie.

Dwie ważne charakterystyki grafów planarnych, twierdzenie Kuratowskiego, że grafy planarne są dokładnie grafami, które nie zawierają ani K 3,3, ani pełnego grafu K 5 jako podziału, oraz twierdzenie Wagnera, że grafy planarne są dokładnie grafami, które nie zawierają ani K 3 , 3 ani K 5 jako małoletni , wykorzystują i uogólniają niepłaski K 3,3 .

K 3,3 to wykres toroidalny , co oznacza, że ​​można go osadzić bez skrzyżowań na torusie . Jeśli chodzi o problem trzech domków, oznacza to, że problem można rozwiązać, wykonując dwa otwory w płaszczyźnie (lub kuli) i łącząc je rurą. Zmienia to właściwości topologiczne powierzchni, a użycie rurki pozwala na połączenie trzech domków bez przekraczania linii. Równoważne stwierdzenie mówi, że rodzaj wykresu wykresu użyteczności jest jeden, a zatem nie może być osadzony w powierzchni rodzaju mniejszego niż jeden. Powierzchnia rodzaju jeden jest równoważna torusowi. Toroidalny osadzanie K 3,3 można otrzymać przez zastąpienie przejście przez rurę, jak opisano powyżej, w którym dwa otwory, w których łączy się rurę do płaszczyzny są umieszczone wzdłuż jednej krawędzi przejściach po obu stronach skrzyżowania. Innym sposobem zmiany zasad układanki jest zezwolenie liniom użyteczności na przejście przez domki lub instalacje; ta dodatkowa swoboda pozwala rozwiązać zagadkę.

Problem fabryki cegieł Pála Turána prosi bardziej ogólnie o wzór na minimalną liczbę skrzyżowań na rysunku pełnego wykresu dwudzielnego K a , b w kategoriach liczby wierzchołków a i b po obu stronach dwudzielnego . Wykres użyteczności K 3,3 można narysować tylko z jednym skrzyżowaniem, ale nie z zerami, więc jego numer przecięcia wynosi jeden.

Inne właściwości teorii grafów

Wykres użyteczności K 3,3 jest wykresem cyrkulacyjnym . Jest to (3,4) -cage , najmniejszy wykres sześcienny bez trójkątów . Podobnie jak wszystkie inne pełne wykresy dwudzielne , jest to dobrze pokryty wykres , co oznacza, że ​​każdy maksymalny niezależny zestaw ma ten sam rozmiar. Na tym wykresie jedyne dwa maksymalne niezależne zbiory to dwie strony dwupartycji i oczywiście są one równe. K 3,3 to jeden z zaledwie siedmiu dobrze zakrytych wykresów z 3 regularnymi 3 połączeniami .

Jest to również wykres Lamana , co oznacza, że ​​tworzy minimalnie sztywny system, gdy jest osadzony (z przecięciami) w płaszczyźnie. Jest to najmniejszy przykład niepłaskiego grafu Lamana, ponieważ inny minimalny niepłaski graf, K 5 , nie jest minimalnie sztywny.

Bibliografia

Zewnętrzne linki