Plus "petit" sous-graphe connexe

Reinhard

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 là 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.

lourrran

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.

Reinhard

Pour moi une boucle c'est une arête d'un sommet $i$ vers le sommet $i$.

claude quitté

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.

Reinhard

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 ]