Plus "petit" sous-graphe connexe — Les-mathematiques.net The most powerful custom community solution in the world

Plus "petit" sous-graphe connexe

Bonjour à tous. J'espère que vous arrivez tous à garder l'esprit sain pendant ce confinement.
Voici le problème que je rencontre.

J'ai un graphe $G$ connexe non-orienté mais avec une fonction de poids associée (j'ai oublié la terminologie mathématique usuelle). J'entends par que ça me coûte $w(i,j)$ de passer du sommet $i$ au sommet $j$, ou du sommet $j$ au sommet $i$. On va supposer qu'il n'y a pas de boucle.

Ma question est la suivante : existe-t-il un algorithme permettant de trouver le "plus" petit sous-graphe connexe. J'entends par là trouver un sous-graphe $S$ tel que pour toute paire de sommets $(v_1, v_2)$ de $G$, il existe un chemin de $S$ reliant $v_1$ à $v_2$. Et ce graphe $S$ est optimal au sens du critère : $$

\min_ {S \ \mathrm{graphe} } \sum_{(u,v) \in S} w(u,v) \\
S \ \mathrm{graphe}

$$ En fait parmi les algos sur graphes que je connais :
- Floyd-Warshall et Bellman,
- Max Flot, Min Cut,
aucun ne permet de traiter ce problème.
Merci d'avance.

Réponses

  • Ton graphes est non-orienté, et il n'y a pas de boucle.
    Moi aussi j'ai oublié toute la théorie, mais je pense qu'avec ces 2 caractéristiques, ce graphe est forcément minimal.
    Autrement dit, si tu supprimes le moindre arc, ton graphe ne sera plus connexe.

    S'il y a 2 chemins pour aller de A à B, on peut en prendre 1 à l'aller et l'autre au retour. Il y a donc une boucle.
  • Pour moi une boucle c'est une arête d'un sommet $i$ vers le sommet $i$.
  • Reinhard,

    Est ce que ta question n'est pas liée à la recherche d'un arbre (ou d'une forêt) de poids minimum ? Si oui, il y a plusieurs algorithmes : Prim, Kruskal, ...etc.. cf la section 6.2 ainsi que 8.5 dans la traduction du Bondy Murty par F. Havet http://www-sop.inria.fr/members/Frederic.Havet/Traduction-Bondy-Murty.pdf

    Sinon (i.e. si pas de rapport avec la choucroute) préviens tout de suite la modération qu'il y a un troll sur ton fil.
  • Bonjour Claude Quitté,

    je viens de lire la description des algorithmes de Kruskal et de Prim et ça m'a l'air d'être exactement ce qu'il me faut ! Merci beaucoup.

    [ Sujet : Résolu ]
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!