¿Cuál es el número cromático de un gráfico conexo simple de n vértices que no contiene ningún ciclo de longitud impar? Suponga que n >= 2.
(A) 2
(B) 3
(C) n-1
(D) n
Respuesta: (A)
Explicación: El número cromático de un gráfico es el menor número de colores necesarios para colorear los vértices de tal que no hay dos vértices adyacentes que compartan el mismo color. Este tipo de preguntas se pueden resolver por sustitución con diferentes valores de n.
1) n = 2 Este gráfico simple se puede colorear con 2 colores.
2) norte = 3
Aquí, en este gráfico, supongamos que el vértice A está coloreado con C1 y los vértices B, C se pueden colorear con el color C2 => el número cromático es 2 De la misma manera, puede verificar con otros valores, el número cromático es igual a 2
Esta solución aportada por Anil Saikrishna Devarasetty
//Un gráfico simple sin ciclos impares es un gráfico bipartito y un gráfico bipartito se puede colorear usando 2 colores (ver esto )
Cuestionario de esta pregunta
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA