Grafo
Páginas: 2 (269 palabras)
Publicado: 15 de mayo de 2012
Coloración de grafos
Una coloración de vértices para el grafo de Petersen utilizando tres colores, el número mínimo posible.
En Teoría de grafos, la coloración degrafos es un caso especial de etiquetado de grafos; es una asignación de etiquetas llamadas colores a elementos del grafo. De manera simple, una coloración de los vérticesde un grafo tal que ningún vértice adyacente comparta el mismo color es llamado vértice coloración. Similarmente, una arista coloración asigna colores a cada aristatalque aristas adyacentes no compartan el mismo color, y una coloración de caras de un grafo plano a la asignación de un color a cada cara o región tal que caras que compartanuna frontera común tengan colores diferentes.
El vértice coloración es el punto de inicio de la coloración, y los otros problemas de coloreo pueden ser transformadosa una versión con vértices. Por ejemplo, una arista coloración de un grafo es justamente una vértice coloración del grafo línea respectivo, y una coloración de caras deun grafo plano es una vértice coloración del grafo dual.
La convención de usar colores se origina de la coloración de países de un mapa, donde cada cara es literalmentecoloreada. Esto fue generalizado a la coloración de caras de grafos inmersos en el plano. En representaciones matemáticas y computacionales es típicamente usado enterosno-negativos como colores. En general se puede usar un conjunto finito como conjunto de colores. La naturaleza del problema de coloración depende del número de colorespero no sobre cuales son.
Cotas del número cromático
Asignando distintos colores a distintos vértices siempre obtendremos una coloración propia, entonces
1
Una coloración de vértices para el grafo de Petersen utilizando tres colores, el número mínimo posible.
En Teoría de grafos, la coloración degrafos es un caso especial de etiquetado de grafos; es una asignación de etiquetas llamadas colores a elementos del grafo. De manera simple, una coloración de los vérticesde un grafo tal que ningún vértice adyacente comparta el mismo color es llamado vértice coloración. Similarmente, una arista coloración asigna colores a cada aristatalque aristas adyacentes no compartan el mismo color, y una coloración de caras de un grafo plano a la asignación de un color a cada cara o región tal que caras que compartanuna frontera común tengan colores diferentes.
El vértice coloración es el punto de inicio de la coloración, y los otros problemas de coloreo pueden ser transformadosa una versión con vértices. Por ejemplo, una arista coloración de un grafo es justamente una vértice coloración del grafo línea respectivo, y una coloración de caras deun grafo plano es una vértice coloración del grafo dual.
La convención de usar colores se origina de la coloración de países de un mapa, donde cada cara es literalmentecoloreada. Esto fue generalizado a la coloración de caras de grafos inmersos en el plano. En representaciones matemáticas y computacionales es típicamente usado enterosno-negativos como colores. En general se puede usar un conjunto finito como conjunto de colores. La naturaleza del problema de coloración depende del número de colorespero no sobre cuales son.
Cotas del número cromático
Asignando distintos colores a distintos vértices siempre obtendremos una coloración propia, entonces
1
Leer documento completo
Regístrate para leer el documento completo.