Introduction aux graphes et leurs structures de données

Graphes: quelques définitions

Qu’y a t’il de commun entre tous nos problèmes?

Dans chacun d’entre eux, la résolution se ramènera à étudier comment certains objets sont reliés entre eux. Autrement dit, le problème va pouvoir être modélisé à l’aide d’un graphe.

Informellement: un graphe est la donnée d’un ensemble de sommets reliés par des arêtes. Voilà un exemple avec neuf sommets. Les sommets 0 et 2 y sont reliés entre eux. Mais pas 0 et 6:

from graph_networkx import Graph
G = Graph(nodes=[1, 2, 3, 4, 5],
          edges=[ (1,2), (1,3), (2,4), (3,4), (4,5) ])
G.show()

La définition formelle la plus simple est la suivante:

Un graphe est une paire \(G:=(V,A)\)\(V\) est un ensemble et \(A\) et un ensemble de paires \(\{v_1,v_2\}\) d’éléments de \(V\).

Dans notre exemple, \(G=(V,A)\), où \(V = \{1,2,3,4,5\}\) et \(A = \{\{1,2\}, \{1,3\}, \{2,4\}, \{3,4\}, \{4,5\}, \{5,6\}\}\).

Remarque: dans la définition donnée, une arête est un ensemble à deux éléments:

  • le graphe n’est pas orienté: si \(s\) est relié à \(t\) alors \(t\) est relié à \(s\);

  • il n’y a pas de boucle, c’est à dire une arête reliant un sommet à lui-même;

  • ni d’arête multiple, c’est-à-dire plusieurs arêtes reliant les mêmes sommets;

On parle de graphe simple.

Graphes: Variantes

Le plus souvent, cette information de base est enrichie d’informations supplémentaires: étiquettes sur les sommets, valuations sur les arêtes, orientation des arêtes, …

On remplace la paire \(\{v_1,v_2\}\) par un couple \((v_1,v_2)\):

  • On a en plus: orientation, boucle…

On ajoute un nombre à la paire \((v_1, v_2, c)\):

  • On a en plus: arête multiple, coût, capacité …

Quelques structures de données pour les graphes

Pour étudier un graphe à l’aide d’un ordinateur, il va falloir le représenter, c’est-à-dire choisir une structure de données. Comme le champ d’application des graphes et large, il y a beaucoup d’algorithmes différents, avec des besoins différents en terme de performance des opérations élémentaires. Tel algorithme va demander d’avoir un accès très performant aux voisins d’un sommet; tel autre parcourir les arêtes, etc. De ce fait, il existe de nombreuses structures de données possibles que nous allons explorer maintenant.

On s’intéressera dans cette séance aux graphes orientés où chaque arête aura une capacité c qui sera un nombre.

Liste d’arêtes

Ici, on représentera un graphe par une liste de triplets (v1,v2,c), chacun d’entre eux spécifiant qu’il y a une arête reliant \(v_1\) à \(v_2\) de capacité \(c\).

Ci-dessous, nous donnons la structure de données L0 d’un graphe \(G_0\) avec trois sommets, \(0,1,2\), et deux arêtes; la première relie \(0\) à \(1\) avec une capacité de \(10\) et la deuxième relie \(0\) à \(2\) avec une capacité de \(4\).

L0 = [ (0,1,10), (0,2,4) ]

Voici la structure de donnée pour un autre graphe \(G_1\):

L1 = [ (1,2,1), (1,3,1), (2,4,2), (3,4,0), (4,5,3) ]

Exercice

  • Dessiner sur papier les graphes G_0 et G_1, en mettant sur chaque arête sa capacité.

Rappel: dictionnaires Python

Un dictionnaire en Python est une structure de donnée permettant d’associer à une valeur à une clé. Comme un dictionnnaire de français qui associe une définition à un mot, ou un annuaire qui associe un numéro de téléphone à une personne. Voici un dictionnaire qui associe la valeur 1 à la clé "bla", la valeur 3 à la clé "ble" et la valeur "pi" à la clé 3.13:

t = {"bla": 1, "ble": 3, 3.14: "pi"}
t

On peut accéder à une valeur à partir de sa clé avec l’opération suivante:

t[3.14]

On notera la similitude avec l’accès aux éléments d’un tableau. On peut voir un tableau de taille l comme un dictionnaire associant des valeurs à des clés entre 0 et l-1

Dictionnaire des voisins

Un sommet \(v_2\) est un voisin sortant d’un sommet \(v_1\) s’il y a une arête reliant \(v_1\) à \(v_2\).

On peut représenter un graphe à l’aide d’un dictionaire des voisins qui à chaque sommet associe la liste de ses voisins. Comme on veut représenter des capacités, la valeur associée à la clé v1 sera un liste de paires (v2,c)\(v_2\) sera le voisin et c la capacité de l’arête reliant \(v_1\) à \(v_2\).

Voici le dictionnaire des voisins pour \(G_0\):

DV0 = { 0: [(1,10), (2,4) ] }

Exercice Donner le dictionnaire des voisins pour \(G_1\):

# YOUR CODE HERE
raise NotImplementedError()

Note: si les sommets du graphe sont étiquetés par \(0,1,\ldots\), on peut utiliser une liste au lieu d’un dictionnnaire:

# Avec un tableau (graphe etiquete par 0,1,...)
DV0 = [ [(1,10), (2,4)] ]

Dictionnaire d’arêtes

Utilisons maintenant un dictionnaire d’arêtes pour représenter G_1: il associera à chaque paire (u1,v1) reliés par une arête la capacité de cette arrête. Voici le dictionnaire pour \(G_0\):

DA0 = { (0,1): 10,
        (0,2): 4
      }

Exercice Donner le dictionnaire d’arêtes pour \(G_1\):

# YOUR CODE HERE
raise NotImplementedError()

Matrice d’adjacence

La matrice d’adjacence d’un graphe est un tableau (ou matrice) à deux dimensions M tel que M[v1,v2] est la capacité c de l’arête reliant \(v_1\) à \(v_2\) ou \(0\) s’il n’y a pas d’arête.

M0 = [ [0, 10, 4],
       [0,  0, 0],
       [0,  0, 0]]

Exercice Donner la matrice des voisins pour \(G_1\).

Indication: Vous rajouterez un sommet \(0\).

# YOUR CODE HERE
raise NotImplementedError()