THÉORIE DES GRAPHES

CHAPITRE I Notions fondamentales de la théorie des graphes

Cours 1

1.Introduction

La théorie des graphes et l'algorithmique qui lui est liée est un des outils privilégiés de modélisation et de résolution des problèmes dans un grand nombre de domaines allant de la science fondamentale aux applications technologiques concrètes.. Par exemple, les graphes déterministes et/ou aléatoires sont utilisés en physique, en sciences sociales (pour représenter des relations entre groupes d'individus), en mathématique combinatoire, en informatique (structures de données et algorithmique).

Concernant les très nombreuses applications, on peut citer : les réseaux électriques et transport d'énergie, le routage du trafic dans les réseaux de télécommunications et les réseaux d'ordinateurs, le routage de véhicules et l'organisation des tournées ou rotations, les problèmes de localisation et de placement (d'entrepôts, d'antennes, ...) , les problèmes d'ordonnancement de tâches et d'affectation de ressources...

2.Historique

« À Kœnigsberg, en Poméranie, il y a une île appelée Kneiphof; le fleuve qui l'entoure se divise en deux bras, sur lesquels sont jetés les sept ponts a, b, c, d, e, f, g. Cela posé, peut-on arranger son parcours de telle sorte que l'on passe sur chaque pont, et que l'on ne puisse y passer qu'une seule fois ? Cela semble possible, disent les uns; impossible, disent les autres. »C'est ainsi que commence le fameux Mémoire d'Euler : Solution problematis ad Geometriam situs pertinentis (1736).

La solution d'Euler est d'une très grande beauté......!

Ce Mémoire est un texte fondateur de ce qu'on connaît aujourd'hui comme la théorie des graphes.

Jusqu'en 1946, la théorie des graphes reste du domaine des mathématiques; les mathématiciens ayant associé leurs noms aux travaux les plus marquants sont, entre autres :

- au 19ème siècle : Kirchoff, Hamilton, Sylvester, Kempe, Lucas, Petersen, Tarry

- au 20ème siècle (1ère moitié) : Poincare, Sainte-Lagüe, Kuratowski, Hall, Polya, König, Tutte.

Des recherches militaires liées au conflit mondial de (1939 - 1945) naît la Recherche Opérationnelle provoquant un développement de la théorie des graphes comme modèles de problèmes concrets, cet aspect est encore renforcé, dans les années qui suivent, par le développement des Sciences économiques et de gestion. Les grands spécialistes de cette nouvelle orientation des graphes seront des auteurs tels que Kuhn, Dantzig, Ford, Fulkerson, Ghouila-Houry, Harary, Saaty, Bellmann, Roy, Berge, Faure, Kaufmann, etc...

Une troisième époque a été ouverte dans les années 1960, avec le développement des sciences de l'information et de la communication. Des informaticiens tels que Dijkstra, Knuth, Wirth, Sakharovitch, Gondran et beaucoup d'autres, participent au développement de l'algorithmique des graphes autant qu'à la modélisation de problèmes nés de ces nouvelles sciences en terme de graphes.

3.Relations graphes et informatique

Les relations entre graphes et informatique sont à double sens :

1. l'informatique, outil de résolution de problèmes de graphes.

2. les graphes, outil de modélisation de problèmes informatiques.

4.Concepts fondamentaux

Un graphe est un ensemble de points nommés (sommets ou nœuds), reliés par des traits (segments) ou flèches nommées arêtes ou arcs. L'ensemble des arêtes entre nœuds forme une figure similaire à un réseau.

4.1 Graphe orienté :

Un graphe orienté est un graphe G(S,A) où :

• S : ensemble fini d’éléments appelés sommets ou nœuds.

S = {s₁,...,s_n} où |S|= n (Le nombre de sommets d’un graphe s’appelle l’ordre d’un graphe).

• A : ensemble fini de paires ordonnées de sommets appelés arcs.

A ⊂ S x S = { (s,t) /s,t ∈ S }

Les arcs d'un graphe orienté constituent une relation sur l'ensemble de ses sommets.

Notation : On note l'arc (s,t) par s ---> t avec :

- s l'origine

- t l'extrémité

L'arc (s,s) est représenté par s->s , est une boucle.

4.2 Graphe non orienté :

Un graphe non orienté est un graphe G(S,A) où :

• S : ensemble fini d’éléments appelés sommets ou nœuds.

• A : ensemble fini de paires de sommets appelés arêtes.

A ⊂ S x S = { (s,t) /s,t ∈ S }

4.3 Graphe valué :

Un graphe valué orienté (non orienté) est un triplet G(S,A,V) où :

S : ensemble fini de sommets.

A : ensemble fini d’arcs (arêtes).

V : une fonction de coût, de valeur, de poids etc...

4.4 P-Graphe :

Un P-graphe est un graphe dans lequel il n’existe pas plus de p-arcs (p-arête) entre deux sommets, quelque soit s,t de S(G).

Exemple :

Un 1-graphe est un graphe tel que il ne peut exister plus d'un arc de la forme (s,t). Un multigraphe c'est l'inverse.

4.5 Fonctions Successeur/Prédécesseur :

Soit G=(S,A) un graphe orienté :

S = {s₀,...,s_n} où |S|= n , A = {a₀,...,a_p} où |A|= p et A ⊂ S x S = { (s,t) /s,t ∈ S }

Successeur noté Γ : S ---> P(S) Avec P(S) l'ensemble des sommets

s ---> Γ(s) = { t∈S / (s,t) ∈ A } = ensembles des successeur de s

Prédécesseur noté Γ ^-1 : S ---> P(S) Avec P(S) l'ensemble des sommets

t ---> Γ ^-1(s) = { s∈S / (s,t) ∈ A } = ensembles des prédécesseur de t

On remarque que, dans le cas d'un graphe non orienté, on a Γ = Γ ^-1

4.6 Arcs (arêtes) adjacents :

1. Deux arcs (arêtes) d'un graphe orienté (non orienté) sont adjacents si ils ont au moins une extrémité commune.

2. Deux sommets d'un graphe non orienté sont dit adjacents si il existe une arête les joignant.

3. Dans un graphe orienté, le sommet t est dit adjacent au sommet s si il existe un arc s--->t∈A.

4.7 Co-cycle d'un graphe :

Soit G = (S,A) un graphe orienté et soit X ⊂ S, on définit :

w⁺(X)= ensemble des arcs ayant leur origine dans X et l'autre extrémité dans X^c = S\X S privé de X

w⁺(X) = { a=(s,t)∈A / s∈X et t∈X^c }

w^-(X)= ensemble des arcs ayant leur extrémités dans X et leur origine dans X^c

w^-(X) = { a=(s,t)∈A / s∈X^c et t∈X }

On note w(X) = w⁺(X) + w^-(X) Co-cycle du graphe G

4.7 Degré et Demi-Degré :

Dans un graphe non orienté, le degré d'un sommet est le nombre d'arêtes que contient ce sommet.

Dans un graphe orienté, on distingue 2 type de degré :

Demi-Degré extérieur/sortant :

C'est le nombre d'arcs dont s est l'origine.

Il est noté d⁺(s) = |Γ(s)|

Demi-Degré intérieur/entrant :

C'est le nombre d'arcs dont s est l'extrémité.

Il est noté d^-(s) = |Γ ^-1(s)|

Dans un graphe orienté on a : d(s) = d⁺(s) + d^-(s).

Remarque : une boucle compte pour un degré entrant et sortant (1 pour un graphe non orienté).

5.Graphes particuliers

5.1 Graphe simple :

Un graphe est dit simple si :

- Il est sans boucle.

- Il n'a pas plus de un arc entre 2 sommets quelconque.

5.2 Sous Graphe :

Soit G=(S,A) un graphe. Le sous graphe de G engendré par S'⊂S est le graphe G' dont les sommets sont les éléments de S' et dont les arcs (arêtes) sont les arcs (arêtes) de G ayant leur 2 extrémités de S'.

G' = (S',A')

A' = { (s,t) ∈ S' x S' / (s,t) ∈ A }

5.3 Graphe partiel :

Le graphe partiel de G engendré par A' ⊂ A est le graphe G' = (S,A') dont les sommets sont les éléments de S et dont les arcs (arêtes) sont ceux de A' c'est à dire on élimine de G les arcs (arêtes) de A\A'

5.4 Graphe symétrique :

Un graphe est dit symétrique si pour toute paires de sommet (s,t)∈A on a (t,s)∈A.

5.5 Graphe antisymétrique :

Un graphe est dit antisymétrique si (s,t)∈A ⇒ (t,s)∉A.

5.6 Graphe complet :

Un graphe est dit complet si pour toute paire de sommet (s,t) il existe au moins un arc de la forme (s,t) ou (t,s) dans le graphe. C'est à dire que tous les sommets sont relié entre eux.

Dans le cas d'un graphe non orienté le graphe est dit complet si il existe au moins une arête (s,t) pour tout couple de sommets (s,t) ∈ S.

5.7 Graphe vide :

On appelle graphe vide tout graphe qui ne contient aucun arcs (arête).

C'est à dire G = (S,A) et A = ∅

5.8 Graphe bi-partie :

On dit qu'un graphe est Bi-parti si l'ensemble des sommets S peut être partitionné en 2 sous ensemble S₁ et S₂ de telle sorte que pour tout arcs (arête) (s,t) ∈ A :

s ∈ S₁ => t ∈ S₂

_{s ∈ S2 => t ∈ S1}

5.9 Graphe planaire :

On qualifie de graphe planaire tout graphe pouvant être dessiné sans que les arêtes (arcs) se croisent.

5.10 clique :

Un graphe non orienté est dit une clique s'il est un graphe simple pour lequel il existe exactement une arête entre toute paire de sommet.

T1: Expliquer la solution d'Euler