8063591567

Rozdział 2

Algorytmy grafowe

Literatura [WDA] - 23⁼ [ASD] - 7 [MD] - 3.2, 6

Graf G definiowany jest jako para (V,E), gdzie V to zbiór wierzchołków, natomiast E to multizbiór krawędzi łączących wierzchołki z V. Dla grafu G — (V,E) z czterema wierzchołkami oraz pięcioma krawędziami, przedstawionego na rysunku 2.1.a, zbiór V = {1,2,3,4}, natomiast E = {(1,2), (1,2), (1,3), (2,4), (3,3)}.

Krawędzie grafu mogą być skierowane (jak na rysunku 2.1.b), bądź nieskierowane (rysunek 2.1.a). Zarówno z wierzchołkami, jak i krawędziami można wiązać dodatkowe informacje, takie jak waga, kolor czy długość. Grafy znajdują wiele odpowiedników w świecie rzeczywistym, co sprawia, że są one bardzo przydatnym narzędziem podczas rozwiązywania praktycznych problemów algorytmicznych.

Rozpatrzmy dla przykładu zbiór skrzyżowań w mieście połączonych drogami. Naturalnym jest utożsamienie wierzchołków grafu ze skrzyżowaniami, a krawędzi grafu z drogami. Drogi mogą być jednokierunkowe (równoważne krawędziom skierowanym) lub dwukierunkowe (równoważne krawędziom nieskierowanym), mają określoną długość (którą możemy również przypisać krawędziom). Skrzyżowania natomiast mogą mieć określone położenie geograficzne, które możemy przechowywać w reprezentujących je wierzchołkach. Na potrzeby tego rozdziału wprowadzimy kilka często używanych pojęć:

Definicja 2.0.1 Pętla to dowolna krawędź (skierowana lub nieskierowana), prowadząca do wierzchołka, z którego wychodzi. Innymi słowy, jest to krawędź postaci (v,v), v € V.

Definicja 2.0.2 Multikrawędzie to co najmniej dwie krawędzie prowadzące między tymi samymi wierzchołkami. W przypadku grafów nieskierowanych są to krawędzie łączące tę samą parę wierzchołków, natomiast w przypadku grafów skierowanych — wychodzące z tego samego wierzchołka oraz wchodzące do tego samego wierzchołka.

(b)

Rysunek 2.1: (a) graf nieskierowany — krawędzie łączące wierzchołki 1 i 2 są multikrawędziami, natomiast (3,3) to pętla, (b) Graf skierowany zawierający pętlę (1,1) oraz multikrawędzie (1,2). (c) Graf indukowany przez graf z rysunku (b) przez zbiór wierzchołków {1,2,3}