Grafy i sieci - ebook

Od Autorów

Za narodziny teorii grafów przyjmuje się zazwyczaj rok 1736, gdy Leonard Euler opublikował pracę Solutio problematis ad geometriam situs pertinentis, w której sformułował i rozwiązał tzw. problem mostów królewieckich (p. rozdz. 1). Tematyka teorii grafów okazała się atrakcyjna dla matematyków, a także dla osób zajmujących się naukami stosowanymi i od publikacji Eulera przeżywa intensywny rozwój.

Pierwszymi naukami stosowanymi wykorzystującymi teorię grafów były nauki elektryczne (od prawa Kirchhoffa aż po topologiczne metody analizy obwodów), a później również chemia, nauki ekonomiczne, logistyka, transport itd. W ostatnich dziesięcioleciach obserwujemy intensywny rozwój zastosowań teorii grafów w informatyce – zarówno w warstwie metod (bazy danych, sztuczna inteligencja), jak i algorytmów kombinatorycznych.

Dostępne podręczniki dotyczące grafów są najczęściej publikacjami zagranicznymi w języku angielskim. Literatura polska jest dość uboga. Spośród znaczących książek można wskazać tłumaczone z angielskiego dwie pozycje: R. Wilsona: Wprowadzenie do teorii grafów z 2004 roku oraz N. Deo: Teoria grafów i jej zastosowania w technice i informatyce z 1980 roku. Ta ostatnia książka przez wiele lat była ważna dla nauk stosowanych, a zwłaszcza elektroniki i informatyki.

Większość książek z grafów i sieci jest pisana przez matematyków i dla matematyków. Drugi nurt to książki na poziomie popularyzatorskim. Na polskim rynku brakuje współczesnego podręcznika. Ta książka wypełnia tę lukę, a jej cechą wyróżniającą jest zharmonizowanie teorii z praktycznymi umiejętnościami rozwiązywania problemów.

Od piętnastu lat prowadzimy wykład z grafów i sieci na Wydziale Elektroniki i Technik Informacyjnych Politechniki Warszawskiej. Wykład jest oferowany co semestr dla grupy około 80 studentów. Wieloletnia popularność wykładu zachęciła nas do napisania tej książki. Słuchacze wykładu to studenci studiów magisterskich specjalności informatyka lub telekomunikacja oraz doktoranci. Powody, dla których studenci wybierają ten wykład, są silnie zróżnicowane. Niektórzy wybierają go z czystego zainteresowania teorią grafów, inni jako przedmiot wspomagający do studiów w zakresie telekomunikacji i informatyki lub innych dziedzin zastosowań.

Adresatami książki mogą być również pracownicy naukowo-badawczy uczelni i instytutów, instytucji mających piony badawcze oraz inżynierowie projektanci. Książka będzie też przydatna dla doktorantów prowadzących badania w dziedzinach, w których teoria grafów dostarcza użyteczne modele, metody ich analizy oraz algorytmy.

Książka składa się z dziewiętnastu rozdziałów i rozszerza zakres wykładu prowadzonego przez nas. Zawiera też wyniki naszych własnych prac badawczych. Każdy rozdział to jeden lub dwa dwugodzinne wykłady akademickie. Typowo semestr trwa 15 tygodni. Książka zawiera więc nadmiar materiału dla jednosemestralnego wykładu. Wykłady z grafów i sieci lub pokrewne są prowadzone w wielu polskich uczelniach. Pisząc tę książkę, wzięliśmy pod uwagę zarówno różnorodność zastosowań, jak i różnorodność programów przedmiotu. Wykładowcy będą mogli wybierać poszczególne rozdziały odpowiadające ich przedmiotowi.

Rozdziały książki mają powtarzalną strukturę: część opisowa (notacja, definicje, teoria), algorytmy, zadania oraz wykaz literatury. W sumie jest 470 zadań, nie wliczając przykładów umieszczonych w tekście. Około 80 procent zadań ma podane pełne rozwiązania. Naszą intencją jest, by część opisowa dawała Czytelnikowi podstawy teoretyczne, część zadaniowa umiejętności praktyczne, a algorytmy – pokazywały, w jaki sposób można zaimplementować teorie.

Wydanie tej książki nie byłoby możliwe bez wsparcia finansowego. Chcąc wyrazić wdzięczność instytucjom, które w trudnym ekonomicznie okresie wsparły finansowo jej wydanie, chcemy podziękować Wydziałowi Elektroniki i Technik Informacyjnych Politechniki Warszawskiej, który w osobie ówczesnego dziekana Wydziału, a obecnie Rektora PW profesora Jana Szmidta, szczodrze dotował wydanie. Podziękowania na­leżą się również instytutowi badawczemu Naukowa i Akademicka Sieć Komputerowa (NASK), który poprzez dyrektora Michała Chrzanowskiego sponsorował wydanie książki.

Warszawa, wrzesień 20131 Definicja grafu i przykłady zastosowań

1.1. Podstawowe pojęcia grafów

Pojęcie grafu jest dość intuicyjne i być może z tego powodu w różnych podręcznikach spotykamy nieco różniące się definicje, w zależności od tego, jaką klasę problemów autor chce modelować.

Pojęciami pierwotnymi są: zbiór wierzchołków, który będziemy oznaczali jako V oraz rodzina krawędzi oznaczana symbolem E (rodzina, w odróżnieniu od zbioru, może zawierać elementy powtarzające się). Grafem nazywamy parę uporządkowaną G = (V, E). Graf musi mieć co najmniej jeden wierzchołek, , oraz . Liczbę wierzchołków grafu będziemy oznaczali symbolem n, a liczbę krawędzi symbolem q. Ograniczymy się do klasy grafów skończonych, tzn. takich, że n i q są liczbami skończonymi.

Krawędzią grafu e ∈ E jest uporządkowana para wierzchołków e = (v₁, v₂), v₁ ∈ V, v₂ ∈ V. Jeżeli rodzina E zawiera powtarzające się elementy, to takie krawędzie nazywamy równoległymi lub wielokrotnymi. Jeżeli (v₁, v₂) ∈ E i (v₂, v₁) ∈ E, to taka para jest nazywana krawędzią niezorientowaną (nieskierowaną) lub wprost krawędzią i oznaczana symbolem e = {v₁, v₂}. Jeśli (v₁, v₂) ∈ E, (v₂, v₁) ∉ E, to krawędź nazywamy łukiem albo krawędzią zorientowaną (skierowaną). Jeżeli łuk łączy wierzchołek v z w, to v jest poprzednikiem wierzchołka w, a w jest następnikiem v.

Na podstawie wprowadzonej terminologii możemy dokonać wstępnej klasyfikacji grafów.

Graf niezorientowany (nieskierowany) – graf niezawierający łuków.

Graf zorientowany (skierowany) – graf niezawierający krawędzi niezorientowanych.

Multigraf – graf z krawędziami równoległymi.

Graf zwyczajny (prosty) – graf niezorientowany bez pętli i krawędzi równoległych (tzn. rodzina krawędzi jest po prostu zbiorem).

Powyższa klasyfikacja nie jest wyczerpująca, ponieważ np. istnieją grafy zawierające zarówno krawędzie, jak i łuki (czasami są one nazywane grafami częściowo zorientowanymi). Przykładem takiego grafu może być sieć ulic miasta, w której skrzyżowania są reprezentowane przez wierzchołki, a ulice przez krawędzie. Niektóre z ulic mogą być dwukierunkowe, a inne jednokierunkowe. Na podstawie tego przykładu można również zaobserwować względność modelu: niektóre z ulic miasta są wielopasmowe i tylko od analizowanego problemu zależy, czy będziemy takie ulice reprezentować za pomocą krawędzi pojedynczych, czy równoległych.

Odrębną klasą grafów są tzw. grafy ważone. G = (V, E) nazywamy grafem ważonym, jeżeli istnieje funkcja w: E → R⁺ przyporządkowująca każdej krawędzi dodatnią liczbę rzeczywistą. W zależności od kontekstu jest ona nazywana wagą lub kosztem krawędzi.

Mówimy, że dwa wierzchołki v, u sąsiadują ze sobą, jeżeli istnieje krawędź grafu łącząca te wierzchołki. Jeżeli krawędź e ∉ E łączy wierzchołki v, u, to krawędź jest incydentna z tymi wierzchołkami (co zapisujemy veu).

Jeżeli G = (V, E) jest grafem niezorientowanym, to stopniem d(v) wierzchołka v ∈ V nazywamy liczbę krawędzi incydentnych z wierzchołkiem v. Przyjmujemy, że pętle są liczone podwójnie. Jeżeli G jest grafem zorientowanym, to z każdym wierzchołkiem jest związany stopień wyjściowy i stopień wejściowy. Stopień wyjściowy d ⁺(v) jest równy liczbie łuków incydentnych z v i zorientowanych od tego wierzchołka. Stopień wejściowy d ^(–)(v) jest liczbą łuków incydentnych z v i zorientowanych do wierzchołka.

Chociaż graf jest pojęciem abstrakcyjnym, to często reprezentujemy go w postaci rysunku na płaszczyźnie. Wierzchołki grafu przedstawiamy jako punkty płaszczyzny, a krawędzie jako linie łączące pary wierzchołków. Przyjmuje się symbole graficzne krawędzi pokazane na rys. 1.1.

Rys. 1.1. Reprezentacja krawędzi grafu: a) krawędź niezorientowana; b) łuk; c) pętla

Wprowadzone przez nas grafy są grafami nieetykietowanymi, tzn. krawędzie nie mają etykiet i są identyfikowane przez podanie wierzchołków końcowych. Jednym ze skutków takiej definicji jest brak możliwości jednoznacznej identyfikacji krawędzi równoległych. Wprowadza się również pojęcie grafu etykietowanego, w którym każda z krawędzi ma nadaną unikalną etykietę. Na rysunku 1.2a są pokazane dwie sieci elektryczne, a na rys. 1.2b – struktura połączeń krawędzi tych sieci reprezentowanych za pomocą zorientowanego grafu nieetykietowanego (orientacja łuków jest zgodna z kierunkiem przepływającego prądu). Grafy etykietowane odpowiadające tym sieciom są pokazane na rys. 1.2c. Dla tych, którzy trochę znają teorię obwodów elektrycznych, jest oczywiste, że graf nieetykietowany wystarcza do napisania równań Kirchhoffa (identycznych dla obu obwodów), natomiast do obliczenia prądów i napięć musimy się posłużyć grafem etykietowanym.

Rys. 1.2. Sieci elektryczne: a) schematy elektryczne; b) model jako graf nieetykietowany; c) model jako graf etykietowany

W podręcznikach teorii grafów zazwyczaj podaje się pewne rodzaje grafów jako grafy przykładowe. Poniżej przedstawimy niektóre z nich.

Ścieżka (lub łańcuch) n-wierzchołkowa P_(n) jest grafem:

- – niezorientowanym, w którym są dwa wierzchołki stopnia pierwszego i n – 2 wierzchołków stopnia drugiego. Przykład ścieżki P₅ jest pokazany na rys. 1.3a;
- – zorientowanym, w którym istnieją wierzchołki v, w nazywane wierzchołkiem początkowym i końcowym ścieżki takie, że d ⁺(v) = d ^(–)(w) = 1 oraz d ^(–)(v) = d ⁺(w) = 0 (rys. 1.3b).

Cyklem n-wierzchołkowym C_(n) jest graf:

- – niezorientowany, w którym stopnie wszystkich wierzchołków są równe 2 i dowolną parę wierzchołków można połączyć ścieżką (rys. 1.3c);
- – zorientowany, w którym stopień wejściowy i wyjściowy każdego z wierzchołków jest równy 1 i dowolną parę wierzchołków można połączyć ścieżką zorientowaną (rys. 1.3d).

Gwiazda K_(l,m) ma jeden wierzchołek stopnia m i m wierzchołków stopnia pierwszego. Gwiazda o sześciu wierzchołkach jest pokazana na rys. 1.3e.

Koło n-wierzchołkowe (n ≥ 4) W_(n) jest grafem, w którym jeden wierzchołek jest stopnia n – 1, a pozostałe wierzchołki są wierzchołkami stopnia 3 (rys. 1.3f).

Wachlarz n-wierzchołkowy (n ≥ 3) F_(n) jest grafem o jednym wierzchołku stopnia n – 1, n – 3 wierzchołkach stopnia 3 oraz dwóch wierzchołkach stopnia 2. Wachlarz otrzymuje się poprzez usunięcie jednej krawędzi leżącej na obwodzie koła (rys. 1.3g).

Krata L_(k,m), l ≥ 2, m ≥ 2 jest grafem o zbiorze wierzchołków {1, 2 …, l} × {1, 2 …, m}. Pomiędzy wierzchołkami (i₁, j₁) i (i₂, j₂) istnieje krawędź wtedy i tylko wtedy, gdy | i₁ – i₂ | + | j₁ – j₂ | = 1. Przykład kraty o l = 2, m = 3 przedstawia rys. 1.3h.

Rys. 1.3. Przykłady niektórych grafów: a) ścieżka niezorientowana P₅; b) ścieżka zorientowana P₅; c) cykl niezorientowany C₅; d) cykl zorientowany C₅; e) gwiazda K_(1,5); f) koło W₆; g) wachlarz F₆; h) krata 2 × 3

Aby zachęcić Czytelnika do głębszego zainteresowania grafami, w dalszym tekście przedstawimy kilkanaście prostych problemów ilustrujących zastosowania grafów do modelowania i analizy zjawisk oraz procesów. Przytoczone przykłady nie wyczerpują oczywiście bogactwa zastosowań. Za pierwszy impuls do powstania teorii grafów jako działu kombinatoryki uważa się problem mostów królewieckich sformułowany i rozwiązany przez Leonarda Eulera. Niemal wszystkie książki zajmujące się grafami rozpoczynają się od zacytowania tego problemu. W tej książce zgodnie z tradycją również przedstawimy problem mostów królewieckich, zwłaszcza że będzie to intuicyjnym wprowadzeniem do rozdziału 7 omawiającego tzw. grafy Eulera.

Rys. 1.4. Problem Eulera mostów królewieckich

Przez znaczną część swojego życia Euler pracował w Königsberg (Królewcu, Kaliningradzie). W mieście tym znajdował się park, do którego Euler chodził na spacery. Przez park płynęła rzeka Pregoła, a na niej były dwie wyspy i siedem mostów. Rysunek 1.4a schematycznie przedstawia sytuację topograficzną miejsca. Euler spacerując, zadał sobie pytanie, czy startując z dowolnego punktu, można tak zaprojektować trasę spaceru, aby przejść przez wszystkie mosty, przekraczając każdy z nich dokładnie jeden raz. Zadanie Eulera można łatwo sformułować jako problem grafowy. Na rysunku 1.4b jest przedstawiony model grafowy problemu. Wierzchołki grafu odpowiadają częściom lądowym parku, a krawędzie reprezentują mosty. Można łatwo stwierdzić, że odpowiedź jest negatywna. W 1736 roku Euler uogólnił i rozwiązał problem mostów królewieckich dla dowolnych grafów . Grafy, w których istnieje droga zamknięta spełniająca omówione warunki, noszą nazwę grafów Eulera. Graf pokazany na rys. 1.4b jest grafem ważonym. Wagi można interpretować np. jako długości odcinków drogi.

1.2. Przykłady zastosowań grafów

Problem 1.1. Graf znajomości

W trzypiętrowym budynku mieszkalnym na każdym poziomie są dwa mieszkania. Mieszka w nich osiem rodzin: na parterze Kowalscy (K) i Wiśniewscy (W), na pierwszym piętrze Zarembowie (Z) i Nowakowie (N), na drugim Adamscy (A) i Michalscy (M), a na trzecim Biernaccy (B) i Słowikowie (S). Przyjmujemy, że rodziny mieszkające na tym samym piętrze znają się nawzajem i znają rodziny mieszkające na wyższych piętrach. Mając do dyspozycji tę informację, narysujemy tzw. graf znajomości (rys. 1.5). W tym grafie wierzchołkami są rodziny, a krawędzie pokazują, że rodziny znają się nawzajem.

Rys. 1.5. Graf znajomości

Problem 1.2 . Uściski dłoni

Państwo Kowalscy zaprosili cztery pary małżeńskie na spotkanie w ich domu. Kiedy goście przybywali, niektórzy z nich na powitanie wymienili uściski dłoni z już obecnymi. Oczywiście nikt nie wymieniał uścisku dłoni ze swoim współmałżonkiem ani dwukrotnie z tą samą osobą. Kiedy wszyscy goście przybyli, pani Kowalska zapytała każdego z gości, ile uścisków dłoni wymienił. W odpowiedzi każdy z zapytanych podał inną liczbę. Ile uścisków dłoni wymienił pan Kowalski?

Rozwiązanie

Pytanie do tego zadania nie ma pozornie głębszego związku logicznego z jego treścią. Pokażemy, w jaki sposób model grafowy ułatwi rozwiązanie tego problemu kombinatorycznego. Osoby biorące udział w przyjęciu są reprezentowane przez wierzchołki grafu. Pary, które wymieniły uścisk dłoni łączymy krawędzią. Liczba wierzchołków grafu jest równa 10. Najmniejsza liczba uścisków może być równa zeru, a największa osiem. Wierzchołek reprezentujący panią Kowalską opatrzymy etykietą 9, a każdy z pozostałych wierzchołków grafu otrzyma numer będący liczbą uścisków dłoni wymienionych przez daną osobę. Pierwszy krok rozwiązania jest przedstawiony na rys. 1.6a. Wierzchołek reprezentujący panią Kowalską wyróżniono innym symbolem graficznym.

Rys. 1.6. Ilustracja algorytmu obliczania uścisków dłoni

Osoba o numerze 0 nie wymieniła żadnego uścisku dłoni. Zatem osoba o numerze 8 musiała wymienić uściski ze wszystkimi osobami o numerach 1–7 oraz z panią Kowalską. Goście o numerach 0, 8 tworzą więc parę małżeńską. Następnym gościem o największej liczbie uścisków jest osoba opatrzona etykietą 7. Nie mógł on wymienić pozdrowień z osobami o numerach 0, 1 (wyczerpane limity uścisków), a zatem musiał uścisnąć dłonie osób o numerach 2–6, pani Kowalskiej oraz zgodnie z poprzednim krokiem gościa o numerze 8 (rys. 1.6b). Małżonkiem tej osoby jest gość oznaczony numerem 1. W następnym kroku budowania modelu grafowego wierzchołek o numerze 6 staje się wierzchołkiem rozpatrywanym. Osoba etykietowana tym numerem nie mogła wymienić pozdrowień z gośćmi o numerach 0, 1, 2. Musiała uścisnąć dłonie osób o numerach 3, 4, 5, pani Kowalskiej i zgodnie z poprzednimi krokami gości o numerach 7 i 8 (rys. 1.6c). Małżonkiem tej osoby jest gość opatrzony numerem 2. Przechodząc do wierzchołka o numerze 5, w podobny sposób stwierdzamy, że osoba etykietowana tym numerem nie mogła wymienić uścisku z gośćmi o numerach 0, 1, 2, 3. Natomiast wymieniła uściski z osobą o numerze 4, panią Kowalską oraz zgodnie z poprzednimi krokami z gośćmi o numerach 6, 7, 8. Tę sytuację przedstawia graf na rys. 1.6d. Małżonkiem osoby o etykiecie 5 jest gość opatrzony numerem 3. Tym krokiem zakończyliśmy procedurę, gdyż stopień każdego wierzchołka budowanego grafu jest równy jego numerowi. Małżonkiem pani Kowalskiej może być tylko osoba o etykiecie 4, a pan Kowalski wymienił cztery uściski dłoni.

Problem 1.3. System ostrzegania pomiędzy zamkami

W średniowieczu do obrony terytorium służył system zamków obronnych. W przypadku zbliżania się nieprzyjaciela zamki przesyłały sobie nawzajem ostrzeżenia. Przypuśćmy, że rozpatrywane terytorium jest kwadratem o boku 50 km. Znajduje się na nim 7 zamków: trzy duże i cztery małe. Informacje z dużych zamków mogą być przesyłane na odległość nie większą niż 20 km, a z małych do 14 km. Przyjmijmy jeden z wierzchołków kwadratu za początek układów współrzędnych. Lokalizacja poszczególnych zamków jest opisana w tabeli 1.1 podającej współrzędne (x, y) zamku. Chcemy narysować graf obrazujący system komunikacji.

Tabela 1.1. Współrzędne położenia zamków

------------- ---------- ---------- ---------- ---------- ---------- ---------- ----------
Zamek A B C d e f g
Typ duży duży duży mały mały mały mały
Współrzędne (14, 16) (34, 14) (25, 35) (25, 10) (12, 35) (37, 37) (24, 25)
------------- ---------- ---------- ---------- ---------- ---------- ---------- ----------

System obronny był pomyślany tak, aby informacja wysłana z dowolnego zamku mogła być przekazana do wszystkich pozostałych. Czy ten warunek jest spełniony? Podczas złej pogody zasięg przesyłu informacji z każdego zamku maleje o 10%. Czy nadal informacja wysłana z dowolnego zamku może być przekazana do wszystkich pozostałych zamków? Gdy jeden z zamków (dowolny) wskutek awarii nie będzie mógł przesyłać informacji, czy system ostrzeżeń będzie nadal działał poprawnie pomiędzy pozostałymi zamkami?

Rozwiązanie

W tabeli 1.2 przedstawiono odległości zamków. Pogrubionym drukiem zaznaczono odległości mniejsze od zasięgu przesyłu informacji, zakładając, że element wiersz przesyła informację do elementu kolumny.

Graf sieci komunikacji zamków jest przedstawiony na rys. 1.7a. Poprzez inspekcję grafu stwierdzamy, że z każdego wierzchołka grafu istnieje ścieżka zorientowana do dowolnego innego (graf jest silnie spójny, p. rozdz. 5).

Tabela 1.2. Odległości między zamkami

--- ------- ------- ------- ------- ------- ------- -------
A B C d e f g
A – 20,01 21,95 12,53 19,11 31,14 13,45
B 20,01 – 22,85 9,85 30,41 23,19 14,87
C 21,95 22,85 – 25,00 13,00 12,16 10,05
d 12,53 9,85 25,00 – 28,18 29,55 15,03
e 19,11 30,41 13,00 28,18 – 25,08 15,02
f 31,14 23,19 12,16 29,55 25,08 – 17,69
g 13,45 14,87 10,05 15,03 15,02 17,69 –
--- ------- ------- ------- ------- ------- ------- -------

Zmniejszenie zasięgu przesyłu o 10% spowoduje zmniejszenie zasięgu nadawania z dużego zamku do 18 km i małego zamku do 12,6 km. Skutkuje to usunięciem z grafu z rys. 1.7a krawędzi (A, e), (e, C) oraz (g, A). Graf z usuniętymi krawędziami jest pokazany na rys. 1.7b. W tym grafie wierzchołek e nie może przesyłać żadnej informacji, wierzchołek f może się komunikować jedynie z C, e, g, a wierzchołek g z C, e, f. Zatem system ostrzeżeń nie będzie działał prawidłowo.

Awaria węzła jest równoważna usunięciu węzła oraz incydentnych z nim krawędzi. Zakładając np. awarię węzła g, otrzymamy graf pokazany na rys. 1.7c. W tym grafie komunikacja wzajemna pomiędzy pozostałymi wierzchołkami nie jest możliwa, gdyż nie można przesłać informacji z węzłów f, C, e do żadnego z pozostałych.

Rys. 1.7. a) Graf sieci komunikacji zamków (zasięgi 14 km i 20 km); b) graf sieci komunikacji zamków (zasięgi 12,6 km i 18 km); c) graf sieci komunikacji zamków po awarii węzła g

Problem 1.4. Graf płaski

Rozpatrzmy iteracyjną procedurę podziału kwadratu o ustalonym boku. Kwadrat dzielimy na dwie równe części, np. linią poziomą. W następnym kroku górny prostokąt jest dzielony pionową linią na dwie równe części. Procedura podziału jednego z dwóch ostatnio utworzonych prostokątów (górnego lub prawego) jest powtarzana iteracyjnie. Kolejne cztery kroki procedury podziału ilustruje rys. 1.8a. Proces podziału może być modelowany za pomocą grafu. Wierzchołkami grafu są prostokąty. Dwa wierzchołki są połączone krawędzią wtedy, gdy odpowiadające im prostokąty mają wspólny bok. Grafy kolejnych kroków podziału prostokąta są pokazane na rys. 1.8b.

Rys. 1.8. a) Podział kwadratu; b) model grafowy

Łatwo jest zauważyć, że:

- – graf G_(i) ma i wierzchołków;
- – każdy z grafów G_(i) jest płaski, tzn. jest narysowany na płaszczyźnie w taki sposób, że jedynymi wspólnymi wierzchołkami różnych krawędzi mogą być tylko ich końce.

Graf pokazany na rys. 1.8b jest tzw. grafem maksymalnie płaskim (p. rozdz. 6).

Problem 1.5. Sieć radiowa

Pakietowa sieć radiowa (ang. Multihop Packet Radio Network) składa się z pewnej liczby komunikujących się ze sobą stacji radiowych. Każda ze stacji może być stacją nadawczą, odbiorczą bądź pośredniczącą. Ze względu na ograniczoną moc stacji, zanim pakiet dotrze od węzła początkowego do końcowego, przebywa drogę przez węzły pośrednie. Węzły nadające mogą wprowadzać zakłócenia pracy sieci. Wyróżniamy dwa typy konfliktów:

- – stacja w danej chwili może wykonywać tylko jedną czynność, tzn. nie może jednocześnie nadawać lub odbierać więcej niż jednej przeznaczonej dla niej transmisji (jest to tzw. konflikt główny). Sytuacja konfliktowa jest zilustrowana na rys. 1.9a, ponieważ stacja v₂ jednocześnie odbiera transmisję od v₁ i nadaje do v₃. Konflikt główny występowałby również wtedy, gdyby węzły v₁ i v₃ jednocześnie nadawały do v₂.
- – jeżeli stacja odbiera od pewnego nadajnika, to żaden inny nadajnik, w którego zasięgu znajduje się ta stacja, nie może w tym czasie nadawać (jest to tzw. konflikt drugorzędny). Na rysunku 1.9b jest przedstawiony konflikt drugorzędny: v₁ nadaje do v₂, a v₃ do v₄, ale v₂ jest w zasięgu transmisji stacji v₃. Gdyby ta transmisja była przeznaczona do stacji v₂, to występowałby konflikt główny. Tak więc konflikty główne i drugorzędne różnią się adresatem transmisji.

Rys. 1.9. Przykłady konfliktów w pakietowych sieciach radiowych: a) konflikt główny; b) konflikt drugorzędny

W celu uniknięcia konfliktów stosuje się metody kontroli dostępu do pasma radiowego. TDMA (ang. Time Division Multiple Access) jest systemem z wielodostępem czasowym. Czas jest dzielony na odcinki (szczeliny czasu), powtarzane cyklicznie w tzw. cyklu TDMA. Każda ze stacji ma przydzieloną szczelinę czasową, w trakcie której może nadawać. Przydział szczelin ma zapewnić, że nie pojawią się konflikty główne i drugorzędne. Liczba szczelin cyklu TDMA powinna być zminimalizowana, gdyż zapewnia to większą przepustowość sieci.

Model sieci to graf, w którym wierzchołki odpowiadają stacjom, a wierzchołki v, u są połączone łukiem (v, u) wtedy, gdy u jest w zasięgu stacji v. Należy zaprojektować najkrótszy z możliwych, wolny od konfliktów, cyklicznie powtarzany harmonogram nadawania stacji. Jako przykład rozpatrzmy sieć o strukturze pierścieniowej, złożoną z sześciu stacji (rys 1.10a), o symetrycznych zasięgach stacji, tzn. jeżeli stacja v leży w zasięgu stacji u, to również stacja u leży w zasięgu stacji v. Model takiej sieci jest więc grafem niezorientowanym.

Rozwiązanie

W celu uniknięcia konfliktów głównych i drugorzędnych przekształcimy graf G reprezentujący sieć w następujący sposób: wierzchołki G odległe o 2 (tj. przedzielone jednym wierzchołkiem) połączymy dodatkowymi krawędziami przedstawionymi przerywaną linią na rys. 1.10b. Otrzymany graf jest tzw. kwadratem G² grafu oryginalnego (p. rozdz. 10). Zagadnienie minimalizacji liczby szczelin czasowych można sprowadzić do zadania kolorowania wierzchołków grafu, tj. przydziału minimalnej liczby kolorów wierzchołkom grafu tak, aby każde dwa wierzchołki połączone krawędzią miały różne kolory. Zauważmy, że wierzchołki każdej z par {v₁, v₄}, {v₂, v₅}, oraz {v₃, v₆} mogą być pokolorowane tym samym kolorem. Problem wymaga więc 3 szczelin czasowych z przydziałem stacji do szczelin pokazanym na rys. 1.10c.

Rys. 1.10. a) Graf sieci radiowej; b) graf konfliktów radiowych; c) przydział szczelin czasowych

Przykład sieci jest na tyle prosty, że może być rozwiązany metodą przeglądu grafu. Bardziej zaawansowane rozważania dotyczące kolorowania grafów można znaleźć w rozdziale 16.

Problem 1.6. Zagadka o wilku, kozie i kapuście

Ten przykład jest rozszerzoną wersją znanej zagadki o wilku, kozie i kapuście.

Pewien kupiec szedł na targ sprzedać kozę i kapustę. Dla ochrony zabrał ze sobą oswojonego wilka. W pewnym momencie cała czwórka (kupiec, wilk, koza i kapusta) dotarła nad rzekę. Przy brzegu stała łódka. Była ona tak mała, że naraz mógł się tam zmieścić tylko kupiec i jedno zwierzę albo kapusta. Kupiec wiedział, że pozostawiony bez opieki wilk najpewniej pożre kozę, która z kolei chętnie zjadłaby całą kapustę.

Dodatkowo każda przeprawa przez rzekę wymaga uiszczenia opłaty. Opłaty wynoszą: c_(w) = 8 (wilk), c_(k) = 5 (koza), c_(p) = 1 (kapusta), c_(u) = 1 (kupiec). Przy każdej przeprawie w łódce musi być kupiec. Jak powinien postąpić kupiec, aby bezpiecznie przewieźć wilka, kozę i kapustę na drugi brzeg, minimalizując przy tym koszt przeprawy?

Rozwiązanie

Mamy cztery obiekty: wilk, koza, kapusta i kupiec. Każdy z obiektów może przebywać w danej chwili na lewym brzegu rzeki – L lub prawym – P. Przyjmujemy, że naszym celem jest przeprawa z lewego brzegu rzeki na prawy. Zakładając porządek elementów: (wilk, koza, kapusta, kupiec), można podać 16 słów binarnych, np. LPLL – wilk, kapusta i kupiec są na lewym brzegu rzeki, a koza na prawym. Z warunków zadania wynika, że niektóre spośród tych wektorów są kombinacjami zabronionymi, np. zabroniona jest kombinacja LLLP, gdyż oznacza to, że wilk, koza i kapusta są na tym samym (lewym) brzegu rzeki – koza może zjeść kapustę, a wilk kozę. Podobnie niedopuszczalna jest kombinacja PPLL, gdyż wilk i koza pozostają na tym samym brzegu. Lista kombinacji zabronionych obejmuje sześć przypadków: LLLP, PLLP, PPLL, LPPL, LLPP, PPPL.

Skonstruujmy etykietowany graf niezorientowany będący modelem problemu. Wierzchołki odpowiadają dziesięciu dozwolonym kombinacjom, czyli niezabronionym położeniom wszystkich obiektów w danej chwili względem rzeki. Są to: LLLL, PLLL, PPLP, LPPP, LPLL, LPLP, LLPL, PLPL, PLPP, PPPP. Krawędź w grafie występuje, kiedy zgodnie z warunkami zadania dopuszczalne jest przejście od jednej kombinacji do drugiej. Tabela 1.3 pokazuje, zaznaczone symbolem „1”, przejście między takimi kombinacjami. Z warunków zadania wynika, że element tablicy jest równy „1” wtedy, gdy następuje zmiana na ostatniej pozycji wektora (kupiec zawsze musi się znajdować w łódce), a na pierwszych trzech pozycjach wektora może nastąpić zmiana na nie więcej niż jednej pozycji (ograniczenie pojemności łódki do kupca i jednego z pozostałych obiektów), np. dozwolone jest przejście od kombinacji PPLP do PLLL (i vice versa), gdyż oznacza, że na drugi brzeg rzeki przeprawia się kupiec i koza. Tabela 1.3 jest przykładem tzw. macierzy sąsiedztwa grafu (p. rozdz. 9).

Graf odpowiadający tabeli 1.3 jest przedstawiony na rys. 1.11. Jest to graf ważony, gdyż z każdą krawędzią związana jest waga równa kosztowi przejścia z jednego wierzchołka do drugiego – kosztowi przeprawy przez rzekę.

Tabela 1.3. Dopuszczalne zmiany stanów do problemu 1.6

------ ------ ------ ------ ------ ------ ------ ------ ------ ------ ------
LLLL PLLL PPLP LPPP LPLL LPLP LLPL PLPL PLPP PPPP
LLLL 0 0 0 0 0 1 0 0 0 0
PLLL 0 0 1 0 0 0 0 0 1 0
PPLP 0 1 0 0 1 0 0 0 0 0
LPPP 0 0 0 0 1 0 1 0 0 0
LPLL 0 0 1 1 0 1 0 0 0 0
LPLP 1 0 0 0 1 0 0 0 0 0
LLPL 0 0 0 1 0 0 0 0 1 0
PLPL 0 0 0 0 0 0 0 0 1 1
PLPP 0 1 0 0 0 0 1 1 0 0
PPPP 0 0 0 0 0 0 0 1 0 0
------ ------ ------ ------ ------ ------ ------ ------ ------ ------ ------

Rys. 1.11. Graf do zagadki o wilku, kozie i kapuście

Naszym celem jest przejście od stanu LLLL do stanu PPPP, minimalizując koszty przeprawy (p. rozdz. 5 – poszukiwanie najtańszej ścieżki). Jak widać na rys. 1.11, są dwa rozwiązania zagadki o identycznym koszcie: 15 + 10 + 11 + 15 + 18 + 10 + 15 = 94.

Dla górnej ścieżki harmonogram przewozów jest następujący:

Na prawy brzeg przepływają kupiec i koza. Na lewym pozostają wilk i kapusta. Koszt – 15.

Kupiec przeprawia się na lewy brzeg. Koszt – 10.

Kupiec przewozi kapustę na prawy brzeg. Na prawym brzegu są koza, kapusta i kupiec. Koszt – 11.

Kupiec wraca na lewy brzeg zabierając kozę. Koszt – 15.

Kupiec przewozi na prawy brzeg wilka. Koszt – 18. Na prawym brzegu są: wilk, kapusta, kupiec.

Kupiec samotnie wraca na lewy brzeg. Koszt – 10. Na lewym brzegu są: koza i kupiec, a na prawym wilk i kapusta.

Kupiec przewozi kozę na prawy brzeg. Koszt – 15. Na prawym brzegu znajdują się wszyscy pasażerowie, co kończy przeprawę przez rzekę.

Harmonogram przewozów jest dość skomplikowany. Rozwiązanie tej zagadki dobrze ilustruje, jak teoria grafów pomaga budować modele skomplikowanych problemów kombinatorycznych i dostarcza narzędzi do ich rozwiązywania.

Problem 1.7. Rozkład sesji egzaminacyjnej

Należy przygotować rozkład sesji egzaminacyjnej dla ośmiu przedmiotów (oznaczonych numerami {1, 2, …, 8}). Egzamin z dwóch przedmiotów nie może się odbywać w tym samym terminie, jeżeli chociaż jeden student uczęszcza na obydwa przedmioty. W tabeli 1.4 pokazano konflikty egzaminacyjne, tzn. pary egzaminów, które nie mogą odbywać się w tym samym terminie.

1. a) Przedstawić reprezentację problemu w postaci modelu grafowego.
2. b) Jaka jest minimalna liczba terminów potrzebnych do przeprowadzenia wszystkich egzaminów?

Tabela 1.4. Sesja egzaminacyjna

--- --- --- --- --- --- --- --- ---
1 2 3 4 5 6 7 8
1 X X X X
2 X X X X
3 X X X X
4 X X X X X
5 X X X
6 X X X
7 X X
8 X X X
--- --- --- --- --- --- --- --- ---

Rozwiązanie

W modelu grafowym egzaminy są reprezentowane przez wierzchołki. Krawędź łączy dwa wierzchołki odpowiadające egzaminom, które nie mogą się odbywać w tym samym terminie. Graf ten jest pokazany na rys. 1.12.

Rozwiązanie zadania polega na podziale zbioru wierzchołków grafu na możliwie najmniejszą liczbę podzbiorów, takich że elementami podzbioru są wierzchołki niepołączone w grafie krawędzią. Rozwiązanie tego problemu można sprowadzić do tzw. zbiorów niezależnych (p. rozdz. 15) lub kolorowania wierzchołków grafu (p. rozdz. 16). Przedstawiony problem jest mały i rozwiązanie otrzymamy metodą intuicyjną. Do przeprowadzenia wszystkich egzaminów potrzebne są trzy terminy. W każdym z terminów mogą się jednocześnie odbywać następujące egzaminy: {1, 6, 8}, {4, 5, 7}, {2, 3}.

Rys. 1.12. Graf sesji egzaminacyjnej

Problem 1.8. Serwis gwarancyjny

Serwis gwarancyjny ma cztery pojazdy specjalistyczne {1, 2, 3, 4} oraz cztery ekipy specjalistów {a, b, c, d}. Serwis otrzymał do wykonania siedem napraw w różnych miejscowościach. Każda naprawa wymaga odpowiedniej ekipy i odpowiedniego pojazdu, co przedstawia graf G na rys. 1.13a. Zakładamy, że jedna ekipa, używając jednego pojazdu, może jednego dnia wykonać dokładnie jedną naprawę. Opracuj taki plan napraw w poszczególnych dniach, aby wszystkie naprawy łącznie trwały jak najmniejszą liczbę dni.

Rys. 1.13. Przydział zadań dla serwisu

Rozwiązanie

Jedną z metod rozwiązania jest przydzielenie minimalnej liczby kolorów krawędziom grafu, tak aby krawędzie o wspólnym wierzchołku miały różne kolory. Przedstawiono to na rys. 1.13b – „kolory” krawędzi są wyróżnione liczbami w nawiasach okrągłych. Naprawy odpowiadające krawędziom o różnych kolorach mogą być wykonane tego samego dnia, a krawędzie o identycznych kolorach odpowiadają poszczególnym dniom naprawy. Przeprowadzenie napraw może być wykonane w ciągu 3 dni. Więcej wiadomości na temat kolorowania krawędzi grafu można znaleźć w rozdziale 16.

Problem 1.9. Obsada stanowisk

Firma „Przyszłość” ogłosiła nabór pracowników na cztery stanowiska (nazwijmy je a, b, c, d) wymagające określonych umiejętności. Zgłosiło się pięciu kandydatów (oznaczmy ich jako 1, 2, 3, 4, 5). W tabeli 1.5 są pokazane umiejętności kandydatów kwalifikujące ich do objęcia poszczególnych stanowisk. Zaproponować obsadę stanowisk.

Tabela 1.5. Ilustracja umiejętności kandydatów

--- --- --- --- --- ---
1 2 3 4 5
a X X – – –
b X – X – –
c – X X X –
d – – – X X
--- --- --- --- --- ---

Rozwiązanie

Zadanie można przedstawić za pomocą grafu, w którym zbiór wierzchołków jest podzielony na dwa rozłączne podzbiory V₁ = {a, b, c, d} oraz V₂ = {1, 2, 3, 4, 5}. Krawędzie łączą kandydata ze stanowiskiem, do którego ma kwalifikacje (rys. 1.14). Jest to tzw. graf dwudzielny (p. rozdz. 2). Rozwiązanie problemu, wyrażone w języku grafów, wymaga znalezienia czterech wierzchołkowo rozłącznych krawędzi. Przykładowe rozwiązanie wskazują pogrubione krawędzie grafu. Zadanie jest ilustracją tzw. problemu skojarzenia (p. rozdz. 16): w naszym przykładzie skojarzone są następujące pary wierzchołków: a–2, b–1, c–4, d–5 (pogrubione krawędzie na rysunku).

Rys. 1.14. Przydział kandydatów do stanowisk

Problem 1.10. Kody binarne wykrywające i korygujące błędy

Kostka Q_(l) jest grafem niezorientowanym, której wierzchołki odpowiadają ciągom binarnym o długości l, a krawędzie łączą wierzchołki odpowiadające ciągom różniącym się na dokładnie jednej pozycji. Przykłady kostek dla l = 1, 2, 3 są pokazane na rys. 1.15.

Rys. 1.15. Kostki Q_(l) dla l = 1, 2, 3

Kostka ma zastosowanie np. w kodowaniu binarnym z wykrywaniem (ewentualnie korekcją) błędów. Jeżeli np. dla l = 3, z możliwych ośmiu słów binarnych wybierzemy cztery słowa kodowe różniące się na dwóch pozycjach, to otrzymamy kod z możliwością wykrywania błędu pojedynczego bitu. Przykładem takiego wyboru są słowa kodowe 000, 011, 101, 110. Jeżeli wskutek błędu odbierzemy np. słowo kodowe 001, to będziemy pewni, że nie jest to słowo z naszego kodu. Zauważmy, że w rozpatrywanym przykładzie jako słowa kodowe wybraliśmy z grafu te wierzchołki, które nie są połączone krawędzią (jest to tzw. niezależny zbiór wierzchołków – p. rozdz. 16). Omawiany przykład można rozszerzyć na słowa binarne o większej liczbie bitów różniące się na więcej niż jednej pozycji i wtedy nasze możliwości wykrywania i korygowania błędów się zwiększą. Ceną jest względna redukcja liczby ważnych słów kodowych.

Problem 1.11. Preferencje rynkowe konsumentów – turnieje

W badaniach preferencji rynkowych konsumentów stosuje się metodę porównywania parami. Przypuśćmy, że chcemy uszeregować szampony do włosów na podstawie badania rynku. Wybranej grupie osób każdorazowo dajemy do porównania dwa szampony – wygrywającym jest ten szampon, który uzyska więcej głosów. Procedurę powtarzamy aż do wyczerpania wszystkich możliwych par szamponów. Taką technikę nazywamy turniejem. Narysować graf preferencji konsumentów.

Rozwiązanie

Graf modelujący badanie rynkowe jest grafem zorientowanym o liczbie wierzchołków równej liczbie badanych szamponów i takiej liczbie krawędzi, jak liczba par, które można utworzyć z elementów zbioru o liczności n, tj. . Dla każdej pary wierzchołków krawędź jest skierowana od wierzchołka oznaczającego szampon, który spotkał się z większym uznaniem respondentów do wierzchołka oznaczającego szampon wybrany przez mniejszą liczbę badanych. Przykładowy graf preferencji konsumentów dla n = 6 jest pokazany na rys. 1.16.

Rys. 1.16. Graf porównywania parami

Problem 1.12. Łańcuch pokarmowy

W ekosystemach rozpatruje się tzw. łańcuchy pokarmowe. Reprezentacją graficzną takiego łańcucha jest graf zorientowany, w którym wierzchołkami są gatunki występujące w danym ekosystemie, a krawędź skierowana od wierzchołka u do v oznacza, że gatunek v jest pożywieniem dla gatunku u. Przypuśćmy, że w pewnym ekosystemie przeprowadzamy obserwację piętnastu gatunków : niedźwiedź (1), ptak (2), sarna (3), lis (4), wąż (5), owad (6), trawa (7), królik (8), szop (9), szczur (10), salamandra (11), skunks (12), ropucha (13), dziki kot (14), wilk (15). Graf łańcucha pokarmowego dla tego ekosystemu jest pokazany na rys. 1.17. Czytelnik z łatwością odczyta zależności pokarmowe gatunków.

Rys. 1.17. Graf łańcucha pokarmowego

Dla danego łańcucha pokarmowego rozpatruje się również graf konkurencji. Jest to graf niezorientowany, którego wierzchołkami są gatunki. Krawędź między wierzchołkami u, v oznacza, że istnieje gatunek w będący pożywieniem zarówno dla u, jak i v. Graf konkurencji dla rozpatrywanego łańcucha pokarmowego jest przedstawiony na rys. 1.18. Dwa wierzchołki: (7) – trawa, (10) – szczur nie są połączone z żadnym innym wierzchołkiem. Oznacza to, że nasz model jest niepełny i nie obejmuje wszystkich gatunków żyjących w rozpatrywanym ekosystemie.

Rys. 1.18. Graf konkurencji dla łańcucha pokarmowego z rys. 1.17

1.3. Literatura

Deo N., Teoria grafów i jej zastosowania w technice i informatyce, PWN, Warszawa 1980.

Euler L., Solutio problematis ad geometriam situs pertinentis, Comment. Academiae Sci. I. Petropolitanae, 1736, vol. 8, s. 128–140.

Foryś U., Matematyka w biologii, WNT, Warszawa 2005.

Harary F., Graph theory, Addison-Wesley Publishing Company, 1969.

Michalewicz Z., Fogel D.B., Jak to rozwiązać, czyli nowoczesna heurystyka, WNT, Warszawa 2006.

Roberts F., Discrete mathematics and its applications, Random House, New York 1988.

Walczak Z., Metody rozwiązywania konfliktów w pakietowych sieciach radiowych. Rozprawa doktorska, Politechnika Warszawska, Warszawa 2001.

Wilson R.J., Wprowadzenie do teorii grafów, WN PWN, Warszawa 2004.