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

I.2.5. Distances

La distance entre deux sommets d'un graphe connexe (ou entre 2 sommets d'une même composante connexe d'un graphe non connexe) est le nombre minimum d'arcs (on dit aussi la longueur) d'une chaîne allant de l'un à l'autre.

Dans l'exemple 1.9 la distance de a à f est de 2 : on peut aller de a à f en 2 arcs, mais pas en 1 arc.

L'écartement d'un sommet est la distance maximale existant entre ce sommet et les autres sommets du graphe. (Si le graphe n'est pas connexe, l'écartement est infini).

Dans l'exemple 1.9, l'écartement de a est de 2, comme d'ailleurs pour tous les autres sommets, sauf d dont l'écartement vaut 1.

On appelle centre d'un graphe, le sommet d'écartement minimal.  (Le centre n'est pas nécessairement unique).Par exemple, dans une clique, tous les sommets sont « centres »

 

On appelle rayon d'un graphe G, noté ñ(G), l'écartement d'un centre de G. Le rayon est de 1 dans l'exemple 1.9. d est le seul centre de ce graphe.

On appelle diamètre d'un graphe G, noté ä(G), la distance maximale entre deux sommets du graphe G. Le diamètre est de 2 dans l'exemple 1.11.

Exemple 1.11 :

Figure 1.11 : Représentation sagittale d'un graphe illustrant la notion de distance

1.2.6. Graphe planaire

Un Graphe sera dit planaire s'il admet une représentation sagittale planaire, c'est à dire une représentation dans le plan où les sommets du graphe sont des points du plan et les arcs des courbes simples ne se rencontrant qu'en un sommet.

Remarque : Pour qu'un graphe soit planaire, il faut qu'il admette au moins une représentation planaire.

Exemple 1.12 :

Figure 1.12 : Graphe planaire

K₄ est-il planaire ?

Si on se fonde sur sa représentation sagittale classique ci-contre, il semblerait que non.

Pourtant, on pourrait représenter le graphe autrement, en faisant passer l'arc 2,4 par l'extérieur, on aurait alors une représentation planaire.

 

K₄ est donc bien un graphe planaire.

Dans la représentation planaire d'un graphe, on appellera face toute région du plan non traversée par des arcs.

Dans l'exemple 1.12, il y a 6 faces (n'oubliez pas la face infinie), 12 sommets et 16 arcs.

Exemple 1.13 :

6

Figure 1.13 : Faces d'un graphe planaire

Propriété 1.1 (Formule d'Euler): Dans un graphe planaire d'ordre n avec m arcs, on a: 

f = a - n + 2.

 

Démonstration : par récurrence sur a,
C'est vrai pour le graphe contenant 2 sommets et un arc : f=1, n=2, a=1 d'où :

f-a+n= 2 

Quand on rajoute un arc, deux cas de figure peuvent se présenter : soit on rajoute un sommet dans une face et le nombre de faces ne change pas; soit on ne rajoute pas de sommet, l'arc ajouté arrive donc sur un sommet déjà existant, mais alors, on a coupé une face en 2, donc ajouter une face.

Dans tous les cas, le nombre f-a+n ne varie pas, reste donc égal à2.

Propriété 1.2 : K₅ n'est pas planaire

Démonstration : S'il était planaire, sa représentation planaire comporterait (d'après la Formule d'Euler) 10-5+2 = 7 faces.
Or, il faut au moins 3 arcs pour fermer une face et un arc pouvant servir de frontière à 2 faces, avec 10 arcs, il ne peut y avoir plus de 20/3 faces, d'où une contradiction.

Propriété 1.3 : K_3,3 n'est pas planaire

 

Démonstration : S'il était planaire, sa représentation planaire comporterait (d'après la Formule d'Euler) 9-6+2 = 5 faces.
Or, il faut au moins 4 arcs (dans le cas d'un graphe biparti, on ne peut pas fermer une face avec un nombre impair d'arcs!) pour fermer une face et un arc pouvant servir de frontière à 2 faces, avec 9 arcs, il ne peut y avoir plus de 18/4 faces, d'où une contradiction.

Nota : Il existe une réciproque à ces deux propriétés, connue sous le nom de Théorème de Kuratowski, dont la démonstration est assez difficile.

Propriété 1.4 (Théorème de Kuratowski) :

Les seuls graphes non planaires sont ceux admettant K₅ ou K_3,3 comme sous-graphes.