Cycle 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

181   Cycle eulérien ou chaîne eulérienne d'un graphe simple non orienté Outil
Tale ES 
3099   Cycle hamiltonien ou chaîne hamiltonienne d'un graphe simple non orienté Outil
Tale ES