G es un gráfico en n vértices y 2n – 2 aristas. Las aristas de G se pueden dividir en dos árboles de expansión de aristas disjuntas. ¿Cuál de los siguientes NO es cierto para G?
(A) Para cada subconjunto de k vértices, el subgrafo inducido tiene como máximo 2k-2 aristas
(B) El corte mínimo en G tiene al menos dos aristas
(C) Hay dos caminos separados por aristas entre cada par de vértices
(D ) Hay dos caminos disjuntos de vértice entre cada par de vértices
Respuesta: (D)
Explicación:El contador para la opción D es el siguiente. Tome dos copias de K4 (gráfico completo en 4 vértices), G1 y G2. Sean V(G1)={1,2,3,4} y V(G2)={5,6,7,8}. Construya un nuevo gráfico G3 usando estos dos gráficos G1 y G2 fusionándolos en un vértice, digamos fusionar (4,5). El gráfico resultante tiene dos aristas conectadas y de grado mínimo 2, pero existe un vértice cortado, el vértice fusionado.
Gracias a Renjith P por proporcionar la explicación anterior.
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