POJĘCIA PODSTAWOWE

Graf prosty G - Para (V(G), E(G)) gdzie V(G) jest niepustym skończonym zbiorem elementów zwanych wierzchołkami, a E(G) jest skończonym zbiorem uporządkowanych par różnych (w parach) elementów zbioru V(G) zwanym krawędziami.

V(G) - zbiór wierzchołków.

E(G) - zbiór krawędzi.

V(G) = {n, v, w, z}
E(G) = { {n, v} {w, v} {n, w} {w, z} }

Uwalniając się od ograniczenia że każda krawędź musi łączyć dwa różne wierzchołki (możliwość występowania pętli):
Obiekt w którym dozwolone są pętle i krawędzie wielokrotne - graf ogólny.

Dwa wierzchołki grafu są sąsiednie, jeśli istnieje krawędź je łącząca.

Wierzchołek jest incydentny z krawędzią jeśli łączą się.

Dwie krawędzie grafu są sąsiednie jeżeli posiadają przynajmniej jeden wspólny wierzchołek.

Stopień wierzchołka - liczba krawędzi incydentnych z tym wierzchołkiem. Licząc stopień wierzchołka przyjmuje się że każda pętla jest liczona 2 razy ! (liczy się wyjścia)

Największy stopień wiarzchołka w grafie oznacza się:
(G)
Najmniejszy stopień wiarzchołka w grafie oznacza się:
(G)

Wierzchołek stopnia zero - izolowany.
Wierzchołek stopnia jeden - końcowy (wiszący).

REPREZENTACJA GRAFU

zbiory

V(G) = {u, v, w, y, x}

E(G) = {{u, v} {u, y} {v, y} {v, w} {y, x} {w, x} {w, y}}

przypisania

u: v, y
v: u, w, y
w: v, y, x
x: w, y
y: u, v, w, x

macierz sąsiedztwa

Jeżeli w grafie G wierzchołki oznakowane są liczbami ze zbioru {1,2, ... , n} to macierz sąsiedztwa jest macierzą wymiaru n x n, kórej wyraz o indeksach i,j jest równy ilości krawędzi łączących wierzchołek i z wierzchołkiem j.

macierz incydencji

Jeżeli w grafie G krawędzie oznakowane są liczbami ze zbioru {1,2, ... , m} to macierz incydencji jest macierzą wymiaru n x m, której wyraz o indeksach i, j jest równy 1 jeśli wierzchołek i jest incydentny z krawędzią j , a równy 0 w przeciwnym przypadku. Macierz incydencji jest macierzą binarną (zawiera tylko 0 i 1)

TYPY GRAFÓW

graf pusty

Graf którego zbiór krawędzi jest zbiorem pustym. (składa się tylko z wierzchołków)

Oznaczany:   N_n   gdzie n - ilość wierzchołków.

graf pełny

Graf prosty w którym dowolne dwa wierzchołki są sąsiednie.

Oznaczany:   K_n   gdzie n - ilość wierzchołków.

Ilość krawędzi:   n ( n - 1 ) / 2

graf regularny

Każdy wierzchołek garfu ma taki sam stopień.
Jeżeli każdy wierzchołek jest stopnia r, to graf jest regularny stopnia r.

Oznaczany:   K_n   gdzie n - ilość wierzchołków.

graf platoński

Graf regularny utworzony przez wierzchołki i krawędzie jednego z pięciu wielościanów foremnych. (czworościan, sześcian, ośmiościan, dwunastościan, dwudziestościan)

czworościan
sześcian
ośmiościan
dwunastościan
dwudziestościan

graf dwudzielny

Graf jest dwudzielny jeżeli zbiór wierzchołków grafu G można podzielić na dwa rozłączne zbiory V₁ i V₂ w taki sposób że każda krawędź grafu G łączy dowolny wierzchołek ze zbioru V₁ z dowolnym wierzchołkiem ze zbioru V₂

Oznaczany:   K_{r, s}   gdzie r - ilość wierzchołków zbioru V₁, s - ilość wierzchołków zbioru V₂.

graf cykliczny

Graf spójny, regularny stopnia drugiego.

Oznaczany:   C_n   gdzie n - ilość wierzchołków.

graf liniowy

Graf otrzymany z grafu cyklicznego poprzez usunięcie jednej krawędzi.

Oznaczany:   P_n   gdzie n - ilość wierzchołków.

koło

Graf powstały z grafu cyklicznego poprzez połączenie każdego wierzchołka z nowym, dodanym wierzchołkiem

Oznaczany:   W_n   gdzie n - ilość wierzchołków.

graf Petersena

graf Grötzscha

POJĘCIA

grafy izomorficzne

Dwa grafy G₁ i G₂ są izomorficzne, jeżeli istnieje wzajemna jednoznaczna odpowiedniość między wierzchołkami grafu G₁ i wierzchołkami grafu G₂, taka że liczba krawędzi łącząca dwa dowolne wierzchołki w G₁ jest równa liczbie krawędzi łączących odpowiadające im wierzchołki w G₂.

podgraf

Podgraf grafu G to graf którego wszystkie wierzchołki należą do V(G), i wszystkie krawędzie należą do E(G).

dopełnienie grafu prostego

Jeżeli G - graf prosty ze zbiorem wierzchołków V(G), to dopełnienie
jest grafem prostym którego zbiór wierzchołków jest równy V(G), i w którym dwa wierzchołki są sąsiednie wtedy i tylko wtedy, gdy nie są sąsiednie w grafie G.

SUMA I ZESPOLENIE

suma

Jeżeli:
G₁ = ( V(G₁) , E(G₁) )   i   G₂ = ( V(G₂) , E(G₂) )
oraz   V(G₁)   i   V(G₂)   - zbiory rozłączne to:
suma   G₁ 
 G₂   - graf ze zbiorem wierzchołków   V(G₁) 
 V(G₂)   i rodziną krawędzi   E(G₁) 
 E(G₂).

zespolenie

Zespolenie G₁ + G₂ to suma tych grafów gdzie poprowadzono krawędzie z każdego wierzchołka G₁ do każdego wierzchołka G₂

graf spójny

Graf który nie może być przedstawiony w postaci sumy dwóch grafów.

graf niespójny

Graf który może być przedstawiony w postaci sumy dwóch grafów.

SPÓJNOŚĆ

Zbiór rozspajający grafu spójnego G - zbiór krawędzi których usunięcie spowoduje że graf G przestanie być spójny.

Rozcięcie - zbiór rozspajający, którego żaden podzbiór właściwy nie jest już zbiorem rozspajającym.

Jeżeli rozcięcie składa się z jednej krawędzi, to krawędź taka nazywana jest mostem.

Spójność krawędziowa -
(G) - w grafie spójnym liczba krawędzi należąca do najmniej licznego rozcięcia grafu G.

Zbiór rozdzielający - zbiór wierzchołków których usunięcie spowoduje że graf przestanie być spójny.

Wierzchołek rozcinający - jeżeli zbiór rozdzielający skłąda się z jednego wierzchołka to wierzchołek ten nazywamy wierzchołkiem rozcinającym.

Spójność wierzchołkowa - k(G) - w grafie spójnym i niepełnym, liczba elementów najmniejszego zbioru rozdzielającego.

GRAFY NIEOZNAKOWANE I OZNAKOWANE

Graf nieoznakowany - pomijane są nazwy wierzchołków.

Graf oznakowany - występują nazwy wierzchołków.

Różnica między grafami nieoznakowanymi a oznakowanymi staje się wyraźna gdy je zliczamy.

GRAF PŁASKI

Graf płaski - graf narysowany na płaszczyźnie w taki sposób że żadne dwie krawędzie nie przecinają się geometrycznie z wyjątkiem wierzchołków z którymi są incydentne.

Graf planarny - graf izomorficzny z grafem płaskim.

Dwa grafy są homeomorficzne jeżeli mogą być otrzymane z tego samego grafu poprzez umieszczenie nowych wierzchołków stopnia dwa na jego krawędziach.

Graf jest planarny wtedy i tylko wtedy gdy nie zawiera podgrafu homeomorficznego.

MARSZRUTA

Marszruta (trasa) - skończony ciąg krawędzi:   v₀, v₁, ... , v_n   gdzie v₀ - początek, v_n - koniec.

Długość - liczba krawędzi w marszrucie.

Łańcuch (ścieżka) - marszruta w której wszystkie krawędzie są różne.

Droga - łańcuch w którym wszystkie wierzchołki są różne.

Jeżeli v₀ = v_n - łańcuch lub droga zamknięta.

Cykl - droga zamknięta zawierająca przynajmniej jedną krawędź.

Jeżeli G jest grafem dwudzielnym, to każdy cykl ma parzystą długość.

Graf jest spójny gdy dla dowolnej pary wierzchołków v i w istnieje droga z v do w.

GRAFY EULEROWSKIE

Graf spójny nazywamy grafem eulerowskim gdy istnieje zamknięta ścieżka (łańcuch) zawierająca każdą krawędź grafu. (przechodząca przez każdą krawędź jeden raz, gdzie wierzchołek początkowy ścieżki równa się wierzchołkowi końcowemu)

Ścieżka taka nazywana jest cyklem eulera

Graf półeulerowski - jeżeli istnieje ścieżka zawierająca każdą krawędź. (każdą krawędź tylko raz, początek nie równa się końcowi)

Twierdzenie Eulera (1736 rok):

Graf spójny G jest grafem eulerowskim wtedy i tylko wtedy, gdy stopień każdego wierzchołka grafu G jest liczbą parzystą.

Graf spójny G jest grafem półeulerowskim wtedy i tylko wtedy, gdy ma dokładnie dwa wierzchołki których stopnie są liczbami nieparzystymi. (Jeden określa początek, drugi koniec.)

Algorytm Fleury'ego

Algorytm pomagający znaleźć cykl Eulera w grafie:

Zacznij cykl w dowolnym wierzchołku i przechodź przez pozostałe w dowolnej kolejności przeszczegając dwóch zasad:

1. usuwaj z grafu przechodzone krawędzi oraz wierzchołki izolowane powstające w wyniku usuwania krawędzi.

2. w każdym momencie przechodź przez most tylko wtedy gdy nie masz już innej drogi.

GRAFY HAMILTONOWSKIE

Graf spójny nazywamy grafem hamiltonowskim gdy istnieje zamknięta ścieżka przechodząca przez każdy wierzchołek grafu tylko raz.

Ścieżka taka nazywana jest cyklem hamiltonowskim (hamiltona).

Graf półhamiltonowski - graf niehamiltonowski, gdy istnieje w nim droga przechodząca przez każdy wierzchołek.

KOLOROWANIE GRAFÓW

Graf jest k - kolorowalny jeżeli każdemu wierzchołkowi można przypisać jeden z k kolorów, w taki sposób że żadne dwa wierzchołki sąsiednie nie mają tego samego koloru.

Jeżeli G jest k - kolorowalny ale nie jest (k-1) - kolorowalny to G jest k - chromatyczny.

Liczba chromatyczna - X(G) - najmniejsza liczba kolorów, wystarczająca do pokolorowania wiarzchołków grafu w taki sposób że żadne dwa wierzchołki sąsiednie nie mają tego samego koloru

Indeks chromatyczny - X'(G) - najmniejsza liczba kolorów, wystarczająca do pokolorowania krawędzi grafu w taki sposób że żadne dwie krawędzie o wspólnym wierzchołku nie mają tego samego koloru.

DRZEWA

Las - graf nie zawierający cykli.

Drzewo - las spójny. (graf spójny bez cykli)

Własności drzew (dla grafu T mającego n-wierzchołków):

1. T nie zawiera cykli, ilość krawędzi = n-1

2. T jest grafem spójnym, każda krawędź jest mostem.

3. Każde dwa wierzchołki T połączone są dokładnie jedną drogą.

4. T nie zawiera cykli, ale po dodaniu dowolnej nowej krawędzi otrzymujemy graf z dokładnie jednym cyklem.

PROBLEM: MOSTY KRÓLEWSKIE

Wiek osiemnasty. Miszkańcy Królewca mają przyjemne hobby: lubią spacerować po siedmiu mostach na rzece Pregole. Ale po pewnym czasie znudziło im się takie spacerowanie i zaczeli zastanawiać się czy można by przejść przez każdy most tylko raz i wrócić do punktu z którego zaczeło się spacer. Niestety nie udało im się w taki sposób określić drogi spaceru, a że byli uparci postanowili napisać do cenionego matematyka Leonharda Eulera.

Układ mostów wyglądał tak:

Euler przedstawił taki układ w postaci grafu:

i stwierdził że mieszkańcy królewca powinni znaleźć sobie inne hobby ;-) (czyli po prostu w takim grafie nie występuje cykl Eulera - nie da się przejść przez każdą krawędź raz i tylko raz i powrócić do punktu startu.)

PROBLEM CHIŃSKIEGO LISTONOSZA

W 1962 chiński matematyk Mei Ku Kwana sformułował problem który w opisie werbalnym wygląda następująco:

Listonosz musi roznieść listy. Wyrusza z poczty i musi przejść przez każdą ulicę w swoim rejonie. Jako że listy swoje ważą należy postawić pytanie: jak ma określić swoją wędrówkę by była jak najkrótsza ?

Dowolny układ ulic można przedstawić jako graf którego wierzchołki odpowiadają skrzyżowaniom a krawędzie ulicom. Dodatkowo każda krawędź posiada wagę która odpowiada odległości pomiędzy wierzchołkami (czyli skrzyżowaniami). Należy znaleźć taką trasę by przejść po każdej ulicy przynajmniej raz oraz, jeśli po niektórych ulicach trzeba przejść więcej niż raz, suma odległości pomiędzy skrzyżowaniami była jak najmniejsza. Oczywiście należy wrócić do punktu startu.

Jeżeli graf posiada cykl Eulera to jest on rozwiązaniem problemu listonosza. Jeżeli natomiast graf nie posiada cyklu Eulera a jest spójny, należy wybrać taką trasę by suma wag przyporządkowanych krawędziom była najmniejsza.

PROBLEM KOMIWOJAŻERA

Komiwojażer wyrusza ze swego miasta. Musi odwiedzić określoną ilość miast i wrócić do domu. Oczywiście chce by trasa była jak najkrótsza. W tym przypadku za najkrótszą trasę można też uważać trasę o najkrótszym czasie przejazdu, lub najniższym koszcie.

Przedstawiając miasta w postaci grafu, gdzie są one wierzchołkami, natomiast krawędzie określają relacje zachodzące między nimi (np.: połączenie drogowe) i mają przyporządkowane wagi (odległość, czas, koszt ...), należy znaleźć w tym grafie trasę która przechodzi przez każdy wierzchołek przynajmniej raz.

Jeżeli graf posiada cykl Hamiltona to jest on rozwiązaniem problemu komiwojażera. Jeżeli natomiast graf nie posiada cyklu Hamiltona a jest spójny, należy wybrać taką trasę by suma wag przyporządkowanych krawędziom była najmniejsza.

---