Przeskocz do treści

Delta mi!

Elektryzująca metryka pingpongowa

Michał Szurek

o artykule ...

  • Publikacja w Delcie: lipiec 2014
  • Publikacja elektroniczna: 01-07-2014
  • Autor: Michał Szurek
    Afiliacja: Instytut Matematyki, Wydział Matematyki, Informatyki i Mechaniki, Uniwersytet Warszawski
obrazek

Wśród wielu typów zagadnień matematycznych bardzo sobie cenię takie, które po wierzchu są elementarne, łatwe na początku i dające się rozwiązać nietypowymi, efektownymi, niecodziennymi metodami. Dobrze jest też, gdy zadania te są wierzchołkiem pewnej góry lodowej, albo – stosując inne porównanie – są początkiem ścieżki wiodącej nas w nieznane.

Zadanie 1. Mamy sześcian (a raczej jego szkielet), wykonany z drutu. Do przeciwległych wierzchołków sześcianu podłączono prąd. Wyznaczyć opór zastępczy układu. Zakładamy, że opór każdej krawędzi wynosi math

Jest to bardzo łatwe zadanie dla każdego, kto choć trochę zna prawa rządzące przepływem prądu. Nasuwa się od razu oczywiste uogólnienie: jak to jest dla innych wielościanów i ogólniej: dla innych układów. W latach sześćdziesiątych XX wieku wiele uwagi poświęcił podobnym zagadnieniom matematyk brytyjski i kanadyjski Crispin Alvah Nash-Williams (1932-2001).

Związek z geometrią dostrzegli tu przed stu laty E.E. Brooks i A.W. Poyser w książce Magnetism and Electricity. Jeden z najbardziej znanych popularyzatorów matematyki, Charles Wilderman Trigg 1898-1989),  wracał do tego zadania kilkakrotnie, głównie na łamach Journal of Recreational Mathematics. Z jego artykułu w tym magazynie z roku 1981 pochodzi zadanie o oporze dla przeciwległych wierzchołków kostki dowolnego wymiaru. Potem zadanie zaczęło żyć własnym życiem i obrastać w teorię. Z zagadnieniami tymi można się zapoznać w sieci, na przykład pod hasłem resistance distance, co ja tłumaczę jako „odległość elektryczna”.

Od pewnego czasu wielościany (w szczególności foremne) sklejam z piłeczek pingpongowych. Jakoś lepiej mi się myśli, gdy mogę wziąć w rękę taki model. Stąd się wziął ten dziwny tytuł artykułu. Załączam zdjęcie sześcianu nad Giewontem.

Definicja. Niech math będzie grafem spójnym. Wyobraźmy sobie, że krawędzie jego są wykonane z materiału dobrze przewodzącego prąd i że dana jest oporność każdej krawędzi. Dla dowolnych dwóch wierzchołków grafu określamy ich odległość elektryczną jako opór zastępczy całego układu, gdy do wierzchołków tych podłączony jest prąd.

Z praw dotyczących przepływu prądu otrzymujemy natychmiast, że dla każdych trzech wierzchołków math  odległość między math i  math  jest nie większa niż suma odległości między math i  math  oraz między math  i  math  Znaczy to, że tak określona odległość elektryczna jest rzeczywiście odległością w sensie matematycznym i zbiór wierzchołków grafu tworzy pewną przestrzeń metryczną, a konkretniej nawet wielościan.

Zadanie może być sprowadzone do algebry. Mamy bowiem prawa Kirchhoffa:

I prawo Kirchhoffa. Suma natężeń prądów wpływających do węzła i z niego wypływających jest równa zeru. Inaczej mówiąc, ładunek elektryczny nie jest gromadzony w węźle.

II prawo Kirchhoffa. Suma spadków napięć na elementach obwodu zamkniętego jest równa zeru.

Mamy do dyspozycji też prawo Ohma oraz reguły rządzące opornością najprostszych typów połączeń oporników. Dla połączeń szeregowych opór zastępczy jest sumą oporów składowych, dla połączeń równoległych przepustowość układu jest równa sumie przepustowości składników. Przez przepustowość układu rozumiemy tu odwrotność oporu.

Równania Kirchhoffa nie są zwykle skomplikowane – jest ich jednak dużo. Gdzie tylko można, należy od nich uciekać, najczęściej odwołując się do geometrii. Możliwe to jest tam, gdzie układ cechuje pewna symetria. Rozpatrzmy uogólnienie zadania 1.

Zadanie 2. Wyznaczyć opór zastępczy układu, gdy wejście i wyjście (źródło i ujście prądu) są przeciwległymi wierzchołkami kostki math-wymiarowej.

Rozwiązanie. Wierzchołki odległe o tyle samo (w sensie odległości „po grafie”) od tych punktów mają te same potencjały, więc nie popłynie między nimi prąd. Dzięki temu możemy je utożsamić, co prowadzi do układu połączonych ze sobą szeregowo math podukładów połączeń równoległych. Pozostaje określić, ile jest przewodów w każdym z tych połączeń równoległych. Jeżeli napięcie przyłożone jest w  math a ujście jest w  math to wierzchołki są równoważne, gdy mają tę samą sumę współrzędnych. Proste rozumowanie kombinatoryczne pokazuje, że liczba krawędzi wynosi kolejno math gdzie math Na przykład, dla sześcianu mamy kolejno 3, 6 i 3 połączenia, dla kostki wymiaru 4 mamy kolejno 4, 12, 12 i 4 połączenia. Wynika stąd (po łatwych obliczeniach), że opór zastępczy układu jest równy

display-math

Opór ten maleje wykładniczo wraz z wymiarem math Czy jest to zgodne z naszą intuicją? Powinno być: chociaż odległość między skrajnymi punktami rośnie liniowo, to liczba połączeń rośnie wykładniczo.


Przykład 1. Interesujące matematycznie jest zadanie obliczenia oporu zastępczego szkieletu kostki math-wymiarowej, gdy źródło i ujście znajdują się w sąsiednich wierzchołkach

Pełne wyliczenie pozostawimy Czytelnikowi. Wynik brzmi: math Opór ten maleje wraz ze wzrostem math ale dość wolno. Znów możemy się zastanowić, czy jest to zgodne z intuicją.

Często radzę uczniom i studentom tak: zmień fabułę zadania (nie zmieniając jego treści matematycznej) na inną, nawet żartobliwą lub niepoważną. Zrób to, po pierwsze, dla samego ćwiczenia. Otrzymasz – w terminologii wybitnego matematyka holenderskiego Hansa Freudenthala – zadanie izomorficzne. Po drugie, a nuż po takim przeformułowaniu zadanie będzie wyglądać ciekawiej i może nawet łatwiej się rozwiąże.

obrazek

Wielu ludzi z pokolenia autora artykułu ma sentyment do kolei, najlepiej starych, parowych, wlokących się dostojnie po szynach na drewnianych podkładach. No to przełóżmy zadanie na język „kolejowy”, zamieniając je na problem przepustowości sieci. Rozważę przypadek math Spójrzmy jeszcze raz na diagram oczami dyspozytora kolejowego, który ma wysłać 96 wagonów ze stacji math  do stacji math  tak, by znalazły się tam w jak najkrótszym czasie. Ma on do dyspozycji sieć stacji pośrednich math Czarne liczby 1, 3, 6 umieszczone na trasie oznaczają przepustowość danej
linii. Za jednostkę przepustowości weźmiemy odwrotność czasu przejazdu jednego wagonu. Przepustowość 3 oznacza zatem, że w jednostce czasu da się tym odcinkiem linii przesłać trzy wagony.

Dla młodszych Czytelników niech będą narty. Możemy sobie wyobrazić, że math to podnóże góry, math – wierzchołek a diagram to sieć wyciągów. Niektóre z nich są wolniejsze, inne szybsze. Na przykład na odcinku math posuwamy się 3 razy wolniej niż na math  i  math  a sześć razy wolniej niż na math  i  math  Na dole czeka 96 narciarzy. Jak najszybciej wwieźć ich wszystkich na górę? Liczy się oczywiście czas, po którym ostatni narciarz wjedzie na górę.

obrazek

Rozwiążemy zadanie w interpretacji narciarskiej. 45 narciarzy wjeżdża trasą math (czyli Stąd-Dotąd), jeden po drugim. Zajmuje im to łącznie 45 minut. Pozostałych 51 narciarzy w 17 minut osiąga math (na rysunku: drugi poziom). Tu rozdzielają się, 33 jedzie do  math; przy przepustowości 3 zajmuje im to 11 minut. W tym samym czasie 11 minut 15 turystów dociera do punktu math trasą math  a trzech trasą math  Po 45 minutach wszyscy spotykają się na górze. Wyciągi pracowały bez przestojów, zatem jest to najlepszy możliwy czas wykonania zadania. Wyciągi przewiozły zatem 96 turystów w 45 minut, co daje przepustowość math turysty na minutę. Przepustowość to odwrotność oporu, zadanie rozwiązane, odpowiedź jest zgodna z podaną wcześniej.

Metryką elektryczną zainteresowali się fizycy i chemicy (zwłaszcza krystalografowie). Odkryto metody algebraiczne, pozwalające na obliczenie wszystkich odległości elektrycznych dla konkretnego grafu. Niestety, obliczenia są skomplikowane. Należy bowiem rozważyć wszystkie połączenia w grafie, co prowadzi do rozważania macierzy o kilkunastu czy nawet kilkudziesięciu wierszach i kolumnach i obliczania ich macierzy odwrotnych, a to zawsze było skomplikowane rachunkowo. Ale my poprzestańmy na prostych grafach, gdzie – zabierając dziecku zabawkę – możemy bawić się kolejką elektryczną.