Inaugurée par Euler au xvme siècle, la théorie des graphes a pour objet de modéliser des situations concrètes complexes à l’aide de représentations graphiques, de permettre de manipuler ces objets plus simples et de répondre à des questions d’optimisation que ces situations posent.
COMMENT OPTIMISER
La théorie des graphes est une boîte à outils mathématiques qui permet de résoudre des situations concrètes et complexes, telles que les interconnexions routières entre plusieurs villes ou les liens entre les composants d’un circuit électronique. Les graphes modélisent la structure d’une situation et permettent de manipuler plus facilement les objets et leurs relations à l’aide d’une représentation graphique relativement naturelle. Il est alors possible de répondre à des questions du type : quel est le plus court chemin pour se rendre d’une ville à une autre? Comment minimiser la longueur totale des connexions d’un circuit? La théorie des graphes offre des réponses à des problèmes d’optimisation. Depuis le début du xxe siècle, elle constitue une branche à part entière des mathématiques, grâce aux travaux de mathématiciens tels que Kbnig, Cayley ou Erdôs. L’algorithmique étant un outil important ici, nombre d’informaticiens travaillent à son développement
ORDRE ET MULTIGRAPHE
L’outil fondamental de la théorie des graphes est tout naturellement le graphe. Un graphe est défini comme un couple (V, E) où V est un ensemble fini d’objets (les sommets du graphe) et E est un sous-ensemble de V x V (les éléments de E sont appelés les « arêtes » du graphe). Les arêtes sont donc définies comme un couple de sommets (et non pas comme un segment joignant deux sommets comme en géométrie, car sa forme géométrique n’a pas d’importance). Les sommets sont appelés les « extrémités » de l’arête, et leur nombre définit ce que l’on nomme l’« ordre » du graphe. Ici, seule une arête relie deux sommets ; on parle alors de « graphe simple ». Dans le cas contraire, on parlera de « multigraphe ».
On parlera de « graphe non orienté » lorsque l’on ne spécifie pas d’ordre dans les extrémités. On considérera que le graphe est orienté si l’un des sommets est spécifié comme l’extrémité initiale et l’autre comme l’extrémité finale. Par exemple, le graphe représentant tournoi de tennis est graphe non orienté.
LES PONTS DE KONIGSBERG
Le mathématicien Euler est considéré comme le père de la théorie des graphes. Il habitait à Konigsberg, ville qui possédait sept ponts. Les habitants se demandaient s’il était possible de partir d’un point quelconque de la ville et d’y revenir en ne traversant qu’une seule fois chaque pont. Euler étudia ce problème en le représentant sous forme de graphe. On voit bien qu’au-delà de la représentation graphique du problème apparaît une autre notion fondamentale en théorie des graphes : la notion de chemin. Un chemin est une liste de sommets telle qu’il existe dans le graphe une arête entre chaque paire de sommets successifs. Sa longueur correspond au nombre d’arêtes parcourues. Pour faire écho au problème posé à Euler, on définit un chemin simple par le fait que chaque arête du chemin n’est empruntée qu’une seule fois, et un cycle comme un chemin simple finissant à son point de départ. Ainsi énoncées, les conditions d’apparition d’un cycle permettent de répondre à la question ici posée.
LA NOTION DE CONNEXITÉ
Une autre question que l’on pourrait se poser face à un graphe est de savoir si, depuis un sommet quelconque, il existe un chemin pour atteindre tout autre sommet. La notion de connexité permet d’y répondre. Un graphe est connexe si et seulement si il existe un chemin entre chaque paire de sommets. Lorsque le graphe n’est pas connexe, on peut s’en sortir en considérant ses composantes connexes. Un graphe non connexe apparaît en effet comme un ensemble de graphes connexes les uns à côté des autres, chacun étant un sous-graphe particulier du graphe d’origine. Ils sont les composantes connexes du graphe d’origine. Il est souvent plus facile pour un problème donné de se placer sur les composantes connexes d’un graphe.
On sent bien que, pour qu’un graphe soit connexe, il est nécessaire qu’il possède un certain nombre d’arêtes afin qu’il existe suffisamment de chemins. Une propriété importante précise que, pour qu’un graphe d’ordre n soit connexe, il faut qu’il comporte au moins n – 1 arêtes.
LE DEGRÉ D’UN SOMMET
Euler a donné son nom au cycle décrit par les habitants de Kdnigsberg : on appelle « cycle eulérien » un cycle passant une et une seule fois par chaque arête du graphe. Un graphe est alors dit « eulérien » s’il admet un cycle eulérien. Pour énoncer la caractérisation des graphes eulériens découverte par Euler, il est nécessaire de définir la notion de degré d’un sommet. On dit qu’une arête est « incidente » à un sommet lorsque ce dernier en est l’une des extrémités. Le degré d’un sommet est alors son nombre d’arêtes incidentes. Euler affirma qu’un graphe est euclidien si et seulement si il est connexe et tous ses sommets sont de degré pair.
Une fois données les conditions d’existence de cycles ou de chemins sur les graphes, il reste une question essentielle dont la théorie des graphes s’est largement emparée : s’il existe plusieurs chemins pour un même graphe, existe-t-il un chemin plus court? Cette question d’optimisation, si elle est loin d’être résolue, a déjà obtenu un certain nombre de réponses.
EN RÉSUMÉ
La théorie des graphes a pour objectif de fournir des modèles simples (sous forme de graphes) à des situations concrètes complexes. Les graphes sont définis par leurs sommets et leurs arêtes. Un chemin est alors une liste de sommets, et un cycle un chemin qui revient à son point de départ. Une fois fournies les conditions d’existence d’un chemin ou d’un cycle pour un graphe donné, il reste à résoudre la question de l’optimisation de ce chemin ou de ce cycle, à laquelle les mathématiciens travaillent encore.