Précédent / Suivant / Table des matières

II. Graphes orientés

                                            

II-1 Généralités:

 

Définition 1 : Un graphe orienté G=(S,A) est la donnée d’un ensemble fini non vide de sommets S et d’un ensemble de flèches (arcs) AS². Si a=(s,s’)A, on dit que a est la flèche (l’arc) de s à s’, on note a=ss’. Si s=s’ on dit que a est la boucle en s. Les sommets s et s’ sont adjacents si (s,s’)A ou (s’,s)A. L’ordre du graphe orienté G est par définition le cardinal |S| de S et sa taille est le cardinal |A| de A.

 

Remarque 1 : Un graphe orienté G=(S,A) est donc la donnée d’un ensemble fini non vide de sommets S et d’une relation binaire A définie sur S. Le graphe G sera dit réflexif, symétrique ou transitif selon que la relation binaire A est réflexive, symétrique ou transitive.

 

Définition 2 : Un chemin de G=(S,A) est une suite alternée finie de sommets et d’arcs de G c=[s₁a₁s₂a₂s₃a₃…s_k] telle que pour i=1, …, k-1  (s_i,s_i+1)A on note c=[s₁s₂s₃…s_k]  s₁ est l’extrémité initiale ou origine de c et s_k son extrémité finale. La longueur l(c) du chemin est égale au nombre d’arcs qu’il comporte. (un même arc peut éventuellement être répété). l(c)=k-1.
Le chemin c est un circuit si s₁=s_k.
Le chemin c est dit simple si tous les arcs sont distincts, il est dit élémentaire si tous les sommets sont distincts (sauf peut-être s₁ et s_k) De façon analogue on définit un circuit simple et un circuit élémentaire.
Pour tout sommet s on admet le chemin c=[s] de longueur zéro, qui est un circuit de s à s.
Une chaîne de s à s’ de longueur k-1 est une suite de sommets [s=s₁s₂s₃…s_k=s’] telle que pour tout
i=1, …, k-1  (s_i,s_i+1)A ou (s_i+1,s_i)A. La chaîne c est un cycle si s=s’. De façon analogue on définit un cycle simple et un cycle élémentaire.

 

Définition 3 : Dans un graphe orienté G=(S,A) considérons deux sous-ensembles S’S et A’A. On dit que H=(S’,A’) est un sous-graphe de G si pour tout arc a de A’ les extrémités de a sont dans S’.

 

Définition 4 : Soit G=(S,A) un graphe orienté et S’S, on appelle sous-graphe engendré par S’ le graphe orienté H=(S’,A’) où A’ est l’ensemble des arcs de G ayant leurs deux extrémités dans S’.
On note G-s le sous-graphe engendré par S’=S-{s}.

 

Définition 5 : Soit G=(S,A) un graphe orienté et A’A, on appelle graphe partiel engendré par A’ le graphe orienté H=(S,A’). On note G-a le graphe partiel engendré par A’=A-{a}.

 

Définition 6 : Soit a=ss’ un arc (qui n’est pas une boucle) d’un graphe orienté G. a est incident à s vers l’extérieur et incident à s’ vers l’intérieur. Le nombre d’arcs incidents à s vers l’extérieur est noté d_G⁺(s) (ou d⁺(s)) et s’appelle le demi-degré extérieur de s. Par analogie, le demi-degré intérieur de s, noté d_G^-(s) (ou d^-(s)) est le nombre d’arcs incidents à s vers l’intérieur. Le degré d_G(s) (ou d(s)) est égal à d⁺(s)+ d^-(s).
Si d(s) est pair (resp impair) alors le sommet s est dit pair (resp impair).
Si d(s)=0 le sommet s est dit isolé, si d(s)=1 le sommet s est dit pendant.
Un arc est pendant s’il est incident à un sommet pendant.

 

Remarque 2 : d⁺(s)=|Γ⁺(s)|=|{s’ tq (s,s’)A}| et d^-(s)=|Γ^-(s)|=|{s’ tq (s’,s)A}|

 

Définition 7 : Un graphe orienté G=(S,A) est fortement connexe si pour tout couple (s,s’) de sommets il existe un chemin de s à s’.
Un graphe orienté G=(S,A) est connexe si pour tout couple (s,s’) de sommets il existe une chaîne de s à s’.

 

 

Définition 8 : Soit G=(S,A) un graphe orienté. La fermeture transitive de G est le graphe orienté  défini par  s’il existe un chemin de G de s à s’.

 

Définition 9 : Soit G=(S,A) un graphe orienté avec S={s₁, s₂, s₃, …, s_n}. La matrice d’adjacence de G est la matrice carrée d’ordre n   M(G) = (m_ij) dont les lignes et les colonnes sont indexées par S et définie par :  

 

Proposition 1 : Soit G=(S,A) un graphe orienté avec S={s₁, s₂, s₃, …, s_n} et M(G) sa matrice d’adjacence. Alors on a :
1)-Pour tout i=1, 2, …, n 
2)-  
3)-G est symétrique si et seulement si M(G) est symétrique
4)-Le nombre de boucles de G est égal à la trace de M(G).