Cómo puede un algoritmo siempre de color conectada bipartito gráficos?

Question

Vamos a considerar un algoritmo voraz para la coloración problema llamado el Dsatur algoritmo, diseñado por Daniel Brélaz en 1979 en la EPFL, Suiza.. Este algoritmo se basa en una orden de los vértices que podemos obtener de la consideración de la saturación de grado de cada vértice $v$$G$. La saturación de grado de un vértice $v$ , que podemos escribir como $DSAT(v)$, es el número de color, el número de diferentes colores que se utilizan en $v$ barrio. La idea es de color primero los vértices con un grado de saturación suficientemente alta para evitar el uso de demasiados colores.

Data : an undirected (*non-orienté*) connected graph $G=(V,E)$.
Output : all vertices of $G$ colored.

SORT the vertices by decreasing order of degrees.
COLOR a vertex of maximum degree with color 1.
While it exists vertices not colored do 
  CHOOSEa vertex $v$ with max DSAT
  COLOR $v$ with the smallest possible color
  UPDATE DSAT for all neighbors of v

Cómo mostrar que DATSUR Algoritmo siempre de color conectada bipartito gráficos ?

Mi intento

Creo que tengo que demostrar por el absurdo :

• La medida en que es un conectada gráfico no puede ser coloreado por un color único.
• Si hay tres colores para la gráfica devueltos por el algoritmo Dsatur, lo que significa que un vértice volvería $Dsatur(v)= 2$ (existe dos vecinos con dos colores diferentes). Que es imposible ,pero, ¿por qué ?

Eso significaría que se da a los tres tipos de colores diferentes... Pero no sé cómo demostrar por qué es imposible... me Pueden ayudar ?

Answer 1

Tenga en cuenta la siguiente. Si entre todos los vértices $v$ con un máximo de $\mathrm{DSAT}(v)$ siempre vamos a tomar un vértice que fue el primero en llegar a este valor, para el caso de conectado bipartito gráfico Dsatur algoritmo se convierte en habitual de búsqueda en anchura. Si tomamos siempre un vértice que fue el último en llegar a la máxima $\mathrm{DSAT}(v)$ luego se vuelve una búsqueda en profundidad.

Ambas búsquedas se pueden utilizar para bipartity de verificación. Y tanto busca construir algunos de árbol de expansión de la gráfica dada. Dsatur algoritmo en el caso de conectado bipartito gráfico también, implícitamente, se construye un árbol de expansión, incluso si en cada paso se elige el arbitraje de vértice con un máximo de $\mathrm{DSAT}(v)$.

Vamos a inducción de la hipótesis es la siguiente: todos los colores de los vértices de la primera parte tienen el primer color y todos los colores de los vértices de la segunda parte el segundo color. Evidentemente tiene después de la coloración sólo un vértice.

Así que por hipótesis de inducción el siguiente vértice $u$ elegido para ser de color tiene todos los colores vecinos en la parte opuesta, y todos ellos son de color en el mismo color. También, a partir de la gráfica está conectado si al menos uno de los vértices no es de color, a continuación, existe siempre un no de color de vértice adyacente a un color de vértice. Esto significa que $\mathrm{DSAT}(u) \ge 1$. Pero la inducción hipótesis implica que $\mathrm{DSAT}(u) \le 1$. Por lo $\mathrm{DSAT}(u) = 1$. Esto significa que $u$ será de color en el color apropiado el 1 o 2 de acuerdo a su parte y hemos demostrado que la hipótesis de inducción se tiene para $k + 1$ vértices si se mantiene por $k$ vértices.

Answer 2

Con referencia a su imagen, supongamos que un algoritmo elegido sin colorear los vértices al azar y se les dio la más baja de color no se utiliza por sus vecinos.

Este algoritmo puede elegir un vértice $v$ $V$ y de color azul; a continuación, seleccione un vértice $u$ $U$ no está conectado a $v$ y de color azul... de nuevo. Si el bipartito gráfico está conectado, que conducirá a usar más de dos colores.

Su tarea es mostrar que la DSATUR algoritmo nunca va a hacer eso. A tal efecto, tenga en cuenta que si el menor color se va a los vértices en $V$ o vértices en $U$ no importa. Vamos a suponer que va a $V$.

Una vez que el primer color que se le asigna, sin embargo, siempre queremos siguiente para elegir un vértice que ya tiene un color de vecino. Dado que el grafo es bipartito, vamos a asignar el "otro" color y todo estará bien.

La conexión de la gráfica garantías de que podemos seguir así hasta que todos los vértices son de color.

La observación clave, en este punto, es que como hay tanto color y sin colorear los vértices, el máximo DSAT de una incoloro vértice es mayor que 0.

Espero que este razonamiento convincente, pero no es una prueba formal todavía. Cómo convertirse en uno? Vamos a utilizar la inducción. Específicamente, vamos a "azul" $0$ "verde" y para $1$. Supongamos, sin pérdida de generalidad, que un vértice en $V$ es inicialmente de color azul.

Queremos demostrar el siguiente invariante: cada vez que el algoritmo se pregunta si se quedan sin colorear los vértices, todos los colores de los vértices en $V$ son de color azul, y todos los colores de los vértices en $U$ son de color verde.

Esta invariante es obviamente cierto después de la inicialización.

Ahora, para la inducción de paso. Si no hay más sin colorear los vértices, la hipótesis inductiva implica que todas las $V$ vértices son el azul y todos los $U$ vértices son de color verde. El éxito!

Supongamos siguiente que todavía están sin colorear los vértices. Debe haber al menos uno de los bordes de la conexión de una incoloro vértice $u$ a de colores de vértice, o de lo contrario el gráfico no estar conectado. DSAT de este vértice $u$ debe ser positivo. Por lo tanto el vértice que es escogido por DSATUR ha de color vecinos.

Supongamos $u$ $U$ (el otro caso es simétrica). A continuación, su color vecinos (puede ser más de uno) están todos en $V$ debido a que el grafo es bipartito. Por la hipótesis inductiva, todos ellos son de color azul. Por lo tanto $u$ se pone de color verde, la preservación de los invariantes. Hemos terminado.