Znajdowanie indeksu chromatycznego grafu

Sformułowanie problemu.
Dane: graf G
Szukane: indeks chromatyczny grafu G

Przykładowe zastosowanie.
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.

Jak rozwiązać problem układania planu zajęć przy pomocy grafów? 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 spó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ą sie odbyć.

Przykład
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. 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ę.

----------------
prof. Mróz IVaIVbIVa
prof. Nowak IVcIVa
prof. Pawlak IVdIVaIVc
prof. Cicho IVcIVdIVb
prof. Lis IVbIVdIVcIVd

W wierszach odpowiadających poszczególnym nauczycielom wypisane są klasy, które 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.



[ Początek strony ] [ MiNIWykłady ]

Wszystkie prawa zastrzeżone © 2000 Wydział Matematyki i Nauk Informacyjnych Politechniki Warszawskiej