5032124679

17

1.1. OD PROBLEM U DO PROGRAMU

RYSUNEK 1.1.

Przykładowe

skrzyżowanie

zwłaszcza przy zawracaniu. Ulice C i E są jednokierunkowe, pozostałe są ulicami dwukierunkowymi. Na skrzyżowaniu tym można wykonać 13 różnych „zakrętów”; niektóre z nich, jak AB (czyli z ulicy A w ulicę B) i EC, mogą być wykonywane równocześnie, inne natomiast, jak AD i EB, kolidują ze sobą i mogą być wykonane tylko w różnych fazach.

Opisany problem daje się łatwo ująć („modelować”) w postaci struktury zwanej grafem. Każdy graf składa się ze zbioru wierzchołków i zbioru linii łączących wierzchołki w pary — linie te nazywane są krawędziami. W naszym grafie modelującym sterowanie ruchem na skrzyżowaniu wierzchołki reprezentować będą poszczególne zakręty, a połączenie dwóch wierzchołków krawędzią oznaczać będzie, że zakręty reprezentowane przez te wierzchołki kolidują ze sobą. Graf odpowiadający skrzyżowaniu pokazanemu na rysunku 1.1 przedstawiony jest na rysunku 1.2, natomiast w tabeli 1.1 widoczna jest jego reprezentacja macierzowa — każdy wiersz i każda kolumna reprezentuje konkretny wierzchołek; jedynka na przecięciu danego wiersza i danej kolumny wskazuje, że odpowiednie wierzchołki połączone są krawędzią.

Rozwiązanie naszego problemu bazuje na koncepcji zwanej kolorowaniem grafu. Polega ona na przyporządkowaniu każdemu wierzchołkowi konkretnego koloru w taki sposób, by wierzchołki połączone krawędzią miały różne kolory. Nietrudno się domyślić, że optymalne rozwiązanie naszego problemu sprowadza się do znalezienia takiego kolorowania grafu z rysunku 1.2, które wykorzystuje jak najmniejszą liczbę kolorów.