Généralités sur les graphes

La théorie des graphes :

Un graphe est composé de sommets (on parle aussi de noeuds) et d’arcs qui relient les sommets entre eux. La forme n’a pas d’importance mais en général on le lit de gauche à droite, parfois de haut en bas, car ce sont des sens naturels.

On appelle un graphe G(X,U) avec X= ensemble de sommets et U = ensembles d’arcs.

Graphe non orienté

– Orientation des arcs : pas d ’importance (plan de circulation sans sens interdits)
– Extrémité initiale et terminale : aucun rôle
– Intéresse à l ’existence ou non d ’un ou plusieurs arcs entre deux sommets.
– A tout arc (xi,xj) , à tout couple de sommets ordonnés (xi,xj) on associe un couple non ordonné (xi,xj) appelée arête

L’ordre des liaisons n’a pasd’importance, on regarde justel’existence d’un lien entre deuxsommets. Donc approche binaire : le lien existe ou pas. Mais ce lien n’a pas de sens.

Vocabulaire :
Ordre d’un graphe : nombre de sommet de ce graphe. Un graphe avec 5 sommets est un graphe d’ordre 5.
X-graphe : nombre maximal de liens entre deux sommets.

On appelle multigraphe un graphe pour lequel il existe plusieurs arêtes entre deux sommets xi,x

• Un multigraphe est un graphe simple si :
  • absence de boucle
  • un arc, max, entre deux sommets

Entre X1 et X3 il y a 4 liens et au total il y a 5 sommets. On parle donc de 4-graphe d’ordre 5.
Attention : le graphe est en deux parties.
U7 et U8 font partie du même graphe.
Quelques trucs importants :
Successeurs et prédécesseurs à un sommet : les successeurs sont les sommets qui partent d’un sommet ; les prédécesseurs sont les sommets qui
arrivent à un autre sommet.

Matrice associé à un graph

Un graphe peut se représenter sous la forme graphique (le dessin du graphe). Mais quand vous en utilisez, faites des calculs ou autre, on a besoin de la forme matricielle.
Il y a trois façons de représenter un graphe par une matrice :

Matrice d ’incidence sommets-sommets

On regarde le nombre de sommets. Si on a 4 sommets, on fait une matrice 4x4. La ligne 1 correspond au sommet 1, la ligne 2 au sommet 2, …. Mais aussi, la colonne 1 correspond au sommet 1, la colonne 2 au sommet 2, … Ensuite on fait un remplissage binaire simple. Par exemple, s’il existe un lien entre le sommet 3 et le sommet 4, on met 1 dans la ligne 3 et la colonne 4 de
la matrice.

matrice d ’incidence sommets-arcs

Mettre en ligne les sommets et en colonne les arcs. Exemple : il existe un arc U3 qui part de X2, on met donc 1 entre U3 et X2. Les autres valeurs possibles sont -1 qui signifie que l’arc arrive et 0, pas d’arc entre les deux.

Matrice d ’incidence sommets-arêtes

Mettre en ligne les sommets et en colonne les arrêtes. Dans cette matrice on ne prend pas en compte l’orientation des arcs.

chaine et de chemin.

– Chaîne élémentaire : On ne rencontre pas deux fois le même sommet en la parcourant.
– Chaîne simple : On ne rencontre pas deux fois le même arc en la parcourant.
– Chemin : C’est une séquence de q arcs dont les arcs sont orientés dans le même sens.Pour tout arc ui (i < q ) l’extrémité terminale de ui coïncide avec l’extrémité initiale ui+1.
– Chemin élémentaire : Les sommets de degré 2 au plus
– Chemins hamiltoniens : Dans un graphe G=(X,U), on dit qu’un chemin m=[x1,x2,…,xn] est hamiltonien s ’il passe une fois et une seule par chaque sommet du graphe. C’est un chemin élémentaire de longueur (N-1). C’est le problème du voyageur de commerce : il doit relier plusieurs points en partant de chez lui.
– La connexité : un graphe G(X,U) est connexe si pour tout couple de sommets (x,y) il existe une chaine joignant x à y. Un graphe G(X,U) est fortement connexe si pour tout couple de sommets (x,y) il existe un chemin joignant x à y et un chemin joignant y à x. La connexité signifie qu’on peut relier tous les
points deux à deux.

Graphe d’ordre 4 et matrice de ce graphe.

Chemin de longueur k : On appelle longueur d’un chemin, entre deux sommets, i et j appartenant à X, sur un graphe G=(X,U), le nombre d’arcs existant entre ces deux sommets.
Un chemin est de longueur, k, s’il comprend k arcs et (k+1) sommets.
Un sommet seul, détermine un chemin de longueur 0.

Si on calcule M² (MxM), on obtient la matrice de tous les chemins de longueur 2, On a 1 entre A et C car on peut aller de A à C en faisant A-B et B-C (chemin de longueur 2 => 2 arcs). Si on fait M3, on obtient tous les chemins de longueur 3, et ainsi de suite (M4, M5,…).
Si un graphe comporte N sommets, le chemin le plus long fera N-1. Exemple : pour relier 4 sommets, la longueur maximale du chemin sera 3.

Graphe d’ordre 4, on calcule M+M²+M3, on obtient tous les chemins possibles de toutes les longueurs entre les sommets.

Fermeture transitive

On appelle fermeture transitive d’un graphe la liste des chemins établis à partir de la propriété de transitivité.

La fermeture transitive s’obtient en faisant la somme booléenne de la matrice unité et des puissances successives de la matrice d’adjacence sommets sommets, M.

La matrice M représente tous les chemins existant entre toute paire de sommets xi,xj.