DSC00278 (9)

Zagadnienie kolorowania wierzchołków grafii

Problem decyzyjny:

W jaki sposób należy przyporządkować kolory poszczególnym państwom na mapie politycznej, aby w wyniku zużyć ną]mniejszą liczbę potrzebnych kolorów przy całkowitym pokolorowaniu mapy.

ModsUiwtowr.

Mapę polityczną traktuje się jako graf zwykły, w którym wierzchołki reprezentują państwa, a krawędzie łączą wierzchołki odpowiadające państwom mąjącym wspólną granicę.

Problem sprowadza się do takiego pokolorowania wszystkich wierzchołków graf aby zużyć jak najmniejszą liczbę barw i aby żadne dwa przyległe wierzchołki nie miały tego samego koloru.

Optymalne kolorowanie wierzchołków grafu - maksymalne podgraty puste, pokrycie minimalne, dobór kolorów

Suboptymalne metody kolorowania wierzchołków grafii (dające rozwiązanie niewiele gorsze od optymalnego):

•    metoda redakąji grafa (Algorytm flj)

W metodzie redukcji grafu dla danego- grafu, twarzy sit ciąg podgrąfów przez usuwanie wierzchołka o najmniejszym stopniu w podgrąfle zaczynają: od danego grafu a kończą: na podgrąfie zawierającym Jeden wierzchołek. Kolorowanie rozpoczynamy od końca • ciągu usuwanych wierzchołków. Nadajemy kolory starając się wykorzystywać w kolejności kolory już stosowane w poprzednich krokach.

•    metoda macierzy podobieństw.

Przykład;

Problem maparvnnwania materiałów chemicznych:

Chcąc zaprojektować magazyn materiałów chemicznych należy uwzględnić, że niektóro z tych materiałów reagują ze sobą na tyle silnie, że nie mogą być przechowywane razem w jednym pomieszczeniu. Koszt budowy i eksploatacji magazynu rośnie wraz z liczbą pomieszczeń. Dla "danego asortymentu materiałów chemicznych zaprojektować magazyn b minimalnej (najmniejszej) lecz wystarczającej liczbie pomieszczeń.

Motel aferowy;

Wierzchołki grafu reprezentują poszczególne materiały chemiczno (rodzaje materiałów). Krawędzie łączą wierzchołki odpowiodąjące materiałom, które nie mogą być przechowywane w jednym pomieszczeniu.

Liczba różnych barw uzyskana w wyniku rozwiązania postawionego problemu będzie liczbą wymaganych pomieszczeń magazynowych, a zbiory wierzchołków pokolorowanych identycznym kolorem odpowiadać będą zbiorom materiałów, które można przechowywać razem w tym samym pomieszczeniu.