Cours

Introduction

• des réseaux de communication (téléphone, internet, sociaux) ;
• des réseaux de transport (routiers, aériens, maritimes, ferrovières, ...)
• des circuits électriques ;
• des relations biologiques (proie-prédateur, évolution, ...)
• des relations entre entités informatiques (fichiers dans un système, tables dans une base de données, ...)

Vocabulaire de la théorie des graphes

• d'un ensemble fini de points appelées sommets ou nœuds,
• d'un ensemble fini de lignes (appelée arêtes) ou de flèches (appelées arcs) reliant les sommets. Lorsqu'un graphe est constitué d'arcs, on parle de graphe orienté, sinon il s'agit d'un graphe non-orienté.

Remarque : Il est possible d'affecter des valeurs, des poids (coefficients positifs), des couleurs, etc... aux arêtes (le plus souvent) ou bien aux sommets (parfois) : on parle de graphe valué. Ces valeurs peuvent indiquer des distances, des coûts, etc. Pour être plus précis, on peut utiliser les termes graphes pondérés pour un graphe valué par des nombres et graphe étiqueté pour un graphe valué par des chaînes de caractères.

Un peu de vocabulaire pour fixer ces notions :

• chaque arête relie deux sommets, qui sont appelés les extrémités de l'arête (dans le cas orienté, on doit distinguer l'extrémité initiale de l'extrémité finale, marquée par la flèche),
• si les 2 extrémités sont égales, on dit que l'arête est une boucle,
• lorsqu'on autorise deux arêtes différentes à avoir les mêmes extrémités (on parle d'arêtes parallèles), on parle de multigraphe :

  

• deux sommets sont voisins (ou adjacents) s'ils sont reliés par une arète. Dans le cas orienté, X → Y, Y est adjacent à X, mais X n'est pas adjacent à Y...
  
• le degré d'un sommet est le nombre d'arêtes dont ce sommet est l'extrémité. Attention : les boucles comptent 2. Si le graphe est orienté, on distingue le degré intérieur/extérieur (nombre de flèches qui pointent vers le / partent du sommet) ;
• Un graphe est complet lorsque tous ses sommets sont adjacents :

Ce qui compte, c'est de se promener sur un graphe... :

• Un chemin ou une chaîne est une suite d'arêtes mises bout à bout (cas orienté : l'extrémité initiale correspond à l'extrémité finale de l'arête précédente). La longueur d'un chemin est le nombre de ses arêtes.
• Un chemin est simple lorsque toutes les arêtes qui le composent sont distinctes ;
• Un chemin est fermé si ses extrémités sont un même sommet ;
• Un chemin simple et fermé est un cycle.
• Pour un graphe non-orienté : un graphe est connexe lorsque tous ses sommets peuvent être reliés par un chemin ;
  Pour un graphe orienté : un graphe est fortement connexe lorsque tous ses sommets peuvent être reliés par un chemin (qui est orienté) ;
  La composante (fortement) connexe d'un sommet est le plus grand sous-graphe (fortement) connexe qui contient ce sommet ; si un graphe est non (fortement) connexe, il peut être séparé en un nombre fini de composantes (fortement) connexes.

Dans un graphe connexe :

• La distance entre deux sommets est la longueur minimale d'un chemin joignant ces sommets (OU BIEN : la somme du poids des arêtes constituant ce chemin pour un graphe pondéré). La plus grande distance entre deux sommets est le diamètre du graphe ;
• L'excentricité (ou écartement) d'un sommet est la distance maximale entre ce sommet et tous les sommets du graphe.
• Les centres d'un graphe sont les sommets qui possèdent l'excentricité minimale de tous les sommets du graphe. On nomme alors cette excentricité minimale le rayon du graphe ; pour les graphes, le diamètre n'est pas toujours le double du rayon.

Les outils de représentation

La liste d'adjacence

Pour un graphe donné, on associe à chaque sommet la liste de ses voisins (sommets adjacents). Dans le cas d'un graphe orienté, on peut aussi parler de «liste de successeurs» (flèches partant du sommet considéré) ; dans le cas orienté, on peut aussi considérer la «liste de prédécesseurs» (flèches arrivant au sommet considéré).
Lorsque le graphe est valué, on associe à chaque sommet une liste de tuples (voisin, dictionnaire), où les clés du dictionnaire (poids, couleur) permettent d'accéder à la/les donnée(s) figurant sur l'arête. Si on utilise une seule donnée, le dictionnaire n'est pas nécessaire : on le remplace dans le tuple directement par cette seule donnée.

La matrice d'adjacence

La matrice d'adjacence est un tableau carré (à double entrée). Les lignes et les colonnes correspondent aux sommets (ordonnés dans l'ordre alphanumérique si rien n'est précisé).
Si le sommet X et adjacent à Y (X-->Y), on remplit dans la matrice, à l'intersection de la ligne de X et de la colonne de Y, un 1 (ou un V pour «vrai»), ou bien une donnée si le graphe est valué (il y aura alors une matrice d'adjacence selon chaque type de donnée). S'il n'y a pas de relation entre X et Y, on note un 0 (ou un F pour «faux»).
Lorsque le graphe n'est pas orienté, la matrice d'adjacence est symétrique par rapport à sa diagonale (diagonale principale : de en haut à gauche à en bas à droite) ; aussi, les boucles apparaissent sur la diagonale.

Le type abstrait graphe et son implémentation

Le type abstrait de données : Graphe

Implémentation

Algorithmes de parcours des graphes

Algorithme de parcours en largeur (BFS)

L'algorithme de parcours en largeur (ou BFS, pour Breadth First Search en anglais) permet le parcours d'un graphe ou d'un arbre de la manière suivante : on commence par explorer un nœud source, puis ses successeurs, puis les successeurs non-explorés des successeurs, etc. L'algorithme de parcours en largeur permet de calculer les distances de tous les nœuds depuis un nœud source dans un graphe non-pondéré (orienté ou non-orienté). Il peut aussi servir à déterminer si un graphe non-orienté est connexe.

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 les voisins non-explorés dans la file (à la fin).
4. Si la file n'est pas vide reprendre à l'étape 2.

Pseudo code : L'algorithme s'implémente à l'aide d'une file.

ParcoursLargeur(Graphe G, Sommet s)
    f = CreerFile()
    f.enfiler(s)
    marquer(s)
    tant que la file est non-vide
        s = f.defiler()
        afficher(s)
        pour tout voisin t de s dans G
            si t non-marqué
                f.enfiler(t)
                marquer(t)

Complexité : La complexité en temps dans le pire cas est en `O( | S | + | A | )` où `| S |` est le nombre de sommets et `| A |` est le nombre d'arcs. En effet, chaque arc et chaque sommet est visité au plus une seule fois.

Algorithme de parcours en profondeur (DFS)

L'exploration d'un parcours en profondeur depuis un sommet S fonctionne comme suit : on suit un chemin dans le graphe jusqu'à un cul-de-sac ou alors jusqu'à atteindre un sommet déjà visité. On revient alors sur le dernier sommet où on pouvait suivre un autre chemin puis on explore un autre chemin. L'exploration s'arrête quand tous les sommets depuis S ont été visités. Bref, l'exploration progresse à partir d'un sommet S en s'appelant récursivement pour chaque sommet voisin de S.
Le nom d'algorithme en profondeur est dû au fait que, contrairement à l'algorithme de parcours en largeur, il explore en fait « à fond » les chemins un par un : pour chaque sommet, il marque le sommet actuel, et il prend le premier sommet voisin jusqu'à ce qu'un sommet n'ait plus de voisins (ou que tous ses voisins soient marqués), et revient alors au sommet père.
Si G n'était pas un arbre, l'algorithme pourrait a priori tourner indéfiniment si on continuait l'exploration depuis un sommet déjà visité. Pour éviter cela, on marque les sommets que l'on visite, de façon à ne pas les explorer à nouveau. Dans le cas d'un arbre, le parcours en profondeur est utilisé pour caractériser l'arbre.

explorer(graphe G, sommet s)
    marquer le sommet s
    afficher(s)
    pour tout sommet t voisin du sommet s
        si t n'est pas marqué alors
              explorer(G, t);
                   
parcoursProfondeur(graphe G, sommet s)
    pour tout sommet du graphe G en partant du sommet s
        si s n'est pas marqué alors
              explorer(G, s)

La recherche de cycles dans un graphe

• La recherche d'un cycle eulérien dans un graphe, c'est-à-dire un cycle qui permet de parcourir tout les sommets du graphe, en bref un circuit touristique : cf problème des sept ponts de Königsberg.
• Dans une langue donnée : chaque mot de la langue est représenté par un sommet ; pour chaque sommet représentant un mot M, on trace des flèches reliant le sommet M aux sommets qui représentent les mots apparaîssant dans la définition de M dans un dictionnaire fixé. Le graphe obtenu contient-il des cycles ? Comment interpréter cela ? Cela dépend-il fortement du dictionnaire utilisé ? Est-ce que ces cycles apparaîssent dans toutes les langues ?
• ...etc...

Algorithmes du plus cours chemin

Ces algorithmes sont utilisés pour traiter des problèmes d'optimisation (transports, câblage électrique ou réseau, déplacements de pnj dans un jeu vidéo, ...).

Illustration de ces algorithmes sur une carte réelle avec : Pathfinding.

6.1. L'algorithme de Dijkstra

6.2. L'algorithme A* (A star)

La bibliothèque networkx (hors-BAC)

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import matplotlib.pyplot as plt   # pour les dessins
import networkx as nx

# Créer un objet graphe (Graph)
G = nx.Graph()
# G = nx.DiGraph()   # pour les graphes orientés
# G = nx.MultiGraph() # avec arêtes parallèles
# G = nx.MultiDiGraph() # avec arêtes parallèles orientées

# Ajouter un sommet / une arête (tout objet hashable sauf None) :
G.add_node("A")
G.add_edge("A", "B")  # le sommet "B" est ajouté directement

# Ajouter depuis un conteneur plusieurs sommets/arêtes (ici : list, aussi : dict, set, Graph, fichier, ...)
G.add_nodes_from(["B", "C", "D"])
G.add_edges_from([("B", "C"), ("C", "D"), ("A", "C"), ("E","E")])

# On peut ajouter des étiquettes { : } sur les arêtes :
# (début, fin, {clé : valeur} )
G.add_edges_from([("A", "E", {"info": 7}), ("B", "E", {"info": 8})])

print("sommets : \n", G.nodes())
print("triés : \n", sorted(G.nodes(), key=str))
print("nombre de sommets : \n",G.number_of_nodes())
print("arêtes : \n", G.edges(data=True))
print("nombre d'arêtes : \n", G.number_of_edges())
print("plus court chemin : \n", nx.shortest_path(G, "A", "D"))
print("distance : \n", nx.shortest_path_length(G, "A", "D"))
print("Diamètre : \n", nx.diameter(G))
print("Rayon : \n", nx.radius(G))
print("Centre : \n", nx.center(G))
print("accès à une étiquette : \n", G["A"]["E"]["info"])
# G[u][v]['width'] est identique à G.edges[u, v]['width']
# print("vue selon les étiquettes : \n", [G.edges.data("info")])
# print("liste des voisins d'un sommet : \n",[item for item in G.neighbors("E")])


# --- LISTE ET MATRICE D'ADJACENCE ---
# print("liste d'adjacence : \n",[item for item in G.adjacency()])

MatAdjG = nx.adjacency_matrix(G)
MatAdjG.setdiag(MatAdjG.diagonal()*2)    # def : boucles comptent 2
print("matrice d'adjacence : \n", MatAdjG.todense())

• algorithme de parcours en profondeur : Depth-First Search (DFS) ;
• algorithme de parcours en largeur : Breadth First Search (BFS) ;
• Noeud : node ;
• Arête : edge ;
• Chemin : path ;
• graphe représentant un réseau : network.