Vés al contingut

Coloració de grafs

De la Viquipèdia, l'enciclopèdia lliure
Una coloració adequada del graf de Petersen amb 3 colors, el mínim nombre possible perquè no n'hi hagi dos de contigus.

En teoria de grafs, la coloració de grafs és un cas especial d'etiquetatge de grafs, una assignació d'etiquetes tradicionalment anomenades «colors» als elements d'un graf subjecte a certes restriccions. En la seva forma més senzilla, és una manera d'acolorir els vèrtexs d'un graf de tal manera que no n'hi hagi dos de contigus del mateix color; d'això se'n diu coloració de vèrtexs. Similarment, la coloració d'arestes consisteix a assignar un color a cada aresta tal que no n'hi hagi dues d'adjacents del mateix color i la coloració de cares d'un graf planar consisteix a assignar un color a cada cara o regió tal que no hi hagi dues cares del mateix color amb un costat en comú.

El punt de partida del tema és la coloració de vèrtexs, ja que la resta de problemes de coloració es poden reduir a una de vèrtexs. Per exemple, la coloració d'arestes d'un graf és tan sols una coloració de vèrtexs del seu graf línia i la coloració de cares d'un graf pla és simplement una coloració de vèrtexs del seu dual. Tanmateix, els problemes que no són de coloració de vèrtexs solen estudiar-se tal com són. Això és per una part per la perspectiva i per l'altra perquè certs problemes són més fàcils d'estudiar amb un sistema diferent —la coloració d'arestes n'és un exemple.

La convenció d'utilitzar colors prové de la cartografia, on els països o regions s'acoloreixen diferent per distingir-se. Aquest sistema es generalitzà acolorint les cares d'un graf incrustat en el pla. Per dualitat planar esdevingué coloració de vèrtexs i d'aquesta forma es generalitza a tots els grafs. En les representacions matemàtiques i computacionals, és habitual usar els primers enters positius o no negatius com a «colors». Més generalment, es pot usar qualsevol conjunt finit com a «conjunt de colors».

La coloració de grafs té diverses utilitats pràctiques així com reptes teòrics. A part dels tipus clàssics de problemes, també es poden aplicar diferents limitacions al graf, a l'assignació del color o fins i tot al color en si. Entre el públic general ha assolit popularitat a través del trencaclosques numèric sudoku. La coloració de grafs segueix sent un camp actiu de recerca.

Fonts

[modifica]
  • Panconesi, A.; Srinivasan, A. Journal of Algorithms. 20, 1996. «On the complexity of distributed network decomposition»