Radiofärgning
I grafteorin , en gren av matematiken, är radiofärgning av en oriktad graf en form av graffärgning där man tilldelar graferna positiva heltalsetiketter så att beteckningarna för intilliggande hörn skiljer sig åt med minst två, och etiketterna för hörn på avstånd två från varandra skiljer sig med minst en. Radiofärgning studerades först av Griggs & Yeh (1992) , under ett annat namn, L (2,1) -märkning. Det kallades radiofärgning av Frank Harary eftersom det modellerar problemet med kanaltilldelning i radiosändningar , samtidigt som man undviker elektromagnetisk störning mellan radiostationer som är nära varandra både i grafen och i deras tilldelade kanalfrekvenser.
Spännvidden för en radiofärgning är dess maximala etikett, och radiofärgningsnumret för en graf är den minsta möjliga spännvidden för en radiofärgning. Till exempel har grafen som består av två hörn med en enda kant radiofärgning nummer 3: den har en radiofärgning med en vertex märkt 1 och den andra märkt 3, men det är inte möjligt för en radiofärgning av denna graf att endast använda etiketterna 1 och 2.
Beräkningskomplexitet
Att hitta en radiofärg med en given (eller minsta) spännvidd är NP-komplett , även när det är begränsat till plana grafer , delade grafer eller komplementen till tvådelade grafer . Det är dock lösbart i polynomtid för träd och kografer . För godtyckliga grafer kan det lösas i singel-exponentiell tid , betydligt snabbare än en brute-force-sökning genom alla möjliga färger.
Övriga fastigheter
Även om radiofärgningsnumret för en n -vertexgraf kan variera från 1 till 2 n −1 , har nästan alla n -vertexgrafer radiofärgningsnummer exakt n . Detta beror på att dessa grafer nästan alltid har en diameter på minst två (som tvingar alla hörn att ha distinkta färger och tvingar radiofärgningsnumret att vara minst n ), men de har också nästan alltid en Hamiltonsk bana i komplementgrafen . Konsekutiva hörn i denna väg kan tilldelas konsekutiva färger, vilket tillåter en radiofärgning för att undvika att hoppa över några siffror.