Wikipedia

Diferencia entre revisiones de «Coloración de grafos»

Explorar historial interactivamente
← Ir a diferencia anteriorIr a siguiente diferencia →
Contenido eliminado Contenido añadido
VisualWikitexto
ZéroBot (discusión · contribs.)
337 129 ediciones
mSin resumen de edición
Línea 23:
 
=== Polinomio cromático ===
[[Archivo:Chromatic_polynomial_of_all_3-vertex_graphs.png|thumb|200px|Todos los grafos no-isomorfos de 3 vértices y sus polinomios cromáticos. El grafo vació ''E''<sub>3</sub> (rojo) admite una 1-coloración. El grafo verde admite 12 coloraciones con 3 colores.]]
El '''polinomio cromático''' cuenta el número de maneras en las cuales puede ser coloreado un grafo usando no más que un número de colores dado. Por ejemplo, usando 3 colores, el grafo en la imagen de la derecha puede ser coloreado de 12 formas distintas. Con solo 2 colores, no puede ser coloreado. Con 4 colores, puede ser coloreado de 24+4*12 maneras distintas: usando los cuatro colores juntos, hay 4!= 24 coloraciones validas (toda asignación de cuatro colores a algún grafo de cuatro vértices es una coloración propia); y para cada elección de tres de los cuatro colores, hay 12 3-coloraciones validas. Así que, para el grafo del ejemplo, una tabla de números de coloraciones validas puede comenzar como esta:
 
Obtenido de «https://es.wikipedia.org/wiki/Coloración_de_grafos»