Graphe des cellules et plus long chemin garanti

Comme nous l'expliquions dans l'introduction, nous nous attardons sur deux cas précis de graphes définissable depuis un arrangement de droite. 

Dans ce second cas, celui du graphe des cellules, nous allons chercher à trouver une longueur de chemin dépendante de N, la plus grande possible, telle qu’il soit toujours possible, pour un N donné et quelques soit les N droites choisies, que le graphe dual de l'arrangement ainsi formé contiennent un chemin de cette longueur maximale garantie. 

Nous appellerons "Lgarantie" cette longueur, qui est la borne inférieure du chemin le plus long trouvable dans un graphe dual quelconque défini par un arrangement de droites.

De plus, nous étudierons ensuite un problème similaire : celui des chemins alternants dans un arrangement bichromatique.

Pourquoi chercher un chemin maximal garanti ?

L’objectif d’une telle valeur serait de déterminer s’il est toujours possible ou non de trouver une solution à un problème de recherche. En effet, si on arrive à réduire notre problème initial à une recherche de chemin dans un graphe tel que défini par un arrangement de droites, et qu’on a besoin de trouver un chemin de taille M, si M<Lgarantie, on est sûr que notre problème aura une solution. Dans le cas contraire, il aura peut-être une solution, en fonction du graphe précis.

Si on connait également une borne maximale de notre problème, Lmax, on peut aussi déterminer si notre problème n’a jamais de solution. En effet, si on réduit notre problème initiale à une recherche d’un chemin de longueur M>Lmax, on est sûr de ne jamais pouvoir trouver un tel chemin et donc de ne jamais trouver de solution à notre problème initial.

Longs chemins
dans un arrangement de droites monochromatique

Explication de la méthode

Dans le cas général, on montre que le graphe dual peut être transformé (en retirant un nombre linéaire de points) en un graphe 4-connecté ayant donc toujours un nombre de sommets en O(n²).

Comme les graphes 4-connectés possèdent toujours un chemin Hamiltonien (théorème de Tutte, 1956), on sait qu'il existe toujours un chemin de cette taille.

Transformations appliquées au graphe dual

• Ajout d'un sommet v_∞ auquel sont relié toutes les faces infinies.
• Transformation de tous les sommets de degrés 3 selon la figure suivante :

Démonstration interactive (1/1)

Dans cette démonstration, un algorithme a été implémenté pour trouver le plus long chemin. Comme vous pouvez le constater, ce problème est NP-difficile dans un graphe arbitraire (et probablement aussi dans notre cas); cela veut dire qu'il devient exponentiellement plus compliqué quand le nombre de droites augmente. Très vite, votre ordinateur va arriver à saturation. Trouver le chemin le plus long est donc un problème très difficile.

Chemin alternants
dans un arrangement bichromatique

Dans cette variante du problème, les droites de l'arrangement peuvent être de deux couleurs différentes, conventionnellement bleues ou rouges, avec au moins une droite de chaque couleur. On veut alors trouver un chemin alternant entre les cellules, c'est à dire que chaque frontière successive du chemin a une couleur différente de la précédente. Par exemple, dans la figure suivante, le chemin passe d'abord une frontière rouge, puis une bleue, etc.

On montre que la taille du chemin alternant maximal garanti dans un arrangement de N droites bichromatiques est de taille linéaire en montrant qu'on peut toujours construire un chemin alternant de taille N.

Démonstration interactive (1/2)

Dans cette démonstration, vous pouvez tracer le graphe des cellules à partir de l'arrangement correspondant, mais vous pouvez également demander de tracer le plus long chemin du graphe.

Enfin, en cliquant sur deux cellules successivement, vous pouvez obtenir le plus long chemin les reliant. C'est intéressant pour vérifier les propriétés des lemmes qui vont suivre dans les prochains chapitres.

Cellules bichromatiques

Dans cet autre exemple, où il n'y a qu'une seule droite rouge, on constate qu'une large partie des cellules sont monochromatiques:

 Chemin alternant entre les cellules bichromatiques

On définit le lemme suivant :

Lemme 1: Toute paire de cellule bichromatique peut être reliée par un chemin alternant.

Pour s'en convaincre, supposons qu'il existe deux cellules bichromatiques (A et B) que l'on ne peut pas relier par un chemin alternant. Soit E la frontière de l'ensemble des cellules accessibles depuis A. Cette frontière ne peut pas contenir deux droites de couleurs différentes. Il existe donc une frontière d'arêtes de la même couleurs séparant le plan en deux parties, chacune contenant une des cellules bichromatiques.

La situation est illustrée dans la figure ci-dessus. Deux cellules bichromatiques séparées par une frontière d'arêtes bleues. Cependant, cette situation est en fait impossible, car les droites sont en position générale. Les droites rouges dans les cellules bichromatiques de chaque côté de la frontière doivent donc se croiser une par une, et donc doivent traverser la frontière en au moins un point. Il est donc toujours possible de tracer un chemin reliera les deux cellules bichromatiques.

Cellules antipodales

Chaque cellule non bornées possède dans sa frontière exactement deux segments non bornés (et un nombre arbitraire de segments bornés). À chaque cellule non bornée correspond une autre cellule, dite antipodale, dont les deux segments non bornés de la frontière proviennent de la même droite. Une illustration de deux cellules antipodales est donnée par la figure suivante

Chemin entre deux cellules antipodales

Vu que tout arrangement contient au moins une droite de chaque couleur, il existe toujours au moins une paire de cellules bichromatiques antipodales. Appelons-les A et B. Le lemme 1 nous dit qu'il existe un chemin alternant entre A et B. Or, par définition, toutes les droites qui se trouvaient au-dessus de A se retrouvent en-dessous de B, et inversement. Un chemin alternant doit donc passer au moins une fois à travers chaque droite de l'arrangement, et a donc une taille d'au moins N.

La figure suivante montre le plus petit chemin possible entre deux cellules bichromatiques antipodales. En effet, il passe une et une seule fois à travers chaque droite de l'arrangement. Notez qu'il existe d'autres chemins entre ces deux cellules avec une plus grande taille

Démonstration interactive (2/2)

Dans cette démonstration, vous pouvez créer vous-même l'arrangement de droite bichromatique de votre choix, et appliquer la recherche du plus long chemin sur celui-ci. Vous pouvez ainsi vérifier certaines propriétés.

Bibliographie

AICHHOLZER Oswin, CARDINAL Jean, HACKL Thomas, et al. Cell-Paths in Mono-and Bichromatic Line Arrangements in the Plane.