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

I. Graphes généralités

 

I-1 Préliminaires:

 

Définition 1 : Un graphe G est la donnée de deux ensembles (finis) S et A et d’une application
 : A → S²  qui à tout aA  associe (a)=(s,s’). On note a=ss’
n=|S|=nombre d’éléments de S est l’ordre de G et p=|A|=nombre d’éléments de A est sa  taille. Un élément aA est un arc de G. Un élément sS est un sommet de G.
On notera G=(S,A,) ou G=(S,A) s’il n’y a pas d’ambiguïté.
s et s’ sont les extrémités de l’arc a=ss’. s est l’origine ou l’extrémité initiale de a, s’ est son extrémité terminale (ou finale). Si s=s’ on dit que a est une boucle.
Deux arcs  sont dit parallèles s’ils ont les mêmes extrémités (initiales et finales).
Un ensemble de k arcs parallèles est appelé arc multiple, k est la multiplicité. Un k-graphe est un graphe dans lequel le maximum de multiplicité est k.

 

Représentation géométrique (graphique) : Soit G=(S,A,). On se donne une bijection entre S et une partie du plan et une bijection entre A et un ensemble d’arcs de Jordan du même plan. (Théoriquement) une telle représentation est toujours possible.

 

Définition 2 : Dans un graphe 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 3 : Soit G=(S,A) un graphe et S’S, on appelle sous-graphe engendré par S’ le graphe 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 4 : Soit G=(S,A) un graphe et A’A, on appelle graphe partiel engendré par A’ le graphe H=(S,A’). On note G-a le graphe partiel engendré par A’=A-{a}.

 

Définition 5 : Deux arcs a₁ et a₂ sont dit adjacents s’ils ont au moins une extrémité commune. Deux sommets s₁ et s₂ sont dit adjacents (ou voisins) s’il existe un arc a tel que (a)=(s,s’) ou (a)=(s’,s). Un sommet s est un prédécesseur ( resp successeur) d’un sommet s’ s’il existe un arc a tel que (a)=(s,s’) (resp (a)=(s’,s)). On note Γ⁺(s) l’ensemble des successeurs d’un sommet s et Γ^-(s) l’ensemble de ses prédécesseurs. Γ(s)=Γ⁺(s)Γ^-(s) désigne l’ensemble des voisins de s.

 

Définition 6 : Soit a=ss’ un arc (qui n’est pas une boucle) d’un graphe 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 1 : d⁺(s)≥|Γ⁺(s)| et d^-(s)≥|Γ^-(s)|

 

 

 

 

Définition 7 : 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 (a_i)=(s_i,s_i+1) 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.
Si aucun arc ne figure plus d’une fois dans le chemin, ce dernier est dit simple. Si aucun sommet ne figure plus d’une fois dans le chemin, ce dernier est dit élémentaire.

 

Remarque 2 : Un chemin élémentaire est un chemin simple.

 

Définition 8 : Un circuit de G est un chemin de la forme c=[s₁s₂s₃…s_ks₁]. De façon analogue on définit un circuit simple et un circuit élémentaire.

 

Définition 9 : Un sous-chemin d’un chemin c=[s₁s₂s₃…s_k] est un chemin c’=[s_is_i+1…s_j] tel que 1≤i≤j≤k et k=i, …, j    s_kc.

 

Définition 10 : La somme de deux chemins c₁=[s₁s₂s₃…s_k] et c₂=[s_ks_k+1…s_j] est un chemin c=[s₁s₂s₃…s_k s_ks_k+1…s_j]. On note c=c₁+ c₂.