Slabé zbarvení - Weak coloring

Slabé 2 barvy.

v teorie grafů, a slabé zbarvení je speciální případ a označení grafu. Slabý $k$ -barvení grafu $G = (PROTI, E)$ přiřadí barvu $C (proti) \in {1, 2, ..., k}$ ke každému vrcholu $proti \in PROTI$ , takže každýizolovaný vrchol sousedí s alespoň jedním vrcholem s jinou barvou. V notaci pro každou neizolovanou $proti \in PROTI$ , existuje vrchol $u \in PROTI$ s ${u, proti} \in E$ a $C (u) \neq C (proti)$ .

Obrázek vpravo ukazuje slabé dvoubarevnost grafu. Každý temný vrchol (barva 1) sousedí s alespoň jedním světlým vrcholem (barva 2) a naopak.

Vytváří slabé 2 zbarvení.

Vlastnosti

Graf vrchol zbarvení je slabé zabarvení, ale nemusí to být nutně naopak.

Každý graf má slabé 2 zbarvení. Obrázek vpravo ilustruje jednoduchý algoritmus pro konstrukci slabého 2barvení v libovolném grafu. Část (a) ukazuje původní graf. Část (b) ukazuje a vyhledávání na šířku strom stejného grafu. Část (c) ukazuje, jak zabarvit strom: počínaje od kořene jsou vrstvy stromu střídány barvami 1 (tmavá) a 2 (světlá).

Pokud není izolovaný vrchol v grafu $G$ , pak slabé 2 zbarvení určuje a domatická přepážka: sada uzlů s $C (proti) = 1$ je dominující sada a množina uzlů s $C (proti) = 2$ je další dominující sada.

Aplikace

Historicky slabé vybarvení sloužilo jako první netriviální příklad problému s grafy, který lze vyřešit lokálním algoritmem (a distribuovaný algoritmus který běží ve stálém počtu synchronních komunikačních kol). Přesněji řečeno, pokud stupeň každého uzlu je liché a ohraničené konstantou, pak existuje algoritmus distribuovaný v konstantním čase pro slabé 2-zbarvení.^[1]

To se liší od (neslabé) vrchol zbarvení: pro zbarvení vrcholů neexistuje žádný distribuovaný algoritmus konstantního času; nejlepší možné algoritmy (pro nalezení minimálního, ale ne nutně minimálního zbarvení) vyžadují $Ó (log * | PROTI |)$ komunikační kola.^[1]^[2]^[3] Tady $log * X$ je iterovaný logaritmus z $X$ .

Reference

^ ^A ^b Naor, Moni; Stockmeyer, Larry (1995), „Co lze vypočítat lokálně?“, SIAM Journal on Computing, 24 (6): 1259–1277, CiteSeerX 10.1.1.29.669, doi:10.1137 / S0097539793254571, PAN 1361156.
^ Linial, Nathane (1992), "Lokalita v algoritmech distribuovaného grafu", SIAM Journal on Computing, 21 (1): 193–201, CiteSeerX 10.1.1.471.6378, doi:10.1137/0221015, PAN 1148825.
^ Cole, Richard; Vishkin, Uzi (1986), „Deterministické házení mincí s aplikacemi pro optimální hodnocení paralelních seznamů“, Informace a kontrola, 70 (1): 32–53, doi:10.1016 / S0019-9958 (86) 80023-7, PAN 0853994.

[naor-stockmeyer-1995-1] A ^b Naor, Moni; Stockmeyer, Larry (1995), „Co lze vypočítat lokálně?“, SIAM Journal on Computing, 24 (6): 1259–1277, CiteSeerX 10.1.1.29.669, doi:10.1137 / S0097539793254571, PAN 1361156.

[2] Linial, Nathane (1992), "Lokalita v algoritmech distribuovaného grafu", SIAM Journal on Computing, 21 (1): 193–201, CiteSeerX 10.1.1.471.6378, doi:10.1137/0221015, PAN 1148825.

[3] Cole, Richard; Vishkin, Uzi (1986), „Deterministické házení mincí s aplikacemi pro optimální hodnocení paralelních seznamů“, Informace a kontrola, 70 (1): 32–53, doi:10.1016 / S0019-9958 (86) 80023-7, PAN 0853994.

[1]

[2]

[3]