vignette|Un tracé de graphe.
La théorie des graphes est la discipline mathématique et informatique qui étudie les graphes, lesquels sont des modèles abstraits de dessins de réseaux reliant des objetsIl existe d'autres objets mathématiques portant le même nom, par exemple les graphes de fonctions, mais ceux-ci n'ont que peu de rapports avec les graphes étudiés ici.. Ces modèles sont constitués par la donnée de sommets (aussi appelés nœuds ou points, en référence aux polyèdres), et d'arêtes (aussi appelées liens ou lignes) entre ces sommets ; ces arêtes sont parfois non symétriques (les graphes sont alors dits orientés) et sont alors appelées des flèches ou des arcs.
Les algorithmes élaborés pour résoudre des problèmes concernant les objets de cette théorie ont de nombreuses applications dans tous les domaines liés à la notion de réseau (réseau social, réseau informatique, réseaux de neurones et intelligence artificielle, télécommunications) et dans bien d'autres domaines (par exemple génétique) tant le concept de graphe, à peu près équivalent à celui de relation binaire (à ne pas confondre donc avec graphe d'une fonction), est général. De grands théorèmes difficiles, comme le théorème des quatre couleurs, le théorème des graphes parfaits, ou encore le théorème de Robertson-Seymour, ont contribué à asseoir cette matière auprès des mathématiciens, et les questions qu'elle laisse ouvertes, comme la conjecture de Hadwiger, en font une branche vivace des mathématiques discrètes.
Définitions
vignette|Un graphe orienté avec trois sommets et quatre arcs. Un graphe est un couple comprenant deux ensembles :
: sommets ; : arêtes, chacune étant associée à un couple ou une paire de sommets ().
Il y a plusieurs principaux types de graphes :
Dans un graphe non orienté, les arêtes n'ont pas d'orientation et sont donc associées à une paire . Dans un graphe orienté, les arêtes sont appelées arcs et ont une orientation de vers ; elles sont ainsi associées au couple . Un graphe mixte comporte à la fois des arêtes et des arcs, on le définit alors plutôt comme le triplet . Un graphe simple est un graphe ne comportant ni boucles ni multi-arêtes, c'est-à-dire qu'aucun sommet n'est connecté à lui-même, et entre deux sommets il n'existe qu'une seule arête. Dans un graphe pondéré (ou valué), à chaque arête est associé un nombre (son poids), représentant par exemple une distance, un coût ou une capacité.
Deux sommets reliés par une arête sont dits voisins ou adjacents.
Topologies
vignette|Principales topologies typiques de graphes. vignette|Topologie typique d'un réseau multipolaire.
Il existe trois grandes familles de graphes et cinq catégories au total : structurés : il est alors possible de définir quatre identités topologiques remarquables : homogènes (1) : les sommets et les arêtes reproduisent un schéma régulier. Le schéma le plus commun est une architecture de type matriciel aussi appelée « en filet de poisson » (mesh) ; hiérarchiques (2) : structure typique des graphes où les sommets s'arrangent en couches hiérarchisées et pyramidales ; cycliques (3) : on peut identifier des cycles dans le graphe. L'exemple le plus parlant est le graphe circulaire ; centralisés ou polaires (4) : c'est une architecture où tous les sommets sont rattachés à un seul sommet, le pôle ; quelconques (5) : aucune propriété topologique ne semble émerger ; multipolaires : c'est une architecture mixte entre les graphes centralisés et décentralisés. Les réseaux multipolaires sont très étudiés en raison de leur proximité avec de nombreux cas concrets, notamment Internet ou les réseaux de neurones. Les graphes multipolaires sont caractérisés par deux types d'arêtes : celles qui forment les liens émanant du pôle : les liens forts ; et les liens réunissant deux pôles entre eux : les liens faibles. Les pôles peuvent par ailleurs prendre une architecture structurée (souvent centralisée) ou quelconque.
Origines et histoire
Un article du mathématicien suisse Leonhard Euler, présenté à l'Académie de Saint-Pétersbourg en 1735 puis publié en 1741, traitait du problème des sept ponts de Königsberg Leonhard Euler - Solutio problematis ad geometriam situs pertinentis, Commentarii academiae scientiarum Petropolitanae 8, 1741, pages 128-140., ainsi que schématisé ci-dessous. Le problème consistait à trouver une promenade à partir d'un point donné qui fasse revenir à ce point en passant une fois et une seule par chacun des sept ponts de la ville de Königsberg. Un chemin passant par toute arête exactement une fois fut nommé chemin eulérien, ou circuit eulérien s'il finit là où il a commencé. Par extension, un graphe admettant un circuit eulérien est dit graphe eulérien, ce qui constitue donc le premier cas de propriété d'un graphe. Euler avait formuléAu regard des mathématiques modernes, la formulation d'Euler est une conjecture puisque le résultat est énoncé sans preuve. Cependant, les mathématiques en son temps ne présentaient pas la même rigueur : tandis que conjecturer un résultat signifie maintenant que l'on renonce à le démontrer, pour Euler l'absence d'une preuve peut signifier que celle-ci n'était pas considérée utile. qu'un graphe n'est eulérien que si chaque sommet a un nombre pair d'arêtes. L'usage est de s'y référer comme théorème d'Euler, bien que la preuve n'en ait été apportée que 130 ans plus tard par le mathématicien allemand Carl Hierholzer Carl Hierholzer, « Über die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren », dans Mathematische Annalen, vol. 6, 1873, .. Un problème similaire consiste à passer par chaque sommet exactement une fois, et fut d'abord résolu avec le cas particulier d'un cavalier devant visiter chaque case d'un échiquier par le théoricien d'échecs arabe Al-Adli dans son ouvrage Kitab ash-shatranj paru vers 840 et perdu depuis Martin G. - The arab role in the development of Chess, Al Shindagah 45, Mars-Avril 2002. Ce problème du cavalier fut étudié plus en détail au par les mathématiciens français Alexandre-Théophile VandermondeAlexandre-Théophile Vandermonde, « Remarques sur des problèmes de situation », dans Mémoires de l’Académie Royale des Sciences, 1771, . Références par LJ.Rossia.org, Pierre Rémond de Montmort et Abraham de Moivre ; le mathématicien britannique Thomas Kirkman étudia le problème plus général du parcours où on ne peut passer par un sommet qu'une fois, mais un tel parcours prit finalement le nom de chemin hamiltonien d'après le mathématicien irlandais William Rowan Hamilton, et bien que ce dernier n'en ait étudié qu'un cas particulier William Tutte - Graph theory as I have known it, Oxford Science Publications, Clarendon Press, 1998, . Chapitre 2 : Knight Errant.. On accorde donc à Euler l'origine de la théorie des graphes parce qu'il fut le premier à proposer un traitement mathématique de la question, suivi par Vandermonde.
180px → 179px → 180px
vignette|Liste des arbres à 2, 3 et 4 sommets.
Au milieu du , le mathématicien britannique Arthur Cayley s'intéressa aux arbres, qui sont un type particulier de graphe n'ayant pas de cycle, i.e. dans lequel il est impossible de revenir à un point de départ sans faire le chemin inverse. En particulier, il étudia le nombre d'arbres à sommets Arthur Cayley, « On the Theory of the Analytical Forms called Trees », dans Phil. Mag., 1857, . et montra qu'il en existe . Ceci constitua « une des plus belles formules en combinatoire énumérative »Martin Aigner et Günter M. Ziegler, « La formule de Cayley pour le nombre d’arbres », dans Raisonnements divins, éd., 2006, domaine consistant à compter le nombre d'éléments dans un ensemble fini, et ouvrit aussi la voie à l'énumération de graphes ayant certaines propriétés. Ce champ de recherche fut véritablement initié par le mathématicien hongrois George Pólya, qui publia en 1937 le théorème de dénombrement qui porte son nom, et le mathématicien néerlandais Nicolaas Govert de Bruijn. Les travaux de Cayley, tout comme ceux de Polya, présentaient des applications à la chimie et le mathématicien anglais James Joseph Sylvester, coauteur de Cayley, introduisit en 1878 le terme de « graphe » basé sur la chimie :
vignette|Équivalence entre les régions d'une carte et un graphe pour le théorème des quatre couleurs.
Un des problèmes les plus connus de théorie des graphes vient de la coloration de graphe, où le but est de déterminer combien de couleurs différentes suffisent pour colorer entièrement un graphe de telle façon qu'aucun sommet n'ait la même couleur que ses voisins. En 1852, le mathématicien sud-africain Francis Guthrie énonça le problème des quatre couleurs lors d'une discussion avec son frère qui demandera à son professeur Auguste De Morgan si toute carte peut être coloriée avec quatre couleurs de façon que des pays voisins aient des couleurs différentes. De Morgan envoya d'abord une lettre au mathématicien irlandais William Rowan Hamilton, qui n'était pas intéressé, puis le mathématicien anglais Alfred Kempe publia une preuve erronée Alfred Bray Kempe, « On the Geographical Problem of the Four Colours », dans American Journal of Mathematics, vol. 2, , septembre 1879, . dans l’American Journal of Mathematics, qui venait d'être fondé par Sylvester. L'étude de ce problème entraîna de nombreux développements en théorie des graphes par Peter Guthrie Tait, Percy John Heawood, Frank Ramsey et Hugo Hadwiger.
Les problèmes de factorisation de graphe émergèrent ainsi à la fin du en s'intéressant aux sous-graphes couvrants, c'est-à-dire aux graphes contenant tous les sommets mais seulement une partie des arêtes. Un sous-graphe couvrant est appelé un -facteur si chacun de ses sommets a arêtes et les premiers théorèmes furent donnés par Julius Petersen Julius Petersen, « Die Theorie der regulären Graphen », dans Acta Mathematica, vol. 15, 1891, . ; par exemple, il montra qu'un graphe peut être séparé en 2-facteurs si et seulement si tous les sommets ont un nombre pair d'arêtes (mais il fallut attendre 50 ans pour que Bäbler traite le cas impair F. Bäbler, « Über die Zerlegung regulärer Streckencomplexe ungerader Ordnung », dans Comment. Math. Helv., vol. 10, 1938, .). Les travaux de Ramsey sur la coloration, et en particulier les résultats du mathématicien hongrois Pal Turan, permirent le développement de la théorie des graphes extrémaux s'intéressant aux graphes atteignant le maximum d'une quantité particulière (par exemple le nombre d'arêtes) avec des contraintes données Bela Bollobas, Extremal Graph Theory, Dover, 2004, telles que l'absence de certains sous-graphes.
Dans la seconde moitié du , le mathématicien français Claude Berge contribue au développement de la théorie des graphes par ses contributions sur les graphes parfaits Claude Berge, « Some classes of perfect graphs », dans « Six papers on Graph Theory », Indian. Statistical Institute, Calcutta, 1969, . et l'introduction du terme d’hypergraphe (à la suite de la remarque de Jean-Marie Pla l'ayant utilisé dans un séminaire) avec une monographieClaude Berge, Graphes et hypergraphes, Dunod, 1970 sur le sujet. Son ouvrage d'introduction à la théorie des graphesClaude Berge, Théorie des graphes et ses applications, Dunod, 1958 proposa également une alternative originale, consistant plus en une promenade personnelle qu'une description complète. Il marquera également la recherche française en ce domaine, par la création conjointe avec Marcel-Paul Schützenberger d'un séminaire hebdomadaire à l'Institut Henri Poincaré, des réunions le lundi à la Maison des Sciences de l'Homme, et la direction de l'équipe Combinatoire de Paris.
Graphes et intelligence artificielle