Duhové zbarvení - Rainbow coloring

Duhové zbarvení a graf kola, se třemi barvami. Každé dva nesousedící vrcholy lze spojit duhovou cestou, buď přímo středním vrcholem (vlevo dole), nebo oklikou kolem jednoho trojúhelníku, aby se zabránilo opakované barvě hrany (vpravo dole).

v teorie grafů, cesta v okrajově zbarvený graf se říká, že je duha pokud se na něm neopakuje žádná barva. Říká se, že je graf spojené s duhou (nebo duhové barvy) pokud je mezi každou dvojicí duhová cesta vrcholy. Pokud je duha nejkratší cesta mezi každou dvojicí vrcholů se říká, že graf je silně spojené s duhou (nebo silně duhové barvy).^[1]

Definice a hranice

The duhové číslo připojení grafu ${ displaystyle G}$ je minimální počet barev potřebných k připojení duhy ${ displaystyle G}$, a je označen ${ displaystyle { text {rc}} (G)}$. Podobně silné duhové číslo připojení grafu ${ displaystyle G}$ je minimální počet barev potřebných pro silné duhové připojení ${ displaystyle G}$, a je označen ${ displaystyle { text {src}} (G)}$. Je zřejmé, že každé silné duhové zbarvení je také duhové zbarvení, zatímco konverzace obecně není pravdivá.

Je snadné si všimnout, že k připojení duhového grafu ${ displaystyle G}$, potřebujeme alespoň ${ displaystyle { text {diam}} (G)}$ barvy, kde ${ displaystyle { text {diam}} (G)}$ je průměr z ${ displaystyle G}$ (tj. délka nejdelší nejkratší cesty). Na druhou stranu nikdy nemůžeme použít více než ${ displaystyle m}$ barvy, kde ${ displaystyle m}$ označuje počet hrany v ${ displaystyle G}$. Nakonec, protože každý graf silně spojený s duhou je spojen s duhou, máme to ${ displaystyle { text {diam}} (G) leq { text {rc}} (G) leq { text {src}} (G) leq m}$.

Následují extremální případy:^[1]

• ${ displaystyle { text {rc}} (G) = { text {src}} (G) = 1}$ kdyby a jen kdyby ${ displaystyle G}$ je kompletní graf.
• ${ displaystyle { text {rc}} (G) = { text {src}} (G) = m}$ kdyby a jen kdyby ${ displaystyle G}$ je strom.

Výše uvedené ukazuje, že z hlediska počtu vrcholů je horní mez ${ displaystyle { text {rc}} (G) leq n-1}$ je obecně nejlepší. Ve skutečnosti duhové zbarvení pomocí ${ displaystyle n-1}$ barvy lze vytvořit zbarvením okrajů kostry stromu ${ displaystyle G}$ v odlišných barvách. Zbývající nezbarvené okraje jsou libovolně zabarveny, aniž by byly zavedeny nové barvy. Když ${ displaystyle G}$ je 2-propojený, máme to ${ displaystyle { text {rc}} (G) leq lceil n / 2 rceil}$.^[2] Navíc je to těsné, jak svědčí např. liché cykly.

Přesná čísla duhy nebo silná čísla duhy

Duhové nebo silné duhové číslo připojení bylo určeno pro některé třídy strukturovaných grafů:

• ${ displaystyle { text {rc}} (C_ {n}) = { text {src}} (C_ {n}) = lceil n / 2 rceil}$, pro každé celé číslo ${ displaystyle n geq 4}$, kde ${ displaystyle C_ {n}}$ je graf cyklu.^[1]
• ${ displaystyle { text {rc}} (W_ {n}) = 3}$, pro každé celé číslo ${ displaystyle n geq 7}$, a ${ displaystyle { text {src}} (W_ {n}) = lceil n / 3 rceil}$, pro ${ displaystyle n geq 3}$, kde ${ displaystyle W_ {n}}$ je graf kola.^[1]

Složitost

Problém rozhodování, zda ${ displaystyle { text {rc}} (G) = 2}$ pro daný graf ${ displaystyle G}$ je NP-kompletní.^[3] Protože ${ displaystyle { text {rc}} (G) = 2}$ kdyby a jen kdyby ${ displaystyle { text {src}} (G) = 2}$,^[1] z toho vyplývá, že rozhodnutí, zda ${ displaystyle { text {src}} (G) = 2}$ je NP-kompletní pro daný graf ${ displaystyle G}$.

Varianty a zevšeobecnění

Chartrand, Okamoto a Zhang^[4] zobecnil číslo duhového připojení následovně. Nechat ${ displaystyle G}$ být okrajově zbarvený netriviální připojený graf objednávky ${ displaystyle n}$. Strom ${ displaystyle T}$ je duhový strom pokud nejsou dva okraje ${ displaystyle T}$ mají stejnou barvu. Nechat ${ displaystyle k}$ být pevné celé číslo s ${ displaystyle 2 leq k leq n}$. Barvení hran z ${ displaystyle G}$ se nazývá a ${ displaystyle k}$- duhové zbarvení pokud pro každou sadu ${ displaystyle S}$ z ${ displaystyle k}$ vrcholy ${ displaystyle G}$, je v ní duhový strom ${ displaystyle G}$ obsahující vrcholy ${ displaystyle S}$. The ${ displaystyle k}$- index duhy ${ displaystyle { text {rx}} _ {k} (G)}$ z ${ displaystyle G}$ je minimální počet barev potřebných v a ${ displaystyle k}$- duhové zbarvení ${ displaystyle G}$. A ${ displaystyle k}$-barvení duhy pomocí ${ displaystyle { text {rx}} _ {k} (G)}$ barvy se nazývá a minimální ${ displaystyle k}$- duhové zbarvení. Tím pádem ${ displaystyle { text {rx}} _ {2} (G)}$ je číslo duhového připojení ${ displaystyle G}$.

Duhové spojení bylo také studováno ve vrcholkových grafech. Tento koncept představili Krivelevich a Yuster.^[5]Tady je číslo připojení duhového vrcholu grafu ${ displaystyle G}$, označeno ${ displaystyle { text {rvc}} (G)}$, je minimální počet barev potřebných k vybarvení ${ displaystyle G}$ tak, že pro každou dvojici vrcholů je spojující cesta, jejíž vnitřní vrcholy mají přiřazené odlišné barvy.

Viz také

• Duhová shoda

Poznámky

Reference

• Chartrand, Gary; Johns, Garry L .; McKeon, Kathleen A .; Zhang, Ping (2008), „Duhové spojení v grafech“, Mathematica Bohemica, 133 (1).
• Chartrand, Gary; Okamoto, Futaba; Zhang, Ping (2010), „Duhové stromy v grafech a zobecněná konektivita“, Sítě, 55 (4), doi:10,1002 / net.20339.
• Chakraborty, Sourav; Fischer, Eldar; Matsliah, Arie; Yuster, Raphael (2011), „Tvrdost a algoritmy pro duhové spojení“, Journal of Combinatorial Optimization, 21 (3): 330–347, arXiv:0809.2493, doi:10.1007 / s10878-009-9250-9.
• Krivelevich, Michael; Yuster, Raphael (2010), „Duhové spojení grafu je (nanejvýš) vzájemné na svůj minimální stupeň“, Journal of Graph Theory, 63 (3): 185–191, doi:10.1002 / jgt.20418.
• Li, Xueliang; Shi, Yongtang; Sun, Yuefang (2013), „Rainbow Connections of Graphs: A Survey“, Grafy a kombinatorika, 29 (1): 1–38, arXiv:1101.5747, doi:10.1007 / s00373-012-1243-2.
• Li, Xueliang; Sun, Yuefang (2012), Duhové spoje grafů, Springer, str. 103, ISBN  978-1-4614-3119-0.
• Ekstein, Jan; Holub, Přemysl; Kaiser, Tomáš; Koch, Maria; Camacho, Stephan Matos; Ryjáček, Zdeněk; Schiermeyer, Ingo (2013), „Duhové číslo připojení 2 propojených grafů“, Diskrétní matematika, 313 (19): 1884–1892, arXiv:1110.5736, doi:10.1016 / j.disc.2012.04.022.