Graphes

Un graphe est un objet mathématique (très utilisé, notamment en informatique) constitué de sommets reliés entre eux par des arêtes :

Définitions

On définit un graphe \(G\) par un couple \(G = (V,E)\) avec :

• \(V\) un ensemble de sommets (vertices) (on dit aussi nœuds ou points)
• \(E\) un ensemble d’arêtes (edges) (on dit aussi arcs, liens ou lignes)

Chaque arête est définie par une paire de deux sommets distincts :

\(E \subseteq \{\{x,y\} | (x,y)\in V^2\land x\ \neq y\}\)

Graphe orienté

Exemple : le jeu de Chifoumi pour représenter la supériorité des figures les unes par rapport aux autres.

Graphe non orienté

Exemple : un réseau de routeurs informatiques

Voisinage et adjacence

Lorsque qu’un sommet \(x\) est relié à un sommet \(y\) par une arête, on dit que \(y\) est adjacent à \(x\), ou que \(y\) est un voisin de \(x\).

Exemples :

Représentation

Un graphe est entièrement défini par l’ensemble de ses sommets et l’ensemble de ses arêtes. Un même graphe peut avoir de nombreuses représentations graphiques.

Exemple : 3 représentations différentes d’un même graphe

Chemins

Un chemin est une séquence finie de sommets reliés entre eux par des arêtes.

Exemple : chemin menant de A à C, que l’on peut noter A→B→C

Remarque : dans un graphe orienté, il peut exister un chemin menant du sommet \(x\) au sommet \(y\), alors que l’inverse n’est pas possible.

Un chemin est qualifié de simple s’il n’emprunte pas deux fois la même arête.

Un chemin est élémentaire s’il ne passe pas deux fois par le même sommet.

Un chemin simple reliant un sommet à lui-même (et contenant au moins une arête) est qualifié de cycle.

Distance

La distance entre deux sommets d’un graphe est la longueur (nombre d’arêtes) du chemin le plus court (s’il y en a un) reliant ces deux sommets.

Exemple : la distance entre A et B est la distance du plus court chemin de A à B (A→D→C), soit 2 (arêtes)

Connexité

Un graphe non orienté est connexe si pour toute paire \((x,y)\) de sommets, il existe un chemin de \(x\) à \(y\).

Un graphe orienté est connexe si le graphe non orienté obtenu en ne tenant pas compte du sens des arêtes est connexe.

Un graphe orienté est fortement connexe si pour toute paire \((x,y)\) de sommets, il existe un chemin de \(x\) à \(y\) et un chemin de \(y\) à \(x\).

Exemples :

graphe connexe, mais pas fortement connexe : il n’existe pas de chemin menant à A

Implémentation

Les sommets d’un graphe peuvent représenter n’importe quel type de donnée.

Le choix d’une représentation plutôt qu’une autre dépend des usages que l’on souhaite faire du graphe (construction, parcours, …)

Matrice d’adjacence

Soit un graphe de \(N\) sommets, d’indices \({0…N-1}\).

La matrice d’adjacence de ce graphe est un tableau \(A\) à deux dimensions, de taille \(N\times N\), contenant des booléens \(A[i][j]\) indiquant si il y a adjacence entre les sommets d’indices \(i\) et \(j\).

Exemple : la matrice d’adjacence du graphe ci-dessous

est :

En Python

On se propose d’implémenter en Python un graphe de n sommets par une matrice d’adjacence, à l’aide d’une classe Graphe_m:

class Graphe_m:
    """ """
    def __init__(self, n):
        self.n = n
        self.A = [[False] * n for _ in range(n)]

    def __repr__(self):
        C = ["\t".join([""]+[str(i) for i in range(self.n)])]
        for l in range(self.n):
            L = [str(l)]
            for c in range(self.n):
                if self.A[l][c]:
                    L.append("1")
                else:
                    L.append("")
            C.append("\t".join(L))
        return "\n".join(C)

Remarque : les données représentées par les sommets pourraient être facilement implémentées dans une simple liste de n éléments.

Inconvénient de cette structure

La dimension de la matrice est égale au carré du nombre de sommets (\(N\times N\)), ce qui peut représenter un important espace en mémoire.

Pour obtenir les voisins d’un sommet, il faut une utiliser une fonction de coût d’ordre \(O(n)\).

Dictionnaire d’adjacence

Un dictionnaire d’adjacence associe chaque sommet d’un graphe à ses voisins, sous forme d’un ensemble (voir les ensembles)

Exemple : le dictionnaire d’adjacence du graphe ci-dessous

est :

{A : {B, D},
 B : {D},
 C : {B},
 D : {B, C}}

En Python

On se propose d’implémenter en Python un graphe de nsommets par un dictionnaire d’adjacence, à l’aide d’une classe Graphe_d:

class Graphe_d:
    """ """
    def __init__(self):
        self.A = {}

    def __repr__(self):
        return str(self.A)

    def voisins(self, x):
        return self.A[x]

Remarques :

• avec cette représentation, les données représentées par les sommets peuvent être directement les clés du dictionnaire, sous réserve d’être hashable. (dans le cas contraire, on utilisera, comme pour la matrice d’adjacence, des indices).
• en Python, une collection est un objet de type set. (voir les ensembles).
• l’obtention des voisins d’un sommet est cette fois-ci une opération en temps constant.

Inconvénient de cette structure

Dans le cas d’un graphe contenant de très nombreuses arêtes, le dictionnaire sera moins avantageux en termes d’occupation mémoire que la matrice d’adjacence.

Suite dans l’article : parcours d’un graphe