Graphes

[pozor16]

Bonjour à tous,

J'ai une petite question à vous poser et j'espère que vous pourrez m'aider ;)

Si j'ai un graphe G connexe(qui n'est pas un arbre), comment peut-on trouver son centre? Existe-t-il un algorithme?

Je sais que pour un arbre on peut utiliser le code de Prüfer mais pour les autres je bloque.

Merci d'avance

[cbmaths]

Bonjour à tous,

J'ai une petite question à vous poser et j'espère que vous pourrez m'aider

Si j'ai un graphe G connexe(qui n'est pas un arbre), comment peut-on trouver son centre? Existe-t-il un algorithme?

Je sais que pour un arbre on peut utiliser le code de Prüfer mais pour les autres je bloque.

Merci d'avance

Bonjour,

Utilisez l'algorithme de Floyd pour trouver le plus court chemin entre toutes les paires de sommets.
A partir de la matrice obtenue vous déterminez l'excentricité de chaque sommet (c'est à dire la distance maxi pour atteindre chaque autre sommet). Le centre du graphe est alors constitué du ou des sommets qui ont la plus faible excentricité.