Grafica el número cromático del vértice en una unión de 2 subgrafos

GRAMO 1 es gráfico en el conjunto de vértices { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 } , GRAMO 1 número cromático de vértice es 5.

GRAMO 2 es gráfico en el conjunto de vértices { 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 17 , 18 , 19 , 20 } , GRAMO 2 número cromático de vértice es 7.

Sabemos GRAMO 1 y GRAMO 2 tener un borde entre el vértice 7 y el vértice 8. (Ya usamos 2 colores diferentes en ambos).

GRAMO es gráfico en el conjunto de vértices { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , dieciséis , 17 , 18 , 19 , 20 } , y su conjunto de aristas es la unión del conjunto de aristas de GRAMO 1 con los bordes establecidos de GRAMO 2 .

El número cromático de vértice de GRAMO es: 5 / 7 / 12 / no podemos saberlo sin más información

Demuestra la respuesta.

Creo que lo tengo, ¿alguien puede aprobarlo?

Después de la unión a GRAMO , copiamos los colores de GRAMO 2 a 7,8,9,10,11,12,13,14,15,16,17,18,19,20, obviamente, GRAMO El número cromático del vértice es 7 y no puede ser menor.

Pasamos por los vértices 1,2,3,4,5,6,7,8.

Buscamos un vértice que no se conecta a un vértice diferente. (Debe haber uno, porque si solo faltara un borde en GRAMO 1 , nuestro número cromático de GRAMO 1 eran 7, pero son 5).

Una vez que encontramos un borde faltante, coloreamos ambos vértices del mismo color.

Pasamos por los vértices 1-6, y coloreamos cada vértice que no tiene color, con los colores de GRAMO 2 que no usamos en GRAMO 1 (Debe haber 4-5 de ellos).

Oh, acabo de notar tu otra pregunta Teoría de grafos: pregunta para colorear grafos ; Mismo problema pero diferente intento. Bueno, de todos modos, espero que mi respuesta ayude.
No existe tal palabra como vértice . La palabra vértices es el plural de vértice .

Respuestas (1)

Entonces, si entiendo correctamente, su prueba es:

  • Debemos usar al menos 7 colores para colorear GRAMO , ya que tiene el subgrafo GRAMO 2 , que tiene número cromático 7 .
  • elegimos algunos 7 -coloración de GRAMO 2 .

  • Usando esos colores, coloreamos dos vértices no adyacentes en GRAMO 1 el mismo color. (Debe haber un no-borde en GRAMO 1 para GRAMO 1 ser 5 -de colores.)

    • Si los dos vértices no adyacentes en GRAMO 1 no incluir 7 o 8 , entonces hemos coloreado 4 vértices en GRAMO 1 con 3 colores, dejando 4 vértices para colorear 4 colores restantes.
    • Si los dos vértices no adyacentes en GRAMO 1 incluir 7 o 8 , entonces hemos coloreado 3 vértices en GRAMO 1 con 2 colores, dejando 5 vértices para colorear 5 colores restantes.

    De cualquier manera, podemos colorear fácilmente los vértices restantes en GRAMO 1 .

  • Así tenemos un 7 -colorear, y GRAMO tiene número cromático 7 .

Es largo, pero funciona.

Una forma más corta es encontrar colorantes de GRAMO 1 y GRAMO 2 , luego modifique uno de ellos para que los vértices 7 y 8 recibe el mismo color en ambos.

Grafica el número cromático del vértice en una unión de 2 subgrafos
RespuestasAquíPolítica de privacidad1y, 0v