Glossary

Chaîne d'un graphe
Middle school year 6 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.
Author of the page: Euler, Académie de Versailles

Related concepts

This page is not in its usual appearance because WIMS is unable to recognize your web browser.
In order to access WIMS services, you need a browser supporting forms. In order to test the browser you are using, please type the word wims here: and press ``Enter''.

Please take note that WIMS pages are interactively generated; they are not ordinary HTML files. They must be used interactively ONLINE. It is useless for you to gather them through a robot program.