Diamètre d'un graphe

Terminale ES

Définitions
Soit G un graphe.

Propriété
Soit n un entier naturel non nul, soit G un graphe d'ordre n et soit A la matrice associée à ce graphe.
On pose, pour tout entier naturel non nul p, A p = ( a i , j ) .
Alors, pour tous les entiers i et j tels que 1 i n et 1 j n , a i , j est égal au nombre de chaînes de longueur p permettant d'aller du sommet i au sommet j.

Définition
Soit C l'ensemble des distances entre deux sommets quelconques d'un graphe G.
Le diamètre de G est le plus grand élément de C.

Exemple

Rubriques connexes

Graphe complet
Graphe connexe
Graphe eulérien
Graphe non orienté
Graphe orienté
Matrice associée à un graphe
Sous-graphe

Pages interactives

3094   Déterminer le diamètre d'un graphe simple non orienté connaissant les longueurs des plus courtes chaînes entre deux sommets quelconques de ce dernier Apprentissage
Tale ES 
3095   Déterminer le diamètre d'un graphe simple orienté connaissant les longueurs des plus courtes chaînes entre deux sommets quelconques de ce dernier Apprentissage
Tale ES 
3091   Diamètre d'un graphe simple Outil
Tale ES