UNIDAD Nº4.coloración de grafos

Coloreo ,Coloración o  Coloreado  de Grafos


El objetivo de este tema  consiste en asignar distintos colores (o números enteros) a los vértices de un grafo, de manera que ningún par de vértices adyacentes compartan el mismo color (o número). El problema puede plantearse también para aristas o para caras de la inmersión plana de un grafo, siendo el desarrollo muy similar al coloreo de vértices.

 

 

  Número Cromático

 Un grafo se denomina k-coloreado si puede colorearse con k colores distintos. Es decir, si existe una asignación de k colores diferentes que permitan un coloreo válido de un grafo G. Se llama coloreo válido al que cumple la propiedad de no asignar el mismo color a un par de vértices adyacentes.

 El número cromático de un grafo es el menor número natural k entre todos los valores posibles que permiten k-colorear un grafo. Se denomina a este valor Χ (G).

 

  Propiedades

    Entre las propiedades del número cromático, se pueden mencionar las siguientes:

     Para un grafo completo Kn ,X(Kn)=n Esto se puede ver intuitivamente, ya que un grafo completo tiene                 todos    sus nodos conectados entre sí, es decir, vvv

Por lo tanto, como un coloreo válido obliga a que dos     nodos    adyacentes     tengan colores distintos, se necesitan n colores distintos para formar un coloreo válido  de G, y este es    el menor  número posible. Luego, \Chi{(G)} = n \,
  • Si G es un ciclo de longitud par, entonces \Chi{(G)} = 2 \,
  • Si G es un ciclo de longitud impar, entonces \Chi{(G)} = 3 \,
  • Para todo grafo G, \Chi{(G)} \ge \omega{(G)}, donde \omega{(G)} \, corresponde al valor de la cliqué de mayor orden de un grafo.
  • Para todo grafo G, \Chi{(G)} \le \Delta{(G)} ó \Chi{(G)} \le \Delta{(G)} + 1,    donde \Delta{(G)} \, es    el máximo entre los grados de todos los nodos (es decir, el grado máximo).
  •  

 

Esta pagina fue creada con la finalidad de  elaboracion de trabajos y aplicacion de nuestros conocimientos sobre la Teoría de grafos