Chaîne 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

179   Déterminer la longueur des plus courtes chaînes entre deux sommets d'un graphe pondéré orienté Apprentissage
Tale ES 
3092   Déterminer la longueur des plus courtes chaînes entre deux sommets quelconques d'un graphe simple non orienté Apprentissage
Tale ES 
3093   Déterminer la longueur des plus courtes chaînes entre deux sommets quelconques d'un graphe simple orienté Apprentissage
Tale ES 
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 
3107   Déterminer la longueur des plus courtes chaînes entre deux sommets d'un graphe pondéré non orienté Apprentissage
Tale ES 
180   Chaînes de longueur donnée associées à un graphe Outil
Tale ES 
181   Cycle eulérien ou chaîne eulérienne d'un graphe simple non orienté Outil
Tale ES 
183   Recherche d'une plus courte chaîne entre deux sommets d'un graphe pondéré Outil
Tale ES 
3091   Diamètre d'un graphe simple Outil
Tale ES 
3099   Cycle hamiltonien ou chaîne hamiltonienne d'un graphe simple non orienté Outil
Tale ES