PODSTAWY INFORMATYKI - GRAFY



Graf

Graf – to taka struktura danych, która składa się z wierzchołków i krawędzie, przy czym poszczególne wierzchołki (zwane też węzłami) mogą być połączone krawędziami (skierowanymi lub nieskierowanymi) w taki sposób, iż każda krawędź zaczyna się i kończy w którymś z wierzchołków. Wierzchołki i krawędzie mogą być numerowane, etykietowane i nieść pewną dodatkową informację - w zależności od potrzeby modelu, do którego konstrukcji są wykorzystane. W porównaniu do drzew w grafach mogą występować pętle i cykle. Krawędzie mogą mieć wyznaczony kierunek (wtedy graf nazywamy skierowanym), mogą mieć przypisaną wagę (pewną liczbę), kolor, etykietę, np. odległość pomiędzy punktami w terenie, rodzaj połączenia.
[Rozmiar: 17326 bajtów]
W ogólności dopuszcza się krawędzie wielokrotne i pętle (czyli krawędzie, które rozpoczynają i kończą się w tym samym wierzchołku).

Mosty królewieckie - narodziny grafów

W osiemnastym wieku mieszkańcy Królewca lubili spacerować po mostach na rzece Pregole, których mieli w mieście siedem. Plan mostów pokazuje rysunek. Ale takie zwykłe spacerowanie po jakimś czasie im się znudziło i zaczęli zastanawiać się, czy jest taka trasa spacerowa, która przechodzi przez każdy most dokładnie raz, żadnego nie omija, i pozwala wrócić do punktu wyjścia.
Nie potrafili sami rozwiązać tego problemu, więc napisali do znanego już wtedy matematyka Leonharda Eulera. Euler pokazał, że nie istnieje rozwiązanie tego zadania. (Jeśli wejdzie się po raz trzeci na wyspę, nie ma jak z niej wyjść.) Można tę sytuację przedstawić jako graf o wielokrotnych krawędziach:
[Rozmiar: 18131 bajtów]
Euler wykazał, że jest to niemożliwe, a decyduje o tym nieparzysta liczba wylotów mostów zarówno na każdą z wysp, jak i na oba brzegi rzeki. Szukając rozwiązania rozważył problem ogólniejszy, starając się ustalić warunki, które muszą być spełnione, żeby dany graf spójny można było opisać linią ciągłą w taki sposób, żeby każda jego krawędź grafu była odwiedziona dokładnie raz (patrz graf eulerowski). Euler pokazał, że jest to możliwe wtedy i tylko wtedy, gdy liczba wierzchołków tego grafu, w których spotyka się nieparzysta liczba krawędzi, jest 0 lub 2, czyli trzeba w grafie znaleźć cykl lub drogę Eulera, czyli cykl lub drogę przechodzący przez wszystkie wierzchołki i wszystkie krawędzie tego grafu dokładnie raz.

Rodzaje grafów

Istnieje wiele rodzajów grafów, które mogą mieć wiele interesujących właściwości. Grafy mogą być, np.:

Grafy w informatyce

Graf w informatyce jest najbardziej skomplikowaną podstawową strukturą danych. Stosy, kolejki, listy i drzewa można traktować jako szczególne przypadki grafu lub grafy uproszczone.
Grafy dostarczają nam potężne możliwości tworzenia różnego rodzaju relacji pomiędzy danymi, które można wiązać na wiele różnych sposobów, reprezentując lub modelując złożone zależności z otaczającego nas świata.
Grafy możemy zaimplementować w postaci tablicy określającej rodzaj połączenia oraz jego etykietę lub dynamicznie korzystając ze wskaźników.

[Rozmiar: 62394 bajtów] [Rozmiar: 57936 bajtów]

Teoria grafów

Teoria grafów to dział matematyki zajmujący się badaniem właściwości grafów. Informatyka zajmuje się rozwijaniem efektywnych algorytmów operujących na grafach, wyznaczających pewne właściwości grafów oraz modelowaniem różnych wycinków rzeczywistości z wykorzystaniem grafów.

Algorytm grafowy

Algorytm grafowy to algorytm rozwiązujący pewien problem z wykorzystaniem grafu (lub też rozwiązujący problem grafowy).

Problem grafowy

Problem grafowy to taki problem, który można rozwiązać przy pomocy grafu.

Droga w grafie

Droga to ścieżka/trasa wyznaczona przez krawędzie polegająca na przejściu od wierzchołka do wierzchołka po łączących je krawędziach od pewnego wyznaczonego wierzchołka początkowego do pewnego wierzchołka końcowego.

Cykl w grafie

Cykl to do droga zamknięta, czyli taka, która kończy się w początkowym wierzchołku drogi w grafie.

Pętla w grafie

Pętla to krawędź zaczynająca się i kończąca w tym samym wierzchołku grafu:
[Rozmiar: 12112 bajtów]

Podgraf

Podgraf to pewien wycinek grafu uzyskany przez usunięcie części wierzchołków wraz z krawędziami w nich kończących się:
[Rozmiar: 18503 bajtów]

Drzewo

Drzewo to graf spójny acykliczny, czyli taki, który nie zawiera żadnej drogi zamkniętej (żadnego cyklu).

Las

Las to graf niespójny, którego wszystkie spójne podgrafy są drzewami.

Ścieżka Eulera

Ścieżka Eulera to taka droga w grafie, która przechodzi przez każdą jego krawędź dokładnie raz.
Twierdzenie Eulera: W grafie można znaleźć ścieżkę Eulera wtedy i tylko wtedy, gdy graf jest spójny i każdy jego wierzchołek poza dwoma ma parzysty stopień.

Cykl Eulera

Cykl Eulera to taka droga w grafie, która przechodzi przez każdą jego krawędź dokładnie raz i powraca do początku (wierzchołka startowego) - czyli zamknięta ścieżka Eulera.
Twierdzenie Eulera: W grafie można znaleźć cykl Eulera wtedy i tylko wtedy, gdy graf jest spójny i każdy jego wierzchołek ma parzysty stopień.

Algorytm Fleury'a

Algorytm Fleury'a pozwala znaleźć cykl Eulera w każdym grafie, o ile istnieje:

  1. Rozpocznij od dowolnego wierzchołka v,
  2. Przejdź z wierzchołka v do dowolnego incydentnego wierzchołka w po niewykorzystanej do tej pory krawędzi v-w,
  3. Oznacz krawędź v-w jako już wykorzystaną.
  4. Powtarzaj kroki 2. i 3. tak długo dopóki nie powrócisz do wierzchołka startowego i wszystkie jego krawędzie nie zostaną oznaczone jako wykorzystane.

Przykład: W tak zaetykietowanym grafie rozwiązaniem jest na przykład droga przechodząca kolejno przez wierzchołki: 1, 2, 3, 1, 12, 11, 1, 10, 11, 13, 12, 3, 13, 14, 3, 4, 14, 15, 4, 5, 6, 4, 16, 15, 13, 22, 15, 17, 16, 6, 17, 18, 6, 7, 18, 19, 17, 22, 11, 21, 22, 19, 7, 8, 9, 7, 20, 19, 21, 20, 9, 21, 10, 9, 1.
(w tym rozwiązaniu przechodzimy po wszystkich krawędziach stopniowo poprzez trójkąty). Trzeba pamiętać, że nie jest to jedyne rozwiązanie, a zapis cyklu można zacząć od dowolnego wierzchołka.

[Rozmiar: 47294 bajtów]

Ścieżka Hamiltona

Ścieżka Hamiltona to taka droga w grafie, która przechodzi przez każdy jego wierzchołek dokładnie raz.

Cykl Hamiltona

Cykl Hamiltona to taka droga w grafie, która przechodzi przez każdy jego wierzchołek dokładnie raz i powraca do początku (wierzchołka startowego) - czyli zamknięta ścieżka Hamiltona.

Kolorowanie grafów

Kolorowanie grafów polega na przypisywaniu określonym elementom składowym grafu (wierzchołkom i krawędziom) wybranych kolorów według ściśle określonych reguł.

Wierzchołkowe kolorowanie grafów polega na przypisaniu wszystkim wierzchołkom w grafie wybranych barw w ten sposób, aby żadne dwa sąsiednie wierzchołki (czyli takie, które są połączone krawędzią) nie miały tego samego koloru – wtedy pokolorowanie nazywamy legalnym lub dozwolonym. Zamiast kolorów są w praktyce używane liczby. Innymi słowy pokolorowanie wierzchołków grafu jest legalne, gdy dowolnym dwóm wierzchołkom na końcach dowolnej krawędzi w grafie nie przyporządkowano tego samego koloru.

Optymalnym pokolorowaniem grafu nazywamy legalne pokolorowanie zawierające najmniejszą możliwą liczbę kolorów.

Liczbą chromatyczną grafu nazywamy liczbę równą najmniejszej możliwej liczbie kolorów potrzebnych do legalnego pokolorowania wierzchołków grafu, czyli tak, żeby każde dwa wierzchołki połączone krawędzią były pokolorowane innym kolorem.
PRZYKŁAD: Przy pomocy algorytmów znajdujących optymalne pokolorowanie wierzchołków grafu można rozwiązać następujący problem dotyczący składowania substancji chemicznych: Zakłady chemiczne wykorzystują przy produkcji n surowców chemicznych. Wiadomo, że niektóre substancje nie mogą być przechowywane razem, gdyż zetknięcie ich ze sobą spowodowałoby „zniszczenie magazynu”, ewentualnie katastrofę ekologiczną. Jaka jest minimalna liczba magazynów potrzebna do przechowywania wszystkich surowców chemicznych używanych w tej fabryce?
ROZWIĄZANIE: Tworzymy graf, którego n wierzchołków odpowiada poszczególnym surowcom chemicznym. Dwa wierzchołki łączymy krawędzią jeśli nie mogą być przechowywane razem. Minimalna liczba magazynów potrzebnych do składowania tych surowców jest równa liczbie chromatycznej tego grafu. Rozważmy dowolne pokolorowanie wierzchołków tego grafu, w którym każde dwa wierzchołki połączone krawędzią są pokolorowane innym kolorem. Surowce odpowiadające wierzchołkom pokolorowanym tym samym kolorem mogą być składowane w jednym magazynie!

Indeks chromatyczny grafu nazywamy liczbę równą najmniejszej możliwej liczbie kolorów potrzebnych do legalnego pokolorowania krawędzi grafu, czyli tak, żeby każde dwie krawędzie połączone do tego samego wierzchołka były pokolorowane innym kolorem.
PRZYKŁAD 1.: Rozważmy następujący problem. Dany jest zbiór m nauczycieli oraz zbiór n klas. Podane są także liczby godzin zajęć jakie musi odbyć w ciągu tygodnia dany nauczyciel z każdą z klas. Szukana jest minimalna liczba godzin w tygodniu, w czasie których mogą odbyć się wszystkie zajęcia. Wiadomo, że w danym momencie czasu nauczyciel może uczyć tylko jedną klasę i każda klasa może być uczona przez tylko jednego nauczyciela.
ROZWIĄZANIE: Stwórzmy graf dwudzielny, którego zbiór wierzchołków można podzielić na dwa rozłączne zbiory odpowiadające nauczycielom oraz klasom. W grafie tym dopuszczamy istnienie wielu krawędzi między każdą parą wierzchołków. Wierzchołek odpowiadający nauczycielowi łączymy tyloma krawędziami z wierzchołkiem odpowiadającym klasie, ile godzin zajęć musi on odbyć z tą klasą w ciągu tygodnia. Zauważmy, że jeśli pokolorujemy krawędzie tego grafu tak, aby każde dwie mające wspólny koniec były różnych kolorów, to krawędzie pokolorowane tym samym kolorem odpowiadają zajęciom, które mogą odbywać się równocześnie. Poszukujemy więc minimalnej liczby kolorów potrzebnych do pokolorowania w ten sposób wszystkich krawędzi. Innymi słowy, poszukiwany jest indeks chromatyczny tego grafu. Problem ten można oczywiście skomplikować dodając założenia dotyczące sal, w których zajęcia mogą się odbywać, bądź narzucając pewne terminy, w których dane zajęcia muszą się odbyć.
PRZYKŁAD 2.: Przypuśćmy, że mamy 5 nauczycieli: profesorów Mroza, Nowaka, Pawlaka, Cicho i Lisa oraz 4 klasy maturalne. Na poniższym rysunku pokazany jest graf stworzony na podstawie informacji o tym ile godzin zajęć w tygodniu z daną klasą ma poprowadzić każdy z nauczycieli. Dla przykładu: profesor Mróz ma 2 godziny z Iva i 1 godzinę z IVb a profesor Nowak po 1 godzinie z IVa i IVc.
[Rozmiar: 37834 bajtów]
ROZWIĄZANIE: Indeks chromatyczny tego grafu wynosi 4. Czyli w ciągu 4 godzin uda się przeprowadzić wszystkie zajęcia. Widać, że mniejsza liczba godzin nie wystarczy ponieważ profesor Lis musi przeprowadzić 4 godziny zajęć. Również klasy IVa, IVc oraz IVd mają zaplanowane po 4 godziny. A oto jak wygląda pokolorowanie krawędzi tego grafu na 4 kolory, w którym żadne dwie krawędzie o wspólnym wierzchołku nie mają tego samego koloru. Jeżeli przyjmiemy, że każdy kolor oznacza pewien 45 minutowy okres czasu (np. 8:15 – 9:00), to w prosty sposób tak pokolorowany graf można przekształcić w poniższą tabelę. W wierszach odpowiadających poszczególnym nauczycielom wypisane są klasy, które profesor powinien uczyć o danej godzinie (przy czym u góry każdej kolumny zamiast godziny jest kolor).
Profesor Mróz ma najpierw godzinę z IVa potem godzinę z IVb, znowu 1 lekcję z IVa i na koniec godzinę wolną. Kolejność terminów (kolorów) możemy ustawić w dowolny sposób. Czyli profesor Mróz może mieć wpierw 2 godziny z IVa a potem 1 lekcję z IVb. Wymaga to tylko zamiany miejscami 2-ej i 3-ej kolumny w tabeli.

Algorytm Dijkstry

Wyobraźmy sobie pewną mapę. Na mapie zaznaczone są drogi między poszczególnymi miastami oraz długości tych dróg. Wybierając z tej mapy dowolne dwa miasta A i B chcemy zaplanować najkrótszą trasę z miasta A do miasta B. Jak rozwiązać ten problem używając grafów?

Stwórzmy graf, którego wierzchołki odpowiadają miastom znajdującym się na danej mapie. Wierzchołki łączymy krawędzią, jeśli istnieje bezpośrednia (nie przebiegająca przez żadne inne miasto zaznaczone na tej mapie) droga łącząca odpowiadające im miasta. Krawędziom nadajemy wagi równe długości danej drogi. Oczywiście opcjonalnie długość drogi możemy zastąpić przez czas trwania podróży lub jej koszt. Znalezienie najkrótszej drogi z miasta A do miasta B oznacza znalezienie pomiędzy odpowiadającymi im wierzchołkami drogi o możliwie najmniejszej sumie wag krawędzi. Kiedy rozwiązanie tego problemu istnieje?

Jesteśmy w stanie znaleźć najkrótszą drogę, jeśli droga między danymi miastami (wierzchołkami w grafie) w ogóle istnieje. Aby można było znaleźć najkrótszą drogę między dowolną parą miast utworzony dla danej mapy graf musi być spójny, tzn. musi istnieć droga pomiędzy dowolnymi dwoma wierzchołkami w grafie. Najbardziej znanym algorytmem rozwiązującym ten problem jest algorytm Dijkstry.

Algorytm Dijkstry znajduje najkrótszą drogę z wierzchołka p (zwanego źródłem lub początkiem) do wszystkich pozostałych wierzchołków grafu lub do wybranego wierzchołka k (zwanego ujściem lub końcem) w grafie, w którym wszystkim krawędziom nadano nieujemne wagi. Polega na przypisaniu wierzchołkom pewnych wartości liczbowych. Taką liczbę nazwijmy cechą wierzchołka. Cechę wierzchołka v nazwiemy stałą (gdy jest równa długości najkrótszej drogi z p do v) albo, w przeciwnym przypadku, tymczasową. Na początku wszystkie wierzchołki, oprócz p, otrzymują tymczasowe cechy ∞. źródło p otrzymuje cechę stałą równą 0. Następnie wszystkie wierzchołki połączone krawędzią z wierzchołkiem p otrzymują cechy tymczasowe równe odległości od p. Potem wybierany jest spośród nich wierzchołek o najmniejszej cesze tymczasowej. Oznaczmy go v. Cechę tego wierzchołka zamieniamy na stałą oraz przeglądamy wszystkie wierzchołki połączone z v. Jeśli droga z p do któregoś z nich, przechodząca przez v ma mniejszą długość od tymczasowej cechy tego wierzchołka, to zmniejszamy tą cechę. Ponownie znajdujemy wierzchołek o najmniejszej cesze tymczasowej i zamieniamy cechę tego wierzchołka na stałą. Kontynuujemy to postępowanie aż do momentu zamiany cechy wierzchołka k na stałą (czyli obliczenia długości najkrótszej drogi z p do k).

[Rozmiar: 102042 bajtów]

Zastosowania algorytmu Dijkstry. Algorytmy znajdujące najkrótszą drogę w grafie są wykorzystywane do wyznaczania najlepszej trasy pomiędzy dwoma miastami na 'komputerowych' mapach. Mapy takie przydatne są w pracy np. firm transportowych.
Algorytm Dijkstry jest przykładem algorytmu zachłannego.

Algorytm Dijkstry - opis działania z prezentacją

Algorytm zachłanny (greedy algorithm)

Algorytm zachłanny (greedy algorithm) to taki algorytm, który w celu wyznaczenia rozwiązania w każdym kroku dokonuje najlepiej rokującego w danym momencie wyboru rozwiązania częściowego, tzw. zachłannego. Innymi słowy mówiąc algorytm zachłanny nie patrzy czy w kolejnych krokach jest sens wykonywać dane działanie, dokonuje lokalnie optymalną decyzję, dokonuje on wyboru wydającego się w danej chwili najlepszym, kontynuując rozwiązanie podproblemu wynikającego z podjętej decyzji.

Problem kojarzenia małżeństw

Załóżmy, że mamy k kawalerów i p panien oraz dla każdej z panien podany jest zbiór kawalerów, których zna. Czy jest możliwe wydanie za mąż każdej z kobiet za kawalera, którego zna?

Sformułowanie problemu przy pomocy grafów:
Zbudujmy graf, którego zbiór wierzchołków składa się z dwóch rozłącznych podzbiorów: zbioru kawalerów K i zbioru panien P. Wierzchołek x ze zbioru K łączymy krawędzią z wierzchołkiem y z P, jeśli panna y zna kawalera x. W otrzymanym grafie nie istnieją krawędzie między żadnymi dwoma wierzchołkami ze zbioru P ani żadnymi dwoma ze zbioru K. Jest to więc graf dwudzielny. Poszukiwany jest w tym grafie zbiór krawędzi M taki, że:

  1. żadna para krawędzi należących do M nie ma wspólnego wierzchołka (tj. małżeństwa są rozłączne – tzn. nie dopuszczamy bigamii),
  2. każdy wierzchołek ze zbioru P jest końcem pewnej krawędzi ze zbioru M (tj. każda panna wychodzi za mąż).
Zbiór krawędzi spełniający takie warunki nazywamy skojarzeniem doskonałym.
Kiedy istnieje rozwiązanie problemu kojarzenia małżeństw?

Twierdzenia Halla (warunek konieczny i wystarczający):
Problem kojarzenia małżeństw ma rozwiązanie wtedy, gdy każde m panien zna łącznie co najmniej m kawalerów, dla m=1,2, ...p.

Oto przykładowy graf dla zbioru P złożonego z trzech panien i zbioru K złożonego z trzech kawalerów. Każda z panien zna dokładnie dwóch kawalerów. Skojarzenie doskonałe istnieje i może wyglądać następująco: Ania może wyjść za Tomka, Kasia za Arka a Zosia za Jasia. Popatrzmy teraz na poniższy graf – w nim skojarzenie doskonałe nie istnieje, gdyż nie można znaleźć męża równocześnie dla Ani i Kasi, gdyż znają tylko Tomka:

[Rozmiar: 82926 bajtów]

Zastosowania.
Problem ten posiada bardziej poważne zastosowania. Przy użyciu tej samej metody możemy rozwiązać problem polegający na przydzieleniu pracownikom zajęć zgodnie z ich kwalifikacjami. W tym przypadku przez P należy rozumieć zbiór pracowników, K zbiór żądań do wykonania. Dwa wierzchołki x i y łączymy krawędzią, jeśli praca y jest zgodna z kwalifikacjami pracownika x (to znaczy może on ją wykonywać).

Problem chińskiego listonosza

Listonosz wyrusza z poczty, dostarcza przesyłki adresatom, by na końcu wrócić na pocztę. Aby wykonać swoją pracę musi przejść po każdej ulicy w swoim rejonie co najmniej raz. Oczywiście chciałby, aby droga, którą przebędzie, była możliwie najkrótsza. Problem ten został sformułowany po raz pierwszy w języku teorii grafów przez chińskiego matematyka Mei Ku Kwana w 1962 roku.
Sformułowanie problemu:
Rozważmy graf, którego krawędzie odpowiadają ulicom w rejonie, odsługiwanym przez listonosza. Wierzchołki to po prostu skrzyżowania ulic. Krawędziom nadajemy wagi, które oznaczają odległości między dwoma skrzyżowaniami. Znalezienie możliwie najkrótszej drogi, którą musi przejść listonosz sprowadza się do znalezienia w tym grafie drogi o minimalnej sumie wag krawędzi, która przechodzi przez każdą krawędź co najmniej raz.
Jeśli graf posiada cykl Eulera, to istnieje taka droga, która zaczyna i kończy się w tym samym punkcie i wymaga przejścia po każdej ulicy dokładnie raz. Zauważmy, że ponieważ każdy cykl Eulera przechodzi raz przez każdą krawędź to suma wag krawędzi (długość drogi, którą musi przejść listonosz) jest zawsze taka sama (nie zależy od wierzchołka, w którym cykl ten zaczyna się i kończy). Rozwiązaniem jest więc dowolny cykl Eulera w tym grafie.
Jeśli graf nie posiada cyklu Eulera, listonosz będzie zmuszony przejść niektórymi ulicami wielokrotnie. Rozwiązanie jest więc cyklem, w którym suma długości krawędzi wybranych więcej niż raz jest możliwie najmniejsza.

Na rysunku pokazany jest układ ulic niedaleko Politechniki Warszawskiej. Załóżmy, że fragmenty tych pięciu ulic tworzą rejon listonosza. Obok nazw ulic umieszczone są odległości w metrach. Prostokąt oznaczony literą P oznacza miejsce, w którym umieściliśmy pocztę, na której pracuje 'nasz' listonosz. (Na marginesie: nazwy i układ ulic są prawdziwe, jednak podane odległości oraz umiejscowienie poczty nie odpowiadają rzeczywistości. Pocztę umieściliśmy w miejscu, gdzie w rzeczywistości znajduje się Gmach Główny, w którym ma swoją siedzibę Wydział MiNI. I niestety nie ma w tym budynku poczty.) Oto jak wygląda graf odpowiadający danemu układowi ulic. Zauważmy, że graf ten nie ma cyklu Eulera ponieważ posiada dwa wierzchołki, z których wychodzi nieparzysta liczba krawędzi. Na rysunku zaznaczono również rozwiązanie czyli optymalną trasę listonosza.
Zwróćmy uwagę, że listonosz musi przejść dwukrotnie tylko ulicę Noakowskiego, zaś pozostałe ulice dokładnie raz. Powyższa droga jest najkrótszą z możliwych ponieważ odcinek, po którym przechodzi dwukrotnie liczy tylko 500 metrów i nie istnieje trasa spełniająca zadane warunki o krótszym odcinku, który listonosz musi pokonać więcej niż raz.

[Rozmiar: 130576 bajtów]

Problem komiwojażera

Dane jest n miast, które komiwojażer ma odwiedzić, oraz odległość pomiędzy każdą parą miast. Komiwojażer ma za zadanie dotrzeć do każdego z nich i wrócić do miasta, z którego wyruszył. Jak powinien zaplanować trasę podróży, aby w sumie przebył możliwie najkrótsza drogę?
Przez odległość między miastami możemy rozumieć odległość w kilometrach, czas trwania podróży między tymi miastami albo koszt takiej podróży (na przykład cenę biletu lotniczego). W takim ostatnim przypadku, poszukiwanie optymalnej trasy polega na zminimalizowaniu całkowitych kosztów podróży. Tak więc możemy poszukiwać trasy najkrótszej, najszybszej albo najtańszej. Zakładamy przy tym, że odległość między dowolnymi dwoma miastami jest nie większa niż długość jakiekolwiek drogi łączącej te miasta, która wiedzie przez inne miasta. Założenie to tylko z pozoru wydaje się być zawsze spełnione.
PRZYKŁAD: Załóżmy, że interesuje nas czas trwania podróży koleją. Najszybsze połączenie z Katowic do Białegostoku wiedzie przez Warszawę. Czas trwania tej podróży traktujemy w tym przypadku jako „odległość” z Katowic do Białegostoku.
Sformułowanie problemu przy pomocy grafów: Zbudujmy graf ważony, którego wierzchołki są miastami. Każda parę miast połączmy krawędziami. Każdej krawędzi nadajemy wagę równa „odległości” między miastami odpowiadającymi wierzchołkom, które są końcami tej krawędzi. Otrzymujemy w ten sposób graf pełny, który ma tyle wierzchołków, ile miast musi odwiedzić komiwojażer (wliczając w to miasto, z którego wyrusza). Odwiedzenie wszystkich miast odpowiada cyklowi, który przechodzi przez każdy wierzchołek danego grafu dokładnie raz - wobec tego szukamy cyklu Hamiltona o minimalnej sumie wag krawędzi.
[Rozmiar: 28104 bajtów]
Rysunek przedstawia graf ważony o wierzchołkach odpowiadających pięciu polskim miastom. Wagami krawędzi są odległości podane w kilometrach. Poszukujemy rozwiązania następującego problemu: Komiwojażer wyrusza z Warszawy i chce odwiedzić wszystkie pozostałe cztery miasta a następnie wrócić do Warszawy. Jak powinien zaplanować podróż, aby przebył możliwie najmniejsza liczbę kilometrów?
Już przy pięciu miastach wszystkich możliwych tras podróży komiwojażera jest 4!/2. Można zauważyć, że przy większej liczbie miast rozważanie wszystkich możliwości nie jest najlepszym pomysłem. Ze względu na dużą złożoność obliczeniową poszukiwania rozwiązania stosujemy często algorytmy przybliżone, które dostarczają zwykle pewnych rozwiązań suboptymalnych, ale dostępnych w realnym czasie.
Dlaczego rozwiązanie tego problemu zawsze istnieje? - Dowolny graf pełny posiada co najmniej jeden cykl Hamiltona. Ponieważ graf ma skończona liczbę wierzchołków, to w zbiorze cykli Hamiltona istnieje taki (niekoniecznie jedyny), który posiada minimalna sumę wag krawędzi. Istnieje wiele algorytmów rozwiązujących ten problem, jednak wszystkie mają jedną podstawową wadę – wymagają rozważenia bardzo dużej liczby przypadków i czas ich działania może być bardzo długi. Niewielki przyrost liczby miast powoduje ogromny wzrost ilości przypadków do rozważenia i tym samym czasu działania algorytmu. Algorytm obliczający całkowitą długość wszystkich istniejących w danym grafie cykli Hamiltona ma złożoność n!/2. Na przykład dla 20 miast liczba cykli Hamiltona w grafie pełnym o 20 wierzchołkach wynosi około 6000000!

Algorytmy przybliżone

Ze względu na dużą złożoność obliczeniową algorytmów dokładnych, przeszukujących całą przestrzeń rozwiązań, zmuszeni jesteśmy czasami zastosować algorytmy mniej dokładne ale charakteryzujące się mniejszą złożonością obliczeniową.
Czas rozwiązywania problemu komiwojażera można zmniejszyć stosując jeden ze znanych algorytmów przybliżonych, który nie wymaga rozważania aż tak dużej liczby przypadków. Jednak algorytm ten nie zawsze znajduje optymalne rozwiązanie. Stworzona przez nie trasa może być znacznie dłuższa od najkrótszej. Stosowanie algorytmów przybliżonych wynika z konieczności znalezienia sensownego kompromisu pomiędzy szybkością znajdowania rozwiązania a jego jakością. Z reguły zakłada się, że wynik działania takiego algorytmu nie może być gorszy od optymalnego o więcej niż pewna ustalona z góry wartość.
Znajdowanie cyklu Hamiltona w dowolnym grafie:

Problem polegający na znalezieniu cyklu Hamiltona jest podobnie jak problem komiwojażera trudny ze względu na długi czas działania znanych algorytmów. Do znalezienia takiego cyklu może wystarczyć trochę szczęścia. Gorzej jest kiedy cykl Hamiltona w badanym grafie nie istnieje. W takim przypadku możemy nawet być zmuszeni do sprawdzenia wszystkich możliwych permutacji zbioru wierzchołków, aby uzyskać pewność, że cykl taki nie istnieje.

Problem niezawodności sieci

Wyobraźmy sobie, że chcemy zaprojektować sieć komunikacyjną (np. telekomunikacyjną, drogową, komputerową). Składa się ona z pewnej liczby punktów węzłowych (np. terminali komputerowych) i bezpośrednich połączeń (linii) między niektórymi z nich. Jak przedstawić sieć komunikacyjną przy pomocy grafu?
Sieć taką możemy przedstawić za pomocą grafu, którego wierzchołki odpowiadają punktom węzłowym a krawędź między dwoma wierzchołkami oznacza bezpośrednie połączenie linią danych dwóch punktów węzłowych. Oto przykładowa sieć składająca się z 6 punktów węzłowych oznaczonych literami A, B, C, D, E, F i pewnych krawędzi między nimi.
[Rozmiar: 17025 bajtów]
Wiemy, że nic nie jest doskonałe i sieć narażona jest na awarie. Spójność wierzchołkowa takiego grafu jest równa minimalnej liczbie awarii w punktach węzłowych sieci, które spowodują awarię całej sieci (to znaczy między niektórymi węzłami zostanie zerwane połączenie). Natomiast spójność krawędziowa oznacza minimalną liczbę awarii łączy między węzłami, które spowodują awarię sieci. Przez niezawodność sieci możemy rozumieć maksymalną liczbę awarii, których wystąpienie nie spowoduje awarii całej sieci. Im większa spójność grafu tym większa niezawodność sieci: Jak skonstruować sieć by jej niezawodność była możliwie największa? Oczywiście im więcej linii (krawędzi) tym niezawodność większa. Z drugiej jednak strony zbudowanie każdego połączenia kosztuje. Możemy założyć, że szukamy możliwie najtańszej sieci o z góry założonej niezawodności, bądź szukamy sieci o ustalonym koszcie i możliwie największej niezawodności. Jedno z możliwych sformułowań tego problemu wygląda następująco:
Załóżmy, że dana jest liczba punktów węzłowych oraz żądana niezawodność sieci k (liczba 'dopuszczalnych' awarii). Zbudowanie każdego bezpośredniego połączenia obarczone jest pewnym kosztem jednostkowym (jest to pewne uproszczenie - w rzeczywistości koszty budowy połączeń są różne). Chcemy zaprojektować sieć o żądanej niezawodności, której koszt budowy będzie możliwie najmniejszy. Poszukujemy więc grafu o n wierzchołkach i możliwie najmniejszej liczbie krawędzi, którego spójność wierzchołkowa lub spójność krawędziowa wynosi k.