Cours: les Graphes

Chapitre 1 : Graphes

!

I) Définition:

Définition: Un graphe G est un couple (V,E) où V est l’ensemble des sommets et E € V*V

est l'ensemble des arêtes.

!

Graphiquement:

V = {a,b,c,d,e}

!

!

Il peut y avoir des variantes:

!

E = {(a,b),(a,c),(b,d),(c,d),(d,e)}

• Graphe dirigé: les arêtes ont une direction. L'arête (a,b) est différente de (b,a).

• Graphe avec ou sans boucle (ou auto arête): L'arête (a,a) est autorisée ou non.

• Graphe multiple: On autorise plusieurs arêtes entre deux sommets.

• Graphe sommet-valué ou arête-valué: Graphe avec vecteur de poids sous les

sommets et/ou pour les arêtes.

• Graphe sommet-coloré ou arête-coloré: Les sommets et/ou les arêtes ont pour

attributs une variable qualitative (qui ne s’exprime pas avec des chiffres).

!

Exemples:

!

- Réseau d’ordinateurs:

!

Sommet = Ordinateur

Arête = Fil entre a et b

Poids sur l'arête = Capacité du fil

!

=> Graphe non dirigé arête valué

!

- Interaction entre protéine:

!

Sommet = Protéine

Arête = Les protéines a et b sont capables de se lier

!

=> Graphe non-dirigé, non-valué

!

- Ordonnancement des taches:

!

Sommet = Tache a effectuer

Arête = (a,b) Si a doit être effectuer pour effectuer la tache b

Poids sur le sommet = durée de la tache en question

!

!

=> Graphe dirigé sommet-valué

Définition: Un sous-graphe H d’un graphe G est un graphe tel que:

V(H) c(inclus) V(G)

E(H) c(inclus) V(G)

schéma:

Définition: Soit G un graphe et A c(inclus) V. Le sous-graphe de G induit par A noté

G[A], est définit par:

- l’ensemble de sommets A

- l’ensemble de toutes les arêtes de G reliant des sommets de A

=> (A*A)⋂ E(G)

II) Représentation d’un graphe

!

1) Représentation graphique - Isomorphisme

!

La représentation graphique d’un graphe G n’est pas unique:

Pour caractériser des structures qui sont identiques, on introduit l’isomorphisme

de graphes.

!

Définition: Deux graphes G et H sont isomorphes si il existe une bijection 


φ: V(G)→V(H)

(Il y a autant de sommets dans G et

...