Ê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
Nombre de croisements (théorie des graphes)
Résumé
vignette| Une représentation du graphe de Heawood avec trois croisements. C'est le nombre minimum de croisements parmi toutes les représentations de ce graphe, qui a donc un nombre de croisements .
En théorie des graphes, le nombre de croisements d'un graphe G est le plus petit nombre d'intersections d'arêtes d'un tracé du graphe G. Par exemple, un graphe est planaire si et seulement si son nombre de croisements est nul. La détermination du nombre de croisements tient une place importante dans le tracé de graphes. Un graphe à but informatif représenté avec peu de croisements facilite la compréhension de celui-ci.
L'étude du nombre de croisements trouve son origine dans le problème de l'usine de briques de Turán, dans lequel Pál Turán a demandé un plan d'usine qui minimiserait le nombre de croisements entre les voies reliant les fours à briques aux sites de stockage. Formellement, ce problème revient à trouver le nombre de croisements d'un graphe biparti complet. Le même problème s'est posé indépendamment en sociologie à peu près au même moment, en relation avec la construction de sociogrammes. La formule conjecturée de Turán pour les nombres de croisements de graphes bipartis complets reste à prouver, tout comme une formule analogue pour les graphes complets.
L' indique que, pour les graphes où le nombre e d'arêtes est suffisamment supérieur au nombre n de sommets, le nombre de croisements est au moins proportionnel à .
Sans autre précision, le nombre de croisements permet des dessins dans lesquels les arêtes peuvent être représentées par des courbes arbitraires. Une variante de ce concept, le nombre de croisements rectilignes, exige que toutes les arêtes soient des segments et est donc supérieur ou égal au nombre de croisements. En particulier, le nombre de croisements rectilignes d'un graphe complet est le nombre minimum de quadrilatères convexes déterminé par un ensemble de n points. Le problème de la détermination de ce nombre est étroitement lié au Happy Ending problem.
À 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.