Overblog Suivre ce blog
Editer l'article Administration Créer mon blog
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...

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