Rádiové vybarvení - Radio coloring
v teorie grafů, obor matematiky, a rádiové vybarvení z neorientovaný graf je forma zbarvení grafu ve kterém jeden přiřadí pozitivní celé číslo štítky ke grafu, že štítky sousedních vrcholů se liší alespoň o dva a štítky vrcholů ve vzdálenosti dva od sebe se liší alespoň o jeden. Rádiové vybarvení nejprve studoval Griggs & Yeh (1992) pod jiným jménem, L(2,1)-Značení.[1][2] Tomu se říkalo rádiové vybarvení Frank Harary protože modeluje problém přiřazení kanálu v rozhlasové vysílání, zatímco se vyhýbá elektromagnetické rušení mezi rozhlasovými stanicemi, které jsou blízko sebe, a to jak v grafu, tak na jejich přiřazených frekvencích kanálu.
The rozpětí rádiového zbarvení je jeho maximální štítek a číslo rádiového vybarvení grafu je nejmenší možné rozpětí rádiového vybarvení.[1] Například graf skládající se ze dvou vrcholů s jednou hranou má rádiové zbarvení číslo 3: má rádiové zbarvení s jedním vrcholem označeným 1 a druhým označeným 3, ale není možné, aby rádiové zbarvení tohoto grafu používalo pouze štítky 1 a 2.
Výpočetní složitost
Nalezení rádiového vybarvení s daným (nebo minimálním) rozpětím je NP-kompletní, i když je omezeno na rovinné grafy, rozdělené grafy, nebo doplňuje z bipartitní grafy.[1][3] Je však řešitelný v polynomiální čas pro stromy a cographs.[1][4] U libovolných grafů to lze vyřešit v jednotlivě exponenciální čas, výrazně rychlejší než vyhledávání hrubou silou ve všech možných barveních.[5][6]
Další vlastnosti
Ačkoli rádiové zbarvení číslo n-vertexový graf se může pohybovat od 1 do 2n − 1, téměř všechny n-vertexové grafy mají rádiové barevné číslo přesně n. Je to proto, že tyto grafy téměř vždy mají průměr alespoň dva (vynucení všech vrcholů, aby měly odlišné barvy, a vynucení čísla rádiového vybarvení alespoň n), ale také téměř vždy mají Hamiltonova cesta v doplňkový graf. Po sobě jdoucím vrcholům na této cestě lze přiřadit po sobě jdoucí barvy, což umožňuje rádiové vybarvení, aby se zabránilo přeskakování čísel.[7]
Reference
- ^ A b C d Broersma, Hajo (2005), „Obecný rámec pro problémy s barvením: staré výsledky, nové výsledky a otevřené problémy“ (PDF), Kombinatorická geometrie a teorie grafů, Poznámky k přednášce ve Výpočtu. Sci., 3330, Springer, Berlín, str. 65–79, doi:10.1007/978-3-540-30540-8_7, PAN 2172960. Viz zejména Část 3, „Rádiové vybarvení“.
- ^ Griggs, Jerrold R .; Yeh, Roger K. (1992), "Označování grafů s podmínkou ve vzdálenosti 2", SIAM Journal on Discrete Mathematics, 5 (4): 586–595, doi:10.1137/0405048, PAN 1186826.
- ^ Bodlaender, Hans L.; Kloks, Ton; Tan, Richard B .; van Leeuwen, leden (2000), "λ-barvení grafů ", STACS 2000: 17. výroční sympozium o teoretických aspektech informatiky, Lille, Francie, 17. – 19. Února 2000, sborník, Přednášky v informatice, 1770, Springer, Berlín, str. 395–406, doi:10.1007/3-540-46541-3_33, PAN 1781749.
- ^ Chang, Gerard J .; Kuo, David (1996), „The L(2,1)problém s označováním na grafech ", SIAM Journal on Discrete Mathematics, 9 (2): 309–316, CiteSeerX 10.1.1.51.2004, doi:10.1137 / S0895480193245339, PAN 1386886.
- ^ Havet, Frédéric; Klazar, Martin; Kratochvíl, Jan; Kratsch, Dieter; Liedloff, Mathieu (2011), "Přesné algoritmy pro L(2,1)-značení grafů " (PDF), Algorithmica, 59 (2): 169–194, doi:10.1007 / s00453-009-9302-7, PAN 2765572, S2CID 2634447.
- ^ Junosza-Szaniawski, Konstanty; Rzążewski, Paweł (2011), "O složitosti přesného algoritmu pro L(2,1)-značení grafů ", Dopisy o zpracování informací, 111 (14): 697–701, doi:10.1016 / j.ipl.2011.04.010, PAN 2840535.
- ^ Harary, Franku; Plantholt, Michael (1999), "Grafy, jejichž rádiové zabarvení se rovná počtu uzlů", Barvení grafů a aplikace (Montréal, QC, 1997), CRM Proc. Poznámky z přednášky, 23„Providence, RI: American Mathematical Society, s. 99–100, PAN 1723637.