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ésentation graphiques.

Exemple : 3 représentations 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.

 

Activité : cycles

Trouver tous les cycles de ce graphe

Et de celui-ci :

 

Distance

La distance entre deux sommets d’un arbre 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

 

Activité : connexité
Déterminer la connexité des graphes suivants :

                 

 

 

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 :

A B C D
A 0 1 0 1
B 0 0 0 1
C 0 1 0 0
D 0 1 1 0

 

Activité : matrice d'adjacence
Déterminer les matrices d’adjacence des graphes ci-dessous :

   

 

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.

 

Activité : ajout d'arête
Ajouter une méthode ajouter_arete(x, y) permettant d’ajouter au graphe une arête du sommet d’indice x vers celui d’indice y.

 

Activité : graphe non orienté

On souhaite à présent implémenter par une matrice d’adjacence un graphe non orienté.

Mettre à jour la classe Graphe_m_net ses méthodes afin qu’elle puisse représenter un graphe non orienté.

 

Activité : voisins
Ajouter une méthode voisins(x)qui renvoie la liste de tous les voisins du sommet x.

 

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}}
Activité : dictionnaire d'adjacence
Déterminer le dictionnaire d’adjacence du graphe ci dessous :

 

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_n:

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.

 

Activité : construction
Ajouter deux méthode ajouter_sommet(x) et ajouter_arete(x, y) permettant d’ajouter au graphe respectivement un nouveau sommet x et une arête du sommet x vers le sommet y.

 

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

Vous aimerez aussi...

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *

*

code