Multikolorowanie grafu

Multikolorowanie grafu jest uogólnieniem pojęcia kolorowania grafu. Polega ono na przypisaniu każdemu z wierzchołków grafu ważonego tylu kolorów, ile wynosi waga danego wierzchołka. Multikolorowanie nazywa się poprawnym (dopuszczalnym, legalnym) jeżeli dwa wierzchołki połączone krawędzią nie posiadają tego samego koloru.

Multikolorowanie grafu ważonego z wagami wierzchołków równymi 1 jest tym samym, co zwykłe kolorowanie tego grafu.

Problem multikolorowania można przetransportować na problem klasycznego kolorowania grafów. Multikolorowanie grafu ważonego $G_{\omega }$ jest tym samym, co zwykłe kolorowanie grafu $G$ powstałego z $G_{\omega }$ przez zastąpienie każdego wierzchołka $v\in V(G_{\omega })$ kliką $K_{v}$ o rozmiarze $\omega (v)$ oraz utworzenie krawędzi pomiędzy każdymi dwoma wierzchołkami klik $K_{v}$ i $K_{u}$ wtedy i tylko wtedy, gdy wierzchołki $v$ i $u$ były połączone krawędzią w $G_{\omega }$.

Najmniejszą liczbę kolorów niezbędną do legalnego pokolorowania grafu ważonego $G_{\omega }$ nazywa się liczbą multichromatyczną lub ważoną liczbą chromatyczną. Oznacza się ją w różny sposób, między innymi przez $\chi _{m}(G_{\omega }),$ przy czym indeksy $m$ i $\omega$ bywają zamieniane na inne lub, jeżeli fakt, iż chodzi o liczbę multichromatyczną grafu ważonego wynika z kontekstu – pomijane.

Definicja formalna

Multikolorowaniem grafu ważonego $G_{\omega }:=(V,E,\omega )$ (zwanym także kolorowaniem ważonym lub $\omega$-kolorowaniem) nazywa się funkcję $\psi ,$ która dla pewnego zbioru kolorów $C,$ każdemu wierzchołkowi przypisuje pewien podzbiór tego zbioru $(\psi \colon V(G)\to 2^{C})$ w taki sposób, aby zachowane były następujące warunki:

1. $\forall _{v\in V(G)}|\psi (v)|=\omega (v),$ czyli do każdego wierzchołka $v$ przypisywanych jest $\omega (v)$ różnych kolorów,
2. $\forall _{{u,v}\in E(G)}\psi (u)\cap \psi (v)=\emptyset ,$ czyli dwóm sąsiednim wierzchołkom przypisywane są rozłączne zbiory kolorów.

Inne modele multikolorowania

Multikolorowanie z listy

W modelu multikolorowania z listy (multikolorowania listowego) każdy z wierzchołków posiada dodatkowo listę dopuszczalnych kolorów. Nie może zostać pokolorowany kolorem spoza listy.

Multikolorowanie sumacyjne

W modelu multikolorowania sumacyjnego minimalizuje się sumę użytych kolorów (oznaczanych liczbami naturalnymi), a nie ich liczbę.

Multikolorowanie n-krotne

W modelu n-krotnego multikolorowania wierzchołki grafu mają jednakowe wagi wynoszące $n$.

Zastosowania

Przydział częstotliwości w sieciach komórkowych

Podstawowym problemem w sieciach telefonów komórkowych jest przydzielanie kanałów radiowych (pasm częstotliwości) nadajnikom tak, aby uniknąć niepożądanych zakłóceń. Liczba wymaganych kanałów może być różna dla różnych nadajników. Przyjmuje się, że nadajniki położone są na płaszczyźnie, w wierzchołkach trójkątnej siatki (o heksagonalnych komórkach): wzór ten umożliwia pokrycie całej powierzchni płaszczyzny. Wierzchołki (nadajniki) sąsiadujące ze sobą nie mogą otrzymać tego samego kanału, by nie nastąpiły zakłócenia.

Planowanie zadań współdzielących zasoby

W systemach wieloprocesorowych część zasobów nie może być wykorzystywana jednocześnie do wielu zadań. Problemem do rozwiązania jest tu optymalne zaplanowanie zadań dzielących zasoby. Muszą przy tym być spełnione warunki: zadania współdzielące zasoby nie mogą być wykonywane jednocześnie oraz każde żądanie wykonania dowolnego z zadań musi być prędzej czy później spełnione. Zakładając, że każde z zadań zostaje wykonane w jednej jednostce czasu, problem można przełożyć na problem multikolorowania grafu, którego wierzchołki reprezentują zadania do wykonania, a krawędzie między nimi oznaczają, że prace te dzielą pewien zasób i nie mogą być wykonywane w tym samym czasie.

Zobacz też

• kolorowanie grafu
• liczba chromatyczna
• liczba multichromatyczna
• multikolorowanie sumacyjne