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:
- les graphes non orientés, o๠la relation binaire entre sommets est symétrique ; les éléments de A sont des paires de sommets (il n'y a pas de relation d'ordre), et se nomment arêtes.
- les graphes orientés, o๠la relation binaire n'est pas symétrique ; les éléments de E sont des couples de sommets (relation d'ordre) et se nomment arcs.
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 :
- l'accessibilité, existe-t-il un chemin reliant deux sommets ?
- arbres couvrants de poids minimaux
- le plus court (respectivement long) chemin entre deux sommets d'un graphe valué
- la coloration de graphe avec un nombre fixé de couleurs
- les sous-graphes denses maximaux (parfois appelés cliques)
- les problèmes de flots maximaux ou minimaux
- allocations de ressources
- le problème du voyageur de commerce
- le problème du postier chinois
- décomposition d'un graphe en niveaux
- ...
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.
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.
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.
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.
Soit G=(V,E) un graphe, un sous-graphe de G, est un graphe G'=(V',E'), oà¹:
Un graphe complet est un graphe dont tous les sommets sont reliés deux à deux. Le graphe complet à n sommets est noté: .
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.
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
Chemins et chaînes
Cycles et circuits
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
Sous graphe
Si , G' est sous-graphe couvrant.
Si G' est un sous-graphe partiel.
Si , G' est un sous-graphe induit.Graphe complet
Graphe planaire
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
