formule d'Euler à partir du théorème de Pick
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.
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.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
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.
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....
Impossible d'y voir plus clair si tu ne reproduis pas totalement et exactement ton cours.
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)...
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.
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]
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 ?