[Graphe] Sommet le plus "central"

Bonjour à tous

J'ai un soucis d'algorithmique avec la théorie des graphes.

Prenons par exemple un graphe où l'ensemble des arrêtes ne peut pas reboucler, comme illustré ici
Pièce jointe 213792

Si on part du sommet "0" et qu'on compte "1" à chaque niveau, il faudra alors 4 itérations pour atteindre l'ensemble des sommets
Pièce jointe 213793

Si maintenant on part du sommet "2", alors il ne faudra plus que 2 itérations
Pièce jointe 213794

Mon problème est de trouver ce sommet "2" permettant à un fluide qui s'en écoulerait d'atteindre tous les autres en un minimum d'itération. J'ai écrit un algorithme récursif qui pour un sommet donné me donne la profondeur maximale du graphe mais c'est trop long de tout tester. Même en optimisant en fournissant à mon algorithme la profondeur minimale déjà trouvée pour un sommet "X" et en le faisant s'arrêter dès qu'il descend plus bas en testant le sommet "Y" c'est encore trop long.

Donc ma question: y a-t-il un autre moyen de trouver ce "sommet 2" sans tout tester ???

Merci de votre attention

Bonjour,

si c'est juste pour franchir un niveau à CodinGame, alors je te laisse chercher. :P

Si c'est une question sérieuse, alors la réponse c'est la médiane.

la médiane est la valeur centrale qui minimise la valeur moyenne des écarts absolus => c'est celle qui est "en moyenne" la moins éloignée de toutes les autres.

A+

Bonjour,
Dans le cas d'un graphe non dirigé acyclique connexe, tu peux simplement retirer toutes les feuilles jusqu'à trouver le nœud ou les nœuds qui seront le ou les centres des graphes.
Dans ton exemple, on commencera par supprimer les nœuds 0,4,5 et 7 et il restera les nœuds 1,2,3 et 6. Ensuite tu supprimeras les nœuds 1,3 et 6, il ne restera que le nœud 2 → le centre de ton graphe.

Si tu avais eu un graphe :
Pièce jointe 213810
Alors les centres auraient été les nœuds 1 et 2.

Bonjour :coucou:

Ce rappel de CodingGame m'a donné envie de faire le "puzzle de la semaine". Facile, marrant et rapide, en bash.

;)

Citation:

---

Envoyé par pseudocode

si c'est juste pour franchir un niveau à CodinGame, alors je te laisse chercher. :P

---

Merci de ton intérêt à mon souci. Effectivement c'est bien pour ce site de jeux algorithmiques. Mais on n'a pas le droit d'en parler ici car c'est aussi un site marchand et Developpez ne veut pas qu'on fasse de pubs pour des sites marchands.
Sinon effectivement c'est bien ce puzzle qui me gêne. J'ai d'ailleurs repris le même exemple (mais j'ai eu la délicatesse de refaire un dessin et non pomper le dessin d'origine). Ceci dit, je n'ai pas l'impression de tricher en venant ici car mon algorithme fonctionne et trouve le noeud central. Sauf qu'il ne le trouve pas assez rapidement et je reste bloqué à 80%...

Citation:

---

Envoyé par pseudocode

Si c'est une question sérieuse, alors la réponse c'est la médiane.
la médiane est la valeur centrale qui minimise la valeur moyenne des écarts absolus => c'est celle qui est "en moyenne" la moins éloignée de toutes les autres.

---

Mouais. Je veux bien une médiane (j'avais aussi pensé au barycentre) mais une médiane de quoi ??? Du n° des noeuds ? De la distance qui sépare chaque noeud du noeud médian ? Dans le premier cas ça n'a pas de sens et dans le second il faut alors calculer chaque distance ce que je fais déjà.

Citation:

---

Envoyé par picodev

Dans le cas d'un graphe non dirigé acyclique connexe, tu peux simplement retirer toutes les feuilles jusqu'à trouver le nœud ou les nœuds qui seront le ou les centres des graphes.
Dans ton exemple, on commencera par supprimer les nœuds 0,4,5 et 7 et il restera les nœuds 1,2,3 et 6. Ensuite tu supprimeras les nœuds 1,3 et 6, il ne restera que le nœud 2 → le centre de ton graphe.

---

Super !!!
Effectivement, c'est comme l'oeuf de Colomb.

Un grand merci pour ton aide.

Citation:

---

Envoyé par pseudocode

si c'est juste pour franchir un niveau à CodinGame, alors je te laisse chercher. :P

---

Décidément, on retrouve les exos de CG partout, plus ou moins modifiés pour ne pas apparaitre trop clairement, je suis sur qu'on en trouve aussi sur S.O. en cherchant bien. :mouarf: