Kolorowanie listy
W teorii wykres , lista barwiących jest farbowanie wierzchołków grafu gdzie kolor każdego wierzchołka jest ograniczone do listy autoryzowanych kolorów. Po raz pierwszy został zbadany w latach 70. w niezależnych artykułach Vadima G. Vizinga i Paula Erdősa , Arthura Rubina (en) i Herberta Taylora.
Definicja
Biorąc pod uwagę krzywą G i zestaw barw dla każdego wierzchołka y (zwany jej lista ), lista barwiących jest funkcją, która wyznacza każdy wierzchołek s do koloru na liście . Podobnie jak w przypadku zwykłego kolorowania wykresów, zazwyczaj zakłada się , że kolorowanie listy jest czyste , co oznacza, że dwa sąsiadujące ze sobą wierzchołki nie mają tego samego koloru. Wykres jest k -wybieralny (lub k -koloryzowany przez list ), jeśli dopuszcza odpowiednie kolorowanie list, niezależnie od sposobu, w jaki listy k kolorów są przypisane do każdego wierzchołka. Choisissabilité (lub listę zabarwienia lub chromatycznej liście indeksów ) CH ( G ) grafu G jest najmniejsza liczba K tak, że G jest k -choisissable.
L(s){\ styl wyświetlania L (s)}L(s){\ styl wyświetlania L (s)}
Mówiąc bardziej ogólnie, funkcja przypisywania dodatniej liczby całkowitej na każdym szczycie , graf G jest -wybieralny (lub -coloriable List ), jeśli lista kolorowania jest przypisana do każdego wierzchołka listy kolorów . W szczególności, jeśli dla wszystkich wierzchołków , to selektywność odpowiada k selektywności.
fa{\ styl wyświetlania f}fa(s){\ styl wyświetlania f (s)}s{\ style wyświetlania}fa{\ styl wyświetlania f}fa{\ styl wyświetlania f}fa(s){\ styl wyświetlania f (s)}s{\ style wyświetlania}fa(s)=k{\ styl wyświetlania f (s) = k}s{\ style wyświetlania}fa{\ styl wyświetlania f}
Przykłady
Rozważamy kompletny graf dwudzielny z sześcioma wierzchołkami A , B , W , X , Y , Z których podział składa się z A i B oraz W , X , Y i Z z drugiej strony; wierzchołki A i B są połączone ze wszystkimi wierzchołkami W , X , Y i Z i nie ma innych krawędzi. Jako wykres dwudzielny, zwykły indeks chromatyczny G wynosi 2: możemy pokolorować A i B tym samym kolorem, a W , X , Y , Z tymi samymi innymi kolorami; w ten sposób dwa sąsiednie wierzchołki nie mają tego samego koloru. Z drugiej strony, G ma indeks chromatyczny listy większy niż 2, co pokazuje następująca konstrukcja: przypisujemy A i B listy {czerwony, niebieski} i {zielony, czarny}, a pozostałym czterem wierzchołkom przypisujemy wymienia {czerwony, zielony}, {czerwony, czarny}, {niebieski, zielony} i {niebieski, czarny}. Niezależnie od wyboru koloru dokonanego na liście A i na liście B , jeden z czterech pozostałych wierzchołków ma spośród dwóch możliwych wyborów tylko kolory, które zostały już użyte do pokolorowania jego sąsiadów. W związku z tym G nie jest 2-wybieralne.
sol=K2,4{\ styl wyświetlania G = K_ {2,4}}
Z drugiej strony, łatwo zauważyć, że G można wybrać za 3 punkty: wybieramy dowolne kolory dla wierzchołków A i B ; co najmniej jeden kolor pozostaje dostępny dla każdego z pozostałych wierzchołków, a kolory te można wybrać dowolnie.
Bardziej ogólnie, niech Q jest liczbą całkowitą dodatnią, niech G będzie zakończeniu dwustronnego wykres . Zakłada się, że dostępne są kolory, które są reprezentowane przez odrębne dwucyfrowe liczby o podstawie q . Dla składowej z wierzchołkami q dwudzielności nadajemy wierzchołkom q zestawy kolorów, w których wszystkie pierwsze cyfry są równe, dla q możliwych wyborów pierwszej cyfry . Dla drugiego składnika dwudzielności podajemy zestawy kolorów wierzchołków, w których wszystkie pierwsze cyfry są różne, dla każdego z możliwych wyborów q -uplet , przez które przebiegają wszystkie możliwe wartości. Rysunek u góry strony pokazuje przykład konstrukcji .
Kq,qq{\ styl wyświetlania K_ {q, q ^ {q}}}q2{\ styl wyświetlania q ^ {2}}q2{\ styl wyświetlania q ^ {2}} {ja0,ja1,ja2,...}{\ styl wyświetlania \ {i0, i1, i2, \ ldots \}}ja{\ styl wyświetlania i}qq{\ styl wyświetlania q ^ {q}}{0w,1b,2vs...}{\ styl wyświetlania \ {0a, 1b, 2c \ ldots \}}qq{\ styl wyświetlania q ^ {q}}{0w,1b,2vs...}{\ styl wyświetlania \ {0a, 1b, 2c \ ldots \}}w,b,vs...{\ styl wyświetlania a, b, c \ ldots}q=3{\ styl wyświetlania q = 3}
Przy tej konstrukcji wykres G nie ma kolorowania listowego dla tych kolorów: bez względu na zestaw kolorów wybrany dla wierzchołków q po krótszej stronie dwudzielności, wybór ten koliduje ze wszystkimi kolorami dla l 'jeden z wierzchołków po drugiej strona dwudzielnej. Na przykład, jeśli dla q = 2, wierzchołek z zestawem kolorów {00.01} jest pokolorowany na 01, a wierzchołek z zestawem kolorów {10.11} jest pokolorowany na 10, to wierzchołek z zestawem kolorów {01.10} nie może być kolorowy. Dlatego indeks chromatyczny listy G wynosi co najmniej .
q+1{\ styl wyświetlania q + 1}
Podobnie, jeśli , to kompletny dwudzielny graf nie jest k -wybieralny. Załóżmy rzeczywiście, że kolory są dostępne w całości i że po jednej ze stron dwupodziału każdy wierzchołek ma do dyspozycji k -krotkę tych kolorów, różniących się od siebie wierzchołkami. Tak więc każda strona dwudzielnej partycji musi używać co najmniej k kolorów, ponieważ każdy zestaw kolorów jest rozłączny z listy wierzchołków. Ponieważ co najmniej k kolorów jest używanych po jednej stronie i co najmniej k po drugiej, musi istnieć kolor używany po obu stronach, ale oznacza to, że dwa sąsiadujące wierzchołki mają ten sam kolor. W szczególności wykres łamigłówek trzech domów ma indeks koloru listy co najmniej trzy, a wykres ma indeks koloru listy co najmniej cztery.
nie=(2k-1k){\ displaystyle n = {\ binom {2k-1} {k}}}Knie,nie{\ styl wyświetlania K_ {n, n}}2k-1{\ styl wyświetlania 2k-1}k-1{\ styl wyświetlania k-1} K3,3{\ styl wyświetlania K_ {3,3}}K10,10{\ styl wyświetlania K_ {10.10}}
Nieruchomości
Na wykresie G , należy zwrócić uwagę na wskaźnik barwy i do maksymalnego stopnia o G . Indeks chromatyczny listy ch ma następujące właściwości:
χ(sol){\ styl wyświetlania \ chi (G)}Δ(sol){\ styl wyświetlania \ Delta (G)}(sol){\ styl wyświetlania (G)}
- rozdz . Wykres listowy k-kolorowalny musi w szczególności mieć kolorowanie listowe, gdy każdemu wierzchołkowi przypisana jest ta sama lista k kolorów, co odpowiada zwykłemu kolorowaniu k kolorami.(sol)≥χ(sol){\ styl wyświetlania (G) \ geq \ chi (G)}
- HP generalnie nie może być ograniczany w zależności od wskaźnika koloru, to znaczy, że nie ma funkcji sprawdzania ch dla dowolnego wykresu G . W szczególności, jak pokazują przykłady kompletnych grafów dwudzielnych, istnieją grafy z dowolnie dużym ch .(sol){\ styl wyświetlania (G)}fa{\ styl wyświetlania f}(sol)≤fa(χ(sol){\ styl wyświetlania (G) \ leq f (\ chi (G)}χ(sol)=2{\ styl wyświetlania \ chi (G) = 2}(sol){\ styl wyświetlania (G)}
- ch gdzie n jest liczbą wierzchołków G .(sol)≤χ(sol)lognie{\ styl wyświetlania (G) \ leq \ chi (G) \ log \, n}
- ch jeśli G jest grafem planarnym .(sol)≤5{\ styl wyświetlania (G) \ leq 5}
- ch jeśli G jest dwudzielnym grafem planarnym .(sol)≤3{\ styl wyświetlania (G) \ leq 3}
Obliczanie selektywności i ( a , b ) -selektywności
Rozpatrzono następujące problemy algorytmiczne:
-
k{\ styl wyświetlania k}-selectable : zdecyduj, czy dany graf jest k -wybieralny dla danego k , oraz
-
(w,b){\ styl wyświetlania (a, b)}- możliwość wyboru : zdecyduj, czy dany wykres jest f- wybieralny dla danej funkcji .fa:V→{w,...,b}{\ displaystyle f: V \ do \ {a, \ kropki, b \}}
Wiemy, że k -selekcyjność w grafach dwudzielnych jest -zupełna dla wszystkiego i jest taka sama dla 4-selekcyjności w grafach planarnych, 3-selekcyjności w grafach planarnych bez trójkąta i (2, 3) -selektywności w grafach dwudzielnych grafy planarne . W przypadku grafów bez P 5 , to znaczy grafów wykluczających ścieżki z 5 wierzchołkami, k- selekcyjność można traktować za pomocą stałego parametru .
Π2p{\ styl wyświetlania \ Pi _ {2} ^ {p}}k≥3{\ styl wyświetlania k \ geq 3}
Można przetestować, czy wykres jest 2-wybieralny w czasie liniowym, poprzez sukcesywne usuwanie wierzchołków stopnia zero lub jednego aż do osiągnięcia 2-jądra wykresu, po którym takie usunięcia nie są możliwe. Początkowy wykres jest 2-wybieralny wtedy i tylko wtedy, gdy jego 2-jądro jest albo cyklem parzystym, albo grafem theta, który składa się z trzech ścieżek ze wspólnymi końcami, gdzie dwie ścieżki mają długość dwa, a trzecia ścieżka parzystej długości.
Aplikacje
Kolorowanie listy pojawia się w praktycznych kwestiach dotyczących przydziału kanałów / częstotliwości
Uwagi i referencje
(fr) Ten artykuł jest częściowo lub w całości zaczerpnięty z
anglojęzycznego artykułu Wikipedii zatytułowanego
" Kolorowanie listy " ( zobacz listę autorów ) .
-
Vadim G. Vizing, „ Kolorowanie wierzchołków z podanymi kolorami (po rosyjsku) ”, Metody Diskret. Analiz. , tom. 29,1976, s. 3-10 ( zbMATH 0362.0506 )
-
Paul Erdős, Arthur Rubin i Herbert Taylor, „Choosability in graphs” , w Proc. Konf. Zachodniego Wybrzeża on Combinatorics, Graph Theory and Computing (Humboldt State Univ., Arcata, Kalifornia, 1979) , coll. "Congressus Numerantium" ( N O XXVI)1980( Recenzje matematyczne 0593902 , czytaj online ) , s . 125–157.
-
Tommy R. Jensen i Bjarne Toft , Problemy z kolorowaniem wykresów , Nowy Jork, Wiley-Interscience,2011, 2 II wyd. ( ISBN 0-471-02865-7 ) , s. 1.9 Kolorowanie listy: strony = 18–21.
-
Tłumaczenie hasła "choissable" z "choisissable" i powiązanymi rzeczownikami ratyfikowane przez choisissabilité w wiktionary
-
Sylvain Gravier , „ Hajósowe twierdzenie o kolorowaniu list ”, „ Matematyka dyskretna” , tom. 152, n kość 1-3,1996, s. 299-302 ( DOI 10.1016 / 0012-365X (95) 00350-6 , Przeglądy matematyczne 1388650 ).
-
Carsten Thomassen , „ Każdy graf planarny jest do wyboru 5 ”, Journal of Combinatorial Theory, Series B , tom. 62,1994, s. 180–181 ( DOI 10.1006 / jctb.1994.1062 ).
-
Noga Alon i Michael Tarsi , „ Kolorowanki i orientacje grafów ”, Combinatorica , tom. 12 N O 21992, s. 125-134 ( DOI 10.1007 / BF01204715 )
-
Shai Gutner , „ Złożoność wyboru grafów planarnych ” , „ Matematyka dyskretna ” , tom. 159 n o 1,1996, s. 119-130 ( DOI 10.1016 / 0012-365X (95) 00104-5 , arXiv 0802.2668 ).
-
Shai Gutner i Michael Tarsi , „ Niektóre wyniki dotyczące ( a : b ) możliwości wyboru ”, „ Matematyka dyskretna” , tom. 309 N O 8,2009, s. 2260–2270 ( DOI 10.1016 / j.disc.2008.04.061 ).
-
Pinar Heggernes i Petr Golovach " Choosability P 5 -Darmowe wykresów ," Lecture Notes on Computer Science , Springer-Verlag, vol. 5734 „Matematyczne podstawy informatyki”,2009, s. 382-391 ( czytaj online ).
-
Wei Wang i Xin Liu , „ Przydział kanałów oparty na kolorowaniu list dla sieci bezprzewodowych o otwartym widmie ”, 2005 IEEE 62. konferencja technologii pojazdów (VTC 2005-Fall) , tom. 1,2005, s. 690–694 ( DOI 10.1109 / VETECF.2005.1558001 ).
-
N. Garg , M. Papatriantafilou i P. Tsigas , „ Dystrybuowane kolorowanie list: jak dynamicznie przydzielać częstotliwości ruchomym stacjom bazowym ”, Ósme sympozjum IEEE na temat przetwarzania równoległego i rozproszonego ,1996, s. 18-25 ( DOI 10.1109 / SPDP.1996.570312 , hdl 21.11116 / 0000-0001-1AE6-F ).
-
Jean-Sébastien Sereni, Kolorowanie grafów i zastosowania: Modelowanie i symulacja , Uniwersytet Nicejski Sophia Antipolis, coll. " Praca doktorska ",2006( HAL tel-00120594 ).
Bibliografia
-
Aigner, Martin i Ziegler, Günter, Dowody z KSIĄŻKI , Berlin, Nowy Jork, Springer-Verlag,2009( ISBN 978-3-642-00855-9 ) , Rozdział 34 Pięciokolorowe wykresy płaskie.
-
Reinhard Diestel, Teoria grafów , Springer-Verlag, Heidelberg, coll. "Graduate Teksty matematyki" ( N O 173)2016, 447 s. ( ISBN 978-3-662-53621-6 i 978-3-96134-005-7 , czytaj online ).
Powiązane artykuły
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">