Glossaire

Chaîne d'un graphe
Terminale Générale Experte

Description

Définitions

Soit G un graphe.
  • Une chaîne de G est une liste ordonnée de sommets de G telle que chaque sommet de la liste soit adjacent au suivant.
  • La longueur d'une chaîne est le nombre d'arêtes qui la composent.
  • La distance entre deux sommets de G est la plus petite des longueurs des chaînes qui les relient.
  • Une chaîne est dite fermée lorsque le sommet de départ et le sommet d'arrivée sont confondus.
  • Un cycle est une chaîne fermée composée d'arêtes toutes distinctes.

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.
Soit p un entier naturel non nul et a i,j les coefficients de la matrice A 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.
Auteur de la page: Euler, Académie de Versailles

Notions connexes

Cette page n'est pas dans son apparence habituelle parce que WIMS n'a pas pu reconnaître votre navigateur web.
Afin de tester le navigateur que vous utilisez, veuillez taper le mot wims ici : puis appuyez sur ``Entrer''.

Veuillez noter que les pages WIMS sont générées interactivement; elles ne sont pas des fichiers HTML ordinaires. Elles doivent être utilisées interactivement EN LIGNE. Il est inutile pour vous de les ramasser par un programme robot.