algorithm - resueltos - arbol de expansion minima pdf

¿Cómo encontrar el máximo árbol de expansión? (7)

Aunque este hilo es demasiado viejo, tengo otro enfoque para encontrar el máximo árbol de expansión (MST) en un gráfico G = (V, E)

Podemos aplicar algún tipo del algoritmo de Prim para encontrar el MST. Para eso tengo que definir Cortar Propiedad para el borde ponderado máximo.

Cortar propiedad: Digamos que en cualquier punto tenemos un conjunto S que contiene los vértices que están en MST (por ahora supongamos que se calcula de alguna manera). Ahora considere el conjunto S / V (vértices no en MST):

Reclamo: El borde de S a S / V que tiene el peso máximo siempre estará en cada MST.

Prueba: digamos que en un punto cuando estamos agregando los vértices a nuestro conjunto S, el borde ponderado máximo de S a S / V es e = (u, v) donde u está en S y v está en S / V. Ahora considere un MST que no contiene e. Agregue el borde e al MST. Creará un ciclo en el MST original. Atraviesa el ciclo y encuentra los vértices u ''en S y v'' en S / V de modo que u ''es el último vértice en S después de lo cual ingresamos S / V y v'' es el primer vértice en S / V en el camino en pasar de u a v.

Quite el borde e ''= (u'', v '') y el gráfico resultante todavía está conectado pero el peso de e es mayor que e'' [ya que e es el borde ponderado máximo de S a S / V en este punto] así que esto da como resultado un MST que tiene una suma de pesos mayor que el MST original. Entonces esta es una contradicción. Esto significa que el borde e debe estar en cada MST.

Algoritmo para encontrar MST:

Start from S={s} //s is the start vertex while S does not contain all vertices do { for each vertex s in S add a vertex v from S/V such that weight of edge e=(s,v) is maximum } end while

Implementación: podemos implementar el uso de Max Heap / Priority Queue donde la clave es el peso máximo del borde desde un vértice en S hasta un vértice en S / V y el valor es el vértice mismo. Agregar un vértice en S es igual a Extract_Max del Heap y en cada Extract_Max cambiar la clave de los vértices adyacentes al vértice recién agregado.

Por lo tanto, se requieren m operaciones Change_Key y n operaciones de Extract_Max.

Extract_Min y Change_Key ambos pueden implementarse en O (log n). n es la cantidad de vértices.

Entonces esto toma el tiempo O (m log n). m es el número de aristas en el gráfico.

¿Funciona lo opuesto al algoritmo de Kruskal para un árbol de expansión mínimo? Quiero decir, ¿elegir el peso máximo (borde) en cada paso?

¿Alguna otra idea para encontrar el máximo árbol de expansión?

Déjame proporcionar un algoritmo de mejora:

primero construye un árbol arbitrario (usando BFS o DFS)
luego toma un borde fuera del árbol, agrégalo al árbol, formará un ciclo, suelta el borde de menor peso en el ciclo.
Continuar haciendo esta utilidad, todos los bordes de descanso se consideran

Por lo tanto, obtendremos el máximo árbol de expansión.

Este árbol satisface cualquier borde fuera del árbol, si se agrega formará un ciclo y el borde exterior <= cualquier borde pesa en el ciclo

De hecho, esta es una condición necesaria y suficiente para que un árbol de expansión sea el árbol de expansión máximo.

Pf.

Necesario: es obvio que esto es necesario, o podríamos cambiar el borde para hacer un árbol con una mayor suma de pesos de borde.

Suficiente: supongamos que el árbol T1 satisface esta condición y T2 es el árbol de expansión máximo.

Luego, para los bordes T1 ∪ T2, hay bordes T1-only, bordes T2-only, bordes T1 ∩ T2, si agregamos un borde T1-only (x1, xk) a T2, sabemos que formará un ciclo, y afirmamos, en este ciclo debe existir un borde T2-only que tenga los mismos pesos de borde que (x1, xk) . Entonces podemos intercambiar estos bordes produciendo un árbol con un borde más en común con T2 y tiene la misma suma de pesos de borde, repitiendo hacer esto obtenemos T2. entonces T1 también es un árbol de expansión máximo.

Demuestre el reclamo:

supongamos que no es cierto, en el ciclo debemos tener un borde T2 porque T1 es un árbol. Si ninguno de los bordes solo T2 tiene un valor igual al de (x1, xk), entonces cada uno de los bordes solo T2 forma un bucle con el árbol T1, entonces T1 tiene un bucle conduce a una contradicción.

Este algoritmo tomado de las notas del profesor UTD R. Chandrasekaran. Puede consultar aquí: Flujos de múltiples terminales de productos individuales

Desde this sitio web:

"Un árbol de expansión máximo es un árbol de expansión de un gráfico ponderado que tiene el peso máximo. Se puede calcular negando los pesos para cada borde y aplicando el algoritmo de Kruskal (Pemmaraju y Skiena, 2003, p 336)".

Negar el peso del gráfico original y calcular el árbol de expansión mínimo en el gráfico negado dará la respuesta correcta. Aquí está el porqué: para el mismo árbol de expansión en ambos gráficos, la suma ponderada de un gráfico es la negación del otro. Por lo tanto, el árbol de expansión mínimo del gráfico negado debe dar el árbol de expansión máximo del árbol original.

Si invierte el peso en cada borde y lo minimiza, ¿obtiene el máximo árbol de expansión? Si eso funciona, puedes usar el mismo algoritmo. Los pesos cero serán un problema, por supuesto.

Solo revertir el orden de clasificación y elegir un borde grueso en un corte de vértice no garantiza un bosque de expansión máximo (el algoritmo de Kruskal genera bosque, no árbol). En caso de que todos los bordes tengan pesos negativos, el Max Spanning Forest obtenido del reverso de kruskal, seguiría siendo un camino de peso negativo. Sin embargo, la respuesta ideal es un bosque de vértices desconectados. es decir, un bosque de | V | árboles singleton, o | V | componentes que tienen un peso total de 0 (no menos negativo).

sí lo hace,

fuente: https://web.archive.org/web/20141114045919/http://www.stats.ox.ac.uk/~konis/Rcourse/exercise1.pdf

Un método para calcular el árbol de expansión de peso máximo de una red G - debido a Kruskal - se puede resumir de la siguiente manera.
Clasifique los bordes de G en orden decreciente por peso. Sea T el conjunto de aristas que comprende el árbol de expansión de peso máximo. Establecer T = ∅.
Agregue el primer borde a T.
Agregue el borde siguiente a T si y solo si no forma un ciclo en T. Si no hay bordes restantes, salga e informe G para que se desconecte.
Si T tiene n-1 bordes (donde n es el número de vértices en G), detén y saca T. De lo contrario, vaya al paso 3.