Mosty królewieckie
Narodziny teorii grafów datuje się na rok 1736, kiedy to czołowy matematyk ówczesnych czasów Leonhard Euler opublikował pracę, w której zawarł rozwiązanie słynnego problemu siedmiu mostów królewieckich.
Przez Królewiec przepływała rzeka Pergoła, w której rozwidleniach znajdowały się dwie wyspy. Ponad rzeką przerzucono siedem mostów, z których jeden łączył obie wyspy, a pozostałe mosty łączyły wyspy z brzegami rzeki. Problemem którym zajmował się Euler brzmiał następująco.
- Czy można odbyć spacer po siedmiu mostach w taki sposób, by przejść przez wszystkie mosty, nie przechodząc po żadnym z nich dwukrotnie i powrócić do punktu wyjścia?
W języku grafów to zagadnienie jest równoznaczne pytaniu, czy graf przedstawiający całą sytuację jest eulerowski? Oczywiście nie można poprowadzić w takim grafie cyklu Eulera, a mówi o tym twierdzenie Eulera które poznaliśmy wcześniej. Było to pierwsze twierdzenie teorii grafów, którego sformułowanie dało solidne podstawy do dalszego badania jeszcze młodej w tamtych czasach dziedziny matematyki.
Technologie informatyczne
Teoria grafów jest szczególnie związana z informatyką i właśnie tutaj ma obecnie największe zastosowanie. W poprzedniej części poznaliśmy podstwowe algorytmy grafowe.
W inforamtyce teoria grafów jest często używana do projektowania struktury witryn internetowych. Na przykład dana część strony może zostać przedstwiona jako wierzchołek, a hiperłącza do innych stron za pomocą krawędzi grafu. W ten sposób uzyskuje się obraz całej witryny.
Teoria grafów może okazać się użyteczna w wielu innych problemach. Na przykład, dzięki algorytmowi znajdowania minimalnego drzewa spinającego o wiele łatwiej jest znaleźć optymalne połączenia drogowe dla całego miasta bądź kraju. Wyszukanie najszybszej trasy w systemach GPS również nie powinno stanowić problemu, jeśli zastosuje się odpowiedni algorytm. Nawet systemy sztucznej inteligencji w niektórych grach komputerowych wyszukują najlepszą drogę dla sterowanych przez program postaci w oparciu o pracę algorytmów grafowych.
Fizyka i chemia
Grafy są przydatne także przy badaniach budowy materii. W fizyce trójwymiarowe symulacje zachowania skomplikowanych struktur atomów są uruchamiane poprzez wygenerowanie odpowiedniego grafu, który przedstawi ułożenie atomów. Takie symulacje idealnie odwzorowują zachowanie materii w realnym świecie, a to przekłada się na zwiększenie dokładności przeprowadzonych badań.
W neurologii graf może przedstawiać funkcjonowanie całego ukłądu nerwowego. Jeśli za wierzchołki przyjmiemy wybrane obszary mózgu, natomiast połączenia między nimi oznaczymy krawędziami, to uzyskany obraz będzie odpowiadał prawdziwej strukturze nerwów. Następnie można przprowadzić symulację komputerową działania całego systemu, w oparciu o stworzoną mapę.
Podobnie w chemii grafy pozwalają w łatwy sposób przedstwić budowę cząsteczki większości substancji chemicznych. Wykorzystuje sie to między innymi w tzw. edytorach molekuł, czyli programów komputerowych stworzonych do modyfikowania struktur chemicznych.
