Sea G cualquier gráfico de conexión, ponderado, no dirigido:
- I. G tiene un árbol de expansión mínimo único si no hay dos aristas de G que tengan el mismo peso.
- II. G tiene un árbol de expansión mínimo único si, para cada corte G, hay un borde de peso mínimo único que cruza el corte.
¿Cuál de las dos afirmaciones anteriores es/son VERDADERAS?
(A) Ni I ni II
(B) Solo I
(C) Solo II
(D) Tanto I como II
Respuesta: (D)
Explicación: La afirmación (I) siempre es correcta, ya que solo necesita (n-1) aristas con Gráfico de n Nodes para el árbol de expansión mínimo. Puede probar que no habrá ninguna otra opción de bordes que no sean los primeros (n-1) bordes de peso más ligero utilizando el algoritmo Krushkal .
Tenga en cuenta que el recíproco de la declaración (I) también es cierto.
La afirmación (II) también es correcta. Supongamos que MST no es único, es decir, existen T1 y T2 donde ambos son MST y no son idénticos. Supongamos que e1 ∈ T1 pero e1 ∉ T2, si eliminamos e1 de T1, entonces tendremos dos árboles con conjuntos de vértices V1 y V2. Por el problema 1 de HW #2, sabemos que e1 es una ventaja de costo mínimo en el corte entre V1 y V2. Ahora considere T2, nuevamente el problema 1 de HW #2, sabemos que T2 contiene un borde e2 que es un borde de costo mínimo del corte entre V1 y V2. Sin embargo, dado que e2 ≠ e1 debemos tener: c(e1) = c(e2) lo cual contradice la suposición de que para cada corte del gráfico, el borde con el menor costo en ese corte es único.
Tenga en cuenta que el recíproco del enunciado (II) puede ser cierto.
Entonces, la opción (D) es correcta.
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