Kolorowanie ułamkowe

5:2-kolorowanie wykresu dwunastościennego . Kolorowanie 4:2 tego wykresu nie istnieje.

Kolorowanie ułamkowe jest tematem młodej gałęzi teorii grafów, znanej jako teoria grafów ułamkowych. Jest to uogólnienie zwykłego kolorowania grafów . W tradycyjnym kolorowaniu grafów każdemu wierzchołkowi na grafie przypisany jest jakiś kolor, a sąsiednie wierzchołki — te połączone krawędziami — muszą mieć przypisane różne kolory. Jednak w kolorowaniu ułamkowym zestaw kolorów jest przypisywany do każdego wierzchołka grafu. Wymóg dotyczący sąsiednich wierzchołków nadal obowiązuje, więc jeśli dwa wierzchołki są połączone krawędzią, nie mogą mieć wspólnych kolorów.

Kolorowanie grafów ułamkowych można postrzegać jako relaksację programowania liniowego tradycyjnego kolorowania grafów. Rzeczywiście, ułamkowe problemy z kolorowaniem są znacznie bardziej podatne na podejście do programowania liniowego niż tradycyjne problemy z kolorowaniem.

Definicje

Powyżej: kolorowanie cyklu 3:1 na 5 wierzchołkach i odpowiadające mu kolorowanie 6:2. Poniżej: Kolorowanie 5:2 tego samego wykresu.

B - krotne kolorowanie grafu G to przypisanie zbiorów o rozmiarze b do wierzchołków grafu w taki sposób, że sąsiednie wierzchołki otrzymują zbiory rozłączne. An a : b -coloring to b -fold coloring spośród dostępnych kolorów . Równoważnie można go zdefiniować jako homomorfizm do grafu Knesera $KG a, b$ . b $_$ , chromatyczna jest najmniejszą że za : b .

Ułamkowa liczba chromatyczna jest zdefiniowana jako ${\ Displaystyle \ chi _ {f} (G)}$

{\ Displaystyle \ chi _ {f} (G) = \ lim _ {b \ do \ infty} {\ frac {\chi _{b}(G)}{b}}=\inf _{b}{\frac {\chi _{b}(G)}{b}}}

${\ Displaystyle \ chi _ {a + b} (G) \ równoważnik \ chi _ {a} (G) + \ chi _ {b} (G).}$ granica istnieje jest subaddytywna $)$ co

Ułamkową liczbę chromatyczną można równoważnie zdefiniować w kategoriach probabilistycznych. ${\ Displaystyle \ chi _ {f} (G)}$ jest najmniejszym k , dla którego istnieje rozkład prawdopodobieństwa w niezależnych zbiorach G taki, że dla każdego wierzchołka v , przy danym niezależnym zbiorze S wylosowanym z dystrybucja,

{\ Displaystyle \ Pr (v \ w S) \ geq {\ Frac {1} {k}}.}

Nieruchomości

Mamy

{\ Displaystyle \ chi _ {f} (G) \ geq {\ Frac {n (G)} {\ alfa (G)}}}

z równością dla grafów wierzchołkowo-przechodnich , gdzie n ( G ) jest rzędem G , α( G ) jest liczbą niezależności .

Ponadto,

{\ Displaystyle \ omega (G) \ równoważnik \ chi _ {f} (G) \ równoważnik \ chi (G),}

gdzie ω ( sol ) to liczba kliki , a to liczba chromatyczna . χ $\ Displaystyle \ chi (G)}$

Ponadto ułamkowa liczba chromatyczna jest zbliżona do liczby chromatycznej w ramach czynnika logarytmicznego, w rzeczywistości:

{\ Displaystyle {\ Frac {\ chi (G)} {1+ \ ln \ alfa (G)}} \ równoważnik \ chi _ {f} (G) \ równoważnik {\ Frac {\ chi _ {b} (G )}{b}}\równik \chi (G).}

${\ Displaystyle \ chi (KG_ {m, n}) = m-2n + 2,}$ $sol$ przykłady dowolnie podczas gdy ${\ Displaystyle \ chi _ {f} (KG_ {m, n}) = {\ tfrac {m} {n}}.}$

Formuła programowania liniowego (LP).

Ułamkową liczbę chromatyczną wykresu ${\ Displaystyle \ chi _ {f} (G)}$ można otrzymać jako rozwiązanie programu liniowego . sol Niech ${\ Displaystyle {\ mathcal {I}} (G)}$ będzie zbiorem wszystkich niezależnych zestawów G i niech ${\ Displaystyle {\ mathcal {I}} (G, x)}$ będzie zbiorem wszystkich tych niezależnych zbiorów, które zawierają wierzchołek x . Dla każdego niezależnego zbioru I zdefiniuj nieujemną zmienną rzeczywistą x _I . Wtedy jest minimalną wartością ${\ Displaystyle \ chi _ {f} (G)}$

{\ Displaystyle \ suma _ {ja \ w {\ mathcal {I}} (G)} x_ {ja},}

z zastrzeżeniem

{\ Displaystyle \ suma _ {ja \ w {\ mathcal {I}} (G, x)} x_ {I} \ geq 1}

dla każdego wierzchołka ${\ displaystyle x}$ .

Podwójny tego programu liniowego oblicza „ułamkową liczbę kliki”, relaksację do wymiernych koncepcji liczby całkowitej liczby kliki . Oznacza to ważenie wierzchołków G w taki sposób, że całkowita waga przypisana dowolnemu niezależnemu zbiorowi wynosi co najwyżej 1 . Silne dualności programowania liniowego gwarantuje, że optymalne rozwiązania obu programów liniowych mają tę samą wartość. Należy jednak zauważyć, że każdy program liniowy może mieć rozmiar, który jest wykładniczy w liczbie wierzchołków G , a obliczenie ułamkowej liczby chromatycznej grafu jest NP-trudne . Kontrastuje to z problemem ułamkowego kolorowania krawędzi grafu, który można rozwiązać w czasie wielomianowym. Jest to prosta konsekwencja twierdzenia Edmondsa o dopasowywaniu polytope.

Aplikacje

Zastosowania kolorowania wykresów ułamkowych obejmują planowanie działań . W tym przypadku graf G jest grafem konfliktowym : krawędź w G między węzłami u i v oznacza, że u i v nie mogą być aktywne jednocześnie. Innymi słowy, zbiór węzłów, które są aktywne jednocześnie, musi być niezależnym zbiorem na grafie G .

Optymalne ułamkowe kolorowanie wykresu w G zapewnia wówczas najkrótszy możliwy harmonogram, taki, że każdy węzeł jest aktywny łącznie przez (co najmniej) 1 jednostkę czasu, aw dowolnym momencie zbiór aktywnych węzłów jest niezależnym zbiorem. Jeśli mamy rozwiązanie x powyższego programu liniowego, po prostu przechodzimy przez wszystkie niezależne zbiory I w dowolnej kolejności. Dla każdego ja pozwalamy, aby węzły w ja były aktywne przez jednostki czasu ${\ displaystyle x_ {I}} ;$ tymczasem każdy węzeł spoza I jest nieaktywny.

Mówiąc bardziej konkretnie, każdy węzeł G może reprezentować transmisję radiową w bezprzewodowej sieci komunikacyjnej; krawędzie G reprezentują zakłócenia między transmisjami radiowymi. Każda transmisja radiowa musi być aktywna łącznie przez 1 jednostkę czasu; optymalne ułamkowe kolorowanie wykresów zapewnia harmonogram o minimalnej długości (lub równoważnie harmonogram o maksymalnej przepustowości), który jest wolny od konfliktów.

Porównanie z tradycyjnym kolorowaniem wykresów

Gdyby dodatkowo wymagano, aby każdy węzeł był aktywny nieprzerwanie przez 1 jednostkę czasu (bez wyłączania i włączania go od czasu do czasu), wówczas tradycyjne kolorowanie wierzchołków grafu zapewniłoby optymalny harmonogram: najpierw węzły koloru 1 są aktywne przez 1 czas jednostki czasu, to węzły koloru 2 są aktywne przez 1 jednostkę czasu i tak dalej. Ponownie, w dowolnym momencie zbiór aktywnych węzłów jest zbiorem niezależnym.

Ogólnie rzecz biorąc, ułamkowe kolorowanie grafów zapewnia krótszy harmonogram niż nieułamkowe kolorowanie grafów; istnieje luka integralności . Możliwe jest znalezienie krótszego harmonogramu kosztem wielokrotnego włączania i wyłączania urządzeń (takich jak nadajniki radiowe).

Notatki

^ Scheinerman, Edward R.; Ullman, Daniel H. (2013). Teoria grafów ułamkowych, racjonalne podejście do teorii grafów . Publikacja Dover. P. 42. ISBN 978-0486485935 . , Propozycja 3.1.1.
^ László Lovász : „ O stosunku optymalnych pokrycia całkowego i ułamkowego ”, Discrete Math. 13:4 (1975), s. 383-390.
^ Carsten Lund i Mihalis Yannakakis : „ O twardości przybliżania problemów minimalizacji ”, J. ACM 41: 5 (1994), s. 960-981.
^ Hajek, B.; Sasaki, G. (1988). „Planowanie linków w czasie wielomianowym”. Transakcje IEEE dotyczące teorii informacji . 34 (5): 910–917. doi : 10.1109/18.21215 .
^ Schrijver, Aleksander (2003). Optymalizacja kombinatoryczna: wielościany i wydajność . Berlinie ; Heidelberg ; Nowy Jork, NY: Springer-Verlag. s. 474 . ISBN 978-3540443896 .

Scheinerman, Edward R .; Ullman, Daniel H. (1997), Ułamkowa teoria grafów , Nowy Jork: Wiley-Interscience, ISBN 978-0-471-17864-4 .
Godsil, Chris ; Royle, Gordon (2001), Algebraic Graph Theory , Nowy Jork: Springer-Verlag, ISBN 978-0-387-95241-3 .

Zobacz też

Dopasowanie ułamkowe

[1] Scheinerman, Edward R.; Ullman, Daniel H. (2013). Teoria grafów ułamkowych, racjonalne podejście do teorii grafów . Publikacja Dover. P. 42. ISBN 978-0486485935 . , Propozycja 3.1.1.

[2] László Lovász : „ O stosunku optymalnych pokrycia całkowego i ułamkowego ”, Discrete Math. 13:4 (1975), s. 383-390.

[3] Carsten Lund i Mihalis Yannakakis : „ O twardości przybliżania problemów minimalizacji ”, J. ACM 41: 5 (1994), s. 960-981.

[4] Hajek, B.; Sasaki, G. (1988). „Planowanie linków w czasie wielomianowym”. Transakcje IEEE dotyczące teorii informacji . 34 (5): 910–917. doi : 10.1109/18.21215 .

[schrijver-5] Schrijver, Aleksander (2003). Optymalizacja kombinatoryczna: wielościany i wydajność . Berlinie ; Heidelberg ; Nowy Jork, NY: Springer-Verlag. s. 474 . ISBN 978-3540443896 .