Metraipolis › archive › dc_16ea566fb3f3
Nombre de croisements (théorie des graphes) — Wikipedia (fr)
- Source
- Wikipedia (fr)
- Original
- https://fr.wikipedia.org/wiki/Nombre_de_croisements_(th%C3%A9orie_des_graphes)
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-10-07T13:29:31.115Z
- SHA-256 of the archived text
218642680023d959370e0e3c3ab1339be8b566654f7d8bbb9658d26915fbd0bd- Stable URL of this page
https://metraipolis.com/documento/dc_16ea566fb3f3
How to cite
Nombre de croisements (théorie des graphes) — Wikipedia (fr) — Wikipedia (fr), https://fr.wikipedia.org/wiki/Nombre_de_croisements_(th%C3%A9orie_des_graphes) (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_16ea566fb3f3 (Metraipolis archive dc_16ea566fb3f3, sha256 218642680023d959370e0e3c3ab1339be8b566654f7d8bbb9658d26915fbd0bd)
BibTeX
@misc{dc16ea566fb3f3,
title = {Nombre de croisements (théorie des graphes) — Wikipedia (fr)},
howpublished = {Wikipedia (fr)},
url = {https://fr.wikipedia.org/wiki/Nombre_de_croisements_(th%C3%A9orie_des_graphes)},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_16ea566fb3f3; sha256 218642680023d959370e0e3c3ab1339be8b566654f7d8bbb9658d26915fbd0bd},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (fr), https://fr.wikipedia.org/wiki/Nombre_de_croisements_(th%C3%A9orie_des_graphes). Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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. 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'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. Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «théorie des graphes»). Fonte: Wikipedia in francese, voce «Nombre de croisements (théorie des graphes)» — https://fr.wikipedia.org/wiki/Nombre_de_croisements_(th%C3%A9orie_des_graphes) Wikidata Q266775 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q266775 Autori: i contributori di Wikipedia (cronologia: https://fr.wikipedia.org/wiki/Nombre_de_croisements_(th%C3%A9orie_des_graphes)?action=history). Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza. Estratto dell'introduzione non modificato nel contenuto; revisione 237790292, consultata il 2026-10-07T13:00:57.294Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: f9bbe5191c93331883ae29f3d7ddd71988d9ae02577652eb11813cd647b6ba0e