Vadné zbarvení - Defective coloring

v teorie grafů, matematická disciplína, zbarvení odkazuje na přiřazení barev nebo štítků k vrcholům, hranám a plochám grafu. Vadné zbarvení je varianta správného zbarvení vrcholů. Při správném zbarvení vrcholů jsou vrcholy zbarveny tak, že žádné sousední vrcholy nemají stejnou barvu. Při defektním zbarvení je naopak vrcholům povoleno mít do určité míry sousedy stejné barvy. (Viz zde pro Glosář teorie grafů )

Dějiny

Vadné zbarvení zavedli téměř současně Burr a Jacobson, Harary a Jones a Cowen, Cowen a Woodall.^[1] Průzkumy tohoto a souvisejících barviv uvádí Marietjie Frick.^[2] Cowen, Cowen a Woodall ^[1] zaměřil se na grafy vložené na povrchy a poskytl úplnou charakteristiku všech k a d tak, že každý rovinný je (k, d) -barevné. Jmenovitě neexistuje a d takže každý rovinný graf je (1, d) - nebo (2, d) -barevný; existují rovinné grafy, které nejsou (3, 1) barevné, ale každý rovinný graf je (3, 2) barevný. Spolu s barvením (4, 0) vyplývajícím z čtyřbarevná věta, tím se vyřeší vadné chromatické číslo pro rovinu. Poh ^[3] a Goddard ^[4] ukázal, že jakýkoli planární graf má speciální (3,2) -barvení, ve kterém je každá barevná třída lineárním lesem, což lze získat z obecnějšího výsledku Woodalla. U obecných ploch se ukázalo, že pro každý rod ${ displaystyle g geq 0}$, existuje a ${ displaystyle k = k (g)}$ tak, že každý graf na povrchu rodu ${ displaystyle g}$ je (4, k) -barevné.^[1] Toto bylo vylepšeno na (3, k) -barvitelné Dan arciděkan.^[5]U obecných grafů je výsledek László Lovász od 60. let, která byla mnohokrát znovuobjevena ^[6][7][8] poskytuje a O (∆E)-časový algoritmus pro vadné barevné grafy maximálního stupně ∆.

Definice a terminologie

Vadné zbarvení

A (k, d) -barvení grafu G je zbarvení jeho vrcholů pomocí k barvy tak, aby každý vrchol proti má nanejvýš d sousedé mají stejnou barvu jako vrchol proti. Zvažujeme k být kladné celé číslo (není důležité uvažovat o případu, kdy k = 0) a d být nezáporné celé číslo. Proto, (k, 0) -barvení je ekvivalentní správnému zbarvení vrcholů.^[9]

d-chybné chromatické číslo

Minimální počet barev k požadované pro které G je (k, d) -barevná se nazývá d-chybné chromatické číslo, ${ displaystyle chi _ {d} (G)}$.^[10]

Pro třídu grafů G, vadné chromatické číslo z G je minimální celé číslo k takové, že pro celé číslo d, každý graf v G je (k,d)-pravděpodobný. Například vadné chromatické číslo třídy rovinných grafů se rovná 4, protože každý rovinný graf je (4,0) barevný a pro každé celé číslo d existuje rovinný graf, který není (3,d)-pravděpodobný.

Nesprávnost vrcholu

Nechat C být vrcholovým zabarvením grafu G. Nesprávnost vrcholu proti z G s ohledem na zbarvení C je počet sousedů proti které mají stejnou barvu jako proti. Pokud nevhodnost proti je tedy 0 proti se říká, že je správně zbarvený.^[1]

Nesprávnost zbarvení vrcholů

Nechat C být vrcholovým zabarvením grafu G. Nesprávnost C je maximum nevhodností všech vrcholů G. Proto je nevhodnost správného zbarvení vrcholů 0.^[1]

Příklad

Příklad vadného vybarvení cyklu na pěti vrcholech, když d = 0, 1, 2

Příklad vadného vybarvení cyklu na pěti vrcholech, ${ displaystyle C_ {5}}$, je znázorněno na obrázku. První dílčí obrázek je příkladem správného zbarvení vrcholů nebo (k, 0) -barvení. Druhý dílčí obrázek je příkladem (k, 1) -barvení a třetí dílčí obrázek je příkladem (k, 2) -barvení. Všimněte si, že,

${ displaystyle chi _ {0} (C_ {5}) = chi (C_ {5}) = 3}$

${ displaystyle chi _ {1} (C_ {5}) = 3}$

${ displaystyle chi _ {2} (C_ {n}) = 1; forall n in mathbb {N}}$

Vlastnosti

• Stačí považovat spojené grafy za graf G je (k, d) -barevný, pokud a jen pokud každý připojená součást z G je (k, d)-pravděpodobný.^[1]
• V teoretických podmínkách grafů tvoří každá barevná třída ve správném zbarvení vrcholů nezávislá sada, zatímco každá barevná třída vadného zbarvení tvoří maximálně podgraf stupně d.^[11]
• Pokud je graf (k, d) -barevné, pak je (k ', d ') -barevné pro každý pár (k ', d ') takové, že k ' ≥ k a d '≥ d.^[1]

Některé výsledky

Každý vnější rovinný graf je (2,2) -barevný

Důkaz: Nechat ${ displaystyle G}$ být spojeným vnějším rovinným grafem. Nechat ${ displaystyle v_ {0}}$ být libovolným vrcholem ${ displaystyle G}$. Nechat ${ displaystyle V_ {i}}$ být množina vrcholů ${ displaystyle G}$ které jsou na dálku ${ displaystyle i}$ z ${ displaystyle v_ {0}}$. Nechat ${ displaystyle G_ {i}}$ být ${ displaystyle langle V_ {i} rangle}$, podgraf vyvolaný ${ displaystyle V_ {i}}$.Předpokládat ${ displaystyle G_ {i}}$ obsahuje vrchol stupně 3 nebo více, pak obsahuje ${ displaystyle K_ {1,3}}$ jako podgraf. Pak smrštíme všechny hrany ${ displaystyle V_ {0} pohár V_ {1} pohár ... pohár V_ {i-1}}$ získat nový graf ${ displaystyle G '}$. Je třeba poznamenat, že ${ displaystyle langle V_ {0} cup V_ {1} cup ... cup V_ {i-1} rangle}$ z ${ displaystyle G '}$ je spojen jako každý vrchol v ${ displaystyle V_ {i}}$ sousedí s vrcholem v ${ displaystyle V_ {i-1}}$. Proto tím, že uzavírání smluv všechny výše uvedené hrany získáme ${ displaystyle G '}$ tak, že podgraf ${ displaystyle langle V_ {0} cup V_ {1} cup ... cup V_ {i-1} rangle}$ z ${ displaystyle G '}$ je nahrazen jediným vrcholem, který sousedí s každým vrcholem v ${ displaystyle V_ {i}}$. Tím pádem ${ displaystyle G '}$ obsahuje ${ displaystyle K_ {2,3}}$ jako podgraf. Ale každý podgraf vnějšího rovinného grafu je vnější rovinný a každý graf získaný smršťováním hran vnějšího rovinného grafu je vnější rovinný. To z toho vyplývá ${ displaystyle K_ {2,3}}$ je vnější rovina, rozpor. Proto žádný graf ${ displaystyle G_ {i}}$ obsahuje vrchol stupně 3 nebo více, z čehož vyplývá, že ${ displaystyle G}$ je (k, 2) -barevný. Žádný vrchol ${ displaystyle V_ {i}}$ sousedí s jakýmkoli vrcholem ${ displaystyle V_ {i-1}}$ nebo ${ displaystyle V_ {i + 1}, i geqslant 1}$, proto vrcholy ${ displaystyle V_ {i}}$ lze zbarvit modře, pokud ${ displaystyle i}$ je liché a červené, pokud sudé. Proto jsme vytvořili (2,2) zbarvení ${ displaystyle G}$.^[1]

Dodatek: Každý rovinný graf je (4,2) -barevný.To následuje, jako by ${ displaystyle G}$ je rovinný než každý ${ displaystyle G_ {i}}$ (stejně jako výše) je vnější rovinný. Proto každý ${ displaystyle G_ {i}}$ je (2,2) -barvitelný. Proto každý vrchol ${ displaystyle V_ {i}}$ mohou být vybarveny modře nebo červeně ${ displaystyle i}$ je sudé a zelené nebo žluté, pokud ${ displaystyle i}$ je liché, a proto vytváří (4,2) zbarvení ${ displaystyle G}$.

Grafy bez úplného vedlejšího

Pro každé celé číslo ${ displaystyle t}$ existuje celé číslo ${ displaystyle N}$ tak, že každý graf ${ displaystyle G}$ bez č ${ displaystyle K_ {t}}$ menší je ${ displaystyle (t-1, N)}$-pravděpodobný.^[12]

Výpočetní složitost

Vadné zbarvení je výpočetně těžké. Je NP-úplné rozhodnout, zda daný graf ${ displaystyle G}$ připouští (3,1) zbarvení, i když ${ displaystyle G}$ je maximálního stupně vrcholu 6 nebo rovinného maximálního stupně vrcholu 7.^[13]

Aplikace

Příkladem aplikace vadného vybarvení je problém s plánováním, kdy vrcholy představují úlohy (řekněme uživatelé v počítačovém systému) a hrany představují konflikty (je třeba získat přístup k jednomu nebo více stejným souborům). Povolení defektu znamená tolerovat určitou hranici konfliktu: každý uživatel může považovat maximální zpomalení vzniklé při načítání dat se dvěma konfliktními dalšími uživateli v systému za přijatelné a s více než dvěma nepřijatelnými.^[14]

Poznámky

Reference