Nombre de croisements (théorie des graphes)

Un article de Wikipédia, l'encyclopédie libre.
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 cr(G) = 3.

En théorie des graphes, le nombre de croisements cr(G) 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[1].

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[2]. 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[3]. 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'inégalité du nombre de croisements (en) 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 à e3/n2.

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 sensiblement le même que[pas clair] 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[4].

Définitions[modifier | modifier le code]

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és[5].

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 croisements[5].

Cas particuliers[modifier | modifier le code]

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érieures[6].

Graphes bipartis complets[modifier | modifier le code]

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 complet[7] ?

Kazimierz Zarankiewicz a tenté de résoudre le problème de l'usine de briques de Turán[8] ; sa preuve contenait une erreur, mais il a établi un majorant correct :

pour le nombre de croisements du graphe biparti complet Km,n. Cette borne est conjecturée être le nombre de croisements pour tous les graphes bipartis complets[9].

Graphes complets et coloration de graphes[modifier | modifier le code]

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 1960[10]. 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 1960[10]. On sait qu'il existe toujours un tracé avec

croisements. Cette formule donne les valeurs 1, 3, 9, 18, 36, 60, 100, 150 pour p = 5, ..., 12 ; (suite A000241 de l'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 1964[11].

Saaty a en outre vérifié que cette formule donne le nombre optimal de croisements pour p ≤ 10 et Pan et Richter ont montré qu'elle était également optimale pour p = 11, 12[12].

La conjecture d'Albertson, formulée par Michael O. Albertson en 2007, déclare que, parmi tous les graphes de nombre chromatique n, le graphe complet Kn a le nombre minimum de croisements. On sait aujourd'hui que la conjecture d'Albertson est valable pour n ≤ 16.[13]

Graphes cubiques[modifier | modifier le code]

Les plus petits graphes cubiques avec les nombres de croisement 1..., 8 et 11 sont connus (suite A110507 de l'OEIS). Le plus petit graphe cubique à 1 croisement est le graphe biparti complet K3,3, 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 connu[14]. Les plus petits graphes cubiques à 8 croisements incluent le graphe de Nauru et le graphe de McGee ou (3,7)-cage, avec 24 sommets[15]. 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 Tutte[15],[16].

Complexité et approximation[modifier | modifier le code]

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-difficile[17]. En fait, le problème reste NP-difficile même lorsqu'il est restreint aux graphes cubiques[18] et aux graphes quasi-planaires (graphes qui deviennent planaires après suppression d'un seul sommet)[19]. Un problème étroitement lié, à savoir la détermination du nombre de croisements rectilignes, est complet pour la théorie existentielle sur les réels[20].

Il existe des algorithmes efficaces pour déterminer si le nombre de croisements est inférieur à une constante fixe k. En d'autres termes, le problème est traitable à paramètre fixe[21],[22]. Il existe également des algorithmes d'approximation efficaces pour approximer cr(G) sur des graphes de degré borné.[23] 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 Number[24].

L'inégalité du nombre de croisements[modifier | modifier le code]

Pour un graphe non orienté G avec n sommets et e arêtes tels que e > 7n, 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édi[25] et par Leighton[26]. Il est connu sous le nom d'inégalité des nombres de croisement ou de lemme de croisement.

La constante 29 est la meilleure connue à ce jour et est due à Ackerman[27]. La constante 7 peut être abaissée à 4, mais au détriment 64 à la place de 29. [25],[26]

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-Trotter[28].

Nombre de croisements rectilignes[modifier | modifier le code]

Les nombres de croisement rectilignes pour à Kn pour n de 5 à 12 sont 1, 3, 9, 19, 36, 62, 102, 153, (suite A014540 de l'OEIS). Les valeurs sont connues jusqu'à K27, et K28 à un nombre de croisements rectilignes égal à 7233 ou 7234. D'autres valeurs sont collectées par le projet Rectilinear Crossing Number[24].

Références[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Crossing number (graph theory) » (voir la liste des auteurs).
  1. ↑ (en) Helen C. Purchase, Robert F. Cohen et Murray I. James « Validating graph drawing aesthetics » () (DOI 10.1007/BFb0021827 Accès libre)
    — « (ibid.) », dans Franz-Josef Brandenburg (éd.), Graph Drawing, Symposium on Graph Drawing, GD '95, Passau, Germany, September 20-22, 1995, Proceedings, vol. 1027, Springer, coll. « Lecture Notes in Computer Science », p. 435–446    .
  2. ↑ P. Turán, « A Note of Welcome », Journal of Graph Theory, vol. 1,‎ , p. 7–9 (DOI 10.1002/jgt.3190010105)
  3. ↑ Urie Bronfenbrenner, « The graphic presentation of sociometric data », Sociometry, vol. 7, no 3,‎ , p. 283–289 (JSTOR 2785096) :

    « The arrangement of subjects on the diagram, while haphazard in part, is determined largely by trial and error with the aim of minimizing the number of intersecting lines. »
  4. ↑ Edward R. Scheinerman et Herbert S. Wilf, « The rectilinear crossing number of a complete graph and Sylvester's "four point problem" of geometric probability », The American Mathematical Monthly, vol. 101, no 10,‎ , p. 939–943 (DOI 10.2307/2975158, JSTOR 2975158)
  5. ↑ a et b J. Pach et G. Tóth « Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS 1998) » () (DOI 10.1109/SFCS.1998.743512).
  6. ↑ E. de Klerk, J. Maharry, D. V. Pasechnik, B. Richter et G. Salazar, « Improved bounds for the crossing numbers of Km,n and Kn », SIAM Journal on Discrete Mathematics, vol. 20, no 1,‎ , p. 189–202 (DOI 10.1137/S0895480104442741, arXiv math/0404142, lire en ligne)
  7. ↑ János Pach et Micha Sharir, Combinatorial Geometry and Its Algorithmic Applications : The Alcalá Lectures, vol. 152, American Mathematical Society, coll. « Mathematical Surveys and Monographs », , 126–127 p., « 5.1 Crossings—the Brick Factory Problem »
  8. ↑ K. Zarankiewicz, « On a Problem of P. Turán Concerning Graphs », Fundamenta Mathematicae, vol. 41,‎ , p. 137–145
  9. ↑ Richard K. Guy, Proof Techniques in Graph Theory (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., 1968), New York, Academic Press, (MR 0253931), « The decline and fall of Zarankiewicz's theorem », p. 63–69.
  10. ↑ a et b R. K. Guy, « A combinatorial problem », Nabla (Bulletin of the Malayan Mathematical Society), vol. 7,‎ , p. 68–72
  11. ↑ T.L. Saaty, « The minimum number of intersections in complete graphs », Proceedings of the National Academy of Sciences of the United States of America, vol. 52,‎ , p. 688–690 (PMID 16591215, PMCID 300329, DOI 10.1073/pnas.52.3.688, Bibcode 1964PNAS...52..688S)
  12. ↑ Shengjun Pan et R. Bruce Richter, « The crossing number of K11 is 100 », Journal of Graph Theory, vol. 56, no 2,‎ , p. 128–134 (DOI 10.1002/jgt.20249, MR 2350621).
  13. ↑ (en) János Barát et Géza Tóth, « Towards the Albertson Conjecture », .
  14. ↑ (en) Eric W. Weisstein, « {{{titre}}} », sur MathWorld
  15. ↑ a et b E. T. Pegg et G. Exoo, « Crossing Number Graphs », Mathematica Journal, vol. 11,‎ (DOI 10.3888/tmj.11.2-2)
  16. ↑ G. Exoo, « Rectilinear Drawings of Famous Graphs »
  17. ↑ Garey, M. R. et Johnson, D. S., « Crossing number is NP-complete », SIAM Journal on Algebraic and Discrete Methods, vol. 4, no 3,‎ , p. 312–316 (DOI 10.1137/0604033, MR 0711340)
  18. ↑ Hliněný, P., « Crossing number is hard for cubic graphs », Journal of Combinatorial Theory, series B, vol. 96, no 4,‎ , p. 455–471 (DOI 10.1016/j.jctb.2005.09.009, MR 2232384)
  19. ↑ Cabello S. and Mohar B., « Adding One Edge to Planar Graphs Makes Crossing Number and 1-Planarity Hard », SIAM Journal on Computing, vol. 42, no 5,‎ , p. 1803–1829 (DOI 10.1137/120872310, arXiv 1203.5944)
  20. ↑ Marcus Schaefer « Complexity of some geometric and topological problems » (DOI 10.1007/978-3-642-11805-0_32, lire en ligne)
    —Graph Drawing, 17th International Symposium, GS 2009 (Chicago, IL, USA, )
    — « (ibid.) », dans [...] Revised Papers, Springer-Verlag, coll. « Lecture Notes in Computer Science » (no 5849), (ISBN 978-3-642-11804-3), p. 334–344    .
  21. ↑ M. Grohe, « Computing crossing numbers in quadratic time », Journal of Computer and System Sciences, vol. 68, no 2,‎ , p. 285–302 (DOI 10.1016/j.jcss.2003.07.008, MR 2059096, arXiv cs/0009010)
  22. ↑ Ken-ichi Kawarabayashi et Bruce Reed « Computing crossing number in linear time » () (DOI 10.1145/1250790.1250848)
    —Proceedings of the 29th Annual ACM Symposium on Theory of Computing
  23. ↑ Guy Even, Sudipto Guha et Baruch Schieber, « Improved Approximations of Crossings in Graph Drawings and VLSI Layout Areas », SIAM Journal on Computing, vol. 32, no 1,‎ , p. 231–252 (DOI 10.1137/S0097539700373520)
  24. ↑ a et b Oswin Aichholzer, « Rectilinear Crossing Number project » [archive du ], and Rectilinear Crossing Number on the Institute for Software Technology at Graz, University of Technology (2009).
  25. ↑ a et b Ajtai, M., Chvátal, V., Newborn, M. et Szemerédi, E. « Crossing-free subgraphs » () (MR 0806962)
    —Theory and Practice of Combinatorics
  26. ↑ a et b Leighton, T., Complexity Issues in VLSI, Cambridge, MA, MIT Press, coll. « Foundations of Computing Series »,
  27. ↑ Eyal Ackerman, « On topological graphs with at most four crossings per edge » [archive du ],
  28. ↑ Székely, L. A., « Crossing numbers and hard Erdős problems in discrete geometry », Combinatorics, Probability and Computing, vol. 6, no 3,‎ , p. 353–358 (DOI 10.1017/S0963548397002976, MR 1464571)
Ce document provient de « https://fr.wikipedia.org/w/index.php?title=Nombre_de_croisements_(théorie_des_graphes)&oldid=210166199 ».