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

III. Graphes simples

                                            

III-1 Généralités:

 

Définition 1 : Etant donné un ensemble fini non vide S muni d’une relation binaire R antiréflexive (irréflexive) et symétrique. On désigne par A l’ensemble des paires de couples de points en relation. On appelle graphe simple la donnée du couple G=(S,A). S est appelé ensemble des sommets du graphe et A est appelé ensemble des arêtes du graphe simple G.
Le graphe simple particulier G=(S,) est appelé graphe discret.

 

Définition 2 : Le nombre de sommets d’un graphe simple est appelé ordre du graphe , on le note ord(G) ou |G|. Le nombre d’arêtes d’un graphe simple est appelé taille du graphe , on le note tail(G). On parlera d’un (n,p)-graphe pour désigner un graphe d’ordre n et de taille p.

 

Définition 3 : On considère un (n,p)-graphe simple G=(S,A). Etant donnée une arête a= s_is_jA, on dit que s_i et s_j sont les extrémités de A, que A relie (ou passe par) s_i et s_j. Les sommets s_i et s_j sont alors dits adjacents (ou voisins) on dit aussi qu’ils sont incidents à l’arête a ou que l’arête a est incidente à s_i et s_j. Un sommet qui n’a pas de voisin est dit isolé. Deux arêtes sont adjacentes si elles sont incidentes à un même sommet. Si deux sommets quelconques de G sont toujours adjacents on dit que le graphe est complet et on note K_n.

 

Définition 4 : A tout (n,p)-graphe simple G=(S,A) on associe sa matrice d’adjacence M(G). C’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 :  

 

Définition 5 : A tout (n,p)-graphe simple G=(S,A) on associe sa matrice d’incidence I(G). C’est une matrice de format n×p  I(G) = (α_ij) 1≤i≤n ; 1≤j≤p dont les lignes sont indexées par S et les colonnes par A et définie par : α_ij = nombre de fois où le sommet s_i est incident à l’arête a_j.

 

Définition 6 : Etant donné un (n,p)-graphe simple G=(S,A) et sA on appelle degré de s et on note deg(s) (ou d(s)) le nombre d’arêtes de A incidentes à s. Le degré d’un sommet isolé est nul.

 

Définition 7 : Un (n,p)-graphe simple G=(S,A) est dit k-régulier si tous les sommets de G sont de degré k. Si k=3 le graphe est dit cubique.

 

 

Définition 8 : sS est dit pair si d(s) est pair, impair sinon

 

Corollaire 1 : Dans un (n,p)-graphe simple G=(S,A) le nombre de sommets impairs est pair.

 

Définition 9 : Dans un graphe simple 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 arête a de A’ les extrémités de a sont dans S’.

 

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

 

Définition 11 : Soit G=(S,A) un graphe simple 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 12 : Soit G=(S,A) un graphe simple. Si s et s’ sont deux sommets non adjacents de G on définit le graphe G+a en ajoutant l’arête a=ss’ au graphe G. G+a = (S,A’) avec A’=A{a}.

 

Définition 13 : Etant donné deux graphes simples G₁=(S₁,A₁) et G₂=(S₂,A₂) on appelle réunion de G₁ et G₂ le graphe G=(S,A) où S=S₁S₂  et A=A₁A₂ . On note G=G₁G₂

 

Définition 14 : Soit G=(S,A) un (n,p)-graphe simple et K_n=(S,A’) le graphe complet dont l’ensemble des sommets est S. On appelle complémentaire de G le graphe  où  

 

Définition 15 : Soit G=(S,A) un graphe simple. On appelle chaîne une suite finie de sommets s_i, s_i+1,…, s_i+m telle que pour tout j 0≤j≤m-1    s_i+j s_i+j+1A. On notera c=[ s_i, s_i+1,…, s_i+m]. L’entier m s’appelle la longueur de la chaîne et on écrit m=l(c). Le sommet s_i est appelé extrémité initiale de la chaîne, le sommet s_i+m est appelé extrémité finale de la chaîne. Lorsque s_i = s_i+m , on dit que la chaîne est fermée et on l’appelle cycle en s_i.
On convient qu’en chaque sommet s_k on a un cycle [s_k] de longueur 0.
Un chaîne de longueur ≥1 dont toutes les arêtes sont distinctes est dite simple.
Un chaîne de longueur ≥1 dont tous les sommets (sauf éventuellement s_i et s_i+m) sont distincts est dite élémentaire.
Un cycle simple est une chaîne simple fermée ayant au moins trois arêtes.
Un cycle élémentaire est une chaîne élémentaire fermée ayant au moins trois arêtes (seuls les deux sommets d’extrémité sont identiques).

 

Remarque 2 : Toute chaîne élémentaire est simple.

 

Proposition 1 : Dans un graphe simple G=(S,A) s’il existe une chaîne du sommet s au sommet s’, alors il existe une chaîne élémentaire de s à s’.

 

 

III-2 Graphes isomorphes:

 

Définition 16 : Etant donné deux graphes simples G=(S,A) et G’=(S’,A’), un isomorphisme  de G sur G’ est une bijection de S sur S’ telle que deux sommets s_i et s_j sont adjacents dans G si et seulement si leurs images (s_i) et (s_j) sont deux sommets adjacents dans G’.

 

Remarque 1 : La bijection de S sur S’ induit une bijection Φ de A sur A’ donnée par :                                                        

 

Proposition 2 : La relation « est isomorphe à » est une relation d’équivalence.

 

Proposition 3 : si deux graphes simples G₁=(S₁,A₁) et G₂=(S₂,A₂) sont isomorphes alors ils ont la même taille et le même ordre.

 

Proposition 4 : si deux graphes simples G₁=(S₁,A₁) et G₂=(S₂,A₂) sont isomorphes alors sS₁ deg(s)=deg((s)) où  est un isomorphisme entre G₁ et G₂ .

 

Définition 17 : Un invariant de G est un nombre associé à G qui est le même pour tout graphe isomorphe à G.

 

III-3 Graphes connexes:

 

Définition 18 : Un graphe simple G=(S,A) est connexe s’il existe toujours une chaîne entre deux sommets quelconques de G.

 

Proposition 5 : Dans un graphe simple G=(S,A) la relation binaire R définie sur S par s R s’ si et seulement si il existe une chaîne de s à s’ est une relation d’équivalence.

 

Remarque 3 : La relation d’équivalence R engendre une partition de S en k parties S₁, S₂, …, S_k.

 

Définition 19 : On appelle composantes connexes du graphe simple G=(S,A) les sous-graphes G_i engendrés par les S_i.

 

Soit G=(S,A) un graphe simple. Pour s et s’ deux sommets de G on pose :        

 

 

Définition 20 : Un géodésique de s à s’ est une chaîne de s à s’ de longueur d(s,s’).

 

Définition 21 : Le diamètre δ(G) d’un graphe connexe G est la longueur du plus long géodésique de G.

 

Définition 22 : L’excentricité e(s) d’un sommet s est le nombre e(s)=max d(s,s’) s’S.

 

Définition 23 : Un centre de G est un sommet s d’excentricité minimum.
c.a.d un sommet s tel que e(s)=min e(s’) s’S.

 

Définition 24 : Le rayon de G est l’excentricité d’un centre de G. On note  r(G).

 

Définition 25 : Soit G=(S,A) un graphe simple connexe (d’ordre ≥2). Un sommet s est un  point d’articulation de G si G-s est non connexe.
Une arête a est un  pont de G si G-a est non connexe.

 

Définition 26 : G est non séparable s’il n’admet aucun point d’articulation.
Un bloc de G est un sous-graphe de G non séparable maximal.

 

 

 

 

III-4 Graphes particuliers:

 

Définition 27 : On appelle bipartition de G la donnée d’une partition de S en deux sous-ensembles X et Y telle que toute arête de G a l’une de ses extrémités dans X et l’autre dans Y. Si G admet une bipartition on dit qu’il est biparti.

 

 

Définition 28 : On appelle arbre un graphe simple connexe sans cycle.
On appelle forêt un graphe simple sans cycle.

 

Lemme 1 : Tout arbre d'ordre n≥2 possède au moins deux sommets pendants.