Vous avez un joli entrelacs, mais ce brin là paraît trop épais, ce serait mieux s’il était coupé en deux ou en trois bandes parallèles. Comment faire ? Appelons ce brin le gros brin.
En fait, il est plus facile de couper en trois bandes qu’en deux :
Pour couper en trois, il suffit de
rajouter deux sommets à chaque croisement du gros brin, c’est-à-dire découper chaque arête qui l’implique en trois et
rajouter un mur le long du gros brin, reliant un de ces deux points supplémentaires au suivant, de chaque côté.
Localement, on remplace un simple croisement par quelque-chose de plus compliqué :
Pour couper en deux, c’est plus difficile. C’est en fait un cas particulier d’une méthode plus générale. Considérez que le gros brin découpe le plan en zones « à l’intérieur » et zones « à l’extérieur ». C’est clair si le gros brin ne se recoupe pas lui-même. Quand il se recoupe lui-même, on raisonne par parité, si vous êtes entouré deux fois par le gros brin, considérez vous dehors ; ça ne fonctionne pas dans la vraie vie, on a beau se vérouiller dans sa cellule, on ne se retrouve pas pour autant à l’extérieur de la prison. Alors il vous faut
remplacer le graphe dans les zones « à l’intérieur » par le graphe dual, les sommets rouges « intérieurs » deviennent maintenant verts, et vice-versa,
rajouter un sommet à chaque croisement du gros brin, c’est-à-dire découper chaque arête qui l’implique en deux et
rajouter un mur le long du gros brin, reliant un de ces deux points supplémentaires au suivant, d’un seul côté (dans l’image suivante, j’ai dessiné le graphe et son dual, ce qui donne l’impression qu’il y a des murs des deux côtés).
Bien-sûr, pour découper le gros brin en n parallèles, il faut diviser chaque arête impliquée en n petits bouts et faire n-1 murs le long du gros brin.
RSS 2.0