Grafami możemy nazwać zbiór kropek i kresek 🙂 Niezbyt to naukowe więc poprawie się. Grafy to zbiór wierzchołków i krawędzi. Krawędzie łączą wierzchołki. Zbiór wierzchołków oznaczamy zazwyczaj Vg – od Vertx a zbiór krawędzi oznaczamy Eg – Edges.
Grafy możemy podzielić na proste i skierowane. Te drugie mają po prostu kierunki opisujące krawędzie. Czyli jest to para uporządkowana dwóch wierzchołków i łączącego je krawędzi (ma początek i koniec). Jest jeszcze multigraf czyli dana para wierzchołek i krawędź może występować wielokrotnie, powtarzać się np. tzw pętla lub krawędź wielokrotna.
Jak sprawdzić czy grafy są jednakowe ?
Izomorficzność grafów sprawdzamy czy ilość krawędzi wychodzących z danego wierzchołka jest identyczna. Analogicznie w grafach skierowana tylko tu liczy się jeszcze początek i koniec czyli to czy wierzchołek jest nada tym samym początkiem (lub końcem) wierzchołka. Czasami możemy spotkać się z określeniem funkcji bijekcji, która jest wzajemnie jednoznaczna. Sprawdzenie czy grafy są izomorficzne polegać będzie w głównej mierze na nadaniu numerów wierzchołków i sprawdzenie czy z wierzchołków w drugim grafie o identycznym numerze wychodzi tyle samo krawędzi.
Kilka pojęć z tzw. słowniczka grafów.
Wierzchołek V jest incydentny z krawędzią e gdy e = { v,w } (czyli krawędź wychodzi lub wchodzi do wierzchołka V)
Wierzchołki są sąsiednie jeśli są incydentne z tą samą krawędzią (analogicznie z krawędziami).
Stopień wierzchołka – liczba krawędzi incydentnych. (pętle liczymy podwójne).
Izomorfizm zachowuje stopnie wierzchołków.
Graf nazywamy pełnym dwudzielnym jeśli istnieją dwa zbiory rozłączne wierzchołków V1 i V2 takie że każdy wierzchołek ze zbioru V1 łączy się z każdym wierzchołkiem ze zbioru V2 ale nie łączą się wzajemnie wewnątrz zbiorów V1 i V2. Trochę zakręcone ale rysunek wszystko wyjaśnia.
Podgraf F grafu H to taki graf, którego krawędzie i wierzchołki stanowią podzbiór wierzchołków i krawędzi grafu H.
Możemy wykonać kilka podstawowych operacji na grafach jak:
- suma grafów
- dodanie wierzchołka
- usunięcie wierzchołka – przy czym usuwając wierzchołek musimy również usunąć krawędzie incydentne z nim
- dodanie krawędzi
- dopełnienie grafu – zostawiamy wierzchołki a wszystkie krawędzie zastępujemy krawędziami, których wcześniej w grafie nie było
- ściągnięcie krawędzi – chyba najbardziej skomplikowana operacja z w/w. Ściągnięcie krawędzi polega na połączeniu wierzchołków incydentnych ze ściąganą krawędzią a sama krawędź jest usuwana. Poniżej operacja ściągnięcia krawędzi e.
Na koniec pozostaje jeszcze podstawowe pytanie – gdzie się nam to przyda ??
Grafy mają swoje zastosowanie wszędzie tam gdzie są jakieś połączenia 🙂 Czyli będą to:
- sieci społecznościowe
- mapy, transport itp.
- cząstki, kryształy
- sieci komputerowe
- diagramy, drzewa decyzyjne
- importy w kodzie (kompilator sprawdza graf importów żeby nie było importu do importu)
- przetwarzanie tekstu
- SQL i bazy danych