graphe dual d'un graphe planaire eulérien

Je reviens sur l'argument de Christophe pour montrer qu'un graphe sans cycle impair est biparti. Je pense avoir compris et voici comment je rédigerais ça :

Quitte à prendre une composante connexe, on se ramène à un graphe connexe et on le suppose non réduit à un sommet (sinon ça n'a pas un intérêt monumental...).
On définit une relation sur les sommets par $x\sim y$ s'il existe un chemin de longueur pair qui joint $x$ à $y$.
On vérifie qu'elle est bien réflexive (on prend des chemins de longueur 0), symétrique (on parcourt un chemin en sen inverse) et transitive (on concatène deux chemins).

Soit $x$ un sommet et $y$ un sommet adjacent à $x$ (existe car le graphe est connexe). Alors $x$ et $y$ ne sont pas équivalents car sinon il existerait un cycle de longueur impair.

Montrons maintenant que si $z$ est un autre sommet ou bien $z\sim x$ ou bien $z\sim y$, autrement dit il n'y a que deux classes d'équivalence.

Si $z\sim x$, c'est fini. Supposons que $z$ n'est pas équivalent à $x$. Alors comme le graphe est connexe il existe un chemin qui joint $z$ à $x$ et comme $z$ n'est pas équivalent à $x$, ce chemin est de longueur impair. Comme $y$ est adjacent à $x$, on obtient un chemin de longueur pair qui joint $z$ à $y$.

Ainsi on a exactement deux classes d'équivalence.
Comme enfin deux sommets dans la même classe d'équivalence ne peuvent être adjacents (sinon il y aurait des cycles impairs), on obtient bien une coloration propre en deux couleurs et le graphe est biparti.

Un petit up au cas où...

Effectivement, je nage complètement. Là, je suis complètement perdu, je sui désolé, mais je ne comprends vraiment pas. Tu dis :

GaBuZoMeu a écrit:

Pour un graphe planaire tout cycle (vu comme l'ensemble de ses arêtes) est somme (dans ce sens) de cycles élémentaires qui sont des bords de faces (bord d'une face = ensemble des arêtes adjacentes à une face). Or pour le dual d'un graphe eulérien plan tout cycle élémentaire est pair, et la somme de cycles pairs est un cycle pair.

Voici comment j'interprète ce que tu as dit à la lueur de ton dernier message :

1) les cycles élémentaires du graphe dual sont pairs
2) comme dans un graphe planaire, tout cycle est somme de cycles élémentaires qui sont les bords des faces, alors tout cycle du graphe dual est pair.

Est-ce une interprétation correcte ?

Si oui, je ne comprends toujours pas et voici ce qui m'échappe :

1) Pourquoi les cycles élémentaire du graphe dual sont-ils pairs ?
2) Pourquoi le graphe dual est-il planaire ?

Encore une fois, je suis désolé...

La définition que j'ai du graphe dual d'un graphe planaire $G$ est le graphe $G^*$ dont les sommets correspondent aux faces de $G$ et tels que deux sommets sont reliés si les faces correspondantes ont une arête de leur bord en commun. C'est la même définition que dans ce précédent fil.
Je ne vois pas a priori pourquoi le graphe $G^*$ serait toujours planaire.

GaBuZoMeu a écrit:

J'ai l'impression que tu n'as jamais dessiné sur une feuille le graphe dual d'un graphe plan. Correct ? Alors fais-le pour de bon !

Non pas correct du tout ! Je sais que je suis très lent et que j'ai beaucoup de mal à comprendre, mais ce n'est pas faute d'essayer réellement : j'en ai fait plein des dessins de graphes duaux, je ne fais même que ça des dessins. Ils étaient effectivement planaires, mais de là à penser que c'était général, il y a un pas que je n'avais pas osé franchir.

En fait je souhaite réussir à rédiger rigoureusement toute assertion que j'utilise et souvent je n'arrive pas à passer de l'intuition visuelle sur le dessin à une rédaction complètement rigoureuse des choses.

Par exemple ici, j'ai du mal à rédiger formellement le fait qu'on peut toujours faire en sorte que deux arêtes du graphe dual ne se croisent pas.

Non, ce n'est pas ça qui manquait. Je réfléchis à tout ça. Merci beaucoup !

Il n'y a pas quelque-chose de précis qui manquait, c'est juste que je suis très lent et que ça me prend du temps d'abord de bien visualiser ce qui se passe, puis (et surtout) de réussir à le traduire en une preuve complète et rigoureuse.

En gros, je vois bien sur le dessin que "ça marche", mais l'argument derrière le "je vois bien que" ne m'est pas immédiat.

Par ailleurs, pour cette histoire de faces convexes, j'avais déjà vu qu'on peut bien rendre toute face bornée convexe, mais dans ce cas, la face infinie ne l'est pas. Cependant, je ne crois pas que ce soit un problème et là, je suis en train d'essayer de rédiger une preuve.

Je solliciterai certainement à nouveau votre aide, car si je pense savoir rédiger une preuve de la planarité du graphe dual, je ne suis pas sûr d'avoir compris la preuve global du caractère biparti du graphe dual... Mais chaque chose en son temps.

Merci beaucoup en tout cas !

Très honnêtement, je n'arrive pas à voir comment, dans le plan, toutes les faces peuvent être convexes en même temps. Si je n'ai que deux faces, une bornée, l'autre pas, et dont le bord commun est un polygone (par exemple un triangle, prenons l'exemple le plus simple possible), je ne vois vraiment pas comment le triangle et son complémentaire peuvent être convexes en même temps.

Mais encore une fois, je n'ai pas l'impression que c'est un problème.

Si si je lis bien. Mais je n'arrive pas à raisonner à deux endroits en même temps. Là je raisonne dans le plan, pas sur la sphère, donc je regarde mon graphe dans le plan.
Et comme je l'ai déjà dit dans mes message précédents : ce n'est pas un problème de ne pas avoir de la convexité sur toutes les faces.
En fait, dans la preuve que je suis en train de mettre au point, je n'ai pas besoin de convexité, j'utilise seulement qu'un ouvert connexe du plan est connexe par arcs polygonaux.

Bon voici comment je rédigerais la preuve de la planarité du graphe dual en suivant la construction décrite par GaBuZoMeu.

On utilise le fait que tout ouvert connexe du plan est connexe par arc polygonal.

Lemme 1 : Tout graphe planaire $G$ admet une représentation plane dont les arêtes sont des arcs polygonaux.

Preuve du lemme 1 : On note $S$ l'ensemble des sommets de $G$. C'est une partie finie du plan.
Pour tout $x\in S$, il existe $\epsilon_x$ tel que le disque de centre $x$ et de rayon $\epsilon_x$ ne rencontre que les arêtes adjacentes de $x$.
Soit $\epsilon:=\min_{x\in S}\epsilon_x$. Quitte à diminuer $\epsilon$, on peut supposer que les disques fermés $\overline{D(x,2\epsilon)}$ pour $x\in S$ sommet sont deux à deux disjoints.

On note $O:=\R^2\setminus\cup_{x\in S}\overline D(x,\epsilon)$. C'est un ouvert connexe du plan.

Soit $A_1,\dots, A_n$ les arêtes de $G$. Soient $x$ et $y$ les sommets adjacents à $A_1$. On représente alors $A_1$ par la courbe polygonale $\Gamma_1$ définie comme suit : on fixe un point $x'$ sur le cercle de centre $x$ et de rayon $2\epsilon$ et un point $y'$ sur le cercle de centre $y$ et de rayon de $2\epsilon$. Les points $x'$ et $y'$ sont dans $O$ donc il existe un arc polygonal les joignant. On complète cet arc par les segments d'extrémités $x$ et $x'$ d'une part et $y$ et $y'$ d'autre part.

On trace de la même manière une représentation polygonale $\Gamma_2$ de $A_2$ dans l'ouvert connexe $O\setminus \Gamma_1$ et ainsi de suite.

Construction d'une une représentation plane du graphe dual de $G$ :

Soit $F_1,\dots, F_p$ les faces de $G$, c'est à dire les composantes connexes du plan privé de $G$. Les $F_i$ sont donc des ouverts connexes de $G$ dont les bords sont des unions de courbes $\Gamma_i$.

Sur chaque $\Gamma_i$, on fixe un point $\gamma_i$ distinct des sommets de $G$. Dans chaque $F_i$, on fixe un point $f_i$, les $f_i$ sont les sommets du graphe dual $G^*$.
Pour tracer les arêtes de $G^*$, il suffit de tracer pour chaque $f_i$ et chaque $\gamma_j$ tel que $\Gamma_j$ est dans le bord de $F_i$ un arc reliant $f_i$ à $\gamma_j$.

Comme chaque arête est le bord d'exactement deux faces, par chaque $\gamma_j$ il ne passe qu'une arête de $G^*$.

Ainsi il suffit de montrer que pour chaque $f_i$ si $\Gamma_{j_1},\cdots, \Gamma_{j_k}$ sont les arêtes qui bordent $F_i$, on peut tracer $k$ courbes $c_1, \dots,c_k$ telles que :

- pour $1\leq \ell \leq k$ les extrémités de $c_\ell$ soient $\gamma_{j_\ell}$ et $f_i$

- pour $\ell\neq \ell'$ l'intersection de $c_\ell$ et de $c_{\ell'}$ est réduite à $f_i$.

L'argument est analogue à celui du lemme 1. On fixe $\epsilon>0$ tel que les disques $D(\gamma_{j_\ell},2\epsilon)$, $1\leq \ell \leq k$ et $D(f_i, 2\epsilon)$ soient deux à deux disjoints.
On fixe $k$ points $x_1, \dots x_k$ sur le cercle de centre $f_i$ et de rayon $2\epsilon$ et pour chaque $\ell$, on fixe $y_\ell$ sur le cercle de centre $(\gamma_{j_\ell}$ et de rayon $2\epsilon$.
On construit un premier arc polygonal joignant $y_1$ à $x_1$ dans l'ouvert $O:=F_i\setminus (\cup_{\ell=1}^kD(\gamma_{j_\ell},\epsilon)\cup D(f_i,\epsilon))$. Puis un arc joignant $y_2$ à $x_2$ dans $O$ privé de l'arc précédent et ainsi de suite.
On complète enfin les arcs par des segments joignant $f_i$ aux $x_\ell$, et $\gamma_{j_\ell}$ à $y_\ell$.

Commentaires : Je suis bien conscient que c'est très lourd comme rédaction et qu'on peut surement alléger beaucoup de choses. En particulier, je me suis payé le luxe de faire des arcs polygonaux, mais j'aurais pu me contenter de chemins continus.