Blog

Université Cadi Ayyad

Ecole Normale Supérieure de Marrakech

Licences professionnelles de qualification dans les métiers de l’éducation Option Informatique

Plan

• Introduction

• Qu’est ce qu’un graphe ?

• Les types de graphes         
  • Les graphes connexes
  • Les graphes non orientés
  • Les graphes orientés
  • Les graphes valués

• Exercice

Introduction à la théorie de graphe

• Quel est le plus court chemin (en distance ou en temps) pour se rendre d’une ville à une autre?
• Comment minimiser la longueur totale des connexions d’un circuit?
• Peut-on mettre une rue en sens unique sans rendre impossible la circulation en ville?

Qu’est ce qu’un graphe ?

Définition :

     Un graphe est défini par deux ensembles :

     un ensemble X= {x1 ; x2 ; …xn } dont les éléments sont appelés sommets , et un ensemble

A= {a1 ;a2; …am }, dont les éléments sont appelés arêtes.

On le note G= (X ;A).

 Le degré d’un sommet x de G :

 Le nombre d’arêtes incidentes à x. Il est noté d(x).

 Lorsque d(x)=0, on dit que le sommet x est isolé.

 Lorsque d(x)=1, on dit que le sommet x est pendant.

LES TYPES DE GRAPHE

Les graphes Connexes

Connexité :

  Un graphe G = (X, U) est connexe si i, j ϵX, il existe une chaîne entre i et j.

  Exemple :

Les graphes non orientés

Définition :

Un graphe non orienté G est déterminé par la donnée :

• d’un ensemble fini S dont les éléments sont appelés sommets ;
• d’un ensemble U de parties de S à un ou deux élément(s) .

chaîne  :

Une suite d’arêtes consécutives.

Cycle  : 

   Chaîne qui commence et se termine au même sommet.

Graphes eulériens

• On dit qu’un graphe est eulérien s’il est possible de trouver un cycle passant une et une seule fois par toutes les arêtes.
• On dit qu’un graphe est semi-eulérien s’il est possible de trouver une chaîne passant une et une seule fois par toutes les arêtes.

•(A; B; C; C; D; B) est une chaîne eulérienne. Ce graphe ne contient aucun cycle eulérien.

une des chaînes eulérienne possibles:  ACEDCBEAB Cycle eulérien : AEDCBECA

Graphes hamiltoniens

• On dit qu’un graphe est hamiltonien s’il est possible de trouver un cycle passant une et une seule fois par tous les sommets.
• On dit qu’un graphe est semi-hamiltonien s’il est possible de trouver une chaîne passant une et une seule fois par tous les sommets.

Dans le graphe ci-dessus, la chaîne ABCDEFG est une chaîne hamiltonienne.

Dans le graphe ci-dessous, BADECGFB est un cycle hamiltonien.

Matrice d’adjacences

  On peut représenter un graphe par une matrice d’adjacences. Une matrice (n x m) est un tableau de n lignes et m colonnes. (i,j) désigne l’intersection de la ligne i et de la colonne j.
Dans une matrice d’adjacences, les lignes et les colonnes représentent les sommets du graphe. Un 1 à la position (i,j) signifie que le sommet i est adjacent au sommet j.

Exemple :

Listes d’adjacences

• On peut aussi représenter un graphe en donnant pour chacun de ses sommets la liste des sommets auxquels il est adjacent.

Exemple:

Cherchons les listes d’adjacences du graphe G:

Exemple

Coloriage de sommet de graphe:

• Colorer un graphe consiste à affecter une couleur à chacun de ses sommets de sorte que deux sommets adjacents ne portent pas la même couleur. 

• Le nombre chromatique d’un graphe est le plus petit nombre de couleurs permettant de le colorer.

Algorithme de coloriage de sommet  d’un graphe

Exemple :

Solution :

Arbres :

• un arbre est un graphe non orienté, acyclique et connexe. Sa forme évoque en effet la ramification des branches d’un arbre.

Exemple:

Les arbres binaires 

Un arbre binaire est un arbre tel que les nœuds sont au plus deux fils (gauche et droit).

Exemple :

  Parcours d’arbres binaires :

• On appelle parcours d’un arbre binaire tout algorithme permettant d’accéder une fois et une seule à tous les nœuds de l’arbre.
• On distingue trois types de parcours:
  • Parcours en pré-ordre (préfixé) 
  • Parcours en post-ordre  (post fixé) 
  • Parcours en ordre (infixé) 

Parcours en pré-ordre (préfixé) :

Soit un arbre dont la racine est A et une référence gauche et droite à ses deux fils

VisiterPréfixe(Arbre A){

   Visiter(A)

  Si Non_Vide(gauche(A))      VisiterPréfixe(gauche(A))

   Si Non_Vide(droite(A))        VisiterPréfixe(droite(A))

}

     Dans cet ordre, chaque nœud est visité ainsi que chacun de ses fils

Exemple:

Parcours en post-ordre (post fixé) :

VisiterPostfixe(Arbre A) {

  Si Non_Vide(gauche(A))         VisiterPostfixe(gauche(A))

  Si Non_Vide(droite(A))      VisiterPostfixe(droite(A))

  Visiter(A)

}

     Dans un parcours postfixé, on affiche chaque nœud après avoir affiché chacun de ses fils.

Exemple :

Parcours en ordre (infixé) :

VisiterInfixe(Arbre A) {

  Si Non_Vide(gauche(A))

   VisiterInfixe(gauche(A))

  Visiter(A)

   Si Non_Vide(droite(A))

  VisiterInfixe(droite(A))

}

Exemple :

Les graphes orientés

Définition des graphes orientés

     Un graphe orienté ou digraphe  est un graphe dont les arêtes sont orientées, à savoir qu’il est possible de distinguer l’extrémité initiale d’une arête de son extrémité finale.

orienté     non orienté

    arc ↔ arête

chemin ↔ chaîne

circuit ↔ cycle

Matrice d’adjacences

  On peut représenter un digraphe par une matrice d’adjacences. Une matrice (n x m) est un tableau de n lignes et m colonnes. (i,j) désigne l’intersection de la ligne i et de la colonne j.
Dans une matrice d’adjacences, les lignes et les colonnes représentent les sommets du graphe. Un 1 à la position (i,j) signifie qu’un arc part de i pour rejoindre j.

Exemple:

Listes d’adjacences

• On peut aussi représenter un digraphe en donnant pour chacun de ses sommets la liste des sommets qu’on peut atteindre directement en suivant un arc (dans le sens de la flèche).

Exemple :

Algorithme de parcours en largeur

Étapes de l’algorithme :

1.Mettre le nœud de départ dans la file.

2.Retirer le nœud du début de la file pour l’examiner.

3.Mettre tous les voisins non examinés dans la file (à la fin).

4.Si la file n’est pas vide reprendre à l’étape 2.

    Exemple:

•Exploration en largeur à partir de 4 :

   4, 2, 5, 3, 6, 1

•Exploration en largeur à partir de 5 :

  5, 6, 3, 1, 4, 2

Parcours en profondeur :

Principe de  l’algorithme :

1-Dans le parcours en profondeur, on utilise une pile. On empile le sommet de départ.

2-Si le sommet de la pile présente des voisins qui ne sont pas dans la pile, ni déjà passés dans la pile : •alors on sélectionne l’un de ces voisins et on l’empile, •sinon on dépile (c’est a dire on supprime l‘élément du sommet de la pile).

3- On recommence au point 2 (tant que la pile n’est pas vide).

    Exemple:

•Exploration en profondeur à partir de 4 :

  4, 2, 3, 1, 5, 6

•Exploration en profondeur à partir de 3 :

  3, 1, 2, 4, 5, 6

Les graphes Valués

Définition :

Graphe où chacune des arêtes a une valeur numérique.

Poids de l’arête : Valeur attribuée à l’arête

Poids d’une chaîne : Somme des valeurs attribuées à chaque arête de la chaîne.

Poids du graphe : Somme des valeurs attribuées à chaque arête du graphe.

Ex. :  Le poids du graphe ABCDE est de 34.

Dijikstra : 

Enoncé:

Une association organise un rallye sportif en VTT : six zones de regroupement notées de A à F et sont reliées par des chemins représentés par les arêtes et pondérées par les distances, exprimées en km, nécessaires pour parcourir ces chemins.

  Un participant est actuellement au point de rendez-vous D et on lui signale qu’il a oublié son dossard au point B .

   Donner, le trajet correspondant à la distance la plus courte lui permettant d’aller récupérer son dossard .

Solution

Telecharger PDF