Dado un gráfico G (V, E) es bipartito, ¿cuál es el número cromático de G?
(A) 2
(B) 3
(C) ∞
(D) No se puede decidir
Respuesta: (A)
Explicación: Dado que el gráfico G es bipartito, el conjunto de vértices V se puede dividir en dos conjuntos disjuntos.
Esto muestra que podemos colorear el gráfico con 2 colores de modo que dos vértices adyacentes no tengan el mismo color.
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