Rozlišující zbarvení - Distinguishing coloring

Rozlišující zbarvení 4-hyperkrychlový graf

v teorie grafů, a rozlišovací zbarvení nebo rozlišovací označení grafu je přiřazení barev nebo štítky do vrcholy grafu, který ničí všechny netriviální symetrie grafu. Barvení nemusí být správné zbarvení: sousedním vrcholům může být přidělena stejná barva. U barevného grafu by nemělo existovat žádné individuální mapování vrcholů k sobě, které by zachovalo sousednost i zbarvení. Minimální počet barev rozlišovacího zbarvení se nazývá rozlišovací číslo grafu.

Rozlišovací barviva a rozlišovací čísla byly zavedeny Albertson & Collins (1996), který uvedl následující motivující příklad na základě hádanky, kterou dříve vytvořil Frank Rubin: „Předpokládejme, že máte prsten klíčů k různým dveřím; každý klíč otevírá pouze jedny dveře, ale všechny pro vás vypadají k nerozeznání. Kolik barev máte Potřebujete zabarvit rukojeti kláves takovým způsobem, abyste mohli každý klíč jednoznačně identifikovat? “[1] Tento příklad je vyřešen použitím rozlišujícího zbarvení pro a graf cyklu. S takovým zbarvením bude každý klíč jednoznačně identifikován podle své barvy a posloupnosti barev, které ji obklopují.[2]

Příklady

Osm asymetrických grafů, z nichž každý dostal charakteristické zbarvení pouze s jednou barvou (červenou)

Graf má rozlišovací číslo jedna právě tehdy, když je asymetrický.[3] Například Frucht graf má rozlišovací zbarvení pouze s jednou barvou.

V kompletní graf, jediné rozlišovací barvy přiřazují každému vrcholu jinou barvu. Pokud by dvěma vrcholům byla přiřazena stejná barva, existovala by symetrie, která tyto dva vrcholy vyměnila a zbytek ponechala na místě. Proto rozlišovací číslo celého grafu K.n je n. Graf získaný z K.n připojením vrcholu stupně jeden ke každému vrcholu K.n má výrazně menší rozlišovací číslo, přestože má stejnou skupinu symetrie: má rozlišovací zbarvení s barvy, získané použitím jiné seřazené dvojice barev pro každou dvojici vrcholu K.n a jeho připojený soused.[2]

Rozlišovací zbarvení prstenu šesti klíčů pomocí dvou barev (červená a nelakovaná)

Pro graf cyklu tří, čtyř nebo pěti vrcholů jsou k vytvoření rozlišovacího zbarvení zapotřebí tři barvy. Například každé dvě zbarvení pěti cyklů má reflexní symetrii. Přiřazení jedinečné barvy každému ze dvou sousedních vrcholů a použití třetí barvy pro všechny zbývající vrcholy má v každém z těchto cyklů za následek tříbarevné rozlišovací zbarvení. Cykly šesti nebo více vrcholů však rozlišují zbarvení pouze dvěma barvami. To znamená, že klíčenka Frank Rubin vyžaduje tři barvy pro kroužky se třemi, čtyřmi nebo pěti klíči, ale pouze dvě barvy pro šest nebo více klíčů nebo pro dva klíče.[2] Například v kruhu šesti zobrazených kláves lze každou klávesu rozlišit podle její barvy a podle délky nebo délek sousedních bloků opačně zbarvených kláves: pro každou kombinaci barvy klíče a délky sousedních bloků existuje pouze jeden klíč .

Hypercube grafy vykazují podobný jev jako cyklické grafy. Dvourozměrné a trojrozměrné grafy hyperkrychle (4-cyklus a graf krychle) mají rozlišovací číslo tři. Každý hyperkrychlový graf vyšší dimenze má však rozlišovací číslo pouze dva.[4]

The Petersenův graf má rozlišovací číslo 3. Avšak kromě tohoto grafu a úplných grafů všechny Kneserovy grafy mít rozlišovací číslo 2.[5] Podobně mezi zobecněné Petersenovy grafy, rozlišovací číslo 3 má pouze samotný Petersenův graf a graf krychle; zbytek má rozlišovací číslo 2.[6]

Výpočetní složitost

Rozlišovací čísla stromy, rovinné grafy, a intervalové grafy lze vypočítat v polynomiální čas.[7][8][9]

Přesná složitost výpočtu rozlišovacích čísel je nejasná, protože úzce souvisí se stále neznámou složitostí izomorfismus grafu. Ukázalo se však, že patří do třídy složitosti DOPOLEDNE.[10] Navíc testování, zda rozlišovací číslo je nejvýše tři, je NP-tvrdé,[9] a testování, zda jsou nanejvýš dvě, je „přinejmenším stejně těžké jako automatický graf, ale ne těžší než izomorfismus grafů“.[11]

Další vlastnosti

Zbarvení daného grafu je pro tento graf rozlišující právě tehdy, pokud je rozlišující pro doplňkový graf. Proto má každý graf stejné rozlišovací číslo jako jeho doplněk.[2]

Pro každý graf G, rozlišovací číslo G je nanejvýš úměrná logaritmus z počtu automorfismy z G. Pokud automorfismy tvoří netriviální abelianská skupina, rozlišovací číslo je dvě, a pokud tvoří a dihedrální skupina rozlišovací číslo je pak nejvýše tři.[2]

Pro každého konečná skupina, existuje graf s touto skupinou jako s její skupinou automorfismů, s rozlišením číslo dvě.[2] Tento výsledek se rozšiřuje Fruchtova věta že každou konečnou skupinu lze realizovat jako skupinu symetrií grafu.

Variace

A správné rozlišovací zbarvení je rozlišovací zbarvení, které je také správným zbarvením: každý dva sousední vrcholy mají různé barvy. Minimální počet barev ve správném rozlišovacím zabarvení grafu se nazývá rozlišovací chromatické číslo grafu.[12]

Reference

  1. ^ Rubin, Frank (1979), „Problém 729: klíče slepce“, Časopis rekreační matematiky, 11: 128. Řešení v obj. 12, 1980. Jak uvádí Albertson & Collins (1996). Místo použití barev Rubin formuloval problém v podobě klíčových rukojetí, které lze od sebe odlišit dotykem. Přesněji tento problém předpokládá, že každý klíč je symetrický, takže klíče nelze od sebe odlišit podle jejich orientace na klíčence.
  2. ^ A b C d E F Albertson, Michael O .; Collins, Karen L. (1996), „Symetrie lámání v grafech“, Electronic Journal of Combinatorics, 3 (1): R18, PAN  1394549.
  3. ^ Viz např. Imrich, Wilfried; Klavžar, Sandi (2006), „Rozlišování kartézských sil grafů“, Journal of Graph Theory, 53 (3): 250–260, CiteSeerX  10.1.1.59.9242, doi:10.1002 / jgt.20190, PAN  2262268, Pokud graf nemá žádné netriviální automorfismy, jeho rozlišovací číslo je 1. Jinými slovy, D(G) = 1 pro asymetrické grafy.
  4. ^ Bogstad, Bill; Cowen, Lenore J. (2004), „Rozlišovací číslo hyperkrychle“, Diskrétní matematika, 283 (1–3): 29–35, doi:10.1016 / j.disc.2003.11.018, PAN  2061481.
  5. ^ Albertson, Michael O .; Boutin, Debra L. (2007), "Použití určujících množin k rozlišení Kneserových grafů", Electronic Journal of Combinatorics, 14 (1): R20, PAN  2285824.
  6. ^ Lal, A. K .; Bhattacharjya, B. (2009), „Prolomení symetrií knižního grafu a zobecněného Petersenova grafu“, SIAM Journal on Discrete Mathematics, 23 (3): 1200–1216, doi:10.1137/080728640, PAN  2538646. Lal a Bhattacharjya (Theorem 4.3) připisují tento výsledek nepublikované diplomové práci K. S. Potanky (Virginia Polytechnic University, 1998).
  7. ^ Cheng, Christine T. (2006), „Při výpočtu rozlišovacích čísel stromů a lesů“, Electronic Journal of Combinatorics, 13 (1): R11, PAN  2200539.
  8. ^ Arvind, V .; Cheng, Christine T .; Devanur, Nikhil R. (2008), „K výpočtu rozlišujících počtů rovinných grafů a dále: přístup počítání“, SIAM Journal on Discrete Mathematics, 22 (4): 1297–1324, arXiv:matematika / 0703927, doi:10.1137 / 07068686X, PAN  2443115.
  9. ^ A b Cheng, Christine T. (2009), „O výpočtu rozlišovacích a rozlišovacích chromatických čísel intervalových grafů a dalších výsledků“, Diskrétní matematika, 309 (16): 5169–5182, doi:10.1016 / j.disc.2009.04.004, PAN  2548918.
  10. ^ Russell, Alexander; Sundaram, Ravi (1998), „Poznámka k asymptotice a výpočetní složitosti rozlišitelnosti grafů“, Electronic Journal of Combinatorics, 5: R23, PAN  1617449.
  11. ^ Eschen, Elaine M .; Hoàng, Chính T .; Sritharan, R .; Stewart, Lorna (2011), „O složitosti rozhodování, zda rozlišovací chromatický počet grafů je nejvýše dva“, Diskrétní matematika, 311 (6): 431–434, arXiv:0907.0691, doi:10.1016 / j.disc.2010.12.013, PAN  2799894.
  12. ^ Collins, Karen L.; Trenk, Ann N. (2006), "Rozlišovací chromatické číslo", Electronic Journal of Combinatorics, 13 (1): R16, PAN  2200544.