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 dla którego wartość gdzie oznacza największy kolor przypisany wierzchołkowi jest jak najmniejsza. Gdy wszystkie wagi wierzchołków w grafie wynoszą 1, multikolorowanie sumacyjne nazywa się po prostu kolorowaniem sumacyjnymAmotz Bar-Noy, Magnus M. Halldórsson, Guy Kortsarz, Ravit Salman, Hadas Shachnai, Sum multicoloring of graphs, Journal of Algorithms 37(2), s. 422–450, 1999..
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 może otrzymać dowolny zbiór 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 grafu nazywa się wartość Ravit Salman: The Sum Multi-Coloring Problem, Technion – Israel Institute of Technology, 1999..
Bez wywłaszczania (ciągłe) W modelu bez wywłaszczania każdy wierzchołek ma przypisany zbiór kolejnych kolorów. Formalnie: multikolorowanie jest kolorowaniem bez wywłaszczenia, jeżeli dla każdego wierzchołka kolory mu przypisane (oznaczone przez ) spełniają warunek dla
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 grafu oznacza się przez .
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 rozłącznych zbiorów niezależnych o następujących dwóch własnościach: dla dowolnych dla dla każdego oraz przy
W kontekście szeregowania zadań oznacza to ukończenie wszystkich zadań związanych ze zbiorem wierzchołków zanim można rozpocząć którekolwiek zadanie ze zbioru wierzchołków dla dowolnego
Minimalną sumę multikolorowania grupowego grafu oznacza się przez .
Zależności Dla każdego grafu zachodzi: gdzie jest sumą wag wierzchołków grafu
Spowodowane jest to następującymi faktami: jest dolnym ograniczeniem dla w dowolnym grafie; równość między nimi następuje, gdy graf jest zbiorem niezależnym. Ponadto jest przypadkiem szczególnym a jest przypadkiem szczególnym .
Zobacz też kolorowanie grafu multikolorowanie grafu
Przypisy
Kategoria:Teoria grafów