Multikolorowanie sumacyjne

Multikolorowanie sumacyjne – jeden z modeli wierzchołkowego multikolorowania grafu. Od klasycznego multikolorowania odróżnia się tym, że optymalizuje się w nim sumę użytych barw (oznaczanych liczbami naturalnymi), a nie ich liczbę. Poszukuje się zatem takiego multikolorowania $\psi ,$ dla którego wartość $SMC(G,\psi )=\sum _{v\in V}f_{\psi }(v),$ gdzie $f_{\psi }(v)$ oznacza największy kolor przypisany wierzchołkowi $v,$ jest jak najmniejsza. Gdy wszystkie wagi wierzchołków w grafie wynoszą 1, multikolorowanie sumacyjne nazywa się po prostu kolorowaniem sumacyjnym.

Multikolorowanie sumacyjne ma zastosowanie w szeregowaniu zadań wykonywanych przez systemy wieloprocesorowe. Zwykłe multikolorowanie jest wtedy równoważne zminimalizowaniu czasu koniecznego do ukończenia wszystkich zadań, natomiast sumacyjne pozwala uzyskać jak najmniejszy średni czas ukończenia zadania.

Modele multikolorowania sumacyjnego

Z wywłaszczaniem

O multikolorowaniu sumacyjnym z wywłaszczaniem mówi się, jeżeli każdy wierzchołek $v$ może otrzymać dowolny zbiór $\omega (v)$ kolorów bez dodatkowych warunków.

W kontekście szeregowania zadań oznacza to, że zadania mogą zostać przerwane i dokończone później.

Minimalną sumą multikolorowania z wywłaszczaniem $\psi$ grafu $G$ nazywa się wartość $pSMC(G)=\min _{\psi }SMC(G,\psi )$.

Bez wywłaszczania (ciągłe)

W modelu bez wywłaszczania każdy wierzchołek $v$ ma przypisany zbiór kolejnych $\omega (v)$ kolorów. Formalnie: multikolorowanie $\psi$ jest kolorowaniem bez wywłaszczenia, jeżeli dla każdego wierzchołka $v\in V$ kolory mu przypisane (oznaczone przez $c_{1}^{\psi }(v),\dots ,c_{\omega }^{\psi }(v)$) spełniają warunek $c_{i+1}^{\psi }(v)=c_{i}^{\psi }(v)+1$ dla $1\leqslant i<\omega (v).$

W kontekście szeregowania zadań oznacza to, że każde zadanie wykonywane jest bez przerwy aż do jego ukończenia.

Minimalną sumę multikolorowania bez wywłaszczania $\psi$ grafu $G$ oznacza się przez $npSMC(G)$.

Grupowe

W modelu grupowym wierzchołki są kolorowane partiami. Każda z nich jest zbiorem niezależnym; zaczyna się kolorować następną, dopiero gdy pokolorowane zostały wszystkie wierzchołki z partii poprzedniej.

Model multikolorowania sumacyjnego grupowego jest rozwiązany przez multikolorowanie ciągłe, jeżeli zbiór wierzchołków grafu może zostać podzielony na $k$ rozłącznych zbiorów niezależnych $V=I_{1}\cup \ldots \cup I_{k}$ o następujących dwóch własnościach:

1. $c_{1}^{\psi }(v)=c_{1}^{\psi }(v')$ dla dowolnych $v,v'\in I_{j},$ dla $1\leqslant j\leqslant k,$
2. $c_{\omega (v)}^{\psi }<c_{1}^{\psi }(v')$ dla każdego $v\in I_{j}$ oraz $v'\in I_{j+1},$ przy $1\leqslant j<k.$

W kontekście szeregowania zadań oznacza to ukończenie wszystkich zadań związanych ze zbiorem wierzchołków $I_{j},$ zanim można rozpocząć którekolwiek zadanie ze zbioru wierzchołków $I_{j+1}$ dla dowolnego $1\leqslant j<k.$

Minimalną sumę multikolorowania grupowego $\psi$ grafu $G$ oznacza się przez $coSMC(G)$.

Zależności

Dla każdego grafu $G$ zachodzi: $S(G)\leqslant pSMC(G)\leqslant npSMC(G)\leqslant coSMC(G),$ gdzie $S(G)=\sum _{v\in V(G)}\omega (v)$ jest sumą wag wierzchołków grafu $G.$

Spowodowane jest to następującymi faktami: $S(G)$ jest dolnym ograniczeniem dla $SMC$ w dowolnym grafie; równość między nimi następuje, gdy graf jest zbiorem niezależnym. Ponadto $coSMC(G)$ jest przypadkiem szczególnym $npSMC(G),$ a $npSMC(G)$ jest przypadkiem szczególnym $pSMC(G)$.

Zobacz też

• kolorowanie grafu
• multikolorowanie grafu