Estoy interesado en la auto-reducibilidad del problema Graph 3-Coloralibity.
Definición del problema del gráfico 3-Coloralibity.
Dado un gráfico no dirigido, ¿existe alguna forma de colorear los nodos de rojo, verde y azul para que ningún nodo adyacente tenga el mismo color?
Definición de auto-reducibilidad.
Un lenguaje es auto-reducible si existe una máquina Turing de oráculo TM tal que y para cualquier entrada de longitud , consulta al oráculo para palabras de longitud como máximo .
Me gustaría mostrar de una manera muy estricta y formal que la capacidad de coloración del Gráfico 3 es auto reducible.
La prueba de auto-reducibilidad de SAT puede usarse como ejemplo ( auto-reducibilidad de SAT ).
En mi opinión, la idea general de la prueba de auto-reducibilidad de la coloración del gráfico 3 es diferente de la prueba de auto-reducibilidad SAT en algunos aspectos.
- SAT tiene dos opciones para cada literal (verdadero o falso) y la capacidad de coloración del gráfico 3 tiene tres opciones (a saber, rojo, verde, azul).
- Las opciones de SAT literal son independientes entre sí y las opciones de colores de la coloración del Gráfico 3 son estrictamente dependientes, cualquier nodo adyacente debe tener un color diferente, esta propiedad podría ayudar a hacer menos iteración entre todos los colores.
La idea general de la prueba .
Denotemos por el color del vértice , que puede tomar uno de los siguientes valores (rojo, verde, azul). Defina el gráfico partir de un gráfico dado coloreando el vértice arbitrario , asigne a' rojo 'y coloque el gráfico con el vértice coloreado en la entrada del oráculo. Si Oracle responde 1, lo que significa que el gráfico modificado sigue siendo de 3 colores, guarde las asignaciones actuales y comience una nueva iteración, con el vértice diferente elegido arbitrariamente, vértice de colorsegún los colores de los vértices adyacentes. Si Oracle responde 0, lo que significa que la asignación anterior ha roto la capacidad de coloración 3, elija un color diferente del conjunto de tres colores, pero aún de acuerdo con los colores de los vértices adyacentes.
La prueba anterior no es matemáticamente robusta, la pregunta es cómo mejorarla y hacerla más formal y matemática estricta. Parece que necesito distinguir más cuidadosamente los casos en que el nuevo vértice no tiene bordes con vértices ya coloreados y cuando el nuevo vértice es adyacente a vértices ya coloreados.
Además, me gustaría demostrar que la capacidad de coloración del gráfico 3 es auto-reducible hacia abajo.
Definición de lenguaje auto-reducible hacia abajo.
dice que el lenguaje es auto-reducible hacia abajo si es posible determinar en tiempo polinómico si usando los resultados de las consultas más cortas.
La idea parece ser simple e intuitiva: comience coloreando un vértice arbitrario, y en cada iteración agregue un vértice coloreado más y verifique con un oráculo si el gráfico aún tiene 3 colores, si no invierte el color anterior y verifique otro color.
Pero cómo escribir la prueba de forma estricta y más importante cómo encontrar una codificación adecuada de un gráfico.
En resumen, me gustaría mostrar que la capacidad de coloración del Gráfico 3 es auto-reducible y auto-reducible hacia abajo de manera estricta y formal.
Apreciaré compartir tus pensamientos con nosotros.
Actualizar:
auto-reducibilidad hacia abajo
La auto-reducibilidad hacia abajo se aplica al problema de decisión y su oráculo responde al mismo problema de decisión con una entrada más corta, al final del proceso de auto-reducción hacia abajo deberíamos tener las asignaciones de color correctas.
Cada gráfico de 3 colores con más de tres vértices tiene dos vértices con el mismo color. Aparentemente, solo hay tres colores y más de tres vértices, por lo que algunos vértices no adyacentes pueden tener el mismo color. Si fusionamos e con el mismo color que el resultado, todavía tenemos un gráfico de 3 colores, solo porque, si el gráfico es de 3 colores, entonces existe una asignación correcta de todos los vértices adyacentes a e acuerdo con el mismo color de , así que al fusionarno necesitamos cambiar ningún color de ningún vértice, solo necesitamos agregar más bordes entre los vértices ya coloreados correctamente (sé que no es la mejor explicación, agradecería si alguien pudiera explicarlo mejor). En cada iteración tomamos dos vértices no adyacentes del gráfico , fusionamos e y obtenemos el gráfico que es nuestra entrada más corta al oráculo. Oracle responde si es de 3 colores o no. Ahora, el problema es que antes de configurar en la entrada de Oracle debería colorear el vértice fusionado y probar la capacidad de coloración de , si no es de 3 colores, cambie el color, pero cómo implementarlo correctamente, necesito la codificación correcta.
auto-reducibilidad
Primero, debemos verificar si un gráfico dado es de 3 colores, así que configúrelo en la entrada de Oracle, y Oracle responderá si es de 3 colores, si es así, comience el proceso. Cualquiera de los dos vértices no adyacentes puede tener el mismo color en un gráfico de 3 colores. El proceso de auto-reducibilidad que debemos ejecutar en iteraciones, creo que podemos comenzar desde el pequeño subgrafo de un gráfico dado y en cada iteración agregar uno más vértices de a . En paralelo, debemos mantener la asignación de vértices ya coloreados. Desafortunadamente, todavía no entiendo la idea por completo. Agradecería por ayuda y sugerencias.
Respuestas:
Como Vor menciona en su comentario, su reducción no funciona, ya que la capacidad de 3 colores no acepta asignaciones parciales de colores. El problema es aún más profundo, ya que establecer el color de un solo vértice no hace ningún progreso para determinar si el gráfico es de 3 colores: de hecho, el gráfico es de 3 colores si hay un color 3 en el que el vértice es color asignado , para cualquier que elija.v c v,c
Aquí hay una pista sobre cómo resolver su ejercicio, segunda parte. En cualquier coloración 3 de un gráfico en más de tres vértices, hay dos vértices obteniendo el mismo color (¿por qué?). Si fusionamos e , el gráfico resultante sigue siendo de 3 colores (¿por qué?). Intente utilizar esta idea para construir un algoritmo de reducción automática descendente para la capacidad de 3 coloraciones.G x,y x y
Editar: Y aquí hay una pista sobre cómo resolver el ejercicio, primera parte. Considere dos vértices no conectados . Si hay un color en el que obtienen el mismo color, entonces es de 3 colores (¿por qué?), Y se puede extraer un color de de un color de (¿cómo?). ¿Cuándo se detendrá este proceso?x,y Gxy G Gxy
fuente
Tal vez así. Podemos agregar dos vértices conectados l1 y l2. Primero, los conectamos con cualquier vértice v *. Tenga en cuenta que este comportamiento significa que, por fin, simplemente bloqueamos algunos vértices de color, incluido v *.
Luego ejecutamos la versión de decisión de la 3-colorabilidad, si el algoritmo de decisión acepta, entonces agregamos este vértice en s_1. repetimos este paso con cada vértice (conecte l1 y l2 con otro vértice), encontraremos que, por fin, se encuentran todos los vértices con el mismo color (denotado por rojo), y estos vértices con color rojo denotan por s_1.
Si hay algún problema, indíquelo.
A continuación, al igual que lo que hacemos arriba, agregue otros dos vértices conectados (l3 l4). Primero, los conectamos con cualquier vértice, excepto los de s_1, ejecute el algoritmo de decisión. Luego otro.....
fuente