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. 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 V × V: (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) 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 krawędzie wielokrotne (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, oraz istnieją krawędzie (v_i, v_{i+1}) [notacja a-b-c-a; patologia: a-a, a-b-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 to acykliczny graf nieskierowany spójny. Drzewo rozpinające (ang. 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).