Overblog Suivre ce blog
Editer l'article Administration Créer mon blog
5 juin 2011 7 05 /06 /juin /2011 12:00

Pour voir les quelques articles sur les graphes : ici

 

Définition. On appelle le degré d'un sommet d'un graphe, le nombre d'arêtes (à deux extrémités) ayant ce sommet pour extremité. 

 

Dans cet article, on supposera que les arêtes ne joignent pas un sommet à lui-même. C'est pour cette raison que dans la définition, les arêtes ont deux extrémités.

 

Pour un sommet V, on note δ(V) le degré de V. (la lettre grec δ se lit delta ; la lettre V est parfois utilisée car en anglais vertex signifie sommet).

 

Exemples :


IMGP4002

 Dans ce graphe Γ1:

δ(G)=4

δ(H)=4

δ(I)=3

δ(J)=4

δ(K)=3

 

 IMGP4010  Dans ce graphe Γ2:

δ(A)=1

δ(C)=2

δ(B)=1

δ(D)=2

δ(E)=2

 

 

Dans le graphe Γ1 :



δ(G)+δ(H)+δ(I)+δ(J)+δ(K)=4+4+3+4+3=18, c'est un nombre pair.

Dans le graphe Γ2 :

δ(A)+δ(B)+δ(C)+δ(D)+δ(E)=1+2+1+2+2=8, c'est un nombre pair.

Dans un graphe, la somme des degré est un nombre pair, plus précisément, c'est le double du nombre d'arêtes. On obtient le Handshaking-Lemma (le lemme des poignées de mains) :

Propriété. Dans un graphe composé de N arêtes, on a la formule suivante :

Démonstration. Chaque arête a 2 extrémités. Chacune de ces extrémités donne 1 au degré du sommet qui est cette extrémité. Ainsi pour chaque arête, on ajoute 2 (1 pour chaque sommet). Donc la somme des degré est le double du nombre d'arêtes.

Fin de la preuve.

Si vous n'êtes pas convaincus par cette preuve, l'utilisation de la propriété de récurrence sur le nombre d'arête N, vous permettra de construire une meilleure démonstration.

Conséquence : La somme de degrés impairs d'un graphe est paire. Pourquoi ?

A suivre ....

Partager cet article

Repost 0
Published by Maths_Buchwald - dans Graphes
commenter cet article

commentaires

Présentation

  • : Maths Otak'
  • Maths Otak'
  • : Au départ, j'ai créé ce blog pour y publier des articles reliant Maths et histoire de l'art et la culture. Maintenant, il me permet d'aborder des sujets simples de la culture mathématique. J'aime parler de jeux vidéos. Vous trouverez aussi sur ce site des fiches de maths et Histoire des Arts de 2009-2010 au format *.pdf. Je ne sais pas où me mène ce blog donc il ne sera sans doute plus le même si je continue à l'alimenter dans un an. N'hésitez pas à laisser des commentaires.
  • Contact

Twitter

Recherche

Mes vidéos

Catégories