Dodatki (dział 1)
Zastosowania
Kiedy rozwój informatyki pozwolił na reprezentowanie grafów za pomocą komputera, okazało się, że algorytmy na nich oparte znajdują wiele praktycznych zastosowań. Szczególny rodzaj grafów zwanych drzewami okazał się przydatny do reprezentacji hierarchii. Przedstawione na rysunku obok drzewo binarne może opisywać np. mistrzostwa sportowe czy drzewo genealogiczne, a po dodaniu etykiet może służyć np. do tworzenia kodów Huffmana, do opisu rozwoju populacji bakterii w laboratorium albo niedeterministycznego automatu skończonego.
Kiedy komputery stały się powszechne okazało się, że grafy można zastosować w wielu problemach. Jako graf przedstawiono sieć dróg. Skrzyżowania stały się wierzchołkami grafu, a ulice jego krawędziami. Potem w podobny sposób przedstawiono sieci pomieszczeń i korytarzy w budynkach. Taka reprezentacja pozwoliła komputerom na poszukiwanie najlepszej drogi ze swojego obecnego położenia do pożądanego celu. Oprogramowanie oparte na algorytmach analizujących grafy znalazło zastosowanie w przenośnych urządzeniach PDA wyposażonych w GPS, które potrafią wskazać kierowcy trasę w nieznanym mieście.
Innym przykładem wykorzystania grafów stały się gry komputerowe, gdzie system sztucznej inteligencji musiał odszukać najlepszą drogę dla postaci sterowanych przez program, która pozwoli zaatakować ludzkiego przeciwnika. Sztuczna inteligencja mogła rozwiązać to zagadnienie tylko dzięki odpowiedniej reprezentacji mapy wirtualnego otoczenia jako grafu.
Projektanci robotów mobilnych również skorzystali z podobnych algorytmów, aby ich maszyny mogły bez udziału człowieka odnaleźć trasę w trudnym terenie. Przedstawienie sieci komputerowych w postaci grafów pozwoliło na stworzenie oprogramowania usprawniającego trasowanie w Internecie.
Aby zwiększyć wydajność pracy w dużych organizacjach, realizację zlecanych przez klientów zadań przedstawiono w postaci grafów. Pracownikom odpowiadać mogą wierzchołki, a przepływ zadań między nimi opisać można za pomocą krawędzi. Zaprojektowano oprogramowanie pozwalające automatycznie śledzić pracę tak opisanej organizacji, co miało służyć wzrostowi wydajności. Rozwiązania tego typu znalazły zastosowanie w działach wsparcia technicznego klientów dużych korporacji.
Uogólnienia
W hipergrafach krawędź może łączyć więcej niż dwa wierzchołki.
Geometryczny graf nieskierowany może być traktowany jako kompleks symplicjalny złożony z 1-sympleksów (krawędzi) i 0-sympleksów (wierzchołków). Tym samym kompleksy symplicjalne są uogólnieniem grafów, gdyż pozwalają też na większą liczbę wymiarów.
W teorii modeli graf jest szczególnym przypadkiem struktury matematycznej. W tym przypadku jednak nie ma ograniczenia na liczbę krawędzi: może to być dowolna liczba kardynalna.