Utilisateur:Lehalle/Digressions

Un article de Wikipédia, l'encyclopédie libre.

Lehalle Chez moi Bloc notes Formulaire Décompressions Contributions

Sommaire

1 Dessiner sans lever son crayon

[modifier] Dessiner sans lever son crayon

Quel écolier n'a pas essayer de tracer une maison au crayon, sans jamais lever le crayon et sans repasser deux fois sur le même trait? L'idée de cette section est de determiner les conditions selon lesquelles un dessin est traçable sans lever le crayon (TSLC).

[modifier] Définitions

un graphe est un ensemble de sommets d'où partent des arrêtes.
un chemin (ou parcours fermé) d'un graphe est une collection ordonnées de ses arrêtes $A_1, A_2, \cdots, A_K$ telle qu'en notant $N (A k, i)$ (avec $i\in\{1,2\}$ ) les deux sommets des extrêmités de l'arrête $A k$ , alors il existe une suite d'indices $i_2, i_3,\cdots,i_{K-1}$ de ${1,2}$ telle que:

$\forall 1\leq k<K,\; N(A_k,i_k)=N(A_{k+1},i_{k+1})$

un graphe connexe est tel qu'il existe au moins un chemin entre deux sommets arbitraires.
la parité d'un sommet $A k$ est celle du nombre de ses arrêtes $\#N(A_k)$ (appelé aussi degré du sommet).
un graphe de classe $C (i, p)$ est un graphe connexe ayant $i$ sommets impairs et $p$ sommets pairs.
la classe MTSI (moins de trois sommets impairs) est constitué de l'union des classes $C (i, p)$ pour $p$ quelconque et $i\in\{0, 1, 2\}$ .

un graphe connexe de la classe C(2,2)

un graphe connexe de la classe C(4,0)

un graphe connexe de la classe C(2,1)

[modifier] Résultats

Théorème 1.a. Il n'existe pas de graphe connexe de classe $C(1,\cdot)$ .

Lemme 1.a. Pour tout graphe connexe dont les sommets sont $S_1,S_2,\cdots,S_K$ de degrés $d(S_1),d(S_2),\cdots,d(S_K)$ , alors:

$\exist n\in{I\!\! N}\,/\;\sum_{k=1}^K d(S_k) = 2\, n$

Cette relation vient immédiatement du fait que toute arrête est partagée par deux sommets (elles sont donc comptées toutes deux fois).

Le théorème 1.a suit immédiatement le lemme 1.a, car pour un graphe de classe $C(1,\cdot)$ , soit $S 1$ le sommet de degré impair (on peut numéroter les sommets arbitrairement), on a :

$\sum_{k=1}^K d(S_k) = \underbrace{d(S_1)}_{2n_1+1} + \sum_{k=2}^K \underbrace{d(S_k)}_{2n_k}=1+2\left( \sum_{k=1}^K n_k\right)$

qui est impair (ce qui est impossible).

Lemme 1.b. un graphe de classe $C(0,\cdot)$ à qui on retire une arrête est encore connexe.

En effet, si en retirant une arrête on obtenait deux graphes connexes non connectés entre eux, ils seraient tout deux de classe $C(1,\cdot)$ et connexes, ce qui est impossible par le théorème 1.a.

Lemme 1.c. il n'y a qu'une seule arrête d'un graphe $C(2,\cdot)$ qui, une fois retirée, en fait un graphe non connexe ; il est toujours possible d'enlever une arrête à un graphe $C(2,\cdot)$ de telle sorte que le graphe résultant soit encore conexe.

Partons d'un graphe $C(2,\cdot)$ et enlevons-lui une arrête:

ou bien l'arrête n'a pas d'extrémité de degré impair. Et dans ce cas la seule façon d'avoir un graphe resultant non connexe est d'obtenir deux graphes de classes respectives $C(3,\cdot)$ et $C(1,\cdot)$ , ce qui est impossible (lemme 1.a).
ou bien elle a exactement une extrémité de degré impair. La seule façon d'obtenir un graphe non connexe est de former deux graphes de classes $C(0,\cdot)$ et $C(1,\cdot)$ , ce qui est encore impossible.
ou bien elle a deux extrémités de degré impairs et c'est alors possible de former deux sous graphes non connectés de classes $C(2,\cdot)$ . Mais il y a une alternative car:

ou bien il n'y a plus que ces deux sommets (dans ce cas c'est terminé)
ou bien il y a un autre sommet de degré pair qui est connecté à notre sommet impair (sinon il est impossible de former des graphes non connectés). Il est donc toujours possible de revenir dans le cas 2.

Finalement, il est toujours possible d'enlever une arrête au graphe sans former un graphe non connecté.

Simplification. les sommets de degré deux n'ont pas d'importance dans le cadre de notre problématique. Un graphe quelconque peut donc dans notre cadre être simplifié en lui enlevant ses sommets de degré deux et en fusionnant les deux arrêtes de ces sommets.

Théorème 2: Réduction d'un graphe. Il est toujours possible de retirer une arrête à un MTSI de telle sorte que le graphe résultant soit dans la classe des MTSI. Pour les graphes de classe $C(2,\cdot)$ , cette arrête a un sommet de degré impair.

Il suffit de le montrer par reccurence pour un graphe de classe $C(0,\cdot)$ et un graphe $C(2,\cdot)$ .

Soit un graphe de $C (0, n)$ , retirons n'importe quelle arrête, le graphe résultant est immédiatement dans $C (2, n - 2)$ .

Soit un graphe de $C (2, n)$ , retirons une arrête partant d'un des sommets de degré impair (notons le $S 1$ , et $S 2$ l'autre sommet):

si $d (S 2)$ est impair, alors le graphe résultant est dans $C (0, n + 2)$ ,
si $d (S 2)$ est pair, alors le graphe résultant est dans $C (2, n - 2)$ .

Il est possible que $d (S 1) = 3$ , alors le sommet résultant est de degré deux, la simplification permet de supprimer ce sommet, le graphe résultant (réduction + simplification) est donc dans $C (0, n + 1)$ .

Remarque: il faut aussi garantir que l'on ne quitte pas le domaine des graphes connexes.

Théorème 3: Graphes TSLC. Les graphes connexes de moins de trois sommets impairs sont des graphes traçables sans lever le crayon.

Ce résultat provient immédiatement du théorème 2 ; il suffit d'observer que le nombre total d'arrêtes diminue strictement lors d'une réduction. En itérant les réductions, on arrive donc irrémédiablement à un graphe de taille zéro. Il faut juste regarder les cas finaux (les graphes de classe $C (0,1)$ et de classe $C (2,0)$ ).

[modifier] Méthodologie

Suivant le théorème 3 (et surtout le théorème 2 qui est constructif), pour les graphes de $C(0,\cdot)$ , on peut commencer par n'importe quel sommet et termer par le même. Et pour les graphes de $C(2,\cdot)$ , il faut commencer par un des deux sommets impairs et finir par l'autre.