NUMERIQUE ET SCIENCES INFORMATIQUES

Niveau : Terminale générale, enseignement de spécialité NSI

D
É
C
O
N
N
E
C
T
É

Les graphes

1 - La théorie des graphes :

On a des sommets et des arrêtes ou arcs si la liaison n'est pas bidirectionnelle. Les sommets de notre graphe se sont les villes, les arrêtes représentent le poids : ici, la distance séparant deux villes entre elles.

Pour aller à Mulhouse à Nancy, quel sera le chemin le plus court :

Les successeurs de Mulhouse sont : Strasbourg, Nancy, Epinal et Vesoul

Les prédécesseurs de Vesoul sont : Nancy, Epinal et Mulhouse qui sont également ses successeurs.

Pour trouver le chemin le plus court dans ce graphe il existe l'algorithme de Dijkstra ou Prim traité à la fin du chapitre.

1.1 - Généralités :

Les graphes sont employés par exemple par les GPS pour trouver le chemin le plus court entre deux villes

villes   

Définitions

  • Un graphe est formé :
    • d'un ensemble S de sommets : les villes dans notre exemple.
    • d'un ensemble A de couples d'éléments de S, appelés arcs (pour les graphes orientés) ou arêtes (pour les graphes non orientés) : les distances séparant les villes.
  • On parle de graphe orienté si l'on distingue un sens pour les arcs. L'arc (i; j) est alors distinct de l'arc (i; j), et si le graphe contient un arc (j; i), il ne contient pas nécessairement l'arc (i; j).
  • Dans le cas contraire, on parle de graphe non orienté. Dans un graphe non orienté, l'arête (j; i) est la même que l'arête (i; j).
  • On représente souvent un graphe à l'aide d'une représentation sagittale dans laquelle :
    • les arcs sont représentés par des flèches dans le cas des graphes orientés
    • les arêtes sont représentées par des segments dans le cas des graphes non orientés, c'est le cas de notre exemple.
    • On appelle taille ou ordre du graphe le nombre de sommets du graphe.

    Remarques.

    • On se limitera dans ce chapitre à des graphes dans lesquels il y a au plus un arc entre deux sommets. On parle de 1-graphe.
    • Les graphes sont une structure de donnée relationnelle : ils permettent de représenter des situations dans lesquelles des éléments sont en relations les uns avec les autres : internet, web, réseau social, réseau routier, carte, labyrinthe...

    2 - Représentation d'un graphe orienté

    Outre la représentation sagittale, il existe plusieurs moyens de représenter un graphe :

    2.1 Tableau des successeurs

    Définitions

    S'il existe un arc (i; j) dans un graphe orienté, on dit que j est un successeur de i dans ce graphe.

    Remarque.

    On peut représenter un graphe par un tableau listant les successeurs de chaque sommet.

    Exemple.

    Sommet 1 2 3 4 5
    Successeurs

    2.2 Tableau des prédécesseurs

    Définitions

    S'il existe un arc (i; j) dans un graphe orienté, on dit que j est un successeur de i dans ce graphe.

    Remarque.

    On peut représenter un graphe par un tableau listant les prédécesseurs de chaque sommet.

    Exemple.

    Sommet 1 2 3 4 5
    Prédécesseurs

    2.3 Matrice d'adjacence

    Définitions

  • Une matrice est un tableau rectangulaire de nombres appelés coeffcients (ou termes, ou éléments). On la note entre parenthèses.
  • La matrice d'adjacence permet de répertorier les prédécesseurs et les successeurs de chaque sommet.
  • La lecture horizontale de la matrice permet de connaître les successeurs d'un sommet.
  • On place la valeur 1 si le sommet cible est un successeur, 0 si ce n'est pas un successeur.
  • La lecture verticale de la matrice permet de connaître le prédécesseur.
  • Exemple :

         1  2   3  4  5
    equation

    3 - Représentation d'un graphe non orienté

    3.1 Tableau des voisins

    Définitions

    S'il existe un arc (i; j) dans un graphe non orienté, on dit que i et j sont voisins.

    Remarque.

    La notion de voisin est l'équivalent pour les graphes non orientés des notions de prédécesseur et de successeur. On peut représenter un graphe par un tableau listant les voisins de chaque sommet.

    Exemple.

    Sommet 1 2 3 4 5
    Voisins

    3.3 Matrice d'adjacence

    Exemple :

    cliquez sur la matrice pour la modifier

    4 - Exercices

    4.1 Exercice 1

    On considère notre réseau routier :

    Etablir le tableau des villes voisines

    Ville Epinal Mulhouse Nancy Strasbourg Vesoul
    Voisins

    Donner la matrice d'ajacence du graphe

    4.2 Exercice 2

    On considère notre réseau routier mais avec certaines routes en sens unique :

    Etablir le tableau des villes voisines

    Ville Epinal Mulhouse Nancy Strasbourg Vesoul
    Voisins

    Donner la matrice d'ajacence du graphe

    4.3 Exercice 3

    On considère le graphe orienté donné par les tableau des successeurs ci-dessous :

    Sommet A B C D E
    SuccesseursBA, C, DBA

    Donner la matrice d'adjacence de ce graphe.

    Tracer une représentation sagittale de ce graphe. https://app.diagrams.net/

    4.4 Exercice 4

    0n considère la matrice ci-dessous :

    equation

    Cette matrice peut-elle correspondre à un graphe non orienté ?

    Tracer une représentation sagittale du graphe associé à cette matrice (on appellera A, B et C ses sommets).

    4.5 Exercice 5 : programmation

    Le but de cet exercice est de construire des représentations de graphes en Python. Dans cet exercice les sommets seront représentés par des entiers de 0 à n-1 où n est 'ordre du graphe. Pour faciliter les tests, une fonction d'affichage est fournie dans le affichier à compléter.

    • Copier et coller le code dans Thonny ou Edupython
    • Dans Edupython :
      • dans le menu outils - outils - installer un module avec conda, entrer networkx et valider.
    • Dans Thonny :
      • dans le menu outils - Gérer les Paquets...
      • recherchez le module networkx et installer-le.
      • Installer le module networkx.
      • Intaller ensuite le module matplotlib de la même manière.

    Ce fichier contient :

    • une fonction afficher_grapheO, qui permet d'afficher des graphes orientés, et plus précisément les objets des classes GrapheO ci-dessous, à conditions que toutes les méthodes aient été écrites,
    • une fonction afficher_grapheNO, qui permet d'afficher les objets de la classe GrapheNO ci-dessous, à conditions que toutes les méthodes aient été écrites.

    1) Compléter le fichier avec une classe GrapheO permettant de représenter des graphes orientés grâce à leur matrice d'adjacence et décrite ci-dessous :

    • Attributs : mat_adj de type list[list[int]]
    • Méthodes :
      • __init__(self, n) -> void : initialise une matrice d'ajacence d'un graphe d'ordre n sans aucun arc
      • ordre(self) -> int : retourne l'ordre du graphe
      • ajouter_arc(self,i,j) -> void : ajoute un arc du sommet i au sommet j
      • existe_arc(self, i, j) -> bool : retourne True si il existe un arc du sommet i au sommet j
      • liste_successeurs(self, i) -> list[int] : retourne la liste des successeurs du sommet i

    2) Compléter le fichier avec une classe GrapheNO permettant de représenter des graphes non orientés grâce à leur matrice d'adjacence et décrite ci-dessous :

    • Attributs : mat_adj de type list[list[int]]
    • Méthodes :
      • __init__(self, n) -> void : initialise une matrice d'ajacence d'un graphe d'ordre n sans aucun arc
      • ordre(self) -> int : retourne l'ordre du graphe
      • ajouter_arete(self,i,j) -> void : ajoute une arête entre les sommets i et j
      • existe_arete(self, i, j) -> bool : retourne True si il existe une arête entre les sommets i et j
      • liste_voisins(self, i) -> list[int] : retourne la liste des voisins du sommet i

    5 - Parcours des graphes

    5.1 Parcours en largeur

    Chemin

    Définitions

  • Un chemin dans un graphe est une suite d'arcs (ou d'arêtes) telle que chaque extré- mité d'arc soit l'origine de l'arc suivant. On notera (s1, s2, ..., sp) le chemin constituédes arcs (s1, s2), (s2, s3),..., (sp-1; sp).
  • La longueur d'un chemin est le nombre d'arcs qui le composent.
  • Un chemin qui a pour origine et pour extrémité un même sommet, qui ne passe pas deux fois par le même arc et qui contient au moins un arc s'appelle un cycle .
  • Exemple :

    Distance

    Définition

    La distance entre deux sommets d'un graphe est la longueur du plus court chemin reliant ces deux sommets, si un tel chemin existe. Si un tel chemin n'existe pas, la distance entre les deux sommets n'est pas définie.

    Exemple :

    Parcours en largeur

    Définitions

    On considère un graphe, dans lequel on se fixe un sommet de départ. Dans le parcours en largeur du graphe, on visite :

  • d'abord le sommet de départ,
  • puis tous les sommet à distance 1 du sommet de départ,
  • puis tous les sommet à distance 2 du sommet de départ,
  • et ainsi de suite jusqu'à avoir visité tous les sommets atteignables depuis le sommet
  • de départ.

    Remarque.

    Le parcours en largeur permet entre autres de déterminer les chemins les plus courts entre deux sommets. Il permet de ce fait de calculer la distance entre deux sommets.

    Exemple :

    Remarque.

    Pour éviter de passer deux fois par le même sommet, il est nécessaire, lorsqu'on parcourt un graphe, de garder une trace des sommets déjà visités.

    Exemple

    graph

    5.2 Mise en pratique

    On désirer trouver le chemin le plus court pour sortir d'un labyrinthe la distance séparant chaque sommet de son voisin est 1.

    laby    carte

    Le joueur (j) se trouve sur le sommet n°9 et la sortie (s) est au n°32

    Le graphe non orienté du labyrinthe est le suivant :

    grapheLaby

    Matrice d'adjacence partielle du labyrinthe :


     9 
    10 11 12 13 18 20 21 25 26 29 32 33 34 35 36 37
    9 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
    10 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0
    11 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
    12 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0
    13 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0
    18 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
    20 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0
    21 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0
    25 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0
    26 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0
    29 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1
    32 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
    33 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0
    34 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0
    35 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0
    36 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1
    37 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0

    5.2.1 - Création du graphe à partir des sommets

    Télécharger puis décompresser le fichier Labyrinthe.zip. Ouvrir le fichier Labyrinthe_EL.py et ajouter y les fonctions permettant de trouver le chemin le plus court vers la sortie, en appliquant la théorie les graphes.

    • Ecrire une fonction creer_graphe qui prend en paramètre sommets : la liste des sommets,
    • qui retourne 2-uplets : la matrice d'ajacence et l'objet de type GrapheNO

    Algorithme :

    Instancier un objet de classe GrapheNO ayant comme grandeur le nombre de sommets
    Parourir les tous les sommets
        si le sommet[i]+1 est dans la liste des sommets alors 
            ajouter une arrête entre sommets.index(sommets[i])et sommets.index(sommets[i]+1)
        si le sommets[i]+larg_laby est dans la liste des sommets 
            ajouter une arrête entre sommets.index(sommets[i])et sommets.index(sommets[i]+larg_laby)
    Retourner la matrice d'ajacence et l'objet GrapheNO
    

    5.2.2 Programmation du parcours en largeur

    Une façon de programmer un parcours en largeur est d'utiliser :

    une liste deja_visites contenant tous les sommets déjà visités,
    une file a_visiter contenant les prochains sommets à visiter,
    une liste parcours,
    Au début, deja_visites et parcours sont vides, a_visiter contient uniquement le sommet de départ.
    Répèter jusqu'à ne plus avoir de sommet à visiter :
        défiler un sommet (notons le s),
        si s n'a pas déjà été visité :
            ajouter s dans la liste deja_visites,
            ajouter s dans la liste du parcours,
            enfiler tous les voisins de s dans la file a_visiter.
    retourner la liste du parcours largeur

    • Écrire en Python la fonction parcours_largeur qui prend en paramètre le graphe non orienté graphe et l'indice du sommet de la position du personnage depart,
    • et retourne la liste des indices des sommets composant le parcours en largeur.

    5.2.3 Recherche du chemin le plus court vers la sortie

    Principe : on part de la sortie pour revenir vers la position joueur

    Exemple de la sortie au sommet 32 :

    graphe

    Tant que la sortie n'a pas atteint la position du joueur :

  • On commence par réduire la liste du parcours largeur jusqu'au sommet 32,
  • On recherche la liste voisins de 32 qui est [33]
  • on parcours la liste des voisin et s'il se trouve être le sommet précédent on l'ajoute denas la liste du parcours : 33
  • Le sommet précédent devient la nouvelle sortie et le cycle recommence.

    Cas du sommet 33 :

    La liste du parcours lageur est réduite à [9,10,11,18,12,26,13,20,25,34,14,21]

    Les voisins de 33 sont [25,32,34,41]

    On a dans cette situation deux voisins qui sont également dans la liste du parcours : 25 et 34. Peut importe du voisin qu'on choisisa, puisque la longueur du chemin sera identique.

    Algorithme :

    ch est une liste vide et contiendra les indices des sommets
    Tant que la sortie est différente de position alors
        Réduire la liste parcours à l'indexe de la sortie
    	mémoriser dans une variables la liste des voisins de la sortie
        Parcourrir la liste des voisins
            si un voisin se trouve dans la liste des voisins
                memoriser ce voisin
        ajouter ce voisin au Chemin
        remplacer la sortie par le voisin
    retourner la liste des indexe des sommets

    Ecrire en Python la fonction chemin qui prend en paramètres le graphe, le parcours largeur : la liste des indexes, sortie : l'indice de la sortie dans les sommets, pos : l'indice de la position du joueur dans la liste des sommets.

    Colez votre code python ci-dessous :

    5.3 Algorithme de recherche de chemin

    Les algorithmes de recherche de chemin, travaillent sur des graphes pondérés (par exemple pour rechercher la route entre un point de départ et un point d'arrivée dans un logiciel de cartographie). Ces algorithmes recherchent aussi souvent les chemins les plus courts. On peut citer l'algorithme de Dijkstra ou encore l'algorithme de Bellman-Ford qui recherchent le chemin le plus court entre un noeud de départ et un noeud d'arrivée dans un graphe pondéré.

    La vidéo ci-dessous explique le principe de fonctionnement de l'algorithme de Dijkstra.

    La vidéo ci-dessous explique le principe de fonctionnement de l'algorithme de Prim.

    Fond :  Texte :  Tables :  Thème du langage: