Comment trouver un arbre maximum étendu?

StackOverflow https://stackoverflow.com/questions/4992664

Question

Est-ce que le contraire de l'algorithme de Kruskal pour le travail minimum de l'arborescence est-il?Je veux dire, choisir le poids maximum (bord) chaque étape?

Toute autre idée pour trouver un arbre de couverture maximum?

Était-ce utile?

La solution

Oui, ça fait.

Une méthode pour calculer le poids maximum de la pondération d'un réseau G - En raison de Kruskal - peut être résumée comme suit.

  1. Trier les bords de G dans l'ordre décroissant en poids.Soit t l'ensemble d'arêtes comprenant l'arbre de poids maximal.Ensemble t= ∅.
  2. Ajoutez le premier bord à t.
  3. ajoutez le bord suivant à T si et seulement si cela ne forme pas de cycle dans T. Si Il n'y a pas de sortie des bords restants et signalez G pour être déconnecté.
  4. si t a des bords N-1 (où n est le nombre de sommets dans g) stop et sortie t.Sinon aller à l'étape 3.

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

Autres conseils

de Ce Site Web:

"Un arbre maximum étendu est un arbre étendu d'un graphique pondéré ayant un poids maximal. Il peut être calculé en niant les poids de chaque bord et en appliquant l'algorithme de Kruskal (Pemmaju et Skiena, 2003, p. 336)."

Si vous inverser le poids sur chaque bord et minimisez-vous, obtenez-vous l'arbre maximum de la couverture?Si cela fonctionne, vous pouvez utiliser le même algorithme.Les poids zéro seront un problème, bien sûr.

Bien que ce fil soit trop vieux, j'ai une autre approche pour trouver l'arborescence maximum étendu (MST) dans un graphique g= (v, e)

Nous pouvons appliquer un algorithme de tri de trier pour trouver le MST. Pour cela, je dois définir une propriété coupée pour le bord pondéré maximum.

Couper la propriété: Dites-le à tout moment, nous avons un ensemble S qui contient les sommets qui sont en MST (pour le moment supposer que cela est calculé en quelque sorte). Considérons maintenant l'ensemble S / V (sommets non en MST):

Réclamation: le bord de S à S / V qui a le poids maximal sera toujours dans chaque MST.

Proof: Disons qu'à un point où nous ajoutons les sommets à notre jeu S, le bord pondéré maximum de S à S / V est E= (U, V) où vous êtes à S et V est en S / V. Envisagez maintenant un MST qui ne contient pas e. Ajoutez le bord e au MST. Il créera un cycle dans le MST original. Traverser le cycle et trouver les sommets U 'dans S et V' dans S / V telle que U 'est le dernier sommet de s après lequel nous entrons S / V et V' est le premier sommet de S / V sur le chemin de la route cycle de u à v.

Retirez le bord E '= (U', V ') et le graphique résultant est toujours connecté, mais le poids de E est supérieur à E' [comme E est le bord pondéré maximum de S à S / V à ce stade. ] Il en résulte donc un MST qui a une somme de poids supérieure à celle du MST original. C'est donc une contradiction. Cela signifie que Edge E doit être dans chaque MST.

algorithme pour trouver le 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

Mise en œuvre: Nous pouvons implémenter à l'aide de la file d'attente maximale des tas / prioritaires où la clé est le poids maximal du bord d'un sommet à S à un sommet de S / V et la valeur est le sommet lui-même. L'ajout d'un sommet en S est égal à extraire_max du tas et à chaque extraction_max modifier la clé des sommets adjacents au sommet juste ajouté.

donc il prend des opérations M Change_Key et N Opérations Extract_max.

Extract_min et Change_Key Les deux peuvent être implémentés dans O (log n). n est le nombre de sommets.

Donc, cela prend du temps O (m journal n). m est le nombre d'arêtes dans le graphique.

Nettère le poids du graphique original et calculer le minimum d'arborescence sur le graphique annulé donnera la bonne réponse.Voici pourquoi: Pour le même arbre étendu dans les deux graphiques, la somme pondérée d'un graphique est la négation de l'autre.Donc, l'arbre minimum couvert du graphique annulé devrait donner le maximum d'arborescence de l'original.

Inverser uniquement l'ordre de tri et le choix d'un bord lourd dans une coupe de vertex ne garantit pas une forêt tangée maximale (l'algorithme de Kruskal génère des forêts, pas une arborescence).Au cas où toutes les bords ont des poids négatifs, la forêt max sur l'inverse de Kruskal, serait toujours un chemin de poids négatif.Cependant, la réponse idéale est une forêt de sommets déconnectés.c'est-à-dire une forêt de | v |arbres singleton, ou | v |Composants ayant un poids total de 0 (pas le moins négatif).

Permettez-moi de fournir un algorithme d'amélioration:

  • Construisez d'abord un arbre arbitraire (en utilisant BFS ou DFS)
  • Choisissez ensuite un bord à l'extérieur de l'arbre, ajoutez à l'arborescence, il formera un cycle, laissez tomber le plus petit bord de poids du cycle.
  • Continuez à faire cet util sur tous les bords de repos sont considérés comme

    Ainsi, nous aurons l'arbre maximum étendu.

    Cet arborescence satisfait tout bord en dehors de l'arborescence, si ajouté formera un cycle et le bord extérieur <= n'importe quel poids de bord dans le cycle

    En fait, il s'agit d'une condition nécessaire et suffisante pour une arborescence étendue d'un arbre de couverture maximum.

    pf.

    Nécessaire: il est évident que cela est nécessaire, ou nous pourrions échanger le bord pour faire un arbre avec une somme plus grande de poids de bord.

    suffisant: Supposons que l'arborescence T1 satisfait à cette condition et T2 est l'arbre maximum étendu.

    Puis pour les bords T1 ∪ T2, il y a des bords T1 uniquement, des bords T2 uniquement, des bords T1 ∩ T2, si nous ajoutons un bord T1 uniquement (X1, XK) à T2, nous savons que cela se formera Un cycle, et nous revendiquons, dans ce cycle, il doit exister un bord de T2 uniquement qui a les mêmes poids de bord que (x1, xk) . Ensuite, nous pouvons échanger ces bords produira un arbre avec un tranchant de plus en commun avec T2 et possède la même somme de poids de bord, répétant cela, nous obtiendrons T2. Donc, T1 est également un arbre maximum étendu.

    prouver la réclamation:

    Supposons que ce ne soit pas vrai, dans le cycle, nous devons avoir un bord de T2, car T1 est un arbre. Si aucun des bords T2 uniquement n'a une valeur égale à celle de (x1, xk), chacun des bords T2 uniquement fait une boucle avec l'arbre T1, alors T1 a une boucle conduit à une contradiction.

    Entrez la description de l'image ici

    Cet algorithme tiré des notes de l'UTD Professor R. Chandrasekaran. Vous pouvez vous référer ici: Flux multi-terminaux à base unique

Changez le poids dans une commande réservée (vous pouvez y parvenir en prenant une valeur de poids négative et en ajoutant un grand nombre, dont le but est de garantir non négatif) puis d'exécuter votre algorithme à base de Geedy sur l'arbre minimal.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top