J'essaie de trouver une méthode efficace de détection si un graphique donné G a deux arbres minimaux minimaux différents. J'essaie également de trouver une méthode pour vérifier si elle dispose de 3 arbres minimaux minimaux différents. La solution naïve que j'ai à propos de courir l'algorithme de Kruskal une fois et qu'il trouve le poids total de l'arbre minimal de Spanning. Plus tard, retirez à nouveau un bord du graphique et exécutant à nouveau l'algorithme de Kruskal et vérifiant si le poids de la nouvelle arborescence est le poids de l'arbre minimal d'origine et minimal, et donc pour chaque bord du graphique. Le temps d'exécution est O (| v || e | journal | v |) qui n'est pas bon du tout, et je pense qu'il y a une meilleure façon de le faire.
Toute suggestion serait utile, merci d'avance
3 Réponses :
Supposons que vous ayez un MST Ce que cela implique est s'il y a plus d'un MST, nous pouvons toujours changer un seul bord d'un MST et obtenir un autre MST. Donc, si vous vérifiez pour chaque bord, essayez de remplacer le bord avec ceux avec le même poids et si vous obtenez un autre ST, c'est une MST, vous obtiendrez un algorithme plus rapide. t0 d'un graphique. Maintenant, si nous pouvons obtenir un autre MST t1 , il doit avoir au moins un bord E différent du MST d'origine. Dresser E à partir de t1 , le graphique est maintenant séparé en deux composants. Cependant, dans t0 , ces deux composants doivent être connectés, il y aura donc un autre bord sur ces deux composants qui ont exactement le même poids que E (ou nous pourrions remplacer le un avec plus de poids avec l'autre et obtenez un petit ST). Cela signifie substituer cet autre bord avec E vous donnera un autre MST.
Vous pouvez modifier l'algorithme de Kruskal pour le faire.
Tout d'abord, trier les bords en poids. Ensuite, pour chaque poids dans l'ordre croissant, filtrez tous les bords non pertinents. Les bords pertinents forment un graphique sur les composants connectés de la forêt minimale - jusqu'à présent. Vous pouvez compter le nombre d'arbres étendus dans ce graphique. Prenez le produit sur tous les poids et vous avez compté le nombre total d'arbres minimum étendus dans le graphique.
Vous récupérez la même heure d'exécution que l'algorithme de Kruskal si vous ne vous souciez que de l'arbre, des deux arbres et des cas de trois ou plus d'arbres. Je pense que vous avez fini par faire un calcul déterminant ou quelque chose pour énumérer des arbres étendus en général, vous avez probablement la liquidation avec un o (mm (n)) en général en général.
"Je pense que tu as fini de faire un calcul déterminant" Yep .
"Prenez le produit sur tous les poids et vous avez compté le nombre total de gradins minimaux dans le graphique." Je ne vois pas quelles sont les valeurs des poids des bords avec le nombre de MST. Si j'ajoute une constante C à tous les poids des bords, je ne change pas le nombre de MST puisque je ne change pas quels jeux de bords forment un MST, mais le produit sur les poids change. Je ne comprends pas non plus ce que vous entendez par "bords non pertinents".
Merci pour la réponse, mais qu'entendez-vous par des bords non pertinents?
@Itamar Edges E pour lesquels il existe un chemin d'un point d'extrémité de E à l'autre sur les bords strictement plus légers que e. Cela peut être testé en faisant des appels supplémentaires () supplémentaires avant que l'un des bords d'une classe de poids ait leurs points de terminaison unis.
@Davideisenstat, vérifiant si un Edge E est pertinent fait tout le temps d'exécution beaucoup plus cher, n'est-ce pas?
@Itamar uniquement par un facteur constant. Numérisez les bords dans des classes de poids. Pour chaque poids w, traiter les bords de poids
@ G.bach: "Prenez le produit sur tous les poids" est légèrement déroutant ... ce que cela signifie réellement, c'est que, pour chaque Poids de bord distinct (c'est-à-dire pour chaque groupe de bords pertinents égaux-poids) , nous pouvons calculer le nombre d'arbres étendus dans le "graphe composant"; Et nous devrions ensuite multiplier tous ces nombres de MSTS (un par poids distinct) ensemble pour obtenir le nombre de MST sur les sommets d'origine.
Supposons que g est un graphique avec n sommets et des bords M; que le poids de tout bord e est w (e); et que p est un arbre de survol minimal sur G, le coût de pesée (W, P).
Soit δ = différence minimale positive entre deux poids de deux niveaux. (Si tous les poids des bords sont identiques, alors Δ est indéterminé; mais dans ce cas, tout ST est un MST, donc cela n'a pas d'importance.) Prenez ε telle que δ> n · ε> 0.
Créer une nouvelle fonction de poids u () avec U (E) = w (E) + ε quand e est en p, sinon u (e) = w (E). Compute Q, un MST de G sous U. Si le coût (U, Q) La méthode ci-dessus détermine s'il ya au moins deux MST distincts, dans le temps O (H (N, M)) si O (H (N, M))) limite le temps nécessaire pour trouver un MST de G.
Je ne sais pas si une méthode similaire peut traiter si trois (ou plus) MST distincts existent; Des extensions simples de celui-ci tombent à des contre-extamples simples.
Ne inter-poster questions. Si vous croyez qu'une question est hors tension, vous pouvez le supprimer s'il n'a aucune réponse et que vous ne le demandez pas sur le site approprié, ou vous pouvez signaler qu'il lui demandant d'être migré. Mais cette question est probablement bien ici.