La théorie des graphes est une branche des mathématiques qui étudie les relations entre les objets (appelés sommets ou nœuds) et les connexions entre eux (appelées arêtes ou arcs). Elle est utilisée dans de nombreux domaines comme les réseaux sociaux, les systèmes de transport, les circuits électriques et l'analyse de données.

Pour manipuler les graphes visuellement : https://d3gt.com/index.html

Définitions de base

V = { 1,2,3,4,5 }
E = {(1,2), (1,3), (2,3), (5,2), (2,4)}

Exemple de graphe orienté

V = { 1,2,3,4,5 }
E = {(1,2), (1,3), (2,3), (3,2), (5,2), (2,4)}

Le poids d'une arrête peut être interprêté comme le temps nécessaire pour parcourir l'arrête ou, plus généralement, comme un coût à payer pour traverser l'arrête.

Exemple de graphe pondéré non orienté

V = { A,B,C,D,E,F,G,H }
E = {(A,B), (A,C), (C,E), (B,D), (D,E), (D,F), (F,H), (H,G), (E,G)}
\( \omega((A,B)) = 1, \; \omega((B,D)) = 3, \; \omega((E,G)) = 2,\) ...

Dessiner un graphe en python

Dans ce cours, les graphes seront représentés avec les bibliothèques python networkx et matplotlib.

#On importe les deux bibliothèques
import networkx as nx
import matplotlib.pyplot as plt

#On créé le graphe
G = nx.Graph() #Non-orienté
#G = nx.DiGraph() #Orienté

#On créé les noeuds
G.add_node(1)
G.add_nodes_from ([2,3,4,5])

#On ajoute les arrêtes entre les noeuds
G.add_edge(1,2)
e = (2,3)
G.add_edge(*e) # the * unpacks the tuple
G.add_edges_from([(1,2),(1,3),(2,4),(2,5)])

#On dessine le graphe
nx.draw(G, with_labels =True)

#On peut sauvegarder la figure
plt.savefig("basicgraph2.png")

#Ou juste l'afficher
plt.show()

On obtient le résultat suivant :

Dans de multiples problèmes nous sommes amenés à parcourir un graphe, c'est-à-dire aller de sommets en sommets en suivant les arrêtes du graphe. Par exemple, pour savoir si deux sommets sont connectés ou pour savoir si le graphe comporte un cycle. Pour parcourir un graphe, il existe principalement deux manières de procéder : l'exploration en profondeur DFS (Depth First Search) ou l'exploration en largeur (Breadth First Search). Ces deux algorithmes ont des temps de calcul très variables (et complémentaires) en fonction de la forme du graphe.

Parcours en profondeur DFS

Le parcours en profondeur consiste à parcourir le graphe en utilisant la stratégie suivante : si je suis à une intersection, je choisis une arrête arbitrairement; je continue ce chemin jusqu'à être coincé ou jusqu'à ce que j'aie trouvé ce que je cherche. Si je suis coincé, je reviens sur mes pas jusqu'à la dernière intersection. Cette stratégie correspond à la stratégie bien connue pour trouver la sortie d'un labyrinthe : toujours prendre à gauche. Voici deux illustrations de la stratégie DFS pour trouver un chemin du sommet A au sommet F à gauche et pour trouver un chemin du sommet A au sommet H à droite.

En vert, le sommet actuel. En jaune, le sommet qu'on recherche. En rouge les sommets déjà parcourus.

D'un point de vue code, on utilise la plupart du temps un algorithme récursif (bien qu'un algo itératif soit envisageable). Voici une implémentation possible en python, en supposant l'existence d'un objet Graphe avec une méthode Voisins qui renvoie la liste des voisins d'un sommet.

def explorer(Graphe, sommetActuel, pointArrivee, parcourus):
    parcourus.append(sommetActuel) #On garde en mémoire les sommets par lesquels on est passé.
    if(sommetActuel == pointArrivee): #Condition d'arrêt : on a trouvé le sommet qu'on recherche.
        return True
    for voisin in Graphe.Voisins(sommetActuel): #On parcourt les voisins du sommet.
        if(voisin not in parcourus): #On vérifie qu'on n est pas déjà passé par là.
            if(explorer(Graphe, voisin, pointArrivee, parcourus)): #On continue l'exploration de ce chemin tant qu on n'est pas bloqué.
                return True
    return False #Si on n a trouvé aucun voisin qui n'a jamais été parcouru, on abandonne ce chemin.
                

Parcours en largeur BFS

Le parcours en largeur consiste à utiliser la stratégie suivante : on explore tous les voisins du point de départ, on liste tous les voisins de ces voisins qui n'ont pas encore été parcourus; on réitère le procédé sur cette nouvelle liste de voisins jusqu'à trouver ce qu'on cherche ou jusqu'à ce qu'on ne trouve plus de voisin non parcourus. Cet algorithme correspond à un parcours par "génération" de voisin. En effet, si on définit la distance de voisinage entre deux sommets A et B comme le nombre d'arrêtes minimal pour passer de A à B, alors le parcours BFS va parcourir tous les sommets à distance 1 du point de départ puis tous les voisins à distance 2 et ainsi de suite. Voici une illustration dans le même contexte que le parcours DFS pour comparer.

En vert, le sommet actuel. En jaune, le sommet qu'on recherche. En rouge les sommets déjà parcourus.

Le parcours BFS est généralement implémenté comme un algorithme itératif à la différence du DFS. En voici une implémentation possible en python, en supposant l'existence d'un objet Graphe avec une méthode Voisins qui renvoie la liste des voisins d'un sommet.

def explore(Graphe, pointDepart, pointArrivee):
      parcourus = []
      nodesToexplore = [pointDepart] #La liste des noeuds à explorer qui sera tenue à jour à chaque itération.
      while(len(nodesToexplore) > 0):
          newNodes = []
          for node in nodesToexplore:
              if(node == pointArrivee): #Condition d'arrêt : si on a trouvé le point d'arrivée, on arrête.
                  return True
              parcourus.append(node)
              for P in Graphe.Voisins(node):
                  if(P not in parcourus):
                      newNodes.append(P) #On remplit la liste newNodes de tous les voisins non parcourus de la prochaine génération.
          nodesToexplore = newNodes
      return False #Si on a plus aucun noeud à explorer, c'est qu'il n'existe pas de chemin reliant le point de départ au point d'arrivée.
                  

Flot maximal et coupe minimale

Problème de flot maximal

Si on se donne un réseau de flot \(V,E,\omega\), un sommet source \(s\) et un sommet puits \(t\), le problème du flot maximal est donc de trouver un flot \(f\) de \(s\) à \(t\) de valeur \(|f|\) maximale.

Algorithme de Ford-Fulkerson

L'algorithme de Ford-Fulkerson permet de trouver un flot maximal lorsque l'algorithme termine (attention il existe des cas où l'algorithme ne termine jamais). Le principe de l'algorithme repose sur l'utilisation d'un graphe résiduel d'un flot \(G_f \). Si on cherche le flot maximal sur \(G = (V,E,c)\), le graphe résiduel \(G_f\) d'un flot \(f\) est un graphe pondéré orienté \(G_f = (V, E_{r_f}, r_f )\) (\(G_f\) a donc les mêmes sommets que \(G\)) où \(r_f\) est défini par : \[ \forall (A,B) \in V^2, \;\; r_f((A,B)) := \left\{ \begin{matrix} c((A,B)) - f((A,B)) & \textrm{ si } (A,B) \in E \\ f((B,A)) & \textrm{ si } (B,A) \in E\\ 0 & \textrm{sinon} \end{matrix} \right. \] et \(E_{r_f} = \{ (A,B) \in V^2, \textrm{ tels que } r_f(A,B) > 0 \} \).

On utilise alors l'algorithme suivant :

Lorsque l'algorithme se termine, le flot \( f \) est alors le flot maximal.

Problème de la coupe minimale

Encore une fois, avant de pouvoir présenter le problème, il faut introduire de nouvelles définitions.

Le problème de la coupe minimale consiste donc à trouver la (ou une des) coupe(s) de poids minimale(s) pour un graphe pondéré donné. Lorsque le graphe est un réseau de flot et qu'on impose les conditions \(s \in S\) et \(t \in T\), le théorème du max flow/min cut montre que le problème de flot maximal et le problème de coupe minimale sont directement reliés.