Intento demostrar que para cualquier grafo existe una ordenación de los vértices tal que el Algoritmo Greedy coloreará los vértices de forma que utilice el número cromático de colores.
Estoy intentando atacar esto por inducción, y tengo la impresión de que casi lo he conseguido. Sin embargo, he estado perdiendo bastante tiempo tratando de hacer el paso inductivo sólido, así que me preguntaba, si alguien sabe si mi estrategia puede incluso potencialmente trabajar?
para cualquier grafo existe una ordenación de los vértices tal que el algoritmo Greedy coloreará los vértices de tal forma que utilice el número cromático de colores
Por supuesto que existe tal ordenación - si tienes la coloración óptima, ordena los vértices st. primero vienen los vértices de color 1, luego los vértices de color 2, ...
¿Es esto lo que querías saber?
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
