Accueil |

Théorie des graphes

            

Les graphes sont des objets mathématiques permettant une représentation intuitive d'une relation binaire transitive entre des éléments d'un ensemble.

Définition : Un graphe est un couple (V,E), V étant un ensemble et E une partie de Và—V (produit cartésien d'ensembles).
Les éléments de V sont appelés les sommets .

On distingue deux types de graphes:

Quand on parle de graphes sans en préciser le type, il s'agit de graphes non orientés.

Graphiquement, une relation entre deux sommets d'un graphe orienté est représentée à  l'aide d'une flèche entre ceux-ci. Dans le cas d'un graphe non orienté, c'est un trait qui symbolise cette relation.

Exemple : le réseau routier est un graphe dont les sommets sont les villes et les arêtes les routes qui mènent directement d'une ville à  une autre sans passer par une ville intermédiaire.

La théorie des graphes étudie les propriétés de ces objets. Parmi les problèmes classiques figurent :

Cette théorie est fortement liée à  l'algorithmique et à  la complexité.

Sommaire
1 Définitions
2 Algorithmes importants de la théorie des graphes

Définitions

Arbre

Un arbre est un graphe connexe acyclique.

Arbre couvrant minimal

Un arbre couvrant minimal est un arbre couvrant d'un graphe pondéré dont la somme des poids des arêtes est minimal.

Valuation d'un graphe

Une valuation d'un graphe est une fonction qui, à  chaque arête, associe un poids (nombre réel).

Exemple : Si on reprend le réseau routier, une valuation possible est la longueur de la route.

Chemins et chaînes

Dans un graphe orienté, un chemin entre deux sommets a et b est une suite finie de n sommets (si) tels que a = s1, b = sn et pour tout i dans [1, n-1] il existe une arête entre si et si+1. Un chemin est dit élémentaire si un sommet y est présent au plus une fois. Dans le cas d'un graphe non-orienté, on parle de chaîne.

Cycles et circuits

Si un sommet est à  la fois premier et dernier d'un chemin, alors ce chemin forme un circuit (graphe non-orienté). Dans le cas d'un graphe orienté, on dit qu'il forme un cycle.

Graphe connexe

Un graphe non orienté est connexe, si et seulement si pour toute paire de sommets [a,b] il existe une chaîne entre les sommets a et b. Si on parle de connexité pour un graphe orienté, c'est que l'on considère non pas ce graphe, mais le graphe non-orienté correspondant.

Graphe k-connexe

Un graphe non orienté est k-connexe si il reste connexe après suppression d'un ensemble quelconque de k-1 arêtes et si il existe un ensemble de k arêtes qui déconnecte le graphe. Autrement dit, un graphe est k-connexe si et seulement si il existe au moins k chaînes indépendantes (arcs-disjointes) entre chaque couple de sommets.

Graphe fortement connexe

Un graphe orienté est dit fortement connexe, si pour tout couple de sommets (u,v) du graphe il existe un chemin de u à  v et de v à  u.

Sous graphe

Soit G=(V,E) un graphe, un sous-graphe de G, est un graphe G'=(V',E'), oà¹:

Si , G' est sous-graphe couvrant.
Si G' est un sous-graphe partiel.
Si , G' est un sous-graphe induit.

Graphe complet

Un graphe complet est un graphe dont tous les sommets sont reliés deux à  deux. Le graphe complet à  n sommets est noté: .

Graphe planaire

Un graphe est planaire si il existe au moins une façon de le dessiner dans le plan sans que deux arêtes se croisent.

Clique

Une clique est un sous-graphe complet. Une p-clique est une clique de p sommets.

Stable

Un stable est un sous-graphe sans arêtes.

Algorithmes importants de la théorie des graphes

Algorithmes de plus court chemin

Algorithme d'arbres couvrant minimaux

Algorithme pour les flots maximums

Algorithmes de parcours de graphe

Algorithmes divers