8063591568

Definicja 2.0.3 Podgraf G = (V , E ) grafu G = (V, E) jest to taki graf, dla którego V C V, oraz E' C E.

Definicja 2.0.4 Grafem indukowanym G' — G\Y'\ przez zbiór V' z grafu G = (V, E), V' C V nazywamy podgraf grafu G, którego zbiorem wierzchołków jest V', natomiast do zbioru krawędzi należą wszystkie krawędzie (u, v) € E, dla których u, v € V'.

Krawędź, łączącą, wierzchołki u i v, będziemy oznaczać przez (u, v) (ewentualnie u —* v), natomiast ścieżkę prowadzącą z wierzchołka u do wierzchołka v przez u v. Cyklem będziemy nazywali ścieżkę mającą swój początek i koniec w tym samym wierzchołku (u u). Szczególnym przypadkiem cyklu jest cykl prosty, który przechodzi przez każdy wierzchołek grafu co najwyżej raz. Odwołując się do poszczególnych wierzchołków grafu, czasem będzie używane pojęcie ich stopnia. Stopień wejściowy wierzchołka, jest to liczba krawędzi do niego wchodzących, stopień wyjściowy natomiast, to liczba krawędzi wychodzących z wierzchołka.

W wielu miejscach — w szczególności podczas omawiania złożoności algorytmów, będziemy odwoływać się do liczby wierzchołków oraz krawędzi w grafie. W sytuacjach, w których jednoznacznie z kontekstu będzie wynikało o jaki graf chodzi, liczbę wierzchołków oznaczać będziemy przez n, natomiast liczbę krawędzi przez m.

W aktualnym rozdziale omówionych jest wiele algorytmów związanych z teorią grafów. Przedstawione zostaną między innymi metody przeszukiwania grafów, topologiczne sortowanie wierzchołków, sprawdzanie czy graf jest acykliczny, wyznaczanie maksymalnego przepływu oraz wiele innych zagadnień. Zanim jednak przejdziemy do analizy tych algorytmów, musimy najpierw omówić sposób reprezentowania grafu w programach.

2.1. Reprezentacja grafu

Literatura [WDA] - 23.⁼1⁼⁼ [ASD] - 1.5.3, 7 [KDP] - 2.1 [MD] - 3.3

Graf będziemy reprezentować przy użyciu sparametryzowanej struktury (ang. template) Graph<V,E>, gdzie V jest typem określającym dodatkowe informacje przechowywane w wierzchołkach, natomiast E jest typem określającym dodatkowe informacje przechowywane w krawędziach grafu. W ten sposób, jeśli chcemy stworzyć graf modelujący sieć dróg w mieście, to wystarczy wzbogacić strukturę V o informacje związane ze skrzyżowaniami, natomiast strukturę E — z ulicami.

Implementacja grafu udostępnia dwa operatory — Graph<V,E>: :EdgeD(int, int, E), oraz Graph<V,E>:: EdgeU(int, int, E), służące odpowiednio do dodawania do grafu krawędzi skierowanych oraz nieskierowanych (ang. directed — skierowane, undirected — nieskierowane). Pierwszy oraz drugi parametr tych funkcji określają numery wierzchołków połączonych dodawaną krawędzią, natomiast ostatni parametr definiuje dodatkowe informacje związane z tą krawędzią. Dla większości algorytmów, korzystających ze struktury Graph<V,E>, te dwa operatory są w zupełności wystarczające, ale w razie potrzeby można w prosty sposób wzbogacić implementację o nowe operacje — chociażby funkcję usuwającą krawędzie z grafu.

Listing 2.1 prezentuje implementację struktury Graph<V,E> wraz z komentarzami wyjaśniającymi przyjęte rozwiązania. Implementacja ta wykorzystuje bibliotekę STL (dokładniej, kontener vector do reprezentowania listy wierzchołków oraz krawędzi).

14