Etude sur la façon de placer 20 points dans un
graphe complet tout en minimisant le nombre d'intersections
Débouchés possibles dans des problèmes
actuels en matière de transport (optimisation du trafic
aérien,...), ou dans les opérations d'impression
de documents (photos, images, textes,...)
Beaucoup de questions en géométrie informatique
et combinatoire se basent sur un ensemble finis de points dans un espace euclidien. Plusieurs
problèmes de la théorie des graphes
sont également adaptés à ce cadre, par
exemple lorsque les arêtes sont définis par avance
par une ligne droite. Une des questions les plus récurrentes
du volumineux problème des Rectilinear Crossing Number
(lié par exemple aux problèmes de transport et
à l'optimisation des opérations
d'impression) : Quel est le nombre minimal d'intersections que l'on
pourrait obtenir en traçant des lignes droites sur un graphe
complet reliant un ensemble de n points différents ? Ici le
graphe complet signifie que n'importe quelle paire de points est
reliée par une ligne droite. L'hypothèse de
départ est que trois points ne peuvent se retrouver sur la
même arrête.
On peut facilement voire qu'il est possible de placer quatre points de
sorte qu'aucun croisement ne se produise. Pour cinq points le
schéma ci-dessous montre les différentes
manières de les placer (Voilà la totalité des
différents types d'ordre
(présentés par Goodman et Pollack
en 1983)). Lorsque l'on dispose cinq points de façon convexe
dans un graphe, on observe cinq croisements. Le mieux que vous puissiez
faire est d'obtenir seulement une intersection (il n'y a aucune autre
manière de tracer un graphe complet de cinq points sans
croisement, sauf si vous permettez des arêtes
courbées). De la même manière, il est
facile de maximiser le nombre de croisements : il suffit simplement de
placer les n points sur un cercle pour obtenir le maximum de
croisements (n supérieur à 4)
Pour de plus grands ensembles de point, il est plus difficile de
déterminer la meilleure configuration. La raison principale
est que le nombre de combinaisons différentes pour placer
ces points augmente exponentiellement. Par exemple, il y a
dejà 2.334.512.907 possibilités
différentes pour n=11 points
La "chasse" aux Crossing Number dans un graphe complet a
été ouverte par R. Guy dans les années
60. Jusqu'en 2000, des valeurs pour n<=9 ont
été trouvé, en 2001 n=10 a
été résolu et le cas de n=11 a
été terminé en 2004. Le but principal
du projet en cours est d'employer des méthodes
mathématiques sophistiquées (prolongement
abstrait des types d'ordre) pour déterminer le nombre
d'intersections linéaires pour de petites valeurs de n. Jusqu'ici nous avons accomplis avec
succès ce travail pour n <= 17 .
Grâce à des recherches mathématiques
très récentes (non encore publié), on
connait les
rectilinear crossing numbers pour n=19 et n=21.
En Janvier 2007, le nombre minimal d'intersection pour n=18 a
été trouvé ; CR(18)=1029 (voir les résultats)
C'est pourquoi le travail le plus captivant est actuellement de
déterminer la valeur correcte pour n=20.
Une liste (régulièrement mise à jour)
des meilleurs ensembles de points connus jusqu'ici est consultable
à cette addresse :
Notez
que par soucis de simplification, l'écran de veille
représente uniquement la structure
générale du graphe et non pas tout les segments reliant chacun des points du graphe.
Cet article a été publié le 19-08-2006 14:18. Vous pouvez suivre les commentaires suscités par cet article grâce au fil RSS 2.0. Vous pouvez laisser un commentaire.
Dernière mise à jour 24-09-2008 20:34
Vos commentaires (0)
Seul les utilisateurs enregistrés peuvent commenter un article.
