Graphes⚓︎

Introduction⚓︎

selon l'idée de Fabrice Nativel

Le problème des ponts de Königsberg⚓︎

Voici une illustration du problème des septs points de Königsberg extrait de la vidéo précédente :

On rappelle que le but du problème est de trouver un chemin qui permet de passer une seule et unique fois par chaque pont de la ville.

1. Faire quelques essais, que penser de ce problème ?
   
2. Vers les graphes
   

On divise la ville en quatre zones notées N (nord de la ville), S (sud de la ville), I (île centrale) et E (est de la ville) comme illustré ci-dessous. Faire un schéma en représentant chaque zone par un rond et un pont par un lien entre ces zones.

1. Notion de graphe et vocabulaire⚓︎

Le concept de graphe permet de résoudre de nombreux problèmes en mathématiques comme en informatique. C'est un outil de représentation très courant, et nous l'avons déjà rencontré à plusieurs reprises, en particulier lors de l'étude de réseaux.

1.1 Exemples de situations⚓︎

1.1.1 Réseau informatique⚓︎

1.1.2 Réseau de transport⚓︎

1.1.3 Réseau social⚓︎

1.1.4 Généralisation⚓︎

Une multitude de problèmes concrets d'origines très diverses peuvent donner lieu à des modélisations par des graphes : c'est donc une structure essentielle en sciences, qui requiert un formalisme mathématique particulier que nous allons découvrir.

L'étude de la théorie des graphes est un champ très vaste des mathématiques : nous allons surtout nous intéresser à l'implémentation en Python d'un graphe et à différents problèmes algorithmiques qui se posent dans les graphes.

1.2 Vocabulaire⚓︎

En général, un graphe est un ensemble d'objets, appelés sommets ou parfois nœuds (vertex or nodes en anglais) reliés par des arêtes ou arcs ((edges en anglais)). Ce graphe peut être non-orienté ou orienté .

1.2.1 Graphe non-orienté⚓︎

Dans un graphe non-orienté, les arêtes peuvent être empruntées dans les deux sens, et une chaîne est une suite de sommets reliés par des arêtes, comme C - B - A - E par exemple. La longueur de cette chaîne est alors 3, soit le nombre d'arêtes.

Les sommets B et E sont adjacents au sommet A, ce sont les voisins de A.

Exemple de graphe non-orienté : le graphe des relations d'un individu sur Facebook est non-orienté, car si on est «ami» avec quelqu'un la réciproque est vraie.

1.2.2 Graphe orienté⚓︎

Dans un graphe orienté, les arcs ne peuvent être empruntés que dans le sens de la flèche, et un chemin est une suite de sommets reliés par des arcs, comme B → C → D → E par exemple.

Les sommets C et D sont adjacents au sommet B (mais pas A !), ce sont les voisins de B.

Exemple de graphe orienté : le graphe des relations d'un individu sur Twitter est orienté, car on peut «suivre» quelqu'un sans que cela soit réciproque.

1.2.3 Graphe pondéré⚓︎

Un graphe est pondéré (ou valué) si on attribue à chaque arête une valeur numérique (la plupart du temps positive), qu'on appelle mesure, poids, coût ou valuation.

Par exemple:

• dans le protocole OSPF, on pondère les liaisons entre routeurs par le coût;
• dans un réseau routier entre plusieurs villes, on pondère par les distances.

1.2.4 Connexité⚓︎

Un graphe est connexe s'il est d'un seul tenant: c'est-à-dire si n'importe quelle paire de sommets peut toujours être reliée par une chaîne. Autrement un graphe est connexe s'il est «en un seul morceau».

Par exemple, le graphe précédent est connexe. Mais le suivant ne l'est pas: il n'existe pas de chaîne entre les sommets A et F par exemple.

Il possède cependant deux composantes connexes : le sous-graphe composé des sommets A, B, C, D et E d'une part et le sous-graphe composé des sommets F, G et H.

2. Modélisations d'un graphe⚓︎

Pour modéliser un graphe, il faut établir par convention une manière de donner les renseignements suivants :

• qui sont les sommets ?
• pour chaque sommet, quels sont ses voisins ? (et éventuellement quel poids porte l'arête qui les relie)

2.1 Représentation par matrice d'adjacence⚓︎

2.1.1 Graphe non orienté⚓︎

Dans ce graphe non orienté, comme B est voisin de C, C est aussi voisin de B, ce qui signifie que l'arête qui relie B et C va donner lieu à deux "1" dans la matrice, situé de part et d'autre de la diagonale descendante (un mathématicien parlera de matrice symétrique).

2.1.2 Graphe orienté⚓︎

2.1.3 Graphe pondéré⚓︎

2.1.4 Exercices⚓︎

2.1.5 Implémentation Python des matrices d'adjacence⚓︎

G = [[0, 1, 1, 1, 1],
      [1, 0, 1, 0, 0],
      [1, 1, 0, 1, 0],
      [1, 0, 1, 0, 1],
      [1, 0, 0, 1, 0]]

Complexité en mémoire et temps d'accès :

• Pour un graphe à \(n\) sommets, la complexité en mémoire (appelée aussi complexité spatiale) de la représentation matricielle est en \(O(n^2)\).

• Tester si un sommet est isolé (ou connaître ses voisins) est en \(O(n)\) puisqu'il faut parcourir une ligne, mais tester si deux sommets sont adjacents (voisins) est en \(O(1)\), c'est un simple accès au tableau.

La modélisation d'un graphe par sa matrice d'adjacence est loin d'être la seule manière de représenter un graphe : nous allons voir une autre modélisation, par liste d'adjacence.

2.2 Représentation par listes d'adjacence⚓︎

1
2
3
4
5
6

G = {'A': ['B', 'C', 'D', 'E'],
     'B': ['A', 'C'],
     'C': ['A', 'B', 'D'],
     'D': ['A', 'C', 'E'],
     'E': ['A', 'D']
    }

Complexité en mémoire et temps d'accès :

• Pour un graphe à \(n\) sommets et \(m\) arêtes, la complexité spatiale de la représentation en liste d'adjacence est en \(O(n+m)\). C'est beaucoup mieux qu'une matrice d'adjacence lorsque le graphe comporte peu d'arêtes (i.e. beaucoup de 0 dans la matrice, non stockés avec des listes).

• Tester si un sommet est isolé (ou connaître ses voisins) est en \(O(1)\) puisqu'on y accède immédiatement, mais tester si deux sommets sont adjacents (voisins) est en \(O(n)\) car il faut parcourir la liste.

2.2.1 Exercices⚓︎

G1 = {
'A': ['B', 'C'],
'B': ['A', 'C', 'E', 'F'],
'C': ['A', 'B', 'D'],
'D': ['C', 'E'],
'E': ['B', 'D', 'F'],
'F': ['B', 'E']
     }

G2 = {
'A': ['B'],
'B': ['C', 'E'],
'C': ['B', 'D'],
'D': [],
'E': ['A']
     }

3. Création d'une classe Graphe⚓︎

Dans cette partie, nous ne traiterons que des graphes non-orientés.

3.1 Interface souhaitée⚓︎

Nous voulons que le graphe puisse être créé grâce aux instructions suivantes :

g = Graphe(['A', 'B', 'C', 'D', 'E'])
g.ajoute_arete('A', 'B')
g.ajoute_arete('A', 'C')
g.ajoute_arete('A', 'D')
g.ajoute_arete('A', 'E')
g.ajoute_arete('B', 'C')
g.ajoute_arete('C', 'D')
g.ajoute_arete('D', 'E')

Nous souhaitons aussi pouvoir tester si deux sommets sont voisins avec la méthode sont_voisins :

>>> g.sont_voisins('E', 'A')
True
>>> g.sont_voisins('E', 'B')
False

Enfin, nous voulons pouvoir obtenir facilement la liste de tous les voisins d'un sommet avec la méthode voisins:

>>> g.voisins('C')
['A', 'B', 'D']

3.2 Conseils d'implémentation⚓︎

L'objet de type Graphe aura comme attributs :

• une liste liste_sommets (donnée en paramètre dans la liste liste_sommets)
• un dictionnaire adjacents, où chaque sommet se verra attribuer une liste vide [].

3.3 Implémentation⚓︎

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Graphe:
    def __init__(self, liste_sommets):
        self.liste_sommets = ...
        self.adjacents = ...

    def ajoute_arete(self, sommetA, sommetB):
        ...
        ...

    def voisins(self, sommet):
        return ...

    def sont_voisins(self, sommetA, sommetB):
        return ...

Implémentation d'une classe Graphe

🐍 Script Python

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95

class Graphe: def __init__(self, liste_sommets): #premier attribut : la liste des sommets self.liste_sommets = liste_sommets #second attribut : un dictionnaire des adjacents #pour chaque sommet de la liste des sommets, on crée une liste vide self.adjacents = {sommet : [] for sommet in liste_sommets} def autre_constructeur(self, liste_sommets): '''Autre constructeur possible pour la classe Graphe''' self.liste_sommets = liste_sommets #initialisation du dictionnaire des adjacents self.adjacents = {} #pour chaque sommet de la liste des sommets, on crée une liste vide for sommet in liste_sommets: self.adjacents[sommet]=[] def ajoute_arete(self, sommetA, sommetB): '''' Procédure permettant d'ajouter une arête entre deux sommets @param sommetA : le premier sommet @param sommetB : le second sommet @pas de retour ''' self.adjacents[sommetA].append(sommetB) self.adjacents[sommetB].append(sommetA) def voisins(self, sommet): '''' Méthode permettant de récupérer la liste des voisins d'un sommet @param sommet : le sommet dont on veut connaître les voisins @return la liste des voisins du sommet ''' return self.adjacents[sommet] def sont_voisins(self, sommetA, sommetB): '''' Méthode permettant de savoir si deux sommets sont voisins @param sommetA : le premier sommet @param sommetB : le second sommet @return True si les deux sommets sont voisins, False sinon ''' return sommetB in self.adjacents[sommetA] def __str__(self): return str(self.adjacents) def supp_arete(self, sommetA, sommetB): '''' Procédure permettant de supprimer une arête entre deux sommets @param sommetA : le premier sommet @param sommetB : le second sommet @pas de retour ''' self.adjacents[sommetA].remove(sommetB) self.adjacents[sommetB].remove(sommetA) def ajoute_sommet(self, sommet): '''' Procédure permettant d'ajouter un sommet @param sommet : le sommet à ajouter @pas de retour ''' self.liste_sommets.append(sommet) self.adjacents[sommet]=[] #Proposer une méthode permettant de supprimer un sommet. def supp_sommet(self, sommet): '''' Procédure permettant de supprimer un sommet @param sommet : le sommet à supprimer @pas de retour ''' self.liste_sommets.remove(sommet) del self.adjacents[sommet] for s in self.liste_sommets: if sommet in self.adjacents[s]: self.adjacents[s].remove(sommet) return def matriceAdjacence(self): ''' Méthode permettant de renvoyer la matrice d'adjacence du graphe @return la matrice d'adjacence ''' n = len(self.liste_sommets) #initialisation de la matrice n x n à 0 matrice = [[0 for i in range(n)] for j in range(n)] #pour chaque point de la matrice, on regarde si il existe une arête entre les sommets correspondants for i in range(n): for j in range(n): if self.sont_voisins(self.liste_sommets[i], self.liste_sommets[j]): matrice[i][j] = 1 return matrice

4. Parcours de graphes ⚓︎

Le choix de la structure de l'ensemble S est prépondérant:

• Si on choisit une file (FIFO): on visitera les sommets dans l'ordre d'arrivée, donc les plus proches du sommet précédent. On obtient donc un parcours en largeur BFS.
• Si on choisit une pile (LIFO): on visitera d'abord les derniers sommets arrivés, donc on parcourt le graphe en visitant à chaque étape un voisin du précédent. On obtient donc un parcours en profondeur DFS.

4.1 Le parcours en largeur (BFS, Breadth First Search)⚓︎

4.1.1 Principe⚓︎

Exemple de parcours en largeur, avec B comme sommet de départ:

Codes couleur :

• vert : les sommets non encore traités.
• rouge : le sommet en cours de traitement.
• orange : la file d'attente des sommets qui seront bientôt traités. On y rajoute à chaque fois les voisins du sommet en cours de traitement, uniquement si ils n'ont pas encore été découverts.
• noir : les sommets traités.

4.1.2 Algorithme BFS⚓︎

On utilise :

• une liste traites qui recueille les sommets visités (c'est-à-dire qu'on a fini de traiter, après avoir ajouté ses voisins dans la file d'attente) et qui sera renvoyée à la fin de l'algorithme;
• une liste decouverts qui contient les sommets découverts au fur et à mesure du parcours;
• une file en_attente qui contient les sommets découverts mais non encore visités. On utilisera au choix une classe File écrite plus tôt dans l'année ou tout simplement une list en utilisant pop(0) (pour défiler) et append() (pour enfiler).

En début d'algorithme, seul le sommet de départ depart donné en paramètre est découvert. La fonction BFS renvoie la liste des sommets dans l'ordre de visite lors du parcours en largeur.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

def BFS(g, depart):
    '''
    Effectue un parcours en largeur du graphe g en partant du sommet depart,
    et renvoie la liste des sommets visités dans l'ordre du parcours.
    '''
    traites = []
    decouverts = [depart]
    en_attente = [depart]
    while en_attente != [] :
        sommet = en_attente.pop(0)
        voisins = g.voisins(sommet)
        for voisin in voisins:
            if voisin not in decouverts:
                decouverts.append(voisin)
                en_attente.append(voisin)
        traites.append(sommet)
    return traites

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

g = Graphe(['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'])
g.ajoute_arete('A', 'B')
g.ajoute_arete('A', 'C')
g.ajoute_arete('B', 'D')
g.ajoute_arete('D', 'C')
g.ajoute_arete('B', 'E')
g.ajoute_arete('D', 'E')
g.ajoute_arete('E', 'F')
g.ajoute_arete('E', 'G')
g.ajoute_arete('F', 'G')
g.ajoute_arete('G', 'H')

>>> BFS(g, 'B')
['B', 'A', 'D', 'E', 'C', 'F', 'G', 'H']

>>> BFS(g, 'D')
['D', 'B', 'C', 'E', 'A', 'F', 'G', 'H']
>>> BFS(g, 'G')
['G', 'E', 'F', 'H', 'B', 'D', 'A', 'C']

4.1.3 Application du BFS : recherche du plus court chemin⚓︎

L'algorithme BFS découvre les sommets «par cercles concentriques» autour du point de départ (ainsi que le montre la structure de la file d'attente). On découvre d'abord tous les sommets à la distance 1 du point de départ, puis à la distance 2, puis 3, etc.

Un sommet situé à la distance 5 sera découvert en tant que voisin d'un sommet à la distance 4, qui lui-même aura été découvert grâce à un sommet à la distance 3, qui lui-même...

On comprend donc que si on arrive à se souvenir du sommet «parent» de chaque sommet (celui qui lui a permis d'être découvert), on pourra alors reconstituer un chemin permettant de remonter au point de départ.

Nous allons pour cela nous servir d'une structure de dictionnaire pour associer à chaque sommet son sommet-parent.

Il faudra ensuite une fonction pour recréer le chemin.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

def recherche_chemin(g, depart, arrivee):
    '''
    Parcours en largeur du graphe g en partant du sommet depart,
    qui s'arrête dès que le sommet arrivee est atteint.
    Renvoie alors le chemin du depart vers arrivee.
    '''
    traites = []
    decouverts = [depart]
    en_attente = [depart]
    parent = {}
    while en_attente != [] :
        sommet = en_attente.pop(0)
        voisins = g.voisins(sommet)
        for voisin in voisins:
            if voisin not in decouverts:
                decouverts.append(voisin)
                en_attente.append(voisin)
                parent[voisin] = sommet
                if voisin == arrivee:
                    return remonte_chemin(depart, arrivee, parent)
        traites.append(sommet)
    return "non trouvé"  


def remonte_chemin(depart, arrivee, parent):
    sommet = arrivee
    chemin = arrivee
    while sommet != depart:
        sommet = parent[sommet]
        chemin = sommet + chemin
    return chemin

4.2 Le parcours en profondeur (DFS, Depth First Search)⚓︎

4.2.1 Parcours DFS récursif⚓︎

Le parcours en profondeur est un parcours où on va aller «le plus loin possible» sans se préoccuper des autres voisins non visités : on va visiter le premier de ses voisins non traités, qui va faire de même, etc. Lorsqu'il n'y a plus de voisin, on revient en arrière pour aller voir le dernier voisin non visité.

Dans un labyrinthe, ce parcours s'explique très bien : on prend tous les chemins sur la droite jusqu'à rencontrer un mur, auquel cas on revient au dernier embranchement et on prend un autre chemin, puis on repart à droite, etc.

C'est un parcours qui s'écrit naturellement de manière récursive :

1
2
3
4
5
6

def DFSrec(g, traites, actuel):
    traites.append(actuel)
    for voisin in g.voisins(actuel):
        if voisin not in traites:
            DFSrec(g, traites, voisin)
    return traites

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class Graphe:
    def __init__(self, liste_sommets):
        self.liste_sommets = liste_sommets
        self.adjacents = {sommet : [] for sommet in liste_sommets}

    def ajoute_arete(self, sommetA, sommetB):
        self.adjacents[sommetA].append(sommetB)
        self.adjacents[sommetB].append(sommetA)

    def voisins(self, sommet):
        return self.adjacents[sommet]

    def sont_voisins(self, sommetA, sommetB):
        return sommetB in self.adjacents[sommetA]


g = Graphe(['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'])
g.ajoute_arete('A', 'B')
g.ajoute_arete('A', 'C')
g.ajoute_arete('B', 'D')
g.ajoute_arete('D', 'C')
g.ajoute_arete('B', 'E')
g.ajoute_arete('D', 'E')
g.ajoute_arete('E', 'F')
g.ajoute_arete('E', 'G')
g.ajoute_arete('F', 'G')
g.ajoute_arete('G', 'H')


def DFSrec(g, traites, actuel):
    traites.append(actuel)
    for voisin in g.voisins(actuel):
        if voisin not in traites:
            DFSrec(g, traites, voisin)
    return traites

>>> DFSrec(g, [], 'A')
['A', 'B', 'D', 'C', 'E', 'F', 'G', 'H']

4.2.2 Parcours DFS itératif⚓︎

Il «suffit» de remplacer la file du parcours BFS par une pile. Ainsi, on partira visiter le voisin tout juste ajouté à la file d'attente (qui porte maintenant mal son nom, puisque c'est devenu une pile).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def DFS_iteratif(graphe, start):
    traites = []
    en_attente = [start]
    while en_attente != []:
        actuel = en_attente.pop()
        if actuel not in traites:
            voisins = g.voisins(actuel)[::-1]
            for voisin in voisins:
                if voisin not in traites:
                    en_attente.append(voisin)
            traites.append(actuel)
    return traites

Remarques :

• À la ligne 7, on inverse l'ordre des voisins pour que ce code renvoie le même parcours quele parcours récursif (sinon c'est le dernier voisin ajouté qui sera dépilé). Cela n'est pas obligatoire : il n'y a pas «un seul» parcours DFS (tout comme il n'y a pas qu'un seul BFS). Ce qui les caractérise est la méthode de découverte, plus que l'implémentation proprement dite.

• Contrairement au BFS, il est possible d'empiler un sommet déjà découvert (on vérifie juste qu'il n'ait pas déjà été traité). Vous pouvez vous en apercevoir en écrivant l'état de la pile lors du parcours DFS itératif du graphe de l'exercice 6.