Hamiltonovské zbarvení - Hamiltonian coloring

Hamiltonovské zbarvení, pojmenoval podle William Rowan Hamilton, je typ zbarvení grafu. Hamiltonovské zbarvení používá koncept zvaný objížďková vzdálenost mezi dvěma vrcholy grafu.[1] Má mnoho aplikací v různých oblastech vědy a techniky.

Terminologie

Rádiové vybarvení

Graf G s průměrem D s n uzly, který je barevný (tj. Má kladné celé číslo přiřazené každému vrcholu) s barvami k, se nazývá rádiové k-zbarvení G, jestliže pro každou dvojici vrcholů a a b je součet vzdálenosti mezi a rozdíl mezi jejich štítky („barvami“) je větší než k. Například dva uzly označené 3 a 7 se vzdáleností 5 jsou přijatelné pro rádio 8-zbarvení, ale ne pro rádio 9-zbarvení, protože , která není větší než 9.

Antipodální zbarvení

Rádiové (d-1) barvení, tj. Kde k se rovná jedné menší než průměr grafu, je známé jako antipodální zbarvení, protože antipodální vrcholy mohou být zbarveny stejně, ale všechny uzly mezi nimi musí být odlišné.

Vzdálenost objížďky

Vzdálenost objížďky mezi u a v in C5 je 4

Vzdálenost mezi dvěma vrcholy v grafu je definována jako minimální délka cesty spojující ty vrcholy. The vzdálenost objížďky mezi dvěma vrcholy, řekněme, u a v je definována jako délka nejdelší cesty u-v v grafu.[1] V případě stromu je vzdálenost objížďky mezi dvěma vrcholy stejná jako vzdálenost mezi dvěma vrcholy.

Hamiltonovské zbarvení

Hamiltonovské zbarvení je variace na antipodální zbarvení, kde se místo uvažování o pravidelné vzdálenosti mezi uzly místo toho uvažuje vzdálenost objížďky. Konkrétně uzly hamiltonovského zbarvení mají tu vlastnost, že vzdálenost objížďky plus rozdíl v barvách je větší nebo roven jednomu menšímu než n, což je počet uzlů v grafu. Pokud je graf G cesta, pak jakékoli Hamiltonovské zbarvení je také antipodálním zabarvením, které je inspirací pro definici Hamiltonovského zbarvení.

Reference

  1. ^ A b Chartrand, Gary; Zhang, Ping (2009). "14. Barvení, vzdálenost a nadvláda". Teorie chromatického grafu. CRC Press. 397–438.
  • Chartrand, Gary a kol. „Hamiltonovské zbarvení grafů.“ Diskrétní aplikovaná matematika, roč. 146, č. 3., 15. března 2005, doi:10.1016 / j.dam.2004.08.007.