Rodzaje grafów

https://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg

WPROWADZENIE

W wielu problemach spotykamy się z sytuacją, w której mamy do czynienia z pewnym zbiorem elementów, ale też z pewnym układem połączeń między parami tych elementów. Wtedy mogą pojawić się naturalne pytania. Czy istnieje droga między dwoma wyróżnionymi elementami, wykorzystująca istniejące połączenia? Ile elementów jest osiągalnych z wyróżnionego elementu? Jaka jest najkrótsza droga pomiędzy parą wyróżnionych elementów? Do modelowania takich sytuacji używamy abstrakcyjnych obiektów zwanych grafami (ang. graphs). Badaniem własności grafów zajmuje się teoria grafów, która jest działem matematyki i informatyki.

Przykłady zastosowań grafów.

• Mapy - połączenia drogowe, kolejowe, lotnicze między miastami.
• Dokumenty hipertekstowe.
• Obwody elektryczne.
• Planowanie - procesy produkcyjne, prace budowlane.
• Transakcje - sieci rozmów telefonicznych, transakcje kupna-sprzedaży.
• Sieci - sieci komputerowe, badanie odporności na uszkodzenia.
• Struktura programu - struktura wywołań funkcji.
• Relacje między ludźmi - zależności służbowe w firmie, znajomi na portalach społecznościowych.

Kilka uwag ogólnych.

• Grafy spotykane w praktycznych zastosowaniach mogą być ogromne, stąd wielka rola wydajnych algorytmów.
• Wydajność algorytmów zależy nie tylko od własności zbioru elementów grafu, ale także od własności zbioru połączeń między tymi elementami, oraz od globalnych własności grafu, które są implikowane przez te połączenia.
• Trudno jest precyzyjnie zdefiniować modele grafów, jakie możemy spotkać w rzeczywistości.

PODSTAWOWE DEFINICJE

Grafem G nazywamy parę (V,E), gdzie V to niepusty i skończony zbiór wierzchołków, a E to skończony zbiór krawędzi, czyli par wierzchołków z V × V. Symbolem n=|V| będziemy oznaczać liczbę wierzchołków, a symbolem m=|E| liczbę krawędzi. Wyróżnia się dwa główne typy grafów:

• Graf skierowany (ang. directed graph, digraph). Krawędź (a,b) ma kierunek od a do b, czyli jest to para uporządkowana. Na rysunku istnieje strzałka od a do b. Inne oznaczenia krawędzi to a-b lub ab.
• Graf nieskierowany (ang. undirected graph). Krawędź (a,b) jest równoważna krawędzi (b,a), czyli pary wierzchołków nie są uporządkowane. Na rysunku istnieje linia bez strzałek pomiędzy a i b. Można przyjąć, że w grafie nieskierowanym zawsze jednocześnie istnieją pary uporządkowane (a,b) i (b,a).
  Formalnie można wprowadzić relację równoważności w zbiorze par z VxV: (a,b)R(c,d) wtw (a=c i b=d) lub (a=d i b=c). Wtedy dostaniemy klasy równoważności par które będą krawędziami; pętla [(a,a)]_R = {(a,a)}; dla a ≠ b mamy [(a,b)]_R = {(a,b), (b,a)}.

NAZEWNICTWO

• Wierzchołek (vertex; vertices), węzeł (node; używane dla reprezentacji grafu), punkt (point).
• Krawędź (edge), linia (line), łuk (arc; w grafach skierowanych), wiązanie (link; używane do struktur danych).
• Podgrafem (ang. subgraph) nazywamy taki podzbiór wierzchołków i krawędzi danego grafu, który tworzy graf.
• Dwa grafy są izomorficzne (ang. isomorfic), jeżeli w wyniku zamiany etykiet wierzchołków w jednym grafie otrzymamy układ krawędzi identyczny jak w drugim. Rozstrzygnięcie, czy dwa grafy są izomorficzne, czy nie, jest skomplikowanym problemem obliczeniowym.

GRAFY SKIEROWANE

• Pętla (ang. self-loop) jest to krawędź łącząca wierzchołek z samym sobą, czyli krawędź typu (a,a).
• Graf prosty (ang. simple graph) nie ma pętli i krawędzi wielokrotnych (równoległych). Mówimy po prostu graf (bez przymiotników), choć niektórzy autorzy przez graf rozumieją ogólnie multigraf.
• Krawędź (a,b) jest wychodząca z wierzchołka a i wchodząca do wierzchołka b.
• Stopień wejściowy wierzchołka (ang. indegree) jest liczbą krawędzi do niego wchodzących. Stopień wyjściowy wierzchołka (ang. outdegree) jest liczbą krawędzi wychodzących z niego. Stopniem wierzchołka w grafie skierowanym nazywamy liczbę będącą sumą jego stopni: wejściowego i wyjściowego.
• Cormen pisze (str. 1194), że jeżeli w grafie istnieje krawędź (a,b) to wierzchołek b jest sąsiedni względem wierzchołka a. W grafie skierowanym nie jest to relacja symetryczna i chyba jest to trochę mylące.
• Cormen pisze (str. 1196), że dla danego grafu skierowanego możemy rozważyć jego wersję nieskierowaną. Wtedy z krawędzi "usuwamy skierowanie", a jeżeli początkowo istnieją dwie krawędzie skierowane (a,b) i (b,a), to stapiają się w jedną krawędź nieskierowaną (a,b) ≡ (b,a).

GRAFY NIESKIEROWANE

• Cormen na str. 1193 nie dopuszcza pętli (a,a) dla grafu nieskierowanego. Może to wynikać z tego, że krawędzie są zdefiniowane jako zbiory dwóch różnych wierzchołków (zbiory, aby nie było uporządkowania wierzchołków).
• Wierzchołki a i b są względem siebie sąsiednie (ang. adjacent), jeżeli istnieje krawędź (a,b) ≡ (b,a), która je łączy. Krawędź jest wtedy incydentna (ang. incident) z tymi wierzchołkami. Relacja sąsiedztwa jest symetryczna (a jest sąsiedni do b i b jest sąsiedni do a).
• Stopień wierzchołka grafu (ang. degree or valency) jest to liczba krawędzi incydentnych z tym wierzchołkiem.
• Cormen pisze (str. 1195), że dla danego grafu nieskierowanego możemy mówić o jego wersji skierowanej. Jest to graf skierowany, gdzie każda krawędź nieskierowana (a,b) ≡ (b,a) jest zastąpiona dwoma krawędziami skierowanymi (a,b) i (b,a).
• Multigraf (ang. multigraph) jest podobny do grafu nieskierowanego [Cormen str. 1196], ale zawiera wielokrotne krawędzie (ang. parallel edges).

ŚCIEŻKI I CYKLE

• Ścieżka (ang. path) długości k w grafie G=(V,E) jest to ciąg (zwykle różnych) wierzchołków (v_0,v_1,...,v_k) takich, że krawędzie (v_{i-1},v_i) należą do E dla i=1,2,...,k. Jest to ścieżka z wierzchołka v_0 do wierzchołka v_k. Ścieżka długości zero to ciąg jednoelementowy (v_0) - zawsze istnieje. W ogólności wierzchołki i krawędzie na ścieżce mogą się powtarzać. Mówimy, że ścieżka zawiera wierzchołki i krawędzie. [notacja a-b-c-d]
• Jeżeli istnieje ścieżka P z a do b, to mówimy, że wierzchołek b jest osiągalny z wierzchołka a po ścieżce P.
• Podścieżka ścieżki P jest ciągiem jej kolejnych wierzchołków.
• Ścieżka prosta (ang. simple path) to ścieżka, w której nie ma powtarzających się wierzchołków i krawędzi.
• Cykl (ang. cycle) jest to ścieżka (v_0,v_1,...,v_k), w której pierwszy i ostatni wierzchołek są takie same, v_0=v_k [notacja a-a, a-b-c-a].
• Cykl prosty jest to cykl, w którym wszystkie wierzchołki są różne, z wyjątkiem ostatniego, który jest równy pierwszemu.
• Dwie ścieżki są rozłączne (ang. disjoint), jeżeli nie posiadają żadnych wspólnych wierzchołków (ewentualnie poza wierzchołkami końcowymi).

WYBRANE KLASY GRAFÓW

• Graf pusty lub graf zerowy N_n (ang. null graph) to graf, którego zbiór krawędzi jest pusty, m=0. W implementacji grafów można przyjąć, że pusty graf to para składająca się z pustego zbioru wierzchołków i pustego zbioru krawędzi. W teorii zwykle nie zezwala się na istnienie pustych grafów, tzn. zakłada się, że przynajmniej zbiór wierzchołków musi być niepusty.
• Graf regularny stopnia k (graf k-regularny) to graf nieskierowany, w którym każdy wierzchołek ma taki sam stopień k.
• Graf pełny K_n (ang. complete graph) to graf prosty NIESKIEROWANY, w którym dla każdej pary wierzchołków istnieje krawędź je łącząca. Jeżeli graf pełny ma n wierzchołków, to posiada m=n(n-1)/2 krawędzi. Graf pełny jest grafem regularnym stopnia n-1. Dopełnienie (ang. complement) grafu G to graf pełny z takim samym zbiorem wierzchołków jak G, lecz z którego usunięto wszystkie krawędzie należące do G.
• Graf spójny (ang. connected graph) to graf NIESKIEROWANY [Cormen], w którym dla każdej pary wierzchołków istnieje ścieżka, która je łączy. Jeżeli graf nie jest spójny, to zbudowany jest ze spójnych składowych (ang. connected components), z których każda jest maksymalnym podgrafem spójnym.
  Można pokazać, że dla grafu nieskierowanego spójnego G=(V,E) zachodzi zależność m ≥ n-1.
• Graf SKIEROWANY jest silnie spójny (ang. strongly connected) [Cormen], jeżeli każde dwa wierzchołki są osiągalne jeden z drugiego. Silnie spójne składowe grafu skierowanego są klasami abstrakcji relacji "są wzajemnie osiągalne" w zbiorze wierzchołków. Graf skierowany jest silnie spójny, jeżeli ma tylko jedną silnie spójną składową.
• Graf dwuspójny (ang. biconnected graph) to graf nieskierowany spójny, który pozostanie spójny po usunięciu dowolnego wierzchołka i krawędzi incydentnych do niego. Pojawia się przy obliczaniu współczynników wirialnych [2013_Wheatley].
• Graf dwudzielny (ang. bipartite graph) to graf NIESKIEROWANY, którego wierzchołki można podzielić na dwa podzbiory, przy czym wszystkie krawędzie łączą wierzchołki jednego podzbioru z wierzchołkami drugiego.
• Graf eulerowski to graf, w którym istnieje cykl Eulera, czyli cykl przechodzący przez wszystkie krawędzie, przez każdą dokładnie jeden raz.
• Graf hamiltonowski to graf, w którym istnieje cykl Hamiltona, czyli cykl przechodzący przez wszystkie wierzchołki, przez każdy dokładnie jeden raz [jest związek z problemem komiwojażera].
• Graf planarny (ang. planar graph) to graf, który może być narysowany na płaszczyźnie tak, aby jego krawędzie nie przecinały się.
• Graf acykliczny to graf, w którym nie ma cykli. Graf nieskierowany acykliczny to drzewo lub las (suma drzew). DAG (ang. directed acyclic graph) to graf skierowany acykliczny.
• Graf cykliczny C_n (ang. cycle graph) to graf spójny, regularny stopnia 2, zawierający n wierzchołków (m=n). Liczba chromatyczna 2 (n parzyste) lub 3 (n nieparzyste).
• Graf liniowy P_n (ang. path graph, linear graph) to graf otrzymany z grafu cyklicznego C_n przez usunięcie jednej krawędzi, m=n-1.
• Graf koło W_n (ang. wheel graph) to graf powstający z grafu C_{n-1} przez połączenie każdego wierzchołka z nowym wierzchołkiem v, m=2n-2.

DRZEWA

Drzewo (tree) to acykliczny graf nieskierowany spójny. Drzewo rozpinające (spanning tree) grafu spójnego jest podgrafem, który zawiera wszystkie wierzchołki grafu i jest jednocześnie pojedyńczym drzewem.

Graf G o n wierzchołkach jest drzewem wtedy i tylko wtedy, gdy spełnia któryś z czterech poniższych warunków:

• G posiada n-1 krawędzi i nie zawiera cykli.
• G posiada n-1 krawędzi i jest spójny.
• Dokładnie jedna ścieżka prosta łączy każdą parę różnych wierzchołków należących do G.
• G jest spójny, ale usunięcie jakiejkolwiek krawędzi rozspaja go.

LEMAT O PODAWANIU RĄK

Dla grafu nieskierowanego zachodzi lemat [Cormen str. 1197]:
\sum_{v ∈ V} degree(v) = 2 * m.

Dla grafu skierowanego zachodzi lemat:
\sum_{v ∈ V} indegree(v) = m = \sum_{v ∈ V} outdegree(v).