C22 Les Graphes ⚓︎

Introduction⚓︎

Problème des 7 ponts de Königsberg

Le problème des sept ponts de Königsberg est connu pour être à l'origine de la topologie et de la théorie des graphes. Résolu par Leonhard Euler en 17351, ce problème mathématique se présente de la façon suivante :

-> ->

La ville de Königsberg (aujourd'hui Kaliningrad) est construite autour de deux îles situées sur le Pregel et reliées entre elles par un pont. Six autres ponts relient les rives de la rivière à l'une ou l'autre des deux îles, comme représentés sur le plan ci-dessus. Le problème consiste à déterminer s'il existe ou non une promenade dans les rues de Königsberg permettant, à partir d'un point de départ au choix, de passer une et une seule fois par chaque pont, et de revenir à son point de départ, étant entendu qu'on ne peut traverser le Pregel qu'en passant sur les ponts.

Source wikipédia

Initiée par le grand mathématicien suisse Euler, avec le célèbre problème des 7 ponts de Königsberg, les applications de la théorie des graphes et de la recherche opérationnelle sont aujourd'hui immenses tant au plan civil que militaire :

aide à la prise de décision ;
recherche de la meilleure stratégie ;
optimisation (plus court chemin, GPS, coût minimal, ordonnancement des tâches ...) ;
réseaux de transports (autoroutes, chemins de fer, métro, lignes aériennes ...) ;
transport de l'énergie (électricité, gaz ...) ;
transport de l'informations : internet, réseaux sociaux ...

Notion de graphe et vocabulaire⚓︎

La théorie des graphes n'est pas une branche indépendante des mathématiques, elle se rattache à la programmation linéaire, la programmation convexe (où le concept plus général de fonction convexe remplace les fonctions linéaires et affines), le calcul des probabilités.
Les graphes sont une structure de données très riche permettant de modéliser des situations variées de relations entre un ensemble d'entités.

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.

Exemples de situations

Réseau informatiqueRéseau de transportRéseau socialMais aussi

On trouve également des applications de la théorie des graphes dans bien d'autres domaines: ...

Ce qu'il faut retenir

D’un point de vue mathématique, un graphe est la donnée

d’un certain nombre de points du plan, appelés sommets ,
certains étant reliés par des segments de droites ou de courbes (simples) appelés arêtes ,
la disposition des sommets et la forme choisie pour les arêtes n’intervenant pas.
Le nombre de sommets du graphe est son ordre.

Graphe non orienté⚓︎

Sauf indication contraire, un graphe sera considéré comme non orienté et les arêtes pourront être parcourues dans les deux sens.

Ce qu'il faut retenir

Dans le cas des graphes non orientés, les relations entre deux sommets se font dans les deux sens. On appelle ses relations des arêtes (edges en anglais), et on a les définitions suivantes :

Sommets adjacents : deux sommets sont adjacents s’ils sont reliés entre eux par une arête.
On dit que l’arête est incidente aux deux sommets.
Voisins d’un sommet x : ce sont tous les sommets reliés à x par une arête.
Degré d’un sommet x : nombre d’arêtes incidentes au sommet, on le note d (x).
Chaîne : séquence ordonnée d’arêtes telle que chaque arête a une extrémité en commun avec l’arête suivante.
Cycle : dans un graphe non orienté, un cycle est une suite d’arêtes consécutives (chaîne) dont les deux sommets extrémités sont identiques.
Boucle : il peut exister des arêtes entre un sommet x et lui-même. Elles sont appelés boucles.

Exercice 1

Citer des sommets adjacents.
Donner le degré de chacun des sommets.
Citer une chaîne.
Donner un cycle.
Y-t-il une boucle ?

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.

Ce qu'il faut retenir

Dans le cas des graphes orientés, les arêtes ont un sens et elles sont appelées arcs. Par exemple,
l’arête a = (x, y) indique qu’il y a un arc d’origine x et d’extrémité finale y. De plus, on a les définitions suivantes.

Successeurs et prédécesseurs d’un sommet x : dans un graphe orienté on ne parle plus de voisins d’un sommet mais de ses successeurs et de ses prédécesseurs : le successeurs de x sont tous les sommets y tels qu’il existe un arc (x, y) (de x vers y) et les prédécesseurs de x sont tous les sommets w tels qu’il existe un arc (w, x) (de w vers x).
Chemin : séquence ordonnée d’arcs consécutifs (on parlait de chaîne dans un graphe non orienté).
Circuit : dans un graphe orienté, un circuit est une suite d’arcs consécutifs (chemin) dont les deux sommets extrémités sont identiques.
Degré d’un sommet x : cette notion existe aussi dans le cas des graphes orientés. On distingue le degré entrant d’un sommet x (noté $d_-(x)$= nombre de prédécesseurs de x) et le degré sortant d’un sommet x (noté $d_+(x)$= nombre de successeurs de x ). Le degré d’un sommet x vaut $d (x) = d_+(x) + d_-(x)$.
• Boucle : ce sont les arcs entre un sommet et lui-même.

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.

Réseaux sociaux : modélisation par un graphe⚓︎

Au premier trimestre 2020, Facebook© revendiquait 2,6 milliards d'utilisateurs actifs chaque mois, en hausse de 9,2% par rapport à début 2019. Le réseau social américain a passé la barre symbolique des 2 milliards au deuxième trimestre 2017. A noter que 42% des utilisateurs actifs mensuels de Facebook viennent d'Asie-Pacifique, 15,6% sont Européens et 9,7% sont Nord-américains. Facebook permet à ses utilisateurs d'entrer des informations personnelles et d'interagir avec d'autres utilisateurs. Les interactions entre utilisateurs reposent sur la notion « d'amis ».

Principe de la modélisation par un graphe non orienté⚓︎

Imaginez un réseau social ayant 7 abonnés (L, M, N, O, P, Q et R) où :

L est ami avec M, N, O et P ;
M est ami avec L et P ;
N est ami avec L, O et P ;
O est ami avec L,N,P,Q et R ;
P est ami avec O,L et M ;
Q est ami avec N et O ;
R est ami avec O.

La description de ce réseau social, malgré son faible nombre d'abonnés, est déjà quelque peu compliquée, alors imaginez cette même description avec un réseau social comportant des millions d'entre eux !
Il existe un moyen plus "visuel" pour représenter ce réseau social :
on peut représenter chaque abonné par un cercle (avec le nom de l'abonné situé dans le cercle) et chaque relation "X est ami avec Y" par un segment de droite reliant X et Y ("X est ami avec Y" et "Y est ami avec X" étant représenté par le même segment de droite). Le mini-réseau social décrit précédemment peut être modélisé sous la forme du graphe ci-dessous :

Implémentation - Matrice d'adjacence⚓︎

Activité 1 : Implémentation avec matrice d'adjacence⚓︎

Principe de l'implémentation
On prend l'exemple du graphe orienté suivant :

a. Recopier et compléter le tableau suivant dans lequel les lignes et les colonnes représentent les sommets et dans lequel on indique par un 1 la présence d'une arête allant du sommet de la ligne vers celui de la colonne et par 0 son absence

A B C D E F

A 0 1 0 0 0 1

B

C

D

E

F

Note

Si on numérote les sommets du graphe (A le numéro 1, B le numéro 2, ...), il n'est plus nécessaire d'indiquer les noms des sommets sur les lignes et les colonnes.

b. De façon générale, une matrice en mathématiques est un tableau de nombres, ici, on a donc représenté notre graphe par une matrice appelé matrice d'adjacence de ce graphe :

\[\begin{pmatrix} 0 & 1 & 0 & 0 & 0 & 1 \\ \dots & \dots & \dots & \dots & \dots & \dots \\ \dots & \dots & \dots & \dots & \dots & \dots \\ \dots & \dots & \dots & \dots & \dots & \dots \\ \dots & \dots & \dots & \dots & \dots & \dots \\ \end{pmatrix}\]

En nommant les sommets A, B, C, D et E dessiner le graphe dont la matrice d'adjacence est :

\[\begin{pmatrix} 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1\\ 0 & 0 & 0 & 0 & 0\\ 1 & 1 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 0\\ \end{pmatrix}\]

c. Que peut-on dire d'un graphe dont la matrice d'adjacence est symétrique par rapport à sa diagonale principale ?

d. Proposer une méthode pour représenter un graphe pondéré par une matrice d'adjacence.
Implémentation en python
On s'inspire de ce qui a été fait pour les arbres et on utilisera la poo pour représenter un graphe par sa matrice d'adjacence. Enfin, on suppose qu'on implémente des graphes orientés.
1. Pour le constructeur de la classe Graphe, on propose de fournir uniquement les sommets et de créer l'objet graphe ayant sa matrice d'adjacence vide initialement. De plus on ajoute un attribut taille au graphe. Compléter le code ci-dessous :
🐍 Script Python
```
class Graphe:

    def __init__(self,sommets):
        self.sommets=sommets
        self.taille = len(......)
        self.matrice = .............  #construction par compréhension avec que des 0
```
1. Poursuivre cette implémentation en ajoutant une méthode d'ajout d'une arête.
  Aide
  - Cette méthode prend en paramètre l'origine et l'extrémité de l'arête à ajouter.
  - On pourra vérifier que l'origine et l'extrémité sont bien dans la liste de sommets et rechercher leur position grâce à la méthode index des listes de python.
2. Ajouter une méthode de suppression d'une arête
3. Ajouter une méthode d'affichage de la matrice d'adjacence
4. Ecrire la méthode voisins qui prend en paramètre un sommet et renvoie la liste de ses voisins.

Activité 2 : Implémentation avec des listes d'adjacences⚓︎

Principe de l'implémentation
On reprend l'exemple du graphe orienté déjà utilisé à l'activité précédente

a. Compléter le schéma suivant où on a fait figuré à côté de chaque sommet la liste des sommets adjacents :
- A : B,F
- B : ...
- C : ...
- . : ...
- . : ...
- . : ...
b. Dessiner le graphe dont la représentation par liste d'adjacence est :
- R : S
- S : R,T,U,V
- T : V
- U : None
- V : R,U
Implémentation en Python
On donne ci-dessous le constructeur d'une classe Graphe qui implémente les graphes sous la forme de listes d'adjacence :
🐍 Script Python
```
class Graphe:

    def __init__(self,sommets):
        self.taille = len(sommets)
        self.listes = {}
        for s in sommets:
            self.listes[s]=[]
```
a. Quel est le type de l'attribut listes d'un objet de la classe Graphe ?

b. On suppose qu'on crée un objet de la classe Graphe en donnant en paramètre la liste ["A","B","C","D"]. Quel est alors le contenu de l'attribut listes de cet objet ?

c. Poursuivre cette implémentation en ajoutant une méthode d'ajout d'une arête.

d. Ajouter une méthode de suppression d'une arête

e. Proposer une méthode permettant d'ajouter un sommet.

f. Proposer une méthode permettant de supprimer un sommet.

g. Ecrire la méthode voisins qui prend en paramètre un sommet et renvoie la liste de ses voisins.

Activité 3 : Parcours d'un graphe⚓︎

Visualisation d'un parcours depth first search
Un outil en ligne, permet de visualiser le résultat du parcours en profondeur d'un graphe. Un graphe est donné en exemple, mais vous pouvez le modifier ou construire le votre.

Attention

Dans les menus déroulants, bien choisir Alorithme : DFS et Example graph : directedGraph
Visualisation d'un parcours breadth first search
Ce même outil en ligne, permet de visualiser le résultat du parcours en largeur d'un graphe. Un graphe est donné en exemple, mais vous pouvez le modifier ou construire le votre :

Attention

Dans les menus déroulants, bien choisir Alorithme : BFS et Example graph : directedGraph
On considère le graphe suivant :
```
graph LR
A(("A"))
B(("B"))
C(("C"))
D(("D"))
E(("E"))
F(("F"))
G(("G"))
A --> B
A --> C
B --> D
C --> F
C --> G
E --> G
A --> E
D --> F
G --> F
B --> C
```
a. Prévoir l'ordre de parcours pour un parcours en profondeur en commençant par le sommet A. Vérifier en testant dans l'outil en ligne.

b. Même question pour un parcours en largeur.

Exercices :⚓︎

Exercice 1 : Vocabulaire sur les graphes⚓︎

On considère le graphe suivant :

graph LR
A(("A"))
B(("B"))
C(("C"))
D(("D"))
E(("E"))
F(("F"))
G(("G"))
H(("H"))
A --- B
A --- C
C --- F
C --- G
E --- G
G --- F
B --- E
C --- H
B --- D
D --- C

Ce graphe est-il orienté ? simple ? complet ? pondéré ?
Donner la liste des voisins de C.
Quel est le degré de G ?
Quels sont les sommets adjacents à A ?

Exercice 2 : Graphe complet⚓︎

Rappeler la définition d'un graphe complet
Dessiner un graphe complet à cinq noeuds.
Combien d'arêtes possède ce graphe ?
Donner la matrice d'adjacence de ce graphe.
Quel est le nombre d'arêtes d'un graphe complet à $n$ noeuds ?

Aide

On pourra utiliser sans avoir à le prouver que : $ 1 + 2 + \dots + n = \dfrac{n(n+1)}{2} $

Exercice 3 : Représentation par matrice d'adjacence⚓︎

Donner la matrice d'adjacence du graphe suivant :

graph LR
A(("A"))
B(("B"))
C(("C"))
D(("D"))
E(("E"))
A --- B
A --- C
C --- E
D --- E
B --- C
C --- D

Dessiner le graphe dont la matrice d'adjacence est :

\[\begin{pmatrix} 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 \\ \end{pmatrix}\]

Exercice 4 : Représentation par listes d'adjacence⚓︎

Donner la représentation sous forme de listes d'adjacences du graphe suivant :

graph LR
A(("A"))
B(("B"))
C(("C"))
D(("D"))
E(("E"))
A --- B
A --- C
C --- E
D --- E
B --- C
C --- D

Dessiner le graphe dont la représentation sous forme de listes d'adjacence est :
- A : [B]
- B : [C,D,E]
- C : [F]
- D : [F]
- E : [F]

Exercice 5 : Parcours d'un graphe⚓︎

On considère le graphe suivant :

graph LR
A(("A"))
B(("B"))
C(("C"))
D(("D"))
E(("E"))
F(("F"))
G(("G"))
A --> B
A --> C
G --> E
C --> D
D --> F
B --> E
E --> F
A --> G

Donner l'ordre de parcours des sommets pour un parcours en largeur en partant de A
Même question pour un parcours en profondeur

Exercice 6 : Implémentation par matrice d'adjacence⚓︎

Récupérer, et revoir l'implémentation des graphes réalisée précédement :
Implémentation graphes par matrice
Utiliser cette implémentation pour créer le graphe de sommets A,B,C,D,E et dont la matrice d'adjacence est :

\[\begin{pmatrix} 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ \end{pmatrix}\]

Ajouter la méthode parcours_largeur ci-dessous à cette implémentation en la complétant.

🐍 Script Python

def parcours_largeur(self,depart):
        assert depart in self.sommets
        a_traiter = [depart]
        deja_vu = [depart]
        pl  = []
        while a_traiter != []:
            sommet = a_traiter[0]
            voisins = self.get_voisin(sommet)
            # Ajout des sommets voisins non encore parcourus à ceux à traiter
            for v in .......:
                if v not in .....:
                    a_traiter......(v)
                    deja_vu.......(v)
            pl.append(sommet)
            a_traiter.....(0)
        return pl

Reconnaître la structure de données utilisée pour la variable a_traiter, expliquer pourquoi le choix d'une liste n'est pas judicieux.

Ajouter la méthode parcours_profondeur ci-dessous à cette implémentation en la complétant.

🐍 Script Python

def parcours_profondeur(self,start,parcourus=None):
        if parcourus == None:
            parcourus = []
        parcourus.append(start)
        for v in self...........(start):
            if v not in parcourus:
                self............(v,parcourus)
        return parcourus

Proposer une méthode permettant d'ajouter un sommet.
Proposer une méthode permettant de supprimer un sommet.

Exercice 7 : Implémentation par listes d'adjacence⚓︎

Reprendre les questions de l'exercice précédent avec l'implémentation par liste d'adjacence :
Implémentation graphes par listes