Przedstawienie pojęcia grafu poprzedzimy krótką historyjką, którą zwykle opowiada się z tej okazji. Otóż szwajcarski matematyk Leonard Euler, przebywając w Królewcu, miał zwyczaj spacerować po mieście. Poszczególne części miasta, położonego na obu brzegach rzeki Pregoły i jej dwu wyspach, połączone były siedmioma mostami, por. Rys 2.11a. Euler starał się znaleźć taką drogę, która pozwoliłaby mu przejść raz po każdym z mostów. Rozwiązanie problemu mostów królewieckich ukazało się w pracy Eulera opublikowanej w 1736 roku, dając początek nowej gałęzi matematyki - teorii grafów. (Do problemu mostów królewieckich wrócimy jeszcze raz nieco później.)

Grafy, o których będzie mowa w tym wykładzie, to proste figury geometryczne składające się z punktów i odcinków lub strzałek łączących niektóre z nich. Tak właśnie ilustrowaliśmy relacje. Matematyczna definicja grafu odsyła nas do pojęcia relacji.

Definicja 2.10

Grafem (lub grafem zorientowanym) nazywamy parę uporządkowaną G = <V, E>, gdzie V jest niepustym zbiorem, a E podzbiorem produktu V ´ V. Elementy zbioru V nazywamy węzłami lub wierzchołkami grafu, a elementy zbioru E nazywamy krawędziami grafu.

Odwrotnie, każda relacja binarna r w zbiorze X, wyznacza jednoznacznie graf, którego węzłami są elementy zbioru X, a krawędziami uporządkowane pary (x, x') należące do r. Zwykle będziemy rozważali grafy skończone, tzn. o skończonej liczbie wierzchołków.

Typowymi przykładami grafów są schematy różnego rodzaju sieci: np. sieci dróg, sieć wodociągowa, sieć telekomunikacyjna, itd. Kilka przykładów grafów zostało już przedstawionych jako ilustracje relacji binarnych. Na rysunku 2.12 przedstawimy jeszcze jeden przykład: graf przedstawiający sieć połączeń drogowych między miastami. Na tym przykładzie wyjaśnimy pewne pojęcia związane z grafami.

Definicja 2.11

Niech G = <V, E> będzie grafem. Wierzchołki połączone krawędzią będziemy nazywać sąsiednimi lub incydentnymi. Drogą w grafie G nazywamy ciąg wierzchołków v₀,v₁,...v_n, taki, że kolejne wierzchołki v_i, v _i+1 są incydentne, tzn. (v_i , v_i+1 ) Î E dla każdego i=0,1,...,n-1. Długość drogi, to liczba jej krawędzi. Jeśli w tym ciągu v₀= v_n, to powiemy, że droga jest zamknięta. Jeśli wszystkie wierzchołki drogi zamkniętej są różne z wyjątkiem pierwszego i ostatniego wierzchołka, to taką drogę nazywamy cyklem.

Ciąg WR, Ł, W-wa, G jest drogą długości 3 w grafie przedstawionym na rysunku 2.12. Natomiast trasa W-wa, G, Sz, Po, Wr, Ł, W-wa jest cyklem, drogą długości 6.

w którym na początku mamy dwie instrukcje przypisania elementu a[0] zmiennej max i jedynki zmiennej i, a następnie instrukcję pętli. Diagram przepływu dla tego programu jest grafem przedstawionym na rysunku Rys. 2.13. Wyróżniono na nim dwa wierzchołki: początek, gdy jeszcze nie wykonaliśmy żadnej instrukcji programu i koniec, gdy wszystkie instrukcje programu zostały wykonane. Każdy inny wierzchołek diagramu zawiera instrukcję przypisania lub test jaki trzeba wykonać, jeśli doszliśmy do tego właśnie miejsca w algorytmie. Niektóre strzałki (krawędzie) w grafie mają przypisane słowa tak lub nie by zaznaczyć, którą z krawędzi trzeba wybrać wtedy, gdy mamy do wyboru dwie drogi zależne od wyniku testu. Czytelnik przyzna, że taki sposób opisu algorytmu jest bardzo intuicyjny. Mając dany ciąg wartości a[0], a[1], ..., a[n] dla jakiegoś ustalonego n, możemy prześledzić na tym grafie każde możliwe wykonanie tego algorytmu. Nota bene: A co robi ten algorytm?

Rys. 2.13 Diagram przepływu dla programu przedstawionego w przykładzie 2.10.

Pytanie 10: Podaj przykładowe dane, dla których wykonanie algorytmu odpowiada przejściu po drodze 1,2,3,4,5,7,4,5,7,4, 8.

Przyjmijmy, że jako szef firmy budowlanej otrzymałeś, drogi Czytelniku, zlecenie zbudowania domu. Jak zabierzesz się do tej pracy? Na początek ustalisz prawdopodobnie jakie czynności trzeba wykonać. Oczywiście, niektóre z nich mogą być wykonywane równocześnie, np. przez różnych fachowców, ale inne muszą być wykonywane w ustalonej kolejności, np. najpierw musimy zbudować fundamenty, a dopiero potem ściany, por. Rys. 2.14. Na ogół tych czynności jest bardzo dużo. Jak sobie z tym wszystkim poradzić? Proste, trzeba narysować graf. Wierzchołki tego grafu odpowiadać będą akcjom, które trzeba wykonać w całym przedsięwzięciu, a krawędzie ustalą kolejność w jakiej je trzeba wykonywać. Rysunek tego grafu pozwoli nie tylko objąć całość przedsięwzięcia jednym spojrzeniem, ale i odpowiednio zaplanować terminy rozpoczęcia i zakończenia poszczególnych prac, lepiej wykorzystać czas i wykonawców.

Definicja 2.12

Powiemy, że graf G = <V, E> jest niezorientowany, jeżeli dla dowolnych dwóch wierzchołków v, v' Î V, (v,v') Î E wttw (v',v) Î E.

Zauważmy, że grafy niezorientowane odpowiadają relacjom symetrycznym. Jeżeli istnieje krawędź (strzałka) o początku w v i końcu w v', to jest też krawędź o początku w v' i końcu w v. Przykład takiego grafu jest przedstawiony na rysunku 2.12a. Zwykle, jeśli mówimy o grafie niezorientowanym, upraszczamy rysunek grafu, zastępując strzałki odcinkami (por. Rys.2.12b). Na krawędzie możemy wtedy patrzeć jak na dwuelementowe zbiory, a nie pary uporządkowane. Pojęcia drogi i cyklu w grafie niezorientowanym pozostają takie same. Dla grafu niezorientowanego definiujemy rząd wierzchołka jako liczbę krawędzi z niego wychodzących. Na rysunku 2.12b rząd wierzchołka W-wa wynosi 5.

Wróćmy na chwilę do problemu Mostów Królewieckich. Można go sformułować następująco: Czy istnieje w grafie przedstawionym na rysunku Rys. 2.11b droga, przechodząca przez wszystkie krawędzie grafu, ale przez każdą tylko raz? Czy istnieje w tym grafie cykl przechodzący dokładnie raz przez każdą z krawędzi? Taki cykl/drogę nazywamy cyklem/drogą Eulera. W przypadku Królewca odpowiedź jest negatywna. Euler podał ogólne kryterium (warunek konieczny i dostateczny) na to, by graf posiadał drogę lub cykl Eulera.

Twierdzenie 2.1

Warunkiem koniecznym i dostatecznym na to, by skończony graf niezorientowany i spójny posiadał cykl Eulera jest by wszystkie wierzchołki tego grafu miały rząd parzysty.

Warunkiem koniecznym i dostatecznym na to by w grafie niezorientowanym skończonym i spójnym istniała droga Eulera łacząca wierzchołki A i B jest by jedynymi wierzchołkami rzędów nieparzystych były co najwyżej wierzchołki A i B.

Sformułowanie tego twierdzenia może się wydać trudne. Jeśli tak, to zachęcamy Czytelnika do powrotu w to miejsce, po przeczytaniu wykładu szóstego. W rzeczy samej, kryterium Eulera jest bardzo proste. Jeśli każdy wierzchołek ma rząd parzysty, to graf taki posiada cykl i drogę Eulera. Jeśli w grafie są wierzchołki rzędu nieparzystego, to albo są dokładnie dwa takie wierzchołki i wtedy istnieje łącząca je droga Eulera, albo nie istnieje żadna droga Eulera w tym grafie.

Sprawdź, w którym z grafów przedstawionych na rysunku 2.15 istnieje cykl lub droga Eulera. Jeśli w grafie istnieje cykl lub droga Eulera, to można ją narysować nie odrywając ołówka od papieru. Miłej Zabawy!

Wyobraźmy sobie turniej, w którym bierze udział 8 drużyn. Rozgrywki odbywają się w kolejnych rundach, w których drużyny rozgrywają mecze parami. Do następnej rundy przechodzą jedynie te drużyny, które zwyciężyły w poprzedniej rundzie. Wszystkie rozgrywki tego turnieju można przedstawić w postaci grafu, por. Rys. 2.16. Wierzchołki grafu (oznaczone na rysunku kolejnymi literami alfabetu) odpowiadają drużynom (ponumerowanym od 1 do 8) biorącym udział w rozgrywkach. Krawędzie wychodzące z dwóch wierzchołków x i y spotykają się w jednym wierzchołku z, tylko wtedy, gdy drużyna z odniosła zwycięstwo w meczu drużyn x i y. Na przykład, mecz drużyn 5 i 6 zakończył się zwycięstwem drużyny 6. Ostatnia runda pozwala wyłonić zwycięzcę turnieju. W naszym przykładzie zwyciężyła drużyna 6.

Graf przedstawiony na rysunku 2.16 ma szczególny kształt, charakterystyczny dla pewnego typu grafów, które nie posiadają cykli, a każde dwa wierzchołki łączy tylko jedna droga.

Definicja 2.13

Graf niezorientowany, który jest

spójny, tzn. między dowolnymi dwa wierzchołkami istnieje droga, i

acykliczny, tzn. nie posiada żadnego cyklu,

nazywamy drzewem.

Pytanie 11: Ile co najmniej krawędzi musi mieć graf niezorientowany o n wierzchołkach aby był spójny? Ile co najwyżej krawędzi może mieć graf niezorientowany, acykliczny o n wierzchołkach? Zachęcamy Czytelnika do wykonania kilku prób.

W drzewie wyróżniamy zwykle jeden wierzchołek i nazywamy go korzeniem. W drzewie turnieju, przedstawionym na rysunku 2.16 wyróżniliśmy wierzchołek o, odpowiadający zwycięzcy turnieju. Każdy inny wierzchołek jest połączony dokładnie jedną drogą z korzeniem. Wszystkie wierzchołki znajdujące się w takiej samej odległości od korzenia tworzą w tym drzewie poziom. Na przykład wierzchołki a,b,c,d,e,f,g,h znajdują się na czwartym poziomie drzewa turnieju, a wierzchołki m,n na drugim poziomie. Jeśli dwa wierzchołki x, y są połączone krawędzią i x znajduje się na poziomie niższym (bliżej korzenia) niż y, to wierzchołek x nazywamy poprzednikiem albo ojcem wierzchołka y, a y nazywamy następnikiem lub synem wierzchołka x. Na rysunku 2.16 wierzchołek n ma dwóch synów k i l, a wierzchołek f nie ma żadnego syna. Wierzchołki, które nie mają następników nazywa się liśćmi drzewa, a pozostałe wierzchołki - wewnętrznymi.

Obserwacja Każdy wierzchołek, z wyjątkiem korzenia, ma dokładnie jednego ojca.

Narysuj drzewo genealogiczne Twojej rodziny, tak by korzeniem tego drzewa był Twój Pradziadek.

Każde wyrażenie arytmetyczne można przedstawić w postaci drzewa, w którym liście odpowiadają zmiennym lub stałym występującym w wyrażeniu, wierzchołki wewnętrzne wykonywanym operacjom, a krawędzie wskazują argumenty tych operacji. Na rysunku 2.17 przedstawiono drzewo odpowiadające wyrażeniu arytmetycznemu (x + y) * Ö z . Na tym drzewie wyraźnie widać w jakiej kolejności trzeba wykonywać wskazane operacje. Korzeniem tego drzewa jest wierzchołek z operacją mnożenia.

Długość najdłuższej drogi od korzenia do liścia nazywamy wysokością drzewa. Jeśli każdy wierzchołek drzewa ma co najwyżej dwa następniki, to takie drzewo nazywamy binarnym. Ponieważ każdy wierzchołek drzew na rysunkach 2.16 i 2.17 ma co najwyżej 2 synów, więc są to drzewa binarne. Wysokość drzewa turnieju wynosi 3, a wysokość drzewa 2.17 wynosi 2.

Drzewo na rysunku 2.18b nie jest drzewem binarnym. Przedstawia ono fragment grafu możliwych sytuacji w opisanej poniżej grze Shannona dla grafu 2.18a. Na krawędziach drzewa zaznaczono możliwe ruchy graczy, tzn. dokonane wybory krawędzi.

Dany jest niezorientowany, spójny graf G i dwa wyróżnione jego wierzchołki A i B. Dwaj gracze wykonują naprzemiennie ruchy. Gracz 1, w każdym ruchu umacnia (np. zaznaczając ją grubą kreską) jedną z istniejących krawędzi. Gracz 2, w każdym ruchu usuwa (skreśla) jedną z nie umocnionych krawędzi grafu.

Celem dla gracza 1 jest zbudowanie drogi łączącej wierzchołki A i B. Celem dla gracza 2 jest uniemożliwienie graczowi 1 zbudowania tej drogi. Wygrywa gracz, który pierwszy osiągnie swój cel. Miłej zabawy.