Znajdowanie liczby chromatycznej grafu
Sformułowanie problemu.
Dane: graf Szukane: liczba chromatyczna grafuPrzykładowe zastosowanie Przy pomocy algorytmów znajdujących optymalne pokolorowanie wierzchołków grafu można rozwiązać następujący problem dotyczący składowania substancji chemicznych: Zakłady chemiczne wykorzystują przy produkcji surowców chemicznych. Wiadomo, że niektóre substancje nie mogą być przechowywane razem, gdyż zetknięcie ich ze sobą spowodowałoby 'zniszczenie magazynu', ewentualnie katastrofę ekologiczną. Jaka jest minimalna liczba magazynów potrzebna do przechowywania wszystkich surowców chemicznych używanych w tej fabryce ?
Jak to zrobić używając grafu ?
Tworzymy graf, którego wierzchołków odpowiada poszczególnym surowcom chemicznym. Dwa wierzchołki łączymy krawędzią jeśli nie mogą być przechowywane razem. Minimalna liczba magazynów potrzebnych do składowania tych surowców jest równa liczbie chromatycznej tego grafu.Dlaczego tak jest ?
Rozważmy dowolne pokolorowanie wierzchołków tego grafu, w którym każde dwa wierzchołki połączone krawędzią sa pokolorowane innym kolorem. Surowce odpowiadające wierzchołkom pokolorowanym tym samym kolorem mogą być składowane w jednym magazynie !
[ Początek strony ] [ MiNIWykłady ]
Wszystkie prawa zastrzeżone © 2000 Wydział Matematyki i Nauk Informacyjnych Politechniki Warszawskiej