KOLOROWANIE JAKO NARZĘDZIE UNIKANIA KONFILKTÓW

dr Konstanty Junosza - Szaniawski

Celem wykładu jest przedstawienie zastosowania teorii grafów do modelowania praktycznych problemów, W szczególności wykład opisuje jak wykorzystać kolorowanie grafu do unikania sytuacji konfliktowych. Pierwsza część wykładu dotyczy jednego z najsławniejszych problemów matematyki - Problemu czterech kolorów - czyli na odpowiedzi na pytanie czy każdą mapę polityczną można pokolorować przy użyciu co najwyżej czterech kolorów. Na przykładzie tego problemu przedstawione jest pojęcie grafu i kolorowania jego wierzchołków, pojęcie grafów planarnych i ich własności, W drugiej części przedstawiony został problem małżeński Halla - czyli problem skojarzenia małżeństw tak, aby każda panna wyszła za kawalera, którego lubi. Na przykładzie tego problemu przedstawione jest zagadnienie skojarzenia w grafie oraz kolorowania krawędzi grafu wraz z zastosowaniem do rozwiązywania sudoku.

Zastosowania

Przy pomocy teorii grafów można modelować bardzo wiele zjawisk, ponieważ grafy w naturalny sposób opisują relacje między elementami zbioru.

Jeśli krawędzią połączymy elementy, które są ze sobą w konflikcie to kolo­rowanie grafu odpowiada podziałowi danego zbioru na podzbiory bez konfliktów, Przykładem takiego konfliktu mogą być niepożądane reakcje chemiczne. Jak wiadomo niektóre substancje chemiczne nie powinny być magazynowane razem, ponieważ mogą ze sobą reagować w nieodpowiedni sposób. Zbudujmy graf, w którym wierzchołki będą odpowiadać poszczególnym substancjom chemicznym, a krawędzie niech połączą te substancje, które nie mogą być przechowywane razem. Kolorowanie takiego grafu to nic innego jak przypisane substancjom numerów (kolorów) w taki sposób, aby żadne dwie, które nie mogą być razem, nie otrzymały tego samego koloru. To oznacza, że sub­stancje, którym przypisano ten sam kolor, mogą być składowane w jednym magazynie

Oczywiście staramy się zminimalizować liczbę magazynów. Najmniejszą liczbę magazynów potrzebną do przechowywania rozważanych substancji określa liczba chromatyczna skonstruowanego grafu. Innym zbiorem, przy którym można zastosować tę metodę, są zakłócające się stacje radiowe. Radiostacje, które są w swoim zasięgu nie mogą nadawać jednocześnie, bo wtedy nie obiorą wiadomości od siebie nawzajem. Również radiostacje, które nie są w swoim bezpośrednim zasięgu, ale mają wspólnego sąsiada, tzn. radiostację we wspólnym zasięgu, nie mogą nadawać jednocześnie ponieważ będą się nawzajem zagłuszać i ta trzecia stacja nie odbierze właściwego sygnału od żadnej z nadających stacji. Stacje radiowe możemy reprezentować jako punkty na płaszczyźnie. Niech punkty reprezentujące radiostacje na płaszczyźnie będą wierzchołkami grafu. Dwa wierzchołki będą połączone krawędzią, jeśli odpowiadające im radiostacje są we nawzajem w swoich zasięgach lub istnieje trzecia radiostacja będąca w ich wspólnym zasięgu. Liczba chromatyczna takiego grafu oznacza najmniejszą liczbę potrzebnych częstotliwości, aby transmisja następowała bez wzajemnych zakłóceń.

Ustawienie elementów zadanego zbioru w pary odpowiada z kolei skojarzeniu w grafie. Można je wykorzystać do przydziału kawalerów pannom, ale również prac pracownikom, zadań procesorom itp. Innym zagadnieniem jest kolorowanie krawędzi grafu - pomocne gdy do wykonania zadań potrzebujemy dwóch elementów np., pracownika i narzędzie, procesor i zasób pamięci.

Streszczenie wykładu

Część I - Problem czterech kolorów.

• Wprowadzenie i rys historyczny problemu czterech kolorów.

• Przetłumaczenie problemu na język teorii grafów, wprowadzenie pojęć grafu, kolorowania wierzchołków grafu, liczby chromatycznej, grafu planarnego.

• Zastosowania kolorowania grafów.

• Formuła Eulera, czyli zależność między liczbą wierzchołków, krawędzi i ścian w grafie planarnym.

• Wyprowadzenie z Formuły Eulera ograniczenia na liczbę krawędzi oraz minimalny stopień grafu planarnego.

• Przedstawienie algorytmu zachłannego do kolorowania grafu oraz faktu, że dzięki ograniczeniu na minimalny stopień, można zagwarantować użycie maksymalnie sześciu kolorów.

• Twierdzenie o pięciu kolorach wraz z idei dowodu.

Część II - Problem małżeński Halla.

• Przedstawienie problemu małżeńskiego.

• Algorytm przydzielający małżeństwa oparty "na przyjęciu" - przedstawienie działania na przykładzie.

• Wyjaśnienie związku warunku wystarczającego Halla z warunkiem zakończenia pracy algorytmu.

• Zastosowania skojarzeń w grafach.

• Zastosowanie twierdzenia Halla dla grafów regularnych.

• Związek kwadratów łacińskich z problemem małżeńskim.

• Problem kolorowania krawędzi grafów.

• Definicja indeksu chromatycznego i jego związek z maksymalnym stopniem.

• Zastosowania kolorowania krawędzi grafu.

• Kolorowanie grafów pełnych.

• Kolorowanie grafów regularnych.

• Kolorowanie krawędzi grafu z dodatkowym warunkiem: różnica liczb krawędzi w poszczególnych kolorach może wynosić co najwyżej jeden.

Słowniczek

Grafem nazywamy parę G = (V, E), gdzie: V - skończony zbiór, E - zbiór dwuelementowych podzbiorów V.

Kolorowaniem grafu nazywamy funkcję c: V → N taką, że dla każdej krawędzi {x, y} zachodzi c(x) ≠ c(y).

Najmniejszą liczbę kolorów potrzebną do pokolorowania grafu nazywamy liczbą chromatyczną grafu i oznaczamy χ(G).

Graf pełny to graf, którego każde dwa wierzchołki są połączone krawędzią, graf

pełny o n wierzchołkach oznaczamy przez K_n.

Ścieżką nazywamy graf

({v₁, v₂, . . . v_k}, {v₁v₂, v₂v₃, . . . , v_k−1v_k}),

a cyklem

({v₁, v₂, . . . v_k}, {v₁v₂, v₂v₃, . . . , _vk−1v_k, v_kv₁}).

Mówimy, że graf jest spójny jeśli dla każdej pary jego wierzchołków istnieje ścieżka łącząca te wierzchołki.

Stopniem wierzchołka v w grafie nazywamy liczbę krawędzi, które zawierają dany wierzchołek (oznaczenie deg v). Największy stopień w grafie G oznaczmy przez Δ(G), a najmniejszy przez δ(G). Graf nazywamy regularnym, jeśli wszystkie jego wierzchołki mają równe stopnie.

Graf planarny to taki, który można narysować tak, aby krawędzie nie przecinały się poza wierzchołkami.

Ścianą grafu planarnego nazywamy obszar ograniczony przez cykl, nie zawierający żadnej krawędzi. Obszar na zewnątrz grafu nazywamy ścianą zewnętrzną.

Grafem dwudzielnym nazywamy graf, którego zbiór wierzchołków można podzielić na dwa podzbiory takie, że każda krawędź w grafie ma dokładnie po jednym końcu w każdym z tych podzbiorów.

Skojarzeniem w grafie nazywamy zbiór rozłącznych krawędzi. Skojarzeniem doskonałym w grafie nazywamy takie skojarzenie, że każdy wierzchołek grafu jest końcem pewnej krawędzi ze skojarzenia.

Kolorowaniem krawędzi grafu G = (V, E) nazywamy funkcję c: E → N
taką, że każde dwie krawędzie o wspólnym końcu mają różne kolory, czyli

Najmniejszą liczbę kolorów potrzebną do pokolorowania krawędzi grafu nazywamy indeksem chromatycznym i oznaczamy przez χ '(G).

Podręcznik dla nauczyciela

Projekt współfinansowany z Europejskiego Funduszu Społecznego w ramach Programu Operacyjnego Kapitał Ludzki

3

Projekt współfinansowany z Europejskiego Funduszu Społecznego w ramach Programu Operacyjnego Kapitał Ludzki

---