Przeskocz do treści

Delta mi!

Loading

Kafelkowanie prostokątów i grafy planarne

Marcin Kotowski i Michał Kotowski

o artykule ...

  • Publikacja w Delcie: październik 2014
  • Publikacja elektroniczna: 01-10-2014
  • Autor: Marcin Kotowski
    Afiliacja: Institute for Quantum Computing, Waterloo, Kanada
    Autor: Michał Kotowski
    Afiliacja: Institute for Quantum Computing, Waterloo, Kanada

Zajmijmy się następującym klasycznym zadaniem: należy pokryć kwadrat jednostkowy kwadratowymi kafelkami o różnych bokach tak, aby żadne dwa kafelki nie nachodziły na siebie. Czytelnik może spróbować poszukać takiego kafelkowania metodą prób i błędów, ale na pierwszy rzut oka nie jest jasne, czy pokrycie o żądanych własnościach w ogóle istnieje...

A nawet jeśli istnieje, to nie wiadomo, jak wiele kafelków trzeba użyć. Okazuje się, że zadanie ma elegancką interpretację w językach teorii grafów planarnych i sieci elektrycznych, która pomoże nam odpowiedzieć na te pytania.

obrazek

Rys. 1

Rys. 1

Zacznijmy od ogólniejszej sytuacji: dany jest prostokąt wykafelkowany kwadratami, na razie niekoniecznie różnymi - na przykład tak jak na rysunku 1. Kafelkowaniu przyporządkowujemy jego graf incydencji, czyli każdemu maksymalnemu poziomemu odcinkowi (być może złożonemu z boków kilku kwadratów) przypisujemy wierzchołek, a każdemu kafelkowi krawędź, w taki sposób, że krawędź odpowiadająca danemu kwadratowi łączy wierzchołki odpowiadające przeciwległym poziomym bokom tego kwadratu. Łatwo przekonać się, że powstały graf jest planarny, to znaczy można go narysować na płaszczyźnie tak, że nie ma przecinających się krawędzi.

Okazuje się, że konstrukcję tę można odwrócić, czyli przekształcać grafy planarne w kafelkowania. Żeby to zrobić, będziemy traktować taki graf jak obwód elektryczny. Przypomnimy najpierw podstawowe prawa dotyczące przepływu prądu w obwodzie.

Jeśli do dwóch punktów obwodu złożonego z oporników podłączymy baterię, na każdym oporniku wytworzy się różnica napięć i przepływ prądu zgodne z prawem Ohma:

display-math

gdzie math to różnica potencjałów, math - natężenie prądu, a math - opór.

Załóżmy, że każda krawędź ma taki sam opór. Niech math oznacza natężenie prądu płynącego po krawędzi od wierzchołka math do math (a więc math). Bezpośrednio z prawa Ohma wnioskujemy, że dla dowolnego cyklu math w obwodzie suma natężeń prądów na tym cyklu jest równa zeru:

display-math

Z kolei prawo Kirchhoffa mówi, że w każdym wierzchołku math suma natężeń prądów jest zerowa:

display-math

gdzie sumujemy po wszystkich wierzchołkach math sąsiadujących z math

obrazek

Niech teraz math będzie dowolnym grafem planarnym. Będziemy myśleć o math jako o obwodzie elektrycznym, w którym każda krawędź ma jednostkowy opór. Wybierzmy w dowolny sposób dwa różne wierzchołki math położone na zewnętrznej ścianie grafu. Podłączmy do nich baterię generującą jednostkową różnicę potencjałów - możemy bez straty ogólności przyjąć math math W ten sposób w każdym wierzchołku math otrzymamy pewną wartość potencjału elektrycznego math a na każdej krawędzi math przepływ prądu math (bo opór na krawędzi jest jednostkowy).

obrazek

Rys. 2

Rys. 2

Kafelkowanie prostokąta odpowiadające grafowi math konstruujemy w następujący sposób. Niech math będzie krawędzią, dla której math Przyporządkowujemy jej kwadrat, którego dolny i górny brzeg znajdują się odpowiednio na wysokościach math i math (a więc długość jego boku jest równa math). Aby otrzymać kafelkowanie, musimy jednak określić jeszcze, gdzie każdy kwadrat jest umieszczony w poziomie. Tu przychodzi nam z pomocą konstrukcja grafu dualnego. Dla grafu planarnego math graf dualny math jest określony następująco: wierzchołki math odpowiadają ścianom math (łącznie z zewnętrzną, nieograniczoną ścianą), przy czym dwa z nich są połączone krawędziami (Rys. 2), jeśli odpowiadające im ściany sąsiadują w math Czyli każdej krawędzi math w math odpowiada dualna krawędź math w math a ściany w math odpowiadają wierzchołkom w math Możemy narysować math tak: w każdej ścianie math zaznaczamy punkt, a następnie dla każdej krawędzi math rysujemy krawędź grafu dualnego łączącą punkty odpowiadające ścianom po obu jej stronach. Zwróćmy uwagę na to, że w ten sposób otrzymujemy nie tylko abstrakcyjną strukturę grafu dualnego, ale również pewien jego rysunek na płaszczyźnie. Na przykład wszystkie drzewa o math krawędziach będą miały takie same abstrakcyjne grafy dualne (jeden wierzchołek z math pętlami), ale otrzymane reprezentacje na płaszczyźnie będą zależały od struktury (i wybranego rysunku!) drzewa.

Zauważmy teraz, że maksymalne pionowe odcinki w kafelkowaniu odpowiadają dokładnie ścianom w jego grafie incydencji. Ponadto z definicji maksymalne poziome odcinki odpowiadają wierzchołkom grafu incydencji. Ponieważ w grafie dualnym wierzchołki przechodzą na ściany, ściany na wierzchołki, a każda krawędź na krawędź, widzimy, że graf dualny jest niemal grafem incydencji kafelkowania obróconego o 90 stopni.

Należy jeszcze poradzić sobie z pewną niedogodnością: boki wyjściowego prostokąta odpowiadają ścianie zewnętrznej w grafie incydencji. Dodajmy więc do grafu math specjalną krawędź math między biegunami math i math W grafie dualnym math bieguny baterii przykładamy między końcami krawędzi dualnej math a następnie usuwamy ją. Z powyższej obserwacji o obracaniu kafelkowania otrzymujemy przepis na współrzędne poziome kafelków: są one wyznaczone dokładnie przez natężenia prądów na krawędziach "poprawionego" grafu dualnego. Czytelnik Wnikliwy zapyta z pewnością, dlaczego taki wybór daje dobry układ kafelków, tzn. dlaczego nie ma w nim "dziur". Sprawdź, Czytelniku, że zapewnia to prawo Kirchhoffa!

obrazek

Każdemu grafowi planarnemu z wybranymi biegunami odpowiada zatem kafelkowanie prostokąta za pomocą kwadratów. Możemy przyjąć, że pionowy bok tego prostokąta ma długość 1. Jaka jest długość poziomego boku? To suma długości boków kafelków przylegających do niego, czyli suma natężeń prądów wypływających z bieguna baterii. Ponieważ math to z prawa Ohma wynika, że suma ta jest równa odwrotności oporu zastępczego między math i math w grafie math Kafelkowanie kwadratu dostaniemy dokładnie wtedy, kiedy opór zastępczy będzie równy 1.

Wobec tego podaliśmy właśnie metodę znajdowania wszystkich możliwych kafelkowań kwadratu za pomocą parami różnych kafelków: należy znaleźć wszystkie grafy planarne o tej własności, że po przyłożeniu napięcia jednostkowego między pewnymi dwoma wierzchołkami opór zastępczy między nimi będzie równy math a natężenia prądów na krawędziach będą niezerowe i parami różne. Korzystając z tej charakteryzacji, znaleziono, oczywiście używając komputera, liczne nowe przykłady kafelkowań kwadratów i innych prostokątów. Ich galerię można znaleźć na stronie http://www.squaring.net.

Na zakończenie wspomnijmy o jeszcze jednym nieoczekiwanym związku. Chcąc znaleźć wszystkie kafelkowania ustalonego prostokąta, wystarczy ograniczyć się do kafelkowań prostych, to znaczy takich, których nie da się podzielić pionowym odcinkiem na dwa rozłączne kafelkowania. Chwila zastanowienia pokazuje, że warunek ten jest równoważny 3-spójności grafu incydencji.

Pochodzące z kombinatoryki wielościanów twierdzenie Steinitza mówi, że math-spójne grafy planarne to dokładnie szkielety wypukłych trójwymiarowych wielościanów. Czytelnik Wnikliwy może się więc zastanowić, jakiemu kafelkowaniu odpowiada jego ulubiony wielościan.

Notice: Undefined index: story_alias_uuid in /home/misc/deltami/public_html/ui/inc/site_php_include/index.inc on line 23 Notice: Undefined index: story_alias_uri in /home/misc/deltami/public_html/ui/inc/site_php_include/index.inc on line 24