Читать книгу Wprowadzenie do teorii obliczeń - Michael Sipser - Страница 22

Graf nieskierowany lub po prostu graf to zbiór punktów z liniami łączącymi pewne z nich ze sobą. Punkty te nazywamy wierzchołkami lub węzłami, zaś linie nazywamy krawędziami, jak na poniższym rysunku.

Rysunek 0.12

Przykłady grafów

Liczbę krawędzi spotykających się w określonym wierzchołku nazywamy stopniem tego wierzchołka. Na rysunku 0.12(a) wszystkie wierzchołki mają stopień 2. Na rysunku 0.12(b) wszystkie wierzchołki mają stopień 3. Między dwoma dowolnymi wierzchołkami dozwolona jest co najwyżej jedna krawędź. W pewnych sytuacjach możemy zezwolić na krawędzie prowadzące od wierzchołka do niego samego, czyli pętle zwrotne.

W grafie G zawierającym wierzchołki i oraz j para (i, j) reprezentuje krawędź łączącą te wierzchołki. Kolejność i oraz j nie ma znaczenia w grafie nieskierowanym, zatem pary (i, j) oraz (j, i) reprezentują tę samą krawędź. Nieskierowane krawędzie są niekiedy przedstawiane jako nieuporządkowane pary przy użyciu notacji zbiorów, czyli {i, j}. Jeśli V to zbiór wierzchołków G, a E jest zbiorem krawędzi, możemy to zapisać jako G = (V, E). Graf możemy przedstawić za pomocą diagramu lub bardziej formalnie specyfikując zbiory V i E. Na przykład formalny opis grafu z rysunku 0.12(a) to

({1, 2, 3, 4, 5}, {(1, 2), (2, 3), (3, 4), (4, 5), (5, 1)}),

a formalny opis grafu z rysunku 0.12(b) to

({1, 2, 3, 4}, {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)}).

Grafy są często wykorzystywane do przedstawiania danych. Wierzchołki mogą być miastami, a krawędzie łączącymi je szosami albo wierzchołki mogą przedstawiać ludzi, natomiast krawędzie – przyjaźń między nimi. Niekiedy dla wygody możemy opatrywać etykietami wierzchołki i/lub krawędzie grafu, który wówczas nazywany jest grafem etykietowanym (labeled graph). Na rysunku 0.13 przedstawiono graf, którego wierzchołki są miastami, zaś krawędzie zostały opisane kosztem najtańszego bezpośredniego przelotu między tymi miastami, o ile taki bezpośredni lot (non stop) jest możliwy.

Rysunek 0.13

Najtańsze taryfy lotnicze non stop między różnymi miastami

Mówimy, że graf G jest podgrafem grafu H, jeśli wierzchołki G są podzbiorem wierzchołków H i krawędzie G są krawędziami H dla odpowiednich wierzchołków¹. Na poniższym rysunku pokazano graf H i podgraf G.

Rysunek 0.14

Graf G (pokazany jako ciemniejszy) jest podgrafem grafu H

Ścieżka w grafie jest ciągiem wierzchołków połączonych krawędziami. Ścieżką prostą (drogą) nazywamy ścieżkę, w której żaden wierzchołek się nie powtarza. Graf jest spójny, jeśli dla dowolnych dwóch wierzchołków istnieje łącząca je ścieżka. Ścieżkę nazywamy cyklem, jeśli jest zamknięta, czyli zaczyna się i kończy w tym samym wierzchołku. Cykl prosty to cykl złożony z co najmniej trzech różnych wierzchołków, w którym powtarza się tylko pierwszy wierzchołek (jako ostatni). Graf jest drzewem, jeśli jest spójny i nie zawiera prostych cykli, jak na rysunku 0.15 (c). Drzewo może zawierać specjalnie wyróżniony wierzchołek nazywany korzeniem. W drzewie, z wyjątkiem korzenia, wierzchołki o stopniu 1 nazywane są liśćmi drzewa.

Rysunek 0.15

(a) Ścieżka w grafie, (b) cykl w grafie oraz (c) drzewo

Graf skierowany jest przedstawiany przy użyciu strzałek zamiast linii, co pokazano na kolejnym rysunku. Liczbę strzałek wychodzących z określonego wierzchołka nazywamy stopniem wyjściowym tego wierzchołka, zaś liczbę strzałek wskazujących na dany wierzchołek nazywamy jego stopniem wejściowym.

Rysunek 0.16

Graf skierowany

W grafie skierowanym krawędź z wierzchołka i do wierzchołka j przedstawiamy jako parę uporządkowaną (i, j). Formalny zapis grafu skierowanego G to (V, E), gdzie V jest zbiorem wierzchołków, E – zbiorem krawędzi. Formalny zapis grafu pokazanego na rysunku 0.16 to

({1,2,3,4,5,6}, {(1,2), (1,5), (2,1), (2,4), (5,4), (5,6), (6,1), (6,3)}).

Ścieżkę, w której wszystkie strzałki wskazują w tym samym kierunku, od początku do końca, nazywamy ścieżką skierowaną. Graf skierowany jest silnie spójny, jeśli dla każdych dwóch węzłów istnieje łącząca je ścieżka skierowana. Grafy skierowane są wygodną metodą opisywania relacji dwuargumentowych. Jeśli R jest relacją dwuargumentową o dziedzinie D × D, to można ją reprezentować jako graf etykietowany G = (D, E), gdzie E = {(x, y) : xRy}.

Przykład 0.17

Graf skierowany pokazany poniżej reprezentuje relację z przykładu 0.10.

Rysunek 0.18

Graf dla relacji bije