Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2023 mgr Jerzy Wałaszek
I LO w Tarnowie

Podstawowe pojęcia dotyczące grafów

SPIS TREŚCI

Definicje

Graf (ang. graph) jest strukturą danych składającą się z dwóch zbiorów: zbioru wierzchołków ( ang. vertices) i zbioru krawędzi (ang. edges ), co matematycznie zapisujemy w postaci uporządkowanej pary (tzn. takiej, gdzie istotna jest kolejność elementów tworzących tę parę ):

G = ( V, E )    
V = { v1, v2, ..., vn }  –  zbiór n  ponumerowanych wierzchołków (ang. V = Vertex )
E = { e1, e2, ... em }  –  zbiór m  ponumerowanych krawędzi (ang. E = Edge ). Każda krawędź jest parą (w grafie skierowanym parą uporządkowaną) wierzchołków grafu połączonych tą krawędzią:

E = { ( u, v ): u, v  ∈ V }

Rząd grafu (ang. graph order) to liczba wierzchołków w grafie.

Rozmiar grafu (ang. graph size) to liczba krawędzi w grafie.

Wierzchołki grafu przechowują informację, natomiast krawędzie określają sposób poruszania się po grafie: z wierzchołka u  można przejść do wierzchołka v  tylko wtedy, gdy istnieje ścieżka (ciąg krawędzi ), która prowadzi w grafie od wierzchołka u  do v.

Grafem zerowym (ang. null graph) jest graf, który posiada wierzchołki, lecz nie posiada żadnych krawędzi:

obrazek        G = ( V, E )
V = { v1, v2, v3, v4, v5 }
E = {  } = Ø

W grafie zwykłym mamy wierzchołki oraz krawędzie, które łączą ze sobą pary wierzchołków grafu:

obrazek        G = ( V, E )
V = { v1, v2, v3, v4, v5 }
E = { e1, e2, e3, e4, e5 }

e1 = ( v1, v2 )
e2 = ( v2, v3 )
e3 = ( v3, v5 )
e4 = ( v1, v5 )
e5 = ( v4, v5 )

Wierzchołek nie połączony krawędzią z żadnym innym wierzchołkiem grafu nazywamy wierzchołkiem izolowanym (ang. isolated vertex ):

obrazek        G = ( V, E )
V = { v1, v2, v3, v4, v5, v6 }
E = { e1, e2, e3, e4, e5 }

e1 = ( v1, v2 )
e2 = ( v2, v3 )
e3 = ( v3, v5 )
e4 = ( v1, v5 )
e5 = ( v4, v5 )

v6 – wierzchołek izolowany

Dane dwa wierzchołki mogą być połączone ze sobą za pomocą więcej niż jednej krawędzi, które nazywamy krawędzią wielokrotną (ang. multi-edge ). Również wierzchołek może łączyć się krawędzią z samym sobą. Otrzymujemy wtedy tzw. pętlę (ang. loop ). Graf zawierający pętle lub krawędzie wielokrotne nazywamy multigrafem (ang. multigraph ).

obrazek        G = ( V, E )
V = { v1, v2, v3, v4, v5 }
E = { e1, e2, e3, e4, e5, e6, e7 }

e1
= ( v1, v2 )
e2 = ( v1, v2 )
e3 = ( v2, v3 )
e4 = ( v3, v5 )
e5 = ( v1, v5 )
e6 = ( v4, v5 )
e7 = ( v4, v4 )

e1, e2
krawędź wielokrotna
e7pętla

Graf nie posiadający pętli oraz krawędzi podwójnych nazywamy grafem prostym (ang. simple graph lub strict graph ).

Krawędź, którą można przebywać tylko w określoną stronę, nazywa się krawędzią skierowaną (ang. directed edge ). Na rysunku krawędzie skierowane oznaczamy strzałkami. Graf zawierający krawędzie skierowane nazywamy grafem skierowanym ( ang. directed graph) lub w skrócie digrafem ( ang. digraph ). Graf nie posiadający krawędzi skierowanych nazywamy grafem nieskierowanym (ang. not directed graph ). W definicji digrafu zbiór krawędzi tworzą uporządkowane pary wierzchołków ( u, v ), z których u oznacza wierzchołek początkowy krawędzi, a v wierzchołek końcowy. Krawędź nieskierowana może być przedstawiona jako dwie krawędzie skierowane w przeciwnych kierunkach.

obrazek        G = ( V, E )
V = { v1, v2, v3, v4, v5 }
E = { e1, e2, e3, e4, e5, e6 }

e1 = ( v1, v2 )
e2 = ( v2, v1 )
e3 = ( v2, v3 )
e4 = ( v3, v5 )
e5 = ( v5, v1 )
e6 = ( v5, v4 )

Zwróć uwagę, że w grafie skierowanym mogą istnieć wierzchołki, pomiędzy którymi nie da się przejść, pomimo istnienia łączących je krawędzi. Oto najprostszy przykład:

obrazek        G = ( V, E )
V = { v1, v2 }
E = { e1 }

e1 = ( v1, v2 )

W grafie tym istnieje droga od wierzchołka v1 do v2, jednakże nie ma drogi powrotnej od v2 do v1, ponieważ łącząca te wierzchołki krawędź może być przebyta tylko w jednym kierunku.

Z krawędziami grafu mogą być związane dodatkowe wartości (np. w świecie rzeczywistym pokonanie drogi z jednego miasta do drugiego może wymagać określonej ilości czasu lub energii ). Wartości te nazywamy wagami (ang. weight ), a graf posiadający takie krawędzie nazywamy grafem ważonym (ang. weighted graph ). Graf ważony posiada zbiór krawędzi zbudowany z uporządkowanych trójek, gdzie dwa pierwsze elementy określają wierzchołki połączone daną krawędzią (w grafie skierowanym wierzchołki te są parą uporządkowaną ), a trzeci element określa wagę tej krawędzi.

obrazek        G = ( V, E )
V = { v1, v2, v3, v4, v5 }
E = { e1, e2, e3, e4, e5 }

e1 = ( v1, v2, w1 )
e2 = ( v2, v3, w2 )
e3 = ( v3, v5, w3 )
e4 = ( v1, v5, w4 )
e5 = ( v4, v5, w5 )

Stopniem wierzchołka (ang. degree) nazywamy liczbę krawędzi, które łączą się z danym wierzchołkiem. Jeśli graf posiada pętle, to liczymy je za 2. W poniższym grafie wierzchołki posiadają następujące stopnie:

obrazek        deg ( v1 ) = 3
deg ( v2 ) = 3
deg ( v3 ) = 2
deg ( v4 ) = 3
deg ( v5 ) = 3

W grafie skierowanym rozróżniamy stopień wchodzący (ang. indegree) – liczba krawędzi wchodzących do wierzchołka oraz stopień wychodzący (ang. outdegree) – liczba krawędzi wychodzących z wierzchołka.

Wierzchołek izolowany posiada zawsze stopień 0.

Ścieżka lub droga (ang. path) jest uporządkowanym ciągiem kolejnych krawędzi, po których należy przejść, aby dotrzeć z wierzchołka startowego ( ang. start vertex) do wierzchołka końcowego (ang. end vertex ). W grafie może istnieć wiele różnych ścieżek pomiędzy dwoma wybranymi wierzchołkami.

obrazek        P ( v1,v 4 ) = { e1, e2, e7 }
P ( v1, v4 ) = { e1, e5 }
P ( v1, v4 ) = { e4, e6 }
P ( v1, v4 ) = { e4, e3, e7 }
...

Ścieżki można również definiować za pomocą ciągu kolejno mijanych wierzchołków (oczywistym jest, iż każde dwa kolejne wierzchołki muszą być połączone krawędzią ).

obrazek        P ( v1, v4 ) = { v1, v2, v3, v4 }

Najkrótsza ścieżka (ang. shortest path) to ta, która zawiera najmniej krawędzi/wierzchołków. Długość ścieżki (ang. path length) to liczba zawartych w niej krawędzi/wierzchołków.

Mówimy, że ścieżka jest prosta (ang. strait path lub simple path ), jeśli każdą krawędź/wierzchołek przechodzimy tylko jeden raz.

Cykl (ang. cycle) to ścieżka, która rozpoczyna się i kończy w tym samym wierzchołku. Uwaga: nie myl cyklu z pętlą – pętla to pojedyncza krawędź.

obrazek        C ( v1 ) = { e1, e2, e7, e6, e4 }
C ( v1 ) = { v1, v2, v3, v4, v5, v1 }

Cykl nazywamy prostym (ang. simple cycle ), jeśli każda jego krawędź/wierzchołek jest przechodzona dokładnie jeden raz. Nie odnosi się to oczywiście do wierzchołka startowego i końcowego, które w cyklu muszą być tym samym wierzchołkiem, innymi słowy ścieżka musi być zamknięta.

Ścieżka prosta zawierająca wszystkie wierzchołki grafu nosi nazwę ścieżki Hamiltona (ang. Hamiltonian path ).

Cykl prosty zawierający wszystkie wierzchołki grafu nazywa się cyklem Hamiltona (ang. Hamiltonian cycle ).

Ścieżka prosta, która przechodzi przez wszystkie krawędzie grafu nazywa się ścieżką Eulera (ang. Eulerian path ).

Cykl Eulera (ang. Eulerian cycle) to cykl prosty, który przechodzi przez wszystkie krawędzie grafu. Zwróć uwagę, że cykl Eulera i cykl Hamiltona to nie to samo! W cyklu Hamiltona ważne jest przejście przez wszystkie wierzchołki dokładnie jeden raz (niektóre krawędzie grafu mogą być w ogóle nie przechodzone ). W cyklu Eulera z kolei musimy przejść przez każdą krawędź, zatem niektóre wierzchołki mogą zostać kilkakrotnie odwiedzone, jeśli łączą się z kilkoma krawędziami.

Graf nazywamy acyklicznym (ang. acyclic graph ), jeśli nie posiada żadnych cykli.

Graf nazywamy planarnym (ang. planar graph ), jeśli da się go narysować na płaszczyźnie, tak aby żadne jego krawędzie się nie przecinały.

obrazek
Graf planarny
       obrazek
Graf nieplanarny

Jeśli graf jest planarny, to spełnia wzór Eulera ( jeśli graf nie spełnia tego wzoru, to na pewno nie jest planarny ):



gdzie

|E| – liczba krawędzi w grafie
|V| – liczba wierzchołków

Graf pełny (ang. complete graph) jest grafem, w którym każda para wierzchołków łączy się krawędzią. Grafy pełne o n  wierzchołkach oznacza się symbolem Kn. Graf pełny o n  wierzchołkach posiada krawędzi. Poniżej przedstawiamy kilka początkowych grafów pełnych:

obrazek obrazek obrazek obrazek obrazek obrazek
K1 K2 K3 K4 K5 K6

Grafy pełne od K5 w górę nie są planarne.

Resztę definicji i pojęć związanych z grafami podamy zgodnie z potrzebami. W następnym rozdziale zajmiemy się podstawowymi sposobami reprezentacji grafów w komputerze.

Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2023 mgr Jerzy Wałaszek

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.