¿Funciona lo contrario del algoritmo de Kruskal para un árbol de expansión mínimo? Quiero decir, ¿elegir el peso máximo (borde) en cada paso?¿Cómo encontrar el árbol de expansión máximo?
¿Alguna otra idea para encontrar el máximo árbol de expansión?
sí lo hace,
fuente: https://web.archive.org/web/20141114045919/http://www.stats.ox.ac.uk/~konis/Rcourse/exercise1.pdf
Un método para el cálculo de la máxima árbol de expansión peso de una red G - debido a Kruskal - pueden resumirse como sigue.
- Ordene los bordes de G en orden decreciente por peso. Sea T el conjunto de bordes que comprende el árbol de expansión de peso máximo . Establezca T = ∅.
- Añadir el primer borde de T.
- Añadir el siguiente flanco de T si y sólo si no se forma un ciclo en T. Si no quedan bordes de salida y informe G para ser desconectado.
- Si T tiene n-1 bordes (donde n es el número de vértices en G) detener y salida T. De lo contrario, vaya al paso 3.
Si invierte el peso en cada borde y lo minimiza, ¿obtiene el árbol de expansión máximo? Si eso funciona, puedes usar el mismo algoritmo. Los pesos cero serán un problema, por supuesto.
+1 Porque esto se aplica básicamente a todos los algoritmos. – hugomg
¿cómo será un problema el peso cero? –
Pesos cero no será un problema, pero si está buscando el árbol de peso máximo en general (en lugar del árbol de * peso máximo *, que está obligado a visitar todos los vértices), los pesos * negativos * serán un problema : este problema es NP-difícil. –
De this sitio web:
"Un árbol recubridor mínimo es un árbol de expansión de una gráfica ponderada que tiene el peso máximo puede calcularse mediante la negación de los pesos para cada borde y aplicando el algoritmo de Kruskal (Pemmaraju y Skiena. , 2003, p 336). "
entonces, mi suposición es cierta, creo :) –
¡Negando los pesos! Tengo el libro de Skienna, pero no saqué esa pepita de la memoria. (El libro está en casa, así que no pude recomendarlo.) Gracias por recordarme. Seré un buen incentivo para seguir leyendo con más cuidado. – duffymo
Si lo único importante es qué bordes están en el árbol de expansión mínimo, solo el orden de los bordes es relevante para el algoritmo de Kruskal. Y el orden es el mismo cuando niega los pesos del borde como cuando invierte el orden de los pesos originales. – Palec
negar el peso del gráfico original y calcular el árbol de expansión mínimo en el gráfico negada dará la respuesta correcta. Aquí está el por qué: 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.
pesar de que este hilo es demasiado viejo, no tengo otro enfoque para encontrar el máximo de árbol de expansión (MST) en un grafo G = (V, E)
Podemos aplicar el algoritmo algún tipo de Prim para encontrar el MST. Para eso tengo que definir Cortar Propiedad para el borde ponderado máximo.
Propiedad de corte: 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):
Reclamación: 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 máximo borde ponderado 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.
Eliminar el borde e '= (u', v ') y el gráfico resultante sigue 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] por lo 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 usando Max Heap/cola de prioridad donde la clave es el peso máximo del borde de un vértice en S a 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 necesitan m operaciones Change_Key y n operaciones de Extract_Max.
Extract_Min y Change_Key ambos se pueden implementar en O (log n). n es la cantidad de vértices.
Esto toma el tiempo O (m log n). m es el número de aristas en el gráfico.
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).
Permítanme ofrecer un algoritmo de mejora:
Por lo tanto, vamos a llegar al árbol de máxima expansión.
Este árbol satisface cualquier borde exterior del árbol, si se añade formará un ciclo y el borde exterior < = cualquier pesos de las aristas en el ciclo
De hecho, esta es una condición necesaria y suficiente para una spanning tree para ser máximo spanning tree.
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 cumple esta condición y T2 es el árbol de expansión máximo.
Luego, para los bordes T1 ∪ T2, hay bordes T1 solamente, bordes T2 solo, bordes T1 ∩ T2, si agregamos un borde solo T1 (x1, xk) a T2, sabemos que lo hará forma un ciclo, y reclamamos, 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.
probar la afirmación:
suponer que no es cierto, en el ciclo debemos tener un T2-T1 única ventaja ya que 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í: Single Commodity Multi-terminal Flows
¿Funciona también para Prim? – banarun
@banarun Muy tarde para la fiesta, pero sí, lo hace. – CJxD