Introduction
Dans la vie de tous les jours, on rencontre des graphes très souvent sans rien remarquer ... En effet lorsque vous prenez le métro, faire un planning, les liaisons aériennes, coloré les cartes de couleurs différents entre deux pays adjacents, etc ......
Un graphe , graphiquement se présente ainsi
Définition : Un graphe G est la donnée de deux ensembles V les sommets et E les arêtes. G=(V,E)
l'arête entre deux sommets A,B est notée (A,B) on la dessine en droite ou en courbe. On note aussi |V|=n le nombre des sommets et |E|=m le nombre des arêtes On dit que G est un graphe d'ordre n.
Vocabulaire
*Sommets = élément de V: A, B, C, ....
*Arêtes = élément de E : (A,B) , (C,F), (D,G), .... NOTE: l'arête (A,B)= l'arête (B,A)
*Chaîne = une suite de sommets reliant par leur arête : ACFBE, BFDE,....
*Cycle = chaîne fermée : ACFBEA, BFDEB, ...
*Degré d'un sommet = le nombre d'arêtes de ce sommet : d°(A)=4, d°(D)=3, ...
*Les voisins de A, Γ(A) = les sommets reliés à A par une arête : Γ(A)={C,F,B,E} , Γ(C)={A,F} ,
*La longeur d'une chaîne = le nombre d'arêtes qui la composent : longeur(ACFBE)=4
*Graphe connexe = deux sommets quelconque sont reliés par un chemin = G est un seul morceau.
Graphes orientés
Pour un graphe orienté, le vocabulaire change, mais ce n'est pas vraiment grave si on le mélange un peu.
*Sommets = élément de V: A, B, C, ....
*Arcs (Arêtes) = élément de E : (A,B) , (C,F), (D,G),... NOTE: l'arc (A,B) ≠ l'arc (B,A)
*Chemin (Chaîne) = une suite de sommets reliant par leur arc : AFBE, CFDGE,...
*Circuit (Cycle) = chemin fermée : FDG,...
*Degré-sortant = le nombre d'arcs-sortant : d+(A) = 3, d+(F) = 2,...
*Degré-entrant = le nombre d'arcs-entrant : d-(A) = 1, d-(F) = 3,...
*Degré d'un sommet = Degré-sortant + Degré-entrant = le nombre d'ars de ce sommet : d°(A)=4, d°(F)=5,...
*Les voisins-sortant (successeurs) de A = les sommets reliés à A par un arc-sortant, Γ+(A) : Γ+(A)={F,B,E}, Γ+(F)={B,D},...
*Les voisins-entrant (prédécesseurs) de A = les sommets reliés à A par un arc-entrant, Γ-(A): Γ-(A)={C} , Γ-(F)={C,A,G} ,
*Les voisins de A = les sommets reliés à A par un arc , Γ(A)=Γ+(A)UΓ-(A): Γ(A)={C,F,B,E} , Γ(F)={C,A,B,D,G} ,
*La longeur d'un chemin = le nombre d'ars qui la composent : longeur(AFBE)=3
*Graphe connexe = deux sommets quelconque sont reliés par un chemin = G est un seul morceau.
[1] 2 3 4
Accueil
DMJ: 23/01/2016