Artykuł ukazał się w Medical Maestro Magazine, Vol. 8, s./p. 1037-1184
Graf to pojęcie z zakresu matematyki i informatyki. Jest wykorzystywany do modelowania relacji pomiędzy pewnymi obiektami. Znajduje zastosowanie w wielu dziedzinach, takich jak: optymalizacja dyskretna, logistyka, logika, a także chemia, genetyka czy teoria gier, a nawet psychologia. Co decyduje o powszechności wykorzystania grafów i w jaki sposób łączą one tak wiele różnych obszarów nauki?
Zacznijmy od podstawowej definicji. Najprościej mówiąc, graf to zbiór wierzchołków połączonych krawędziami, które ilustrują pewien rodzaj relacji. Taką relacją może być np. bezpośrednie połączenie między miastami, dostawa towaru od dystrybutora do sklepu, znajomość pomiędzy pewnymi osobami, a także wizyta pacjenta u danego lekarza. Interpretacja wierzchołków będzie analogiczna: różne miasta, dostawcy i odbiorcy, znajomi, pacjenci i lekarze. Łączymy krawędziami te wierzchołki, które spełniają nasze wymagania, a więc będą to miasta, między którymi istnieje bezpośrednia trasa bądź dany dystrybutor i wszystkie zaopatrywane przez niego gabinety czy też zbiór wierzchołków-lekarzy, połączonych z tymi wierzchołkami-pacjentami, którzy byli u nich z wizytą. Po uzupełnieniu wszystkich połączeń otrzymamy graf, czyli przejrzysty rysunek rozpatrywanej sytuacji. Może być on mały optycznie lub ogromny, w zależności od poziomu skomplikowania relacji w danej sytuacji.
Wykorzystanie grafów do obrazowania planów zabudowy, ulic i skrzyżowań jest jednym z ich najbardziej naturalnych zastosowań. Dzięki ich użyciu Leonhard Euler rozwiązał słynny w historii problem mostów królewieckich. Problem brzmiał następująco: czy można przejść przez wszystkie mosty na rzece Pregoli tak, aby każdy z nich pokonać tylko jeden raz i na końcu powrócić do punktu wyjścia? Pozornie było to zadanie skomplikowane i trudne do rozwiązania, ponieważ musielibyśmy rozpatrzyć wszystkie możliwości przejścia mostów, ale posługując się teorią grafów jesteśmy w stanie odpowiedzieć na to pytanie niemal od razu.
Bardzo powszechnym wykorzystaniem – i interpretacją – grafów jest przedstawianie za ich pomocą sieci komunikacyjnych. Dzięki nim możemy relatywnie łatwo odnaleźć najkrótszą, najtańszą czy najszybszą do przebycia trasę. Na ich bazie zbudowane są sieci GPS. Wyszukując optymalną trasę, informatyczny system bierze pod uwagę przede wszystkim czas, jaki jest potrzebny na jej pokonanie, a to z kolei wymaga przeanalizowania możliwych optymalnych kombinacji. Grafy sprawdzają się także we wszelkich rodzajach schematów, np. obwodów elektrycznych czy w schematach blokowych. Innym przykładem mogą być wykorzystywane w informatyce sieci przepływowe, dla których szukamy maksymalnego przepływu „towarów” przez krawędzie sieci, przy uwzględnieniu ich przepustowości. Nie można też zapominać o informatyce, która robi z grafów bardzo duży użytek. Powstały i wciąż powstają algorytmy wyznaczające pewne ich własności, które służą do rozwiązywania wielu problemów o charakterze praktycznym.
Pacjent przechodzi wszystkie etapy leczenia jeden po drugim – skierowany zostaje do pierwszego specjalisty, później na badania, a następnie do kolejnych dwóch specjalistów.
Zastosowanie grafów do wyboru optymalnej trasy dobrze obrazuje opisywany problem komiwojażera. Mamy daną ilość miast (wierzchołków) połączonych drogami (krawędziami) o różnej długości. Komiwojażer ma za zadanie odwiedzić każde miasto tak, aby jego całkowita trasa była jak najkrótsza. Takie sformułowanie zadania wymusza zastosowanie grafu ważonego, a więc takiego, w którym każda krawędź ma przyporządkowaną „wagę”. Zależnie od interpretacji może to być dystans, koszt lub czas, jaki „zabiera” nam przejście z jednego wierzchołka do drugiego. Grafy w takim ujęciu pozwalają więc na wyszukiwanie optymalnych tras minimalizujących np. koszty przewiezienia towaru pomiędzy różnymi odbiorcami. Takie grafy mogą opisywać drogę ładunku, trasy lotniczej, a także ścieżki pacjenta do specjalisty.
