formule d'Euler à partir du théorème de Pick

bijux3

Bonjour,
Je n'arrive pas à comprendre un passage d'une démonstration :



Soit G un graphe avec n sommets, m arêtes, et f faces. On rappelle le théorème de Pick (admis) : I+1/2B-1=Aire(F) ou I est le nombre de points entiers dans G et B sur les bords de G (donc n=B+I). On cherche à montrer la formule d'Euler : n-m+f=2. En enlevant la face extérieur il reste f-1 faces dans G. On triangularise G. Comme l'aire d'un triangle est 1/2 : Aire(F)= I+1/2B-1=Aire(sommes_des_triangles)=1/2*(f-1)

et donc : f=B+2I-1. Voilà le passage que je ne comprends pas :


Mes problèmes sont les suivants.

1. Pourquoi la longueur de la face vaut le nombre d’arêtes sachant que toutes les arêtes ne font pas la même taille (il y a des diagonales)
2. Si la longueur de la face vaut le nombre d’arêtes, on devrait avoir l(f)=m et non l(f)=2m
3. Enfin pourquoi 2m=3(f-1)+B (je ne comprends rien à l'obtention de cette égalité)

Pouvez-vous m'éclairer ?
Cordialement.

GaBuZoMeu

Déjà, dans la figure 5.1.c), une triangulation avec des carrés qui ne sont pas subdivisés en triangles, ça la fout mal !

PS. Ensuite, pourquoi $n=B+I$ ?

PPS. On ne sait pas si tu raisonnes sur le graphe ou sur la triangulation du graphe plongé dans le réseau entier. Il faut absolument clarifier ça.

bijux3

Bonjour,

J'avais constaté le problème (c'est le schéma de mon cours) mais faisons comme si tout était divisé en triangles. Ensuite le nombre de sommets de G est le nombre total de points (B+I). C'est encore une fois l'explication qui est écrite dans mon cours. Mais de toute façon cette égalité ne sert pas à la démonstration... Je raisonne sur la triangularisation...

PS : Dsl pour le doublon erreur de manipulation....

GaBuZoMeu

Comme tu ne reproduis que des parties de ton cours, il est diffcile de contrôler ce qui y est exactement écrit ! Et il n'est toujours pas clair si on compte les sommets sur le graphe originel ou bien sur la triangulation.
Impossible d'y voir plus clair si tu ne reproduis pas totalement et exactement ton cours.

bijux3

Voici mon cours en pièce jointe

J'ai une petite idée pour le 2m=l(F) il y a toujours deux faces entre chaque arrêtes (quand l'arrête est en bordure il y a la face intérieur et celle extérieur)...

GaBuZoMeu

Je dirais plutôt que chaque arête est adjacente à deux faces.

bijux3

c'est ce que je voulais dire mais pas avec les bons mots. Ca explique donc le point d'incompréhension 2. mais pas 1. et 3.

GaBuZoMeu

De plus, on suppose, sans perte de généralité, que toutes les faces de cette représentation de $G$ sont des triangles à coordonnées entiers sauf peut-être la face extérieure, voir figure 5.1.

C'est assez ole-ole. Il faudrait vérifier que la quantité "#faces - #arêtes + #sommets" est invariante au cours de la triangulation. Je ne vois aucune trace de cette vérification dans le poly.
Si cette vérification avait été faite, on pourrait effectivement travailler sur la triangulation.
L'aire du polygone est égale à la moitié du nombre de triangles, soit $(f-1)/2$. Donc, d'après Pick $f-1=2I+ B-2$ (équation 1).
Le nombre total de sommets est $n=B+I$ (équation 2)..
Le bord du polygone compte $B$ sommets et donc $B$ arêtes. Chaque triangle a trois arêtes adjacentes, la face extérieure $B$ arêtes adjacentes. Chaque arête est adjacente à deux faces. Donc $2m=3(f-1)+B$ (équation 3).
De l'équation 3 on tire $B=2m-3f+3$. En portant dans l'équation 2, on trouve $I=n-2m+3f-3$. Et en portant le tout dans l'équation 1, on obtient
$$f-1=2(n-2m+3f-3) +(2m-3f+3)-2$$ soit
$$2=f-m+n$$

PS. C'est certes intéressant de faire le lien entre formule de Pick et formule d'Euler. Mais ce n'est pas cette démonstration que je choisirais pour cette dernière.

bijux3

Merci grâce à ton explication j'ai enfin compris. Pour que ça puisse servir au autres pour l'équation 3, en sommant le nombre d'arêtes sur les triangles n'ayant aucun contact avec les cotés du polygone, on compte 2 fois chaque arête (une fois en faisant le bilan du premier triangle, et une fois pour le second). Pour pouvoir égaler à 2m (2 fois le nombre total d'arêtes) on rajoute une deuxièmes fois les arrêtes des triangles en contact avec les cotés du polygone (compté qu'une fois jusqu'alors).
Ce nombre est B (comme on ferme le polygone le nombre d'arêtes est égal au nombre de sommets . Ainsi 2m=3(f-1)+B
Le -1 de "f-1" est là pour enlever la face extérieur (f-1= nombre total de faces - La face extérieur).

En effet, il n'a jamais été montré que cette quantité se conserve. Une idée de comment faire ?

[Arrête de mettre 2 'r' à arête. ;-) AD]

GaBuZoMeu

Quand on ajoute un triangle en utilisant un sommet qui est déjà là : on ajoute 2 sommets, 3 arêtes et 1 face : bilan nul. Je te laisse considérer les autres cas.

bijux3

quand il y a déjà 3 sommets on rajoute rien donc bilan : 0
quand il y a déjà 2 sommets on en rajoute 1, 2 aRêtes, et une face : 1 -2 +1 =0 (par Euler)

Par contre quand il n'y aucun sommets déjà présent ( triangle qui ne touche pas un coté du polygone) on rajoute 3 sommets, 3 arêtes, et une face bilan : 1. Cette quantité n'est donc pas invariable ?

GaBuZoMeu

S'il n'y a rien du tout de déjà existant pour le triangle, ça veut dire que tu fais un trou dans la face dans laquelle tu dessines le nouveau triangle, et la face trouée n'est plus simplement connexe. Ou plus simplement, le graphe que tu obtiens en créant un triangle ex nihilo n'est plus connexe. La formule d'Euler vaut pour les graphes plans connexes.