Cours 2

CHAPITRE I Notions fondamentales de la théorie des graphes

Cours 2

6.Chaîne,chemin, boucle, cycle, circuit

Dans un graphe non orienté, une chaîne reliant

à est définie par une suite finie d'arêtes consécutives, reliant à .
Dans un graphe orienté, un chemin reliant

- 7.Connexité et connexité forteUn graphe non orienté est dit connexe (ou simplement connexe) si deux sommets quelconques et distincts du graphe admettent au moins une chaîne qui les relie (il n' y a pas de sommet isolé).
- Un graphe orienté est dit connexe si le graphe non orienté associé est connexe.

Un graphe orienté est fortement connexe si pour tout couple de sommets x, y il existe un chemin reliant x à y et un chemin de y à x. Donc un graphe orienté est fortement connexe si et seulement si pour tout couple de sommets x, y il existe un circuit passant par x et y.
Un graphe orienté fortement connexe est connexe.

Théorème d'Euler:

- Un graphe connexe possède une chaine eulérienne si et seulement si ses sommets sont tous de degré pair sauf au plus deux.
- Un graphe connexe possède un cycle eulérien si et seulement si tous ses sommets sont de degré pair.
- Une version du théorème d'Euler existe aussi pour les graphes orientés. On démontre qu'un graphe orienté fortement connexe possède un circuit eulérien si et seulement si de chaque sommet il part autant d'arcs qu'il en arrive.
- Un sous-graphe connexe d'un graphe non orienté quelconque est une composante connexe de ce graphe.
- Une composante fortement connexe d'un graphe orienté G est un sous-graphe de G qui est fortement connexe.

à est défini par une suite finie d'arcs consécutifs, reliant à .
- Une boucle est (une arête ou un arc) d'un (graphe non orienté ou orienté) ayant pour extrémités le même sommet.
- Une chaîne élémentaire (chemin élémentaire) est une chaîne ne passant pas deux fois par un même sommet, c'est-à-dire dont tous les sommets sont distincts.
- Une chaîne simple (ou chemin simple) est une chaîne ne passant pas deux fois par une même arête (arc), c'est-à-dire dont toutes les arêtes (arcs) sont distinctes.
Un cycle (circuit) est une chaîne (chemin) simple dont les deux extrémités sont identiques.
- Une chaîne eulérienne (chemin eulérien) est une chaine (chemin) passant une et une seule fois par toutes les arêtes (arcs) du graphe.
- Un cycle (circuit) eulérien est une chaine eulérienne (chemin eulérien) dont le sommet de départ et le sommet d'arrivée sont identiques.
- Une chaîne hamiltonienne (chemin hamiltonien) est une chaîne (chemin) qui passe une fois et une seule par chaque sommet du graphe.
Un cycle (circuit) hamiltonien est une chaîne (chemin) hamiltonienne qui est cyclique.
- Un graphe qui contient un cycle (circuit) hamiltonien est appelé graphe hamiltonien. Un graphe semi-hamiltonien est un graphe qui contient une chaîne (chemin) hamiltonienne, mais pas de cycle (circuit) hamiltonien.

Le nom de cycle hamiltonien vient d'un puzzle inventé par Sir William Rowan Hamilton (l'inventeur des quaternions) en 1859. Ce jeu consistait en un dodécaèdre dont les 20 sommets étaient étiquetés par le nom d'une ville. Le but du jeu était de trouver un chemin passant une seule fois par chaque ville et revenant à la ville de départ.

8.Matrice et graphe

8.1 Matrice d'incidence :

La matrice d'incidence d'un graphe est une matrice qui décrit le graphe en indiquant quels liens arrivent sur quels sommets.La matrice d'incidence est une matrice n x p, où n est le nombre de sommets du graphe et p est le nombre de liens (arêtes ou arcs).

Cette matrice est définie de deux façons différentes selon que le graphe est orienté ou non orienté.

Si le graphe est orienté, le coefficient de la matrice d'incidence en ligne

et en colonne vaut :

1 si l'arc
sort du sommet
-1 si l'arc
entre dans le sommet
2 si l'arc
est une boucle sur
0 sinon

Exemple : Voici un exemple de graphe orienté, et la matrice d'incidence associée :

Si le graphe est non orienté, le coefficient de la matrice d'incidence en ligne

On peut remarque que cette matrice est symétrique. C'est le cas pour toutes les matrices d'adjacence d'un graphe non-orienté.

Théorème : Soit G un graphe non-orienté de matrice d'adjacence A. Le nombre de chaines de longueur n joignant le sommet i au sommet j est donné par le terme d'indice i,j de la matrice Aⁿ.

Graphe orienté : On peut également définir la matrice d'adjacence d'un graphe orienté. Cette fois, le coefficient a_i,j désigne le nombre d'arcs d'origine i et d'extrémité j.

Exemple :

et en colonne vaut :

1 si le sommet
est une extrémité de l'arête
2 si l'arête
est une boucle sur
0 sinon

Pour distinguer les deux définitions, on parle de matrice d'incidence orientée et de matrice d'incidence non orientée.

8.2 Matrice d'adjacence :

Graphe non orienté : Soit G un graphe non-orienté qui possède n sommets numérotés de 1 à n. On appelle matrice d'adjacence du graphe la matrice A=(a_i,j) où a_i,j est le nombre d'arêtes joignant le sommet i au sommet j.

Exemple : Voici un graphe non-orienté, et la matrice d'adjacence correspondante :

Cette matrice n'est plus symétrique. En revanche, le terme d'indice (i,j) de la matrice Aⁿ compte toujours le nombre de chemins allant de i vers j.

8.3 Matrice laplacienne :

Une matrice laplacienne, ou matrice de Laplace, est une matrice représentant un graphe simple non valué, orienté ou non. Elle vérifie :

T2 : Trouver la relation entre la matrice d'adjacence et la matrice laplacienne

Page updated

Google Sites

Report abuse