Théorie topologique des graphes
En mathématiques, la théorie topologique des graphes est une branche de la théorie des graphes. Elle étudie entre autres les plongements de graphes dans des surfaces, les graphes en tant qu'espaces topologiques[1] ainsi que les immersions de graphes.
Un plongement d'un graphe dans une surface donnée, une sphère par exemple, est une façon de dessiner ce graphe sur cette surface sans que deux arêtes se croisent. Un problème fondamental de la théorie topologique des graphes, souvent présenté comme un casse-tête mathématique, est l'énigme des trois maisons. D'autres applications existent comme dans l'impression de circuits électroniques où le but est d'imprimer (trouver un plongement) un circuit (le graphe) sur une carte de circuit imprimé (la surface) sans que deux connexions se croisent et provoquent un court-circuit.
Graphes en tant qu'espaces topologiques
modifierÀ un graphe non orienté donné, on peut associer un espace topologique ainsi : chaque sommet est représenté par un point, et chaque arête est un arc homéomorphe à qui relie ses deux extrémités[1]. Avec ce point de vue, on peut définir la notion d'homéomorphisme de graphes découlant directement de celle d'homéomorphisme topologique. De plus la notion de graphe connexe coïncide avec la connexité topologique et un graphe connexe est un arbre si et seulement si son groupe fondamental est trivial.
![{\displaystyle [0,1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/738f7d23bb2d9642bab520020873cccbef49768d)
Exemples de résultats de la théorie topologique des graphes
modifierJohn Hopcroft et Robert Tarjan[2] ont inventé un algorithme pour tester la planarité d'un graphe en temps linéaire en le nombre d'arêtes. Un test de planarité efficace est un outil fondamental pour le tracé des graphes.
Fan Chung et al.[3] ont étudié le problème du plongement d'un graphe dans un livre, en tant qu'espace topologique constitué de feuilles ayant un bord commun, de sorte que les sommets du graphe soient dans ce bord commun. Ses arêtes sont dessinées sur des pages séparées de telle sorte que les arêtes plongées sur une même page ne se croisent pas. Ce problème apparait notamment en pratique lors du routage de cartes de circuits imprimés multicouches.
Parmi les grands résultats de la théorie topologique des graphes, le théorème des quatre couleurs est l'un des plus célèbres : il affirme que tout graphe planaire dont on veut distinguer chaque partie n'a besoin que de 4 couleurs (deux zones contiguës ne sont jamais de la même couleur). Une généralisation de ce théorème est la conjecture de Heawood, qui étend ce résultat à d'autres surfaces.
Les plongements de graphes sont également utilisés pour démontrer des résultats structurels sur les graphes, via entre autres la théorie des graphes mineurs ou le théorème de structure des graphes.
Voir aussi
modifierNotes et références
modifier- J.L. Gross and T.W. Tucker, Topological graph theory, Wiley Interscience, 1987
- Hopcroft et Tarjan, « Efficient Planarity Testing », Journal of the ACM, vol. 21, no 4, , p. 549–568 (DOI 10.1145/321850.321852, lire en ligne)
- Chung, Leighton et Rosenberg, « Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design », SIAM Journal on Algebraic and Discrete Methods, vol. 8, no 1, , p. 33–58 (DOI 10.1137/0608002, lire en ligne)
