Overblog Suivre ce blog
Administration Créer mon blog
18 juillet 2011 1 18 /07 /juillet /2011 12:00

Cet article suit Somme des degrés impairs

 

La propriété vue dans l'article cité plus haut est la suivante :

 

Propriété 1. Dans un graphe la somme de degré impairs est un nombre pair.

 

Autrement dit, en ne considérant que les sommets ayant un degré impair, on obtient un nombre pair en faisant leur somme. Mais, alors cela implique que le nombre de ces sommets de degré impair est nécessairement pair. Cela provient de la propriété suivante concernant les nombres entiers pairs et impairs.

Propriété 2. Une somme de nombres impairs est impaire si et seulement si ces nombres sont en quantité impaire.

Preuve.
Considérons r nombres impairs n1, n2, ......, nr . Comme ces nombres sont impairs, on peut écrire

n1=2k1+1, n2=2k2+1, ....., nr=2kr+1k1, k2, ...., kr sont des entiers.

Alors n1+ n2+ ......+ nr =  2k1+1+2k2+1+....+2kr+1 = 2(k1 + k2+ ....+ kr) + 1+...+1=2(k1 + k2+ ....+ kr) + r

Donc n1+ n2+ ......+ nr = 2m + r, où m=k1 + k2+ ....+ kr .

Si r est impair : r=2p+1 pour un entier p et n1+ n2+ ......+ nr = 2m + 2p+1=2(m+p)+1=2m'+1, avec m'=m+p. Dans ce cas, la somme est impaire.
Sinon, r est impair pair : r=2p et n1+ n2+ ......+ nr = 2m + 2p+1=2(m+p) =2m'  . Dans ce cas la somme est paire. 

FIN DE LA PREUVE.

 

 

Remarque : Même si cela ne sert pas dans la propriété qui suit, les entiers n1, n2, ......, nr ne sont pas nécessairement positifs.

 

On en déduit donc le résultat suivant : 

 

Propriété 3. Dans un graphe le nombre de sommets ayant un degré impair est pair.

 

En gardant l'exemple de mes amis Facebook, je peux construire un graphe composé de ces amis. Il y a une arête lorsque deux de mes amis sont amis entre eux. Le degré d'un ami est donc le nombre d'amis qu'il a en commun avec moi. De la propriété 3, on déduit que j'ai un nombre pair d'amis Facebook ayant un nombre impair d'amis communs avec moi.

 

Autres articles concernant les graphes pour débutants.

Repost 0
Published by Maths_Buchwald - dans Graphes
commenter cet article
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 ....

Repost 0
Published by Maths_Buchwald - dans Graphes
commenter cet article
7 mai 2011 6 07 /05 /mai /2011 12:00

IMGP4003

Combien d'arêtes possède un graphe complet ?

 

Ci-contre, le graphe  a 5 sommets, tous reliés entre eux. Il possède 10 arêtes.

 

Combien un graphe complet de 50 sommets en a-t-il ?

 

A suivre ....

Repost 0
Published by Maths_Buchwald - dans Graphes
commenter cet article
30 avril 2011 6 30 /04 /avril /2011 12:00

Dans l'article Graphe , je posais la question :

 

Le graphe ci-contre a une particularité, laquelle ? IMGP4003

 

Réponse : Chaque sommet est relié à tous les autres par une arrête. On dit alors que le graphe est complet.

 

Aussi, le graphe est simple, car entre deux sommets, il n'y a pas plus d'une arrête.

En général, on dit qu'un graphe est simple s'il entre deux sommets, il y a une arrête maximum et si il n'y a pas d'arrête joignant un sommet à lui-même (une boucle).

 


 

Question : Si un graphe complet a n sommets, combien possède t-il d'arrêtes ?

 

A suivre ...

Repost 0
Published by Maths_Buchwald - dans Graphes
commenter cet article
20 avril 2011 3 20 /04 /avril /2011 12:00

Un graphe est constitué de sommets et d'arêtes. Un arête "relie" deux sommets, il peut y avoir plusieurs arêtes entre deux sommets et il peut y avoir un chemin d'un sommet à lui même.

 

Exemple 1 :

 

Les sommets du graphe sont G,H,I,J et K.

 

Il y a des arêtes entre : G et I, G et H, G et J, G et K, H et I, H et J, H et K, I et J, J et K.

 

IMGP4002.JPG

Exemple 2 :

 

Les sommets du graphe sont A, B, C, D et E.

 

Il y a des arêtes entre : A et C, C et B, D et E (2 arêtes).

 IMGP4010.JPG

Exemple 3 :

 

Les sommets du graphe sont M, N et O.

 

Il y a arêtes entre : M et O, O et N, N et N.

 IMGP4023.JPG

 

Les graphes 1 et 3 ont la particularité d'être en une seule partie. On peut arriver à n'importe quel sommet en partant de n'importe quel autre sommet. Par exemple pour le graphe 1 : pour aller du sommet G au sommet K, il existe un chemin, c'est à dire une suite d'arêtes : G->I (première arête) -> K (deuxième arête). On peut remarquer qu'il y a plusieurs chemins reliant G et K : par exemple G->H->J->G->H->K (ici le chemin comporte 5 arêtes).

 

Définition. Un chemin entre deux sommets S et T est une suite (finie) d'arêtes a,b,c,... telle que :

  • le  sommet S est un extrémité de la première arête
  • pour chaque arête, de la deuxième à l'avant dernière : une des extrémités est une extrémité de l'arête précédente et l'autre extrémité est une extrémité de l'arête suivante
  • le sommet T est une extrémité de la seconde arête.

Lorsque dans un graphe, il y a un chemin possible entre deux sommets distincts quelconques, on dit que le graphe est connexe.

 

Les graphes 1 et 3 sont connexes. Le graphe 2 n'est pas connexe car, il n'y a pas de chemin reliant B et D. Les deux parties du graphe 2 formées de A, C, B et de D,E forment elles même deux graphes. Chacun de ces graphes est connexe, on les appellent les composantes connexes du graphe 2.

 

Voici encore un exemple :

IMGP4003.JPG

 

Le graphe G,H,I,J,K ci dessus a une particularité, laquelle ?

 

La réponse dans un prochain article...

Repost 0
Published by Maths_Buchwald - dans Graphes
commenter cet article

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