De quels chemins parle-t-on?

Dans ce travail, nous allons considérer la question des longs chemins dans des arrangements de droites. Un arrangement de droites, ce n'est rien de plus qu'un espace 2D dans lequel on a dessiné une série de droites. On dit que ces droites sont en position générale lorsqu'elles se croisent toutes deux à deux et qu'aucun triplet de droites ne possède d'intersection commune.

Lorsque l’on dessine un ensemble de droites, on obtient un dessin similaire à celui-ci :

Il existe alors plusieurs manières de définir comment on peut se déplacer dans ce dessin, dont deux qui nous intéresse tout particulièrement :

Graphe des segments

Dans un premier temps, nous considérerons chaque intersection entre deux droites comme étant une ville où on peut s’arrêter. Les droites représentent alors les routes existant entre les villes. 

Plus formellement, on définit les intersections de droites comme les sommets de notre graphe, et les segments s’appuyant sur les droites et reliant deux sommets comme les arrêtes de notre graphe.

Une autre variante (en pointillés) consiste à ajouter des points au "bord" des droites, et à la relier entre eux pour former un cercle. Cette technique permet de calculer le second graphe possible, comme vous allons le voir après.

Lien vers un article: Comment construire une long chemin dans un graphe des segments défini par un arrangement de droites.

Graphe des cellules

Dans un second temps, nous considérerons enfin que chaque région entourée de droites, appelée « cellule », représente un pays où l’on peut s’arrêter. On peut voyager d’un pays à un autre s’ils partagent une frontière commune. 

Plus formellement, on définit les faces dessinées par notre arrangement comme les sommets de notre graphe, et on choisit de relier par une arrête deux sommets si leurs faces respectives possédaient un segment commun.

Lien vers un article: Comment construire un long chemin dans un graphe cellulaire défini par un arrangement de droites.

Passage d'un graphe à l'autre

En fait, il existe un lien entre ces deux manières d’interpréter le dessin. On appelle les deux graphes ainsi formés des graphes duaux, car il existe une opération mathématique qui transforme le premier en le second, et vice-versa. Cette opération est donc son propre inverse. 

Si vous désirez en savoir plus sur la dualité, nous avons créé une page à sujet; Lien vers un article: Explications sur le concept de dualité.