Teoria grafów to relatywnie młoda dziedzina matematyki. Za pierwszą rozprawę w jej ramach uznaje się opis zagadnienia mostów Królewieckich z 1741 roku. Autor pracy, Leonard Euler, dał w niej jednoznaczną odpowiedź na pytanie, czy da się przejść przez wszystkie 7 mostów w mieście Królewiec (ówcześnie Königsberg, wchodzący w skład Prus) w taki sposób, aby przez każdy most przejść tylko jeden raz.
Poprzez przedstawienie problemu za pomocą grafu, gdzie mosty stanowią krawędzie, a ląd wierzchołki, udowodnił, że jest to niemożliwe. Jednocześnie sformułował pierwszą zasadę teorii grafów: aby przejście po wszystkich krawędziach tylko raz było możliwe, graf musi mieć dokładnie 0 lub 2 wierzchołki stopnia nieparzystego (stopień wierzchołka jest równoznaczny z liczbą krawędzi wychodzących z wierzchołka).
Z pozoru, oryginalny problem może nie wydawać się istotny. Jednak różne jego warianty – w tym znalezienie najkrótszego cyklu Hamiltona (cykl w grafie przechodzący przez każdy wierzchołek dokładnie raz) – są absolutnie krytyczne w przypadku logistyki. Dla przykładu, rozwiązanie słynnego problemu komiwojażera, polegającego właśnie na znalezieniu minimalnego cyklu Hamiltona, pomaga optymalizować sposób, w jaki kurierzy rozwożą przesyłki, natomiast firmy spedycyjne dobierają zlecenia w taki sposób, aby ciężarówki pokonywały jak najmniejsze dystanse bez ładunku (np. graf zysków ze zleceń z ujemnymi wartościami na krawędziach, przedstawiającymi koszty przejazdu bez ładunku).
Poza maksymalizacją przychodów dla firm, z teorii grafów korzystamy także na co dzień za sprawą nawigacji, która odnajduje najkrótszą lub najszybszą (uwzględniając ograniczenia prędkości i natężenie ruchu) trasę, gdziekolwiek zmierzamy, oszczędzając nasz czas i paliwo.
Znajomość teorii grafów przydaje się również w informatyce. Niektóre zależności, takie jak relacje międzyludzkie, znacznie lepiej jest przedstawić za pomocą grafu. Wiele baz danych korzysta właśnie z modelu grafowego, zamiast klasycznego, opartego na tabelach. Takie podejście może znacząco przyspieszyć wszelkie operacje wyszukiwania, a co za tym idzie – zaoszczędzić zasoby komputera, oczywiście pod warunkiem, że poprawnie wykorzysta się dobrą teorię.
Zastosowanie teorii grafów jest wyjątkowo częstym rozwiązaniem problemów związanych z branżą gamedevu, czyli programowaniem gier komputerowych (ang. „game development”). Jak przeciwnicy mają odnaleźć ścieżkę do gracza? Jak połączyć lokalizacje na wygenerowanej mapie? Który element interfejsu został wybrany? To tylko kilka z przykładów gdzie zastosowanie teorii grafów może znacząco ułatwić pisanie kodu lub przyspieszyć działanie gry.
Jak widać po przytoczonych przykładach, znajomość teorii grafów może przynieść znaczne korzyści życia codziennego. Natomiast zrozumienie podstaw jest wymagane w przypadku chęci zgłębienia bardziej złożonych tematów, gdzie np. model klasycznych sieci neuronowych można przedstawić za pomocą grafu skierowanego, co znacząco pomaga w jego wizualizacji.
Dla tych, którzy chcą wiedzieć więcej:
Autor: Paweł Olszewski
Linki do źródeł:
https://pl.wikipedia.org/wiki/Teoria_graf%C3%B3w
https://pl.wikipedia.org/wiki/Zagadnienie_most%C3%B3w_kr%C3%B3lewieckich
https://pl.wikipedia.org/wiki/Graf_eulerowski
https://pl.wikipedia.org/wiki/%C5%9Acie%C5%BCka_Hamiltona
https://pl.wikipedia.org/wiki/Problem_komiwoja%C5%BCera
https://en.wikipedia.org/wiki/Graph_database
https://en.wikipedia.org/wiki/Neural_network_(machine_learning)
