Coloración De Grafo

Índice.

Pág.
Introducción…………………………………………………………………………………………………………….3

Contenido………………………………………………………………………………………………………………..4
Coloración de un grafo notable……………………………………………………………………………….4
Ciclo de Euler…………………………………………………………………………………………………………..5
Ciclo de Hamilton…………………………………………………………………………………………………….7
Algoritmo de Fleury…………………………………………………………………………………………………8
Polinomiocromático……………………………………………………………………………………………….9

Conclusión……………………………………………………………………………………………….……………11
Bibliografía………………………………………………………………………………………………………….12

2
Introducción.

En la teoría de grafos, existen diversas maneras en la facilitación del entendimiento de la materia, en la coloración de los grafos hay muchas formas para hacerlo de forma rápida y sencilla, ya que es un caso especial de etiquetado de grafo e; esuna asignación de etiquetas llamadas colores a elementos del grafo. De manera simple, una coloración de los vértices; también se hablara de otros temas muy importantes que son:
El ciclo de Euler que es una mera de recorrer un grafo.
El ciclo de Hamilton.
Algoritmo de Fleury.
Polinomio cromático.
Estos son algunos de los casos de los que trataremos a continuación.






3
Contenido.1.- Coloración de un grafo notable.
La coloración de grafos, es un caso especial; ya que de manera simple se puede llevar a cabo la coloración de los mismos, ya que es una asignación de etiquetas llamadas colores a elementos del grafo. De manera simple, una coloración de los vértices de un grafo tal que ningún vértice adyacente comparta el mismo color es llamado vértice coloración. Similarmente,una aristas coloración asigna colores a cada arista talque 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 compartan una 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 transformados auna 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 de un 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 literalmente coloreada. Esto fue generalizado a la coloración de caras degrafos inmersos en el plano. En representaciones matemáticas y computacionales es típicamente usado enteros no-negativos como colores. En general se puede usar un conjunto finito como conjunto de colores. Las coloraciones siempre existen pues siempre podemos asignar a cada vértice del grafo un color diferente si fuera necesario. Cada coloración de G produce en el conjunto de vértices V (G), unapartición de conjuntos independientes denominados clases de color, un conjunto de vértices I se llama independiente si dos vértices cualesquiera de I no son adyacentes.
Los problemas sobre coloración de grafo fueron, en la segunda mitad del siglo XIX, unos de los hitos iníciales de la teoría de grafos; en aquel tiempo se planteo unos de los problemas clásicos de la teoría de grafos el conocidoproblema de los cuatro colores, que no se resolvió hasta el año 1976, con la ayuda del ordenador.

4
Historia.
El primer resultado acerca de la coloración de grafos trataba exclusivamente sobre grafos planos y la coloración de mapas. Mientras intentaba colorear un mapa de Inglaterra, Francis Guthrie postulo l conjetura de los cuatro colores a, notando que 4 colores son suficientes paracolorear el mapa tal que regiones que comparten un borde común no reciban el mismo color. El hermano de Guthrie pasa el problema a
Su profesor de matemáticas Augustus de Morgan en la universidad, mencionado en una carta a William Hamilton en 1852. Arthur Cayley raised el problema a la London Mathematical Society en 1879. Algunos años después, Alfred Kempe público un papel que...