Wszystko... jest liczbą

Historycy nauki za początek teorii grafów (będącej częścią topologii) uznają rozwiązanie w 1736 roku przez Leonharda Eulera (1707-1783) tzw. problemu mostów w Królewcu. W Królewcu rzeka Pergoła podzieliła miasto na 4 dzielnice. W XVIII wieku połączone były one siedmioma mostami. Euler, spacerując po mieście zastanawiał się nad tym, czy można odbyć taki spacer, w czasie którego  przez każdy most przejdzie on dokładnie jeden raz.

Euler sprowadził problem do abstrakcyjnego schematu, w którym kropki oznaczały dzielnice, a linie zastępowały mosty. W ten sposób pokazał, że dla rozwiązania problemu nie mają znaczenia ani kształt mostów ani wielkość dzielnic, a tylko sposób w jaki są połączone. Wykazał, że odbycie takiego spaceru nie jest możliwe. Metoda użyta przez Eulera stała się podstawą dla rozwoju teorii grafów, działu matematyki, który obecnie wykorzystywany jest np. w informatyce, planowaniu produkcji, transporcie i genetyce. 

Na wystawie można przeprowadzić eksperyment o podobnym schemacie jak XVIII-wieczny problem mostów w Królewcu, używając makiety, na której znajdują się mosty.

Można przedstawić ten problem w formie uproszczonego schematu, w którym kropki oznaczają dzielnice, a linie zastępują mosty. Wędrówkę da się odbyć, gdy z każdej kropki (z wyjątkiem co najwyżej dwóch) wychodzi parzysta liczba linii. A jak należałoby ustawić dodatkowy most, aby taki spacer był możliwy?

Układając sznurek, wyznaczasz dla komiwojażera trasę, dzięki której, wyjeżdżając z Krakowa, odwiedzi on wszystkie oznaczone miasta i powróci do punktu startu. Zadaniem jest znalezienie najkrótszej trasy.

Problem komiwojażera należy do klasy problemów, w których złożoność obliczeń wraz ze wzrostem liczby miast szybko rośnie. Znalezienie szybkiego algorytmu rozwiązania któregokolwiek problemu z tej grupy znajduje się na liście problemów milenijnych ogłoszonych przez Instytut Matematyczny Claya w 2000 roku. Rozwiązanie każdego z nich zostanie uhonorowane nagrodą w wysokości 1 miliona dolarów.

Graf składa się z wierzchołków połączonych krawędziami. Na każdym z grafów należy tak poprowadzić sznurek, aby:

1. przechodził dokładnie jeden raz przez wszystkie krawędzie,
2. przechodził dokładnie jeden raz przez wszystkie wierzchołki.

Dla grafu spójnego, czyli takiego, w którym dla dowolnych dwóch wierzchołków istnieje ścieżka, która je łączy (a takie są grafy w naszych przykładach), mogą istnieć dwie specjalne ścieżki.

Ścieżka Eulera to ścieżka, która przechodzi dokładnie jeden raz przez wszystkie krawędzie grafu. Jeśli ścieżka kończy się w punkcie startu to taki graf nazywamy cyklem Eulera. Ścieżka Eulera odpowiada rysowaniu figury bez odrywania ołówka od papieru. Cykl Hamiltona to ścieżka, która przechodzi dokładnie jeden raz przez każdy wierzchołek grafu i kończy się w punkcie startu (nie musi przechodzić przez wszystkie krawędzie).

Łamigłówkę tworzą cztery kostki, których ścianki pomalowane są na cztery różne kolory. Należy je ustawić w wieżę w taki sposób, aby z każdej strony wieży było widać cztery różne kolory.

Z pozoru zadanie to wydaje się bardzo łatwe. Jednak każda z kostek jest inna i można wieżę ułożyć na 41 472 sposobów. A to oznacza, że rozwiązanie zadania metodą prób i błędów– często stosowaną z sukcesem – może trwać bardzo długo. Natomiast jeśli opiszemy poszczególne kostki przy pomocy grafów, wtedy rozwiązanie można znaleźć bardzo szybko.