Si un gráfico ponderado tiene dos árboles de expansión mínima diferentes y , entonces es cierto que para cualquier borde enT 1 = ( V 1 , E 1 ) T 2 = ( V 2 , E 2 ) e E 1 E 1 e e E 2 e , el número de bordes en con el mismo peso que (incluyendo ) es igual al número de aristas en con el mismo peso que ? Si la afirmación es cierta, ¿cómo podemos probarla?
graph-theory
spanning-trees
weighted-graphs
Aden Dong
fuente
fuente
Respuestas:
Reclamación: Sí, esa afirmación es cierta.
Boceto de prueba: deje que sean dos árboles de expansión mínima con multisets de peso de borde . Suponga y denote su diferencia simétrica con .T1,T2 W1,W2 W1≠W2 W = W 1 Δ W 2W=W1ΔW2
Elija el borde cone∈T1ΔT2 w(e)=minW T 2e e∈T1ΔT2 minW puede ser en ambos árboles, de lo contrario . Wlog deja y asume que tiene más bordes de peso que .minW∉W e∈T1 T1 minW T2
Ahora considere todos los bordes en que también están en el corte que es inducido por en . Si hay un borde que tiene el mismo peso que , actualice conT2 CT1(e) e T1 e′ e T1 e′ e T 1 W e T 2 ∩ C T 1 ( e ) T 1 w ( e ) lugar de ; tenga en cuenta que el nuevo árbol sigue siendo un árbol de expansión mínima con el mismo conjunto múltiple de peso de borde que . Repetimos este argumento, reduciendo por dos elementos y eliminando así un borde del conjunto de candidatos para en cada paso. Por lo tanto, llegamos después de muchos pasos a una configuración donde todos los bordes ene T1 W e T2∩CT1(e) (donde es la versión actualizada) tienen pesos distintos de .T1 w(e)
Ahora siempre podemos elegir modo que podamos intercambiar y ¹, es decir, podemos crear un nuevo árbol de expansióne′∈CT1(e)∩T2 e e′
que tiene un peso menor queT1 T 2 T 1 , T 2 W 1 = W 2 y ; Esto contradice la elección de como árboles de expansión mínima. Por lo tanto, .T2 T1,T2 W1=W2
fuente
Aquí hay un argumento un poco más simple que también funciona para otras matroides. (Vi esta pregunta de otra ).
Suponga que tiene aristas. Sin pérdida de generalidad, suponga que la función de peso toma valores en , por lo que tenemos una partición de en conjuntos para . Podemos hacer inducción sobre el número de no vacío y el número de vértices en ; para y cualquieram w [ m ] E E i : = w - 1 ( i ) i ∈ [ m ] j E i n G j = 1 nG m w [m] E Ei:=w−1(i) i∈[m] j Ei n G j=1 n , el enunciado es obvio.
Un hecho estándar sobre matroides es que por cada MST hay una extensión lineal de la ordenación inducida por de modo que el algoritmo codicioso produce .w TT w T
Para cerrar la inducción, tome como el número más grande para que no esté vacío. Establezca . Observe que cualquier extensión lineal de coloca cada borde en antes que cualquier borde en . Según el hecho, cualquier MST consiste en un bosque que abarca del subgráfico inducido por y algunos bordes de . Según la hipótesis inductiva, cada componente conectado de tiene el mismo número de aristas de cada paraE t E ′ = E 1 ∪ ⋯ ∪ E t - 1 w E ′ E t F E ′ E t F E i i < t F E t F Ft Et E′=E1∪⋯∪Et−1 w E′ Et F E′ Et F Ei i<t . Dado que todas las opciones deF tienen el mismo tamaño, el número de aristas desde requerido para completarEt F a un árbol de expansión es independiente de la elección de y hemos terminado.F
fuente