Czy uda się przejść przez mosty?

Czy można po siedmiu mostach łączących dzielnice Królewca z wyspą na Pregole odbyć spacer w ten sposób, by przejść kolejno przez wszystkie mosty nie przechodząc po żadnym z nich więcej niż jeden raz?

Powyższy problem można rozwiązać stosując tak zwaną teorię grafów. Graf jest strukturą matematyczną, za pomocą której przedstawia się relacje występujące pomiędzy pewnymi, rozważanymi w zadaniu obiektami.

W takiej reprezentacji każdy graf składa się z dwóch zbiorów. Pierwszy z nich to zbiór wierzchołków, gdzie każdy z nich jest pojedynczym obiektem. Drugi z nich to zbiór krawędzi, a każda z nich opisuje dokładnie jedną relację pomiędzy dwoma obiektami. W grafach istotny jest sposób połączenia pomiędzy poszczególnymi wierzchołkami. Dokładniej w niektórych przypadkach sama kolejność / kierunek łączenia poszczególnych wierzchołków ma znaczenie ponieważ można w ten sposób oddać sposób relacji między obiektami. Dlatego wyróżnia się podstawowe dwa rodzaje grafów: skierowane oraz nieskierowane.

Teoria grafów jest jednym z działów matematyki często wykorzystywanych do modelowania zjawisk biologicznych. Warto by tu wspomnieć modele grafowe wykorzystywane w sekwencjonowaniu DNA, modelowaniu drzew filogenetycznych, czy przewidywaniu funkcji białek jak również w modelowaniu łańcuchów pokarmowych.

Kolejnym ważnym przykładem jest problem komiwojażera, którego celem jest znalezienie najkrótszej, najtańszej lub najszybszej drogi pomiędzy określonymi punktami, przyjmując że zaczyna się ona i kończy w tym samym punkcie. Przełożenie tego problemu na przykład na ilość paliwa, jakie zużyje kurier podczas rozwożenia paczek jest wystarczającym powodem aby dogłębniej analizować tego typu problemy.

Korzystając ze strony Kalejdoskopu Matematycznego nieświadomie korzystasz z teorii grafów. Zazwyczaj strona internetowa ma więcej niż jedną podstronę. Większość z nich jest połączona pomiędzy sobą aby można było płynnie przechodzić z jednej na drugą (na przykład za pomocą menu). Każde takie połączenie jest realizowane za pomocą linku, który ze swojej natury działa jednokierunkowo, dlatego każdą strukturę strony można opisać za pomocą grafu skierowanego.

Cały Internet teoretycznie da się opisać za pomocą jednego wielkiego grafu albo sieci wielu podgrafów!!!