théorie des graphes
Née des recherches d'Euler au xviiie s., la théorie des graphes est devenue une branche des mathématiques au début du xxe s., grâce aux travaux de König, de Kuratowski, de Cayley et, plus récemment, de Berge, d'Erdös et de Harary.
Les recherches récentes en informatique et surtout en algorithmique lui donnent un nouveau souffle. La théorie des graphes permet de résoudre efficacement une grande variété de problèmes pratiques ou récréatifs en les ramenant à des configurations qui se dessinent simplement à l'aide de points et de liaisons entre ces points.
La théorie des graphes
On fait généralement remonter la théorie des graphes au problème dit « des ponts de Königsberg » (Kaliningrad). Résolu par Leonhard Euler en 1736, ce problème, à l'allure de casse-tête, s'énonce ainsi : est-il possible, en partant d'une zone de la ville, de retourner dans la même zone en traversant chacun de ses sept ponts une fois et une seule ?
La théorie des graphes sert avant tout à représenter et à organiser les tâches de façon optimale : après avoir traduit un problème sous forme de graphe, on cherche des méthodes systématiques qui permettent de trouver la succession la plus rapide ou la moins coûteuse pour effectuer toutes les tâches.
De fait, ses applications pratiques sont très diverses : optimisation des réseaux de transport – transports routiers ou transports d'information –, conception de réseaux électriques, de réseaux de communication, mécanique statistique, formules chimiques, informatique théorique, sciences sociales, géographie, architecture…
Qu'est-ce qu'un graphe ?
C'est en 1822 que le mot « graphe » est introduit par l'Anglais J.J. Sylvester, et en 1936 que paraît le premier livre sur la théorie des graphes, écrit par D. König. Un graphe est un dessin géométrique défini par la donnée d'un ensemble de points (appelés sommets ou nœuds), reliés entre eux par un ensemble de lignes ou de flèches (appelées arêtes ou arcs). Chaque arête a pour extrémités deux points, éventuellement confondus. Le graphe est dit orienté si, pour chaque arête, on distingue une extrémité initiale et une extrémité terminale.
Les propriétés des graphes caractérisent différents types de problèmes :
– un graphe est dit complet lorsque deux sommets quelconques et distincts sont reliés par une et une seule arête ;
– un graphe est dit connexe si l'on peut relier deux sommets quelconques du graphe par une suite continue d'arêtes.
Un arbre est un graphe connexe qui ne contient pas de chemin fermé. Des exemples d'utilisation d'arbres, ou arborescences, se trouvent dans la gestion des bases de données. Connaître l'arbre suivant lequel sont organisées les informations facilite et optimise leur consultation. La mise en structure parallèle des ordinateurs se fait suivant une procédure d'ordonnancement des tâches : c'est actuellement un domaine de recherches extrêmement actif en informatique mathématique.
Les graphes planaires
Un graphe est dit planaire si on peut le dessiner sur une surface topologiquement plane de telle façon que les arêtes ne se coupent pas. Ce type de graphe est particulièrement utilisé dans les problèmes de circuits imprimés (ces circuits, construits sur des surfaces planes, constituent actuellement l'une des limitations des développements de l'informatique).
Le problème récréatif classique des trois puits et des trois maisons a permis au Polonais Kazimierz Kuratowski de trouver en 1930 une caractérisation des graphes planaires : un graphe est planaire si et seulement si sa configuration ne contient pas trois nœuds reliés à trois autres nœuds, ou cinq nœuds tous reliés aux quatre autres.
Une autre application des graphes planaires est constituée par la représentation des polyèdres sous forme de graphes. Il existe pour cela deux méthodes :
– dessiner les sommets et les arêtes du polyèdre lorsqu'on le regarde par un trou fait en un sommet (on obtient un graphe ouvert comportant des arêtes qui n'ont qu'une extrémité) ;
– dessiner le polyèdre lorsqu'on le regarde à travers une face (on obtient alors un graphe fermé).
Par ailleurs, les graphes planaires vérifient la formule d'Euler-Poincaré reliant le nombre S de sommets, le nombre F de faces (ou régions) au nombre A d'arêtes : S + F = A + 2. Cette formule est aussi valable pour tous les polyèdres convexes.
Flots et tensions dans la théorie des graphes
La théorie des graphes connaît également de nombreuses applications pratiques dans le domaine de la gestion, qui utilise des graphes dits valués. Les arêtes ou les sommets du graphe sont affectés d'un paramètre économique correspondant à certaines contraintes : coûts (transport, distances, durées de travaux, stocks…) ou débits (circulation automobile, courant électrique, débits de ventes, informations binaires…).
Deux types de problèmes caractérisent ce domaine : celui de l'ordonnancement des tâches et celui du voyageur de commerce.
Graphes et problème d'ordonnancement de tâches
L'ordonnancement de tâches consiste à planifier les différentes tâches conduisant à la réalisation d'un produit sur une chaîne de fabrication ou d'un grand projet de construction. Chaque sommet du graphe est associé à un nombre qui caractérise un événement (date ou durée limite de réalisation, par exemple). Les arêtes peuvent porter, elles aussi, des valeurs correspondant à d'autres contraintes (temps minimal entre deux événements, par exemple). On a un problème de tension type : trouver un chemin optimal ou un chemin critique entre le début et la fin du processus.
Un problème de graphes : le voyageur de commerce
Le voyageur de commerce doit trouver le plus court chemin qui, partant d'une ville, y revient en passant par toutes les autres villes. Les arêtes portent des valeurs correspondant à des distances, qui peuvent être mesurées en temps, en coûts de parcours, en débits d'électricité ou d'eau… Ce type de problème a des solutions d'autant plus longues à trouver que le nombre de villes est grand. Si avec 10 villes il faut, par exemple, 64 étapes de calculs (réalisées en une microseconde par un ordinateur), avec 100 villes, il faudrait 264 étapes de calculs, qui mobiliseraient un ordinateur pendant des centaines d'années.
Des algorithmes efficaces
Des algorithmes permettent de trouver une solution optimale à ces problèmes, avec une efficacité fonction du nombre de paramètres. Citons les plus connus :
– la méthode du chemin critique, qui détermine les marges de manœuvre en chaque nœud ;
– la méthode PERT (program evaluation and research task), qui permet de trouver des chemins solutions dans les problèmes de tension en introduisant, pour mesurer les durées de travail en chaque poste, une valeur moyenne calculée à partir de probabilités optimiste et pessimiste. Sans obtenir encore des solutions exactes, on aboutit à des solutions approchées très satisfaisantes.
Calculabilité et complexité selon la théorie des graphes
La théorie des graphes illustre une démarche mathématique de résolution de problèmes qui connaît aujourd'hui de nombreux développements grâce à l'informatique. On distingue, dans cette démarche, trois étapes :
– montrer qu'il y a une ou plusieurs solutions possibles au problème posé ;
– montrer que cette solution est calculable à l'aide d'un algorithme que l'on pourra programmer ;
– s'assurer que cet algorithme est efficace, qu'il conduit à la solution dans un temps de calcul raisonnable, qui n'augmente pas de façon exponentielle en fonction du nombre de paramètres.
Cette dernière étape est un domaine des recherches mathématiques qui s'est développé depuis 1935, à partir des travaux de K. Gödel, A. Church et A. Turing.
Des problèmes aussi voisins apparemment que les chemins eulériens ou les chemins hamiltoniens sont des problèmes de complexité très différente. La recherche de chemins solutions dans chaque type de problème conduit à des algorithmes d'efficacité fort différente. Les chemins eulériens se trouvent grâce à des algorithmes qui ont des temps de calcul raisonnables : ils correspondent à des problèmes de faible complexité. Les chemins hamiltoniens se trouvent grâce à des algorithmes dont les temps de calcul augmentent de façon exponentielle avec le nombre de sommets à relier : ils répondent à des problèmes algorithmiques difficiles, appelés problèmes complexes. On remarquera que les problèmes eulériens ont une caractérisation simple, alors qu'il n'en est pas de même pour les problèmes hamiltoniens.
Les derniers développements de la théorie des graphes
Depuis les années 1930, et de plus en plus au cours des vingt dernières années, la théorie des graphes connaît des développements très importants, tant sur le plan théorique que sur celui des applications. Une grande variété de problèmes sont abordés par l'étude de graphes associés :
– étude des parcours eulériens ou hamiltoniens ;
– étude des graphes planaires et représentation sur différentes surfaces ;
– propriétés algébriques des graphes (flots et tensions) ;
– problème de coloriage de graphes (dont le théorème des quatre couleurs, démontré par Appel et Haken en 1976, est le plus célèbre exemple) ;
– enfin, certains concepts de graphes peuvent être étendus avec succès aux familles d'ensembles, ce sont les hypergraphes.
La théorie des graphes a de nombreux liens avec la plupart des autres domaines des mathématiques discrètes : la combinatoire, la théorie des ensembles, la théorie des groupes, l'algèbre linéaire, la théorie des polyèdres, la programmation linéaire, la théorie des jeux, l'algorithmique…