Base des données orientées-graphe: migration du relationnel vers le noSQL

I.2. GRAPHES

I.2.1. Définition d'un graphe

On appelle graphe G le couple (X, U) où :

· X est un ensemble non vide et au plus dénombrable dont les éléments sont appelés sommets) ou  noeuds.

· U est une famille d'éléments du produit cartésien X×X={(x,y)|x, y X} dont les éléments sont appelés arcs ou arêtes. Ces éléments représentent des liaisons entre sommets du graphe.

En terminologie des graphes,

· On appellera arc une liaison orientée d'un sommet x vers un autre sommet y. On dit que y est un successeur de x s'il existe un arc (x,y); on dit aussi que x est un prédécesseur de y, c'est-à-dire x est un extrémité initiale et y est un extrémité terminale (finale). On appellera y voisin de x dans le graphe G=(X, U) s'il est soit un successeur, soit un prédécesseur de x.

Nota : Dans la vie pratique, on peut interpréter extrémité terminale par « descendant », « fils ou fille», « origine », « ... » et on peut interpréterextrémité initiale par « ascendant », « père ou mère », « cible », « ... ».

· On appellera arête une liaison non-orientée d'un sommet x et un autre sommet y. Dans ce cas x et y sont des extrémités.

Nota : Dans la vie pratique, on l'interprète une extrémité par « un noeud » ou un « bout ».

On notera alors :

· (x) = L'ensemble des successeurs du sommet x dans G

· (x) = L'ensemble des prédécesseurs du sommet x dans G

· (x) = L'ensemble des voisins du sommet x dans G

Ainsi, (x) = (x) + (x)

Un sommet x dans est un sommet isolé ssi c'est-à-dire si et seulement si le sommet x n'a pas de voisin c'est-à-dire qui n'a ni successeur, ni prédécesseur. (1)

b

a

d

e

f

c

u₇

u₂

u₅

u₆

u₁

u₄

u₈

u₃

Figure 1.4 : Représentation sagittale d'un graphe

Exemple 1.3 : Soit le graphe G

Dans cet exemple, on a la représentation sagittale d'un graphe d'ordre 6.

X = {a, b, c, d, e, f} 

U = {u₁, u₂, u₃, u₄, u₅, u₆, u₇, u₈}

Si le cardinal de U est égal à a (|U|=#U=a), alors on dit que le graphe G = (X, U) est de taille a. Dès lors nous considérons U I N est fini. L'exemple 1.3 est de taille a=8, car il y a 8 arcs.

Si le cardinal de X est égal à n (|X|=#X=n), alors on dit que le graphe G = (X, U) est d'ordre n. Dès lors nous considérons X J N est fini. L'exemple 1.3 est d'ordre n=6, car il y a 5 sommets.

L'arc u₇ est une boucle parce que l'extrémité initiale coïncide avec l'extrémité terminale.

L'arc u₃ et l'arc u₈ sont de la même forme, car ils ont même extrémité initiale et même extrémité finale. On dira que G (de l'exemple 1.3) est un 2-graphe d'ordre 6.

Ainsi, un p-graphe d'ordre n est un graphe d'ordre n dont le maximum d'arcs de même est le naturel p.

Un graphe simple est un 1-graphe sans boucle. En d'autres termes, un graphe est dit simple s'il n'y a ni boucle, ni d'arcs de même forme.

Dans un graphe simple, on pourra donc noter un arc à l'aide de ses extrémités initiale et finale.

Un multigraphe est un p-graphe (avec p>1) sans boucle.

Deux arcs sont dits adjacents s'ils ont une extrémité en commun.

Deux sommets sont dits adjacents si un arc les relie. 

Le demi-degré extérieur d'un sommet x (noté d_G⁺(x)) est égal au nombre d'arcs qui « partent » de x.

Le demi-degré intérieur d'un sommet x (noté d_G^-(x)) est égal au nombre d'arcs qui « arrivent » en x.

Le degré du sommet x (noté d_G(x)) est égal à la somme des demi-degrés, c'est-à-dire :

+

En particulier :

· Si = 0, on dit que le sommet est isolé ; (2)

· Si = 1, on dit que le sommet est pendant.

Remarque : Les propositions (1) et (2) sont équivalentes.

Lemme 1.1 : Lemme de poigné de main

Soit G = (X, U) un graphe sans boucle, alors :

Où n le nombre des sommets et a le nombre d'arêtes.

Exemple 1.4 : Soit le graphe G

b

a

d

e

f

c

u₂

u₅

u₆

u₁

u₄

u₃

Figure 1.5 : Représentation sagittale d'un graphe simple

On notera que rien n'interdit la présence dans le graphe de l'arc (e,f) et (f,e).

· d est un sommet isolé parce qu'il n'est ni extrémité initiale, ni extrémité terminale d'aucun arc ;

· a et b sont adjacents ;

· l'arc 4 est incident à f ;

· b et e sont des prédécesseurs de f ;

· b et e sont des successeurs de a ;

· le demi-degré extérieur de e d_G⁺(e)= 1 ;

· le demi-degré intérieur de e d_G^-(e)= 2 ;

· le degré de e d_G(e) = 3.

· (Lemme de poignée de main)