Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Théorie topologique des graphes
Résumé
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 graphiques en tant qu'espaces topologiques 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 le problème des trois chalets. 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 .
À 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. Avec ce point de vue, on peut définir la notion d'homéomorphisme de graphe 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.
John Hopcroft et Robert Tarjan 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. 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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.