Quelques définitions
[Français | English]
Vocabulaire de base
Un graphe est une paire d'ensemble (V,E) où E est une famille de paires (orientées ou non) d'éléments de V.
Un graphe est dit complet si toute paire de sommets de G est une arête.
Une clique de G est un sous-graphe complet de G.
Un stable de G est un sous-graphe de G sans arêtes.
Le degré d'un sommet de G est le nombre des arêtes qui lui sont incidentes.
Un graphe est connexe lorsqu'il existe un chemin entre chaque paire de sommets.
Un hypergraphe est une paire d'ensembles (V,F) où F est une famille de sous-ensembles de V. Voir par exemple le livre de Berge, ou le chapitre écrit par Pierre Duchet dans l'ouvrage collectif Handbook of Combinatorics.
Quelques invariants combinatoires
La taille de la plus grande clique de G est notée
omega(G).
La taille du plus grand stable de
G est notée alpha(G).
Problèmes d'absorption
Dans un graphe G non-orienté (resp. orienté) un ensemble absorbant est un ensemble de sommets A tel que tout sommet hors de A a au moins un voisin (resp. successeur) dans A. Le nombre d'absorption de G noté gamma(G), est la taille d'un plus petit absorbant de G. Déterminer la valeur de gamma(G) est un problème NP-difficile, même si G est biparti.
Dans un graphe orienté un noyau est un ensemble stable et absorbant. Déterminer si un graphe possède un noyau est un problème NP-complet.
Pour ces deux notions voir Berge.
Coloration, Graphes Parfaits
Dans un graphe (voire un hypergraphe) G = (V, E) une k-coloration est une affectation d'une couleur de l'ensemble des couleurs {1, ..., k} à chaque sommet de telle sorte que, pour toute arête uv de G, les sommets u et v ont une couleur différente (pour un hypergraphe on exige que chaque arête porte au moins deux couleurs). Un graphe est dit k-colorable s'il admet une k-coloration.
Déterminer si un graphe est k-colorable est un problème NP-complet pour toute valeur fixée de k (si k vaut au moins 3) [REF: Garey & Johnson].
De nombreux problèmes ouverts sur la coloration sont présentés dans le livre de Jensen et Toft.
Le nombre chromatique de G, noté Chi(G), est le plus petit entier k tel que G est k-colorable.
Sur le thème de la coloration, on visitera avec intérêt la page de Joseph Culberson à l'Université de l'Alberta (Canada).
Un graphe G est parfait si, pour tout sous-graphe H induit de G, le nombre chromatique de H est égal à la taille d'une clique maximum de H, c'est-à-dire, Chi(H)=omega(H). Pour les graphes parfaits voir Golumbic ou Berge & Chvátal.
Flot
Dans un graphe orienté G un flot est l'affectation d'une valeur réelle à chaque arc de G, représentant une quantité de matière transportée sur cet arc, de telle sorte qu'en chaque sommet la somme des flots entrants soit égale à la somme des flots sortants (loi de Kirchhoff).
On se donne habituellement une capacité maximale sur chaque arc, qui sera une borne supérieure sur le flot autorisé sur cet arc; le problème du flot maximum est alors de trouver un flot dont la valeur sur un certain arc donné (source et puits) est maximum.
On peut de plus se donner un coût de transport d'une unité de flot sur chaque arc, et chercher un flot (maximum) de coût minimum.
Ces problèmes sont bien résolus algorithmiquement, depuis le travail pionnier de Ford et Fulkerson conduisant à des algorithmes polynomiaux, et ont de nombreuses applications et généralisations - voir par exemple le livre récent de Ahuja, Magnanti, Orlin.
Connectivité
Un graphe G est k-sommet-connexe (resp. k-arête-connexe) s'il faut ôter au moins k sommets (resp. k arêtes) pour le rendre non-connexe. La connectivité (par sommets ou bien par arêtes) du graphe est le plus grand k tel que G est k-connexe. Ces nombres peuvent être calculés en temps polynomial; en fait on réduit habituellement la résolution des problèmes de connectivité à des problèmes de flots.
Récemment, de nouveaux résultats (Karger; Nagamochi et Ibaraki; Frank) permettent de calculer la connectivité d'un graphe sans avoir recours aux méthodes de flots.
Produits de graphes
Le produit carré de G et H, est le graphe dont l'ensemble des sommets est le produit cartésien de V(G) par V(H), et le couple (ax, by) est une arête du produit si et seulement si soit x=y et ab est une arête de G, soit a=b et xy est une arête de H.
Par exemple, la grille est le produit carré de deux chaînes.
Le produit croisé de G et H, est le graphe dont l'ensemble des sommets est le produit cartésien de V(G) par V(H), et le couple (ax, by) est une arête du produit si et seulement si ab est une arête de G et xy est une arête de H.
Hamiltonicité
Un cycle hamiltonien d'un graphe G est un cycle élémentaire passant par tous les sommets de G. Un graphe est hamiltonien s'il possède un cycle hamiltonien comme sous-graphe. Déterminer si un graphe est hamiltonien est un problème NP-complet. Voir l'article de Gould pour un survey récent sur les questions d'hamiltonicité.
Le problème du voyageur de commerce est de parcourir un réseau en passant au moins une fois en chaque sommet et en minimisant la distance totale, étant donné que chaque arête a une certaine longueur. Voir le livre de Lawler, Lenstra, Rinnooy Kan & Schmoys.
Problèmes eulériens
Un parcours est eulérien s'il passe exactement une fois par chaque arête. Un graphe est dit eulérien s'il admet un tel parcours fermé, ce qui revient à être connexe et avoir tous ses degrés pairs (ceci est un théorème d'Euler, souvent considéré comme le 1er théorème de la théorie des graphes). Le livre de Fleischner aborde de nombreuses questions et généralisations sur ce sujet.
La ville de Königsberg (maintenant Kaliningrad) avait sept ponts sur la rivière Pregel. Les amateurs de questions mathématiques et de promenades digestives se demandaient s'il était possible de faire un tour dans la ville en passant une fois exactement sur chaque pont. Euler, en construisant le graphe représentatif, constata qu'il avait des sommets de degré impair et démontra que cela rendait impossible une telle promenade.
Le problème dit du postier chinois est de parcourir les rues d'une ville en passant au moins une fois dans chaque rue, le réseau n'étant pas nécessairement eulérien; on cherche bien sur à minimiser le parcours total. Voir Lovász & Plummer, ou Ahuja, Magnanti & Orlin.
Planarité
On dit qu'un graphe G est planaire si l'on peut le représenter sur un dessin de sorte que les arêtes forment des lignes qui ne se croisent pas. Kuratowski a donné une caractérisation des graphes planaires par "mineurs" exclus. Il existe plusieurs algorithmes polynomiaux pour déterminer si un graphe est planaire, et , lorsqu'il l'est, pour trouver une représentation planaire. Voir par exemple le livre récent de Nishizeki et Chiba.
Une carte de géographie peut être modélisée par un graphe planaire dont les sommets sont les régions et dont les arêtes sont les paires de régions voisines. On désire colorer les régions d'une telle carte de sorte que des régions voisines aient des couleurs différentes. Empiriquement, il est connu des cartographes depuis longtemps que quatre couleurs suffisent pour une telle tâche. Cependant, malgré diverses tentatives ratées, la 1ère preuve mathématique de ce problème des quatre couleurs n'est apparue qu'en 1976, par Appel et Haken, et elle utilise un ordinateur pour la vérification de nombreux cas. Une preuve plus récente et plus compacte, mais dans le même esprit, a été donnée par Robertson, Seymour, Thomas et Sanders.
Couplage
Un couplage est un ensemble d'arêtes deux à deux non-adjacentes. On sait trouver en temps polynomial un couplage de taille (ou même de poids) maximum. Depuis les travaux de König, Hall, Tutte, Edmonds, Gallai, Lovász, et bien d'autres, la théorie du couplage est très riche, voir par exemple le livre de Lovász & Plummer.