Nombre de croisements (théorie des graphes)
En théorie des graphes, le nombre de croisements Modèle:Formule d'un graphe Modèle:Mvar est le plus petit nombre d'intersections d'arêtes d'un tracé du graphe Modèle:Mvar. 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-ciModèle:Références multiples.
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 completModèle:Références multiples. 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 sociogrammesModèle:Références multiples. 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'Modèle:Lien indique que, pour les graphes où le nombre Modèle:Mvar d'arêtes est suffisamment supérieur au nombre Modèle:Mvar de sommets, le nombre de croisements est au moins proportionnel à Modèle:Formule.
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 Modèle:Pas clair le nombre minimum de quadrilatères convexes déterminé par un ensemble de Modèle:Mvar points. Le problème de la détermination de ce nombre est étroitement lié au Happy Ending problemModèle:Références multiples.
Définitions
Dans le but de définir le nombre de croisements, le tracé d'un graphe non orienté est une application, des sommets du graphe vers des points distincs du plan, et des arêtes du graphe vers des courbes reliant leurs deux extrémités. Aucun sommet ne doit être appliqué sur une arête dont il n'est pas une extrémité, et chaque fois que deux arêtes ont des courbes qui se croisent (autre qu'à une extrémité partagée), leurs intersections doivent former un ensemble fini de croisements. Le nombre de croisements d'un graphe est alors le minimum du nombre de croisements sur tous ces tracésModèle:Références multiples.
Certains auteurs ajoutent plus de contraintes à la définition d'un tracé, par exemple que chaque paire d'arêtes doit avoir au plus un point d'intersection. Pour le nombre de croisements tel que défini ci-dessus, ces contraintes ne font aucune différence, car un tracé qui minimise le nombre de croisements ne peut pas avoir d'arêtes avec plusieurs points d'intersection. Cependant, ces contraintes sont pertinentes pour les définitions de variantes du nombre de croisements qui, par exemple, ne comptent que le nombre de paires d'arêtes qui se croisent plutôt que le nombre de croisementsModèle:Références multiples.
Cas particuliers
Les nombres de croisement sont connus pour très peu de familles de graphes. En particulier, à l'exception de quelques cas, le nombre de croisements de graphes complets, de graphes bipartis complets et de produits de cycles restent tous inconnus, bien qu'il y ait eu quelques progrès sur les bornes inférieuresModèle:Références multiples.
Graphes bipartis complets
Pendant la Seconde Guerre mondiale, le mathématicien hongrois Pál Turán a été contraint de travailler dans une usine de briques, poussant des wagons de briques des fours aux sites de stockage. L'usine avait des pistes de chaque four à chaque site de stockage, et les wagons étaient plus difficiles à pousser aux points où les pistes se croisaient, d'où Turán a été conduit à poser son problème d'usine de brique: comment les fours, les sites de stockage et les pistes être organisé pour minimiser le nombre total de croisements ? Mathématiquement, les fours et les sites de stockage peuvent être formalisés comme les sommets d'un graphe biparti complet, avec les pistes comme arêtes. Un plan d'usine peut être représenté comme un dessin de ce graphe, le problème devient donc : quel est le nombre de croisements d'un graphe biparti completModèle:Références multiples ?
Kazimierz Zarankiewicz a tenté de résoudre le problème de l'usine de briques de TuránModèle:Références multiples ; sa preuve contenait une erreur, mais il a établi un majorant correct :
pour le nombre de croisements du graphe biparti complet Modèle:Mvar. Cette borne est conjecturée être le nombre de croisements pour tous les graphes bipartis completsModèle:Références multiples.
Graphes complets et coloration de graphes
Le problème de la détermination du nombre de croisements d'un graphe complet a été posé pour la première fois par Anthony Hill en 1960Modèle:Références multiples. Hill et son collaborateur John Ernest étaient deux artistes constructivistes fascinés par les mathématiques. Ils ont non seulement formulé ce problème, mais ont également proposé une conjecture pour ce nombre de croisements, que Richard K. Guy a publiée en 1960Modèle:Références multiples. On sait qu'il existe toujours un tracé avec
croisements. Cette formule donne les valeurs Modèle:Formule pour Modèle:Formule ; (Modèle:OEIS). La conjecture est qu'il ne peut y avoir de meilleur tracé, de sorte que cette formule donne le nombre optimal de croisements pour les graphes complets. Une formulation indépendante de la même conjecture a été faite par Thomas L. Saaty en 1964Modèle:Références multiples.
Saaty a en outre vérifié que cette formule donne le nombre optimal de croisements pour Modèle:Formule et Pan et Richter ont montré qu'elle était également optimale pour Modèle:FormuleModèle:Références multiples.
La conjecture d'Albertson, formulée par Michael O. Albertson en 2007, déclare que, parmi tous les graphes de nombre chromatique Modèle:Mvar, le graphe complet Modèle:Mvar a le nombre minimum de croisements. On sait aujourd'hui que la conjecture d'Albertson est valable pour Modèle:Formule.Modèle:Références multiples
Graphes cubiques
Les plus petits graphes cubiques avec les nombres de croisement 1..., 8 et 11 sont connus (Modèle:OEIS). Le plus petit graphe cubique à 1 croisement est le graphe biparti complet Modèle:Formule, avec 6 sommets. Le plus petit graphe cubique à 2 croisements est le graphe de Petersen, avec 10 sommets. Le plus petit graphe cubique à 3 croisements est le graphe de Heawood, avec 14 sommets. Le plus petit graphe cubique à 4 croisements est le graphe de Möbius-Kantor, avec 16 sommets. Le plus petit graphe cubique à 5 croisements est le graphe de Pappus, avec 18 sommets. Le plus petit graphe cubique à 6 croisements est le graphe de Desargues, avec 20 sommets. Aucun des quatre graphes cubiques à 7 croisements, avec 22 sommets, n'est parfaitement connuModèle:Références multiples. Les plus petits graphes cubiques à 8 croisements incluent le graphe de Nauru et le graphe de McGee ou (3,7)-cage, avec 24 sommetsModèle:Références multiples. Les plus petits graphes cubiques à 11 croisements incluent le graphe de Coxeter avec 28 sommets.
En 2009, Pegg et Exoo ont conjecturé que le plus petit graphe cubique avec un nombre de croisements valant 13 est le graphe de Tutte–Coxeter, valant 170 est le 12-cage de TutteModèle:Références multiples.
Complexité et approximation
En général, la détermination du nombre de croisements d'un graphe est difficile ; Garey et Johnson ont montré en 1983 qu'il s'agissait d'un problème NP-difficileModèle:Références multiples. En fait, le problème reste NP-difficile même lorsqu'il est restreint aux graphes cubiquesModèle:Références multiples et aux graphes quasi-planaires (graphes qui deviennent planaires après suppression d'un seul sommet)Modèle:Références multiples. Un problème étroitement lié, à savoir la détermination du nombre de croisements rectilignes, est complet pour la théorie existentielle sur les réelsModèle:Références multiples.
Il existe des algorithmes efficaces pour déterminer si le nombre de croisements est inférieur à une constante fixe Modèle:Mvar. En d'autres termes, le problème est traitable à paramètre fixeModèle:Références multiples. Il existe également des algorithmes d'approximation efficaces pour approximer Modèle:Formule sur des graphes de degré borné.Modèle:Références multiples En pratique, des algorithmes heuristiques sont utilisés, tels que l'algorithme simple qui commence sans arêtes et ajoute continuellement chaque nouvelle arête d'une manière qui produit le moins de croisements supplémentaires possible. Ces algorithmes sont utilisés dans le projet de calcul distribué Rectilinear Crossing NumberModèle:Références multiples.
L'inégalité du nombre de croisements
Pour un graphe non orienté Modèle:Mvar avec Modèle:Mvar sommets et Modèle:Mvar arêtes tels que Modèle:Formule, le nombre de croisements minoré par
- .
Cette relation entre les arêtes, sommets et nombre de croisements a été trouvé indépendamment par Ajtai, Chvátal, Newborn et SzemerédiModèle:Références multiples et par LeightonModèle:Références multiples. Il est connu sous le nom d'inégalité des nombres de croisement ou de lemme de croisement.
La constante Modèle:Formule est la meilleure connue à ce jour et est due à AckermanModèle:Références multiples. La constante Modèle:Formule peut être abaissée à Modèle:Formule, mais au détriment Modèle:Formule à la place de Modèle:Formule. Modèle:Références multiples
Székely a montré que cette inégalité donnait des preuves très simples de certains théorèmes importants de la géométrie d'incidence, tels que le théorème de Beck, et le théorème de Szemerédi-TrotterModèle:Références multiples.
Nombre de croisements rectilignes
Les nombres de croisement rectilignes pour à Modèle:Formule pour Modèle:Formule de Modèle:Formule à Modèle:Formule sont Modèle:Formule, (Modèle:OEIS). Les valeurs sont connues jusqu'à Modèle:Formule, et Modèle:Formule à un nombre de croisements rectilignes égal à 7233 ou 7234. D'autres valeurs sont collectées par le projet Rectilinear Crossing NumberModèle:Références multiples.