Graphes¶
Nous avons vu que les arbes étaient des graphes particuliers. Les graphes sont des objets fondamentaux en informatique qui ont à la fois un intérêt théorique important, puisque tout un pan des mathématiques leur est dédiée. C'est ce qu'on appelle "La théorie des graphes".
Les graphes sont également massivement utilisées pour résoudre des problèmes d'ingénierie, notamment dans les protocoles de routage de paquets sur internet, ou des problèmes scientifiques comme en biologie.
Histoire¶
La théorie des graphes est née des travaux de Leonhard Euler sur les septs ponts de Königsberg (aujourd'hui Kaliningrad en Russie) en 1736.
Le problème consistait à déterminer s'il était possible de travserser la ville en ne passant par chacun des ponts qu'une seule fois.
Euler a démontré mathématiquement que cela était impossible en représentant le problème sous la forme d'un graphe.
Aujourd'hui les graphes sont utilisés dans une très grande variété de domaines.
Exemples d'applications¶
Biologie¶
En biologie la théorie des graphes permet par exemple de modéliser le fonctionnement du cerveau :
Réseaux sociaux¶
On utilise les graphes pour représenter les relations "d'amitié" dans les réseaux sociaux ou les interactions entre utilisateurs.
Internet¶
Internet peut être vu comme un immense graphe où les routeurs correspondent aux sommets et les câbles aux arêtes.
Web¶
PageRank¶
Pour comprendre le fonctionnement de l'algorithme PageRank de Google, il faut s'intéresser aux chaînes de Markov (étudiées en maths expertes). On représente les pages web sous forme de sommets et la navigation d'une page vers une autre par des arcs (le graphe est orienté).
Graphe, non orienté et orienté, pondéré¶
Graphe
Un graphe est une structure de données composée d’objets: les sommets dans laquelle certaines paires d’objets sont reliées par des arêtes (ou arcs dans le cas de graphes orientés).
On note \(G = (V, E)\) où \(V\) correspond à l'ensemble des sommets et \(E\) l'ensemble des arêtes (ou arcs). On notera parfois \(G = (V, A)\) un graphe orienté.
Question
Pour les experts en anglais, pourquoi \(V\) et \(E\) ?
Graphe non orienté et orienté
Dans un graphe non orienté, les arêtes ne possèdent pas d'orientation.
Exemple
Dans un graphe orienté, les arêtes possèdent une orientation. Ces "arêtes orientées" sont souvent appelées "arcs". On dira qu'un graphe orienté \(G\) est un couple \(G = (V, A)\) avec \(V\) un ensemble de sommets et \(A\) un ensemble d'arcs.
Exemple
Arête
Une arête est désignée par les deux sommets u et v qu'elle relie, sous la forme d'une paire \(\{u, v \}\). Ici, les accolades représentent un ensemble et donc l'ordre n'a pas d'importance, \(\{u, v\}\) est équivalent à \(\{v, u \}\).
Arc
Un arc est désigné par les deux sommets u et v qu'elle relie, sous la forme d'un couple \((u, v)\). Ici l'ordre a une importance \((u, v)\) est différent de \((v, u)\).
Question
D'après vous, doit on représenter le problème des ponts de Königsberg plutôt par un graphe orienté ou un graphe non orienté ?
Graphe pondéré
Un graphe pondéré Un graphe pondéré est un graphe dans lequel chaque arête est associée à un poids (un nombre).
En fonction des problèmes on peut chercher à maximiser ou minimiser la somme des poids.
Encore des définitions¶
Chaîne
Dans un graphe non orienté, une chaîne reliant \(u\) à \(v\) est définie par une suite finie d'arêtes consécutives, reliant \(u\) à \(v\).
Sommets adjacents
Deux sommets sont adjacents s'ils sont reliés par une arête.
Degré d'un sommet
Le degré (ou valence) d'un sommet d'un graphe est le nombre de liens (arêtes ou arcs) reliant ce sommet, avec les boucles comptées deux fois.
Ordre d'un graphe
L'ordre d'un graphe est le nombre de sommets de ce graphe.
Connexité
Un graphe non orienté est dit connexe lorsque deux sommets quelconques peuvent être reliés par une chaine.
Implémentation des graphes¶
On représente un graphe sous la forme d'une liste d'adjacence ou d'une matrice d'adjacence. Les deux représentations ont des avantages et des inconvénients. La complexité des algorithmes dépendra de la représentation choisie.
Liste d'adjacence¶
A chaque sommet \(v\) dans un graphe nous allons associer les sommets connectés à \(v\) sous la forme d'une liste.
Graphes non orientés
En utilisant un dictionnaire et des listes Python :
Graphes orientés
En utilisant un dictionnaire et des listes Python :
Matrice d'adjacence¶
On appelle matrice carrée une matrice qui comporte le même nombre de lignes et de colonnes. Les matrices d'adjacences sont des matrices carrées.
A chaque ligne correspond un sommet du graphe et à chaque colonne correspond aussi un sommet du graphe. À chaque intersection, on place un 1 s'il existe une arête entre le sommet \(i\) et le sommet \(j\), et un zéro s'il n'existe pas d'arête entre le sommet \(i\) et le sommet \(j\).
Graphes non orientés
Soit le graphe suivant :
Sa Matrice d'ajacence associée :
Il est assez simple d'utiliser les matrices d'adjacence en Python grâce aux tableaux de tableaux.
graphe = [
[0, 1, 1, 1, 0, 0, 0],
[1, 0, 0, 0, 1, 1, 1],
[1, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 1],
[0, 1, 0, 0, 0, 1, 0],
[0, 1, 0, 0, 1, 0, 0],
[0, 1, 0, 1, 0, 0, 0]
]
Graphes orientés
graphe = [
[0, 0, 1, 1, 0, 0, 0],
[1, 0, 0, 0, 0, 1, 1],
[1, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 1],
[0, 1, 0, 0, 0, 1, 0],
[0, 0, 0, 0, 1, 0, 0],
[0, 1, 0, 1, 0, 0, 0]
]
graphes pondérés ¶
Dans le cas des graphes pondérés pour représenter la matrice d'ajacence, on remplace les 1 par les poids correspondants à chaque arête (ou arc si le graphe est orienté).
Exercice
Faites la matrice d'ajacence du graphe ci-dessous.
On peut inclure l'information correspondant aux poids des arêtes dans la liste d'ajacence.
Exercice
Proposez une représentation sous forme de liste d'ajacence du graphe ci-dessous.
Comparaison entre les deux représentations¶
\(|V|\) correspond au nombre de sommets. \(|E|\) correspond au nombre de d'arêtes.
| Opérations | Matrice d'adjacence | Liste d'adjacence |
|---|---|---|
| Espace | \(O(\lvert V\rvert ^2)\) | \(O(\lvert V\rvert + \lvert E\rvert)\) avantageux quand le graphe est peu dense |
| Vérifier si deux sommets sont adjacents | \(O(1)\) | \(O(\lvert V \rvert)\) |
Algorithmie¶
Tous comme pour les arbres, il est possible de réaliser deux types de parcours d’un arbre:
- le parcours en profondeur(Depth-First Search)
- le parcours en largeur(Breadth First Search)
Cependant, contrairement aux arbres
- Il n’y a pas de racine, donc on doit choisir à partir de quel noeud on part: le noeud source.
- Il peut y avoir un nombre quelconque d’arêtes, et il faut donc marquer les chemins déjà empruntés lors du parcours.
Parcours en largeur¶
Ici, on visite les sommets les plus proches du sommet précédent. Le parcours en largeur visite donc les sommets à distance 1, puis ceux à distance 2, etc
On peut implémenter cet algorithme de manière itérative en utilisant une file.
Les étapes de l'algorithme :
- 1) mettre le nœud source dans la file
- 2) retirer le nœud du début de la file pour le traiter
- 3) mettre tous ses voisins non explorés dans la file (à la fin)
- 4) si la file n'est pas vide reprendre à l'étape 2.
parcoursLargeur(Graphe G, Sommet s):
f = CreerFile();
f.enfiler(s);
tant que la file est non vide
s = f.defiler();
si s non marqué
afficher(s);
marquer(s);
pour tout voisin v de s dans G
f.enfiler(v);
La version Python
def parcours_largeur(graphe, sommet_depart):
"""
Auteur : 'Monsieur NSI'
Args:
graphe (dict): une liste d'ajacence
sommet_depart (str): le sommet de départ
"""
# On initialise la liste des sommets déjà visitée
deja_visite = []
# On initialise la file
file = []
# On enfile le premier sommet
file.append(sommet_depart)
# Tant que la file n'est pas vide
while file:
# Défiler le sommet se trouvant en tête de la file
sommet = file.pop(0)
if sommet not in deja_visite:
print(f'on visite {sommet}')
deja_visite.append(sommet)
# Pour chaque sommet "enfant" adjacent au sommet "sommet"
for enfant in graphe[sommet]:
file.append(enfant)
Exercice
Effectuez un parcours en largeur de ce graphe en partant du sommet A :
Parcours en profondeur¶
On marque le sommet actuel, et on prend le premier sommet voisin jusqu'à ce qu'un sommet n'ait plus de voisins (ou que tous ses voisins soient visités), et on revient alors au sommet père.
Algorithme récursif
parcoursProfondeur(deja_visite dv, graphe G, sommet s)
si s n'est pas dans dv
afficher(s)
ajouter s dans dv
pour tout voisin v de s:
parcoursProfondeur(deja_visite dv, graphe G, sommet v)
La version Python
deja_visite = []
def parcours_profondeur_recursif(deja_visite, graphe, sommet):
if sommet not in deja_visite:
print(f'on visite {sommet}')
deja_visite.append(sommet)
for voisin in graphe[sommet]:
parcours_profondeur_recursif(deja_visite, graphe, voisin)
On peut également implémenter cet algorithme de manière itérative en utilisant une pile.
parcoursProfondeur(Graphe G, Sommet s):
p = CreerPile();
p.empiler(s);
tant que la pile est non vide
s = p.depiler();
si s non marqué
afficher(s);
marquer(s);
pour tout voisin v de s dans G
p.empiler(v);
La version Python
def parcours_profondeur(graphe, sommet_depart):
"""
Auteur : 'Monsieur NSI'
Args:
graphe (dict): une liste d'ajacence
sommet_depart (str): le sommet de départ
"""
# On initialise la liste des sommets déjà visitée
deja_visite = []
# On initialise la pile
pile = []
# On empile le premier sommet
pile.append(sommet_depart)
# Tant que la pile n'est pas vide
while pile:
# Dépiler le sommet se trouvant en haut de la pile
sommet = pile.pop()
if sommet not in deja_visite:
print(f'on visite {sommet}')
deja_visite.append(sommet)
# Pour chaque sommet "enfant" adjacent au sommet "sommet"
for enfant in graphe[sommet]:
pile.append(enfant)
Exercice
Effectuez un parcours en profondeur de ce graphe en partant du sommet A :
Détection de cycle¶
Cycle
Un cycle est une suite d’arêtes consécutives dont les deux sommets extrémités sont identiques.
Pour détecter un cycle dans un graphe non orienté, nous allons simplement parcourir le graphe en profondeur et vérifier qu’aucune arête pointe vers un sommet déjà visité. Il faut aussi vérifier que le sommet n'est pas le prédécesseur du dernier voisin visité. On fait cette vérification car sinon entre deux sommets reliés par une arête on détecterait un cycle alors que l'on est simplement revenu "en arrière".
Par exemple si deux sommets A et B sont reliés par une arête, et que l'on va du sommet A pour aller ensuite vers le sommet B, et qu'on revient ensuite dans le "sens inverse" de B vers A alors on ne doit pas détecter de cycle.
detectionCycle(Graphe G, Sommet s):
p = CreerPile();
p.empiler(s);
tant que la pile est non vide
s = p.depiler();
si s non marqué
afficher(s);
marquer(s);
pour tout voisin v de s dans G
p.empiler(v);
sinon
si s n'est pas le prédécesseur de v
renvoyer Vrai;
renvoyer Faux;
Dans un graphe orienté on parle de circuit.
Circuit
Dans un graphe orienté, on appelle circuit une suite d'arcs consécutifs (chemin) dont les deux sommets extrémités sont identiques.
Recherche de chaîne et de chemin dans un graphe¶
Recherche de chaîne dans un graphe¶
Nous allons maintenant nous intéresser à un algorithme qui permet de trouver une chaine entre 2 sommets (sommet de départ et sommet d'arrivée). Les algorithmes de ce type ont une grande importance et sont très souvent utilisés).
rechercheChaine(Graphe G, Sommet source, Sommet destination):
p = CreerPile();
p.empiler(s);
predecesseurs = {source : Vide}
tant que la pile est non vide
s = p.depiler();
si s non marqué
marquer(s);
pour tout voisin v de s dans G
p.empiler(v);
predecesseurs[v] = s;
si v est égal à destination
renvoyer predecesseurs;
renvoyer None;
Question
Sur quel algorithme s'appuie cette recherche de chaîne ?
Exercice
Prenez une feuille et implémenter cet algorithme en Python
Plus court chemin dans un graphe pondéré¶
Les algorithmes de Dijkstra et de Bellman-Ford permettent de répondre à ce problème. L'algorithme de Bellman-Ford est utilisé avec le protocole RIP.
Nous présentons ici l’algorithme de Dijkstra plus en détail.
Cet algorithme est utilisé dans le protocole OSPF.