Skip to content

Cours et activités sur les graphes

Introduction

Le problème des 7 ponts de Königsberg

La ville de Königsberg (aujourd'hui Kaliningrad, en Russie) est construite autour de deux îles situées sur le Pregel et reliées entre elles par un pont. Six autres ponts relient les rives de la rivière à l'une ou l'autre des deux îles, comme représentés sur le plan ci-dessous.

Le problème consiste à déterminer s'il existe ou non une promenade dans les rues de Königsberg permettant, à partir d'un point de départ au choix, de passer une et une seule fois par chaque pont, et de revenir à son point de départ, étant entendu qu'on ne peut traverser le Pregel qu'en passant sur les ponts. (source wikipédia)

A vous de jouer !

La réponse Cessez de cherchez ! En effet, il n'existe pas de solutions permettant de réaliser cette promenade

Initiée par le grand mathématicien suisse Euler, avec le célèbre problème des 7 ponts de Königsberg, les applications de la théorie des graphes et de la recherche opérationnelle sont aujourd'hui immenses tant au plan civil que militaire :

  • aide à la prise de décision ;
  • recherche de la meilleure stratégie ;
  • optimisation (plus court chemin, GPS, coût minimal, ordonnancement des tâches ...) ;
  • réseaux de transports (autoroutes, chemins de fer, métro, lignes aériennes ...) ;
  • transport de l'énergie (électricité, gaz ...) ;
  • transport de l'informations : internet, réseaux sociaux ...

Le vocabulaire des graphes

Tout graphe est composé de deux types d’éléments : les sommets (aussi appelés nœuds) et les arêtes qui lient deux nœuds entre eux.

Les éléments d’un graphe peuvent être associés à plusieurs informations. Ainsi, on peut associer aux sommets d’un graphe de réseau routier (des lieux) non seulement une adresse, mais aussi des coordonnées GPS et des heures d’ouverture s’il s’agit d’un commerce. De même, on peut associer aux arêtes de ce même graphe leur longueur en kilomètres, la vitesse maximale autorisée ou encore des informations locales de trafic à une heure donnée. Grâce à ces informations, on peut imaginer calculer le chemin le plus court, ou le plus rapide, ou avec le moins d’autoroute, entre deux lieux ou plus.

Un graphe est avant tout une façon abstraite de structurer de l’information, dont une image comme la figure ci- contre n’est qu’une représentation visuelle. Par défaut, un sommet n’a pas de position et un lien n’a pas de longueur. À moins que les arêtes et sommets du graphe n’aient des propriétés géométriques explicites, leurs positions dans la représentation visuelle d’un graphe sont seulement destinées à améliorer sa lisibilité.

L'orientation d'un graphe

Une arête peut être orientée, ce qui signifie que le lien qu’elle représente possède une direction. Une arête orientée s’appelle un arc. Par exemple, une rue à sens unique ne relie deux lieux que dans un seul sens. Un graphe représentant un réseau routier doit donc utiliser des arcs, car certaines rues sont à sens unique ; les rues à double sens sont alors représentées par deux arcs, un dans chaque sens. Suivre (follow) un compte Twitter crée un arc, car la personne suivie ne vous suit pas automatiquement en retour.

Une arête non-orientée représente un lien symétrique entre deux sommets. Par exemple, le réseau social Facebook peut se représenter à l’aide d’arêtes non-orientées car si je suis votre « ami » sur Facebook, vous êtes aussi le mien.

Par extension, un graphe orienté ne contient que des arcs et un graphe non-orienté ne contient que des arêtes. Un graphe contenant des arêtes et des arcs est appelé graphe mixte.

Les graphes simples et les multi-graphes

Le graphe est dit simple, s'il ne peut y avoir au plus qu'une arête entre deux sommets dans le cas de graphes non orientés ou au plus un arc dans chaque sens dans le cas de grphes orientés. Par exemple, un compte twitter (graphe orienté) ne peut pas suivre plusieurs fois un même autre compte. Et un compte Facebook (non-orienté) ne peut pas être ami avec un autre compte plusieurs fois en même temps.

Dans le cas contraire, on parle de multi-graphe. Par exemple, il est possible de voyager de Paris vers Nice en voiture, en train ou en avion : il existe donc au moins trois arcs Paris-Nice dans un graphe représentant les moyens de transport entre les grandes villes.

La compléxité morphologique d'un graphe

Il existe différentes propriétés permettant d'exprimer la forme, la taille ou la compléxité d'un graphe :

  • l'ordre d'un graphe est le nombre de ses sommets S;
  • la taille d'un graphe est le nombre de ses arêtes A;
  • le degré d'un sommet est le nombre d'arêtes qui relient ce sommet à d'autres sommets
  • le degré entrant d'un sommet dans le graphe orienté est le nombre d'arcs entrants, c'est à dire qui ont ce sommet comme destination. De même le degré sortant est le nombre d'arcs sortants, cest à dire qui ont ce sommet comme origine.
  • Deux sommets reliés par une arête sont dits adjacents

Un graphe (simple) est complet si tout ses sommets sont connectés entre eux deux à deux. Pour S sommets, celà correspond à :

  • A=Sx(S-1) arcs dans un graphe orienté
  • A=Sx(S-1)/2 arêtes dans un graphe non-orienté

La densité D d'un graphe simple est une indication générale de sa connectivité et indique s'il à beaucoup ou peu d'arêtes. Différentes métriques existent, parmi lesquelles le rapport entre le nombre d'arêtes existantes et le nombre possible :

  • pour un graphe orienté : D=A/(Sx(S-1))
  • pour un graphe non-orienté : D=2xA/(Sx(S-1))

Ce nombre vaut 1 pour un graphe complet et 0 pour un graphe sans aucune arête. Un graphe est dit « creux » si sa densité D est proche de 0. Il est dit « dense » si D est proche de 1. Il n’existe pas vraiment de seuil numérique permettant de décréter qu’un graphe est plutôt creux ou dense, cela dépend du cas d’application.

Une arête peut relier un sommet à lui-même,, par exemple pour représenter une page Wikipédia contenant un lien qui pointe vers elle-même. On parle alors de boucle. Une boucle ne peut cependant pas exister dans un graphe simple.

Une arête peut être pondérée, c’est-à-dire se voir associer une valeur. Par exemple, on peut décrire dans le graphe d’un réseau électrique la longueur d’un câble ou le courant qu’il peut supporter, afin de calculer les pertes par dissipation. Un sommet peut également être pondéré, par exemple pour exprimer la consommation d’électricité de chaque foyer.

Une arête peut également être étiquetée, c’est-à-dire se voir associer un identifiant ou un type. Par exemple, dans un graphe moléculaire, les arêtes entre deux atomes (sommets) peuvent représenter différentes liaisons chimiques avec des propriétés distinctes. Un graphe étiqueté est un graphe dont les arêtes sont étiquetées.

Une chaîne est une séquence d’arêtes consécutives dans un graphe non-orienté ; dans un graphe orienté on parlera de chemin. Une chaîne ou un chemin est dit simple s’il contient au plus une arête entre deux mêmes sommets. Un graphe est connexe s’il existe une chaîne ou un chemin entre chaque paire de sommets.

Un cycle est une chaîne simple (dans un graphe non-orienté) dont le premier et le dernier sommets sont identiques ; un circuit est l’équivalent dans un graphe orienté.

Un arbre enraciné est défini formellement comme un graphe simple, orienté, connexe et sans cycle. La racine d’un tel arbre est l’unique sommet n’ayant pas d’arc entrant

Comment représenter informatiquement un graphe

Il existe deux façons d’implémenter un graphe:

  • La matrice d’adjacence,
  • la liste de successeurs/prédécesseurs.

Nous allons voir comment réaliser ces deux implémentations, et comment passer de l’une à l’autre.

La liste de successeurs/prédécesseurs.

Définition : La liste d'adjacence

La liste d’adjacence d’un graphe non orienté, est la liste des voisins de chaque sommet.

Exemple de liste d'adjacence

La matrice d'adjacence

Définition : La matrice d'adjacence

On représente les liens entre les n sommets du graphe par une matrice de dimension n dont l’élément non diagonal aij est le nombre d’arêtes (ou son poids pour un graphe pondéré) liant le sommet i au sommet j.

Dans le cas d'un graphe non-orienté, la matrice d'adjacence est symétrique.

Exemple de Matrice d'adjacence d'un graphe non-orienté

la matrice d'un graphe orienté est quelconque

Exemple de Matrice d'adjacence d'un graphe orienté

Quelle représentation choisir ?

Cette représentation est particulièrement adaptée aux graphes creux (c’est-à-dire peu denses), contrairement à la matrice d’adjacence adaptée aux graphes denses.

Implémentation Accès à une arête Accès à un voisin Ulilisation préférable
Matrice d'adjacence O(1) O(n) Graphe dense
liste de successeurs O(n) O(1) Graphe creux

Implémentation en python

soit le graphe suivant :

graphe Un graphe orienté

A -> B
A -> C
B -> C
B -> D
C -> D
D -> C
E -> F
F -> C

La représentation sous la forme d'une liste d'adjacence pour se réaliser à l'aide d'un dictionnaire (type dict).

1
graph = {'A':['B','C'],'B':['C','D'],'C':['D'],'D':['C'],'E':['F'],'F':['C']}

La représentation de la matrices d'adjacence peut se représenter sous la forme d'un tableau de tableaux (type liste).

1
graph = [[0,1,1,0,0,0],[0,0,1,1,0,0],[0,0,0,1,0,0],[0,0,1,0,0,0],[0,0,0,0,0,1],[0,0,1,0,0,0]]

   A B C D E F
A| 0 1 1 0 0 0 |
B| 0 0 1 1 0 0 |
C| 0 0 0 1 0 0 |
D| 0 0 1 0 0 0 |
E| 0 0 0 0 0 1 |
F| 0 0 1 0 0 0 |

graphe de la matrice ci-dessus

On remarque :

L'arête (liaison non-orientée) de couleur orange correspondante à la laison entre C et D.

Activités

Activité 1 : Réseau Electrique

Un de vos amis travaille pour un distributeur d’électricité.

Il doit proposer à son supérieur une représentation du réseau reliant différentes villes.Comme il n’y arrive pas trop, il voudrait que vous la lui fassiez.

Pour simplifier le problème, il a déjà renommé les villes en A, B, C, D, E et F. De plus, il vous donne les informations suivantes :

  • la ville A est reliée par un réseau électrique aux villes B, E et F,
  • la ville B est reliée par un réseau électrique aux villes A, C et D,
  • la ville C est reliée par un réseau électrique aux villes B, D, E et F,
  • la ville D est reliée par un réseau électrique aux villes B, C et F,
  • la ville E est reliée par un réseau électrique aux villes A, C et F,
  • la ville F est relié par un réseau électrique aux villes A, C, D et E.

On vous demande :

  1. Proposer un graphe qui modélise la situation.
  2. Ce graphe est-il complet ? Pourquoi ?
Réponse au 1.

graphe du réseau electrique

Réponse au 2.

Un graphe (simple) est complet si tout ses sommets sont connectés entre eux deux à deux ici comme vous pouvez vous en apercevoir, tous les sommets ne sont pas reliés entre eux deux à deux. Donc ce graphe n'est pas complet.

Activité 2 : Représentation d'un graphe non-orienté

Voici un ensemble des relations :

  • A est ami avec tout le monde sauf G,
  • B est ami avec A, D et H,
  • C est ami avec A, F, G et H,
  • D est ami avec A, B et H,
  • E est ami avec A et H,
  • F est ami avec A et C,
  • G est ami avec C et H,
  • H est ami avec A, B, C, D, E et G.

On vous demande :

  1. Représenter ce graphe et vérifier qu’il est non orienté.
  2. Implémenter ce graphe sous la forme d’un dictionnaire de liste dans lequel chaque clé représente le nœud étudié et les sommets adjacents sont représentés sous la forme d’une liste.
  3. Écrire la matrice d’adjacence et vérifier qu’elle est symétrique(on utilisera l’ordre alphabétique pour indexer les nœuds).
  4. Implémenter la matrice en python sous la forme d’une liste de liste.
Réponse au 1.

graphe des amis

Ce graphe est non-orienté car il suffit qu'au moins deux amis (sommets) soient réciproquements amis (réciproquement reliés entre eux), ce qui est bien le cas ici puisque A est ami avec tout le monde (dont A) sauf G et que B est ami avec A, D et H.

Réponse au 2. 
1
amis={"A":["B","C","D","E","F","H",],"B":["A","D","H"],"C":["A","F","G","H"],"D":["A","B","H"],"E":["A","H"],"F":["A","C"],"G":["C","H"],"H":["A","B","C","D","E","G"]}
Réponse au 3.

On constate bien à l'aide des couleurs que l'on retrouve en colonne ce que l'on a en ligne. La matrice est donc bien symétrique .

Réponse au 4. 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
amis=[[0,1,1,1,1,1,0,1],[1,0,0,1,0,0,0,1],[1,0,0,0,0,1,1,1],[1,1,0,0,0,0,0,1],[1,0,0,0,0,0,0,1],[1,0,1,0,0,0,0,0],[0,0,1,0,0,0,0,1],[1,1,1,1,1,0,1,0]]

# alors de cette autre manière plus lisible

amis=  [[0,1,1,1,1,1,0,1],
        [1,0,0,1,0,0,0,1],
        [1,0,0,0,0,1,1,1],
        [1,1,0,0,0,0,0,1],
        [1,0,0,0,0,0,0,1],
        [1,0,1,0,0,0,0,0],
        [0,0,1,0,0,0,0,1],
        [1,1,1,1,1,0,1,0]]

Activité 3 : test présence d'un arc entre deux sommets

On veut estimer le nombre de tests nécessaires pour vérifier l’existence d’un arc entre 2 sommets d'un graphe.

Compléter la fonction suivante qui détermine le nombre de tests pour déterminer l’existence d’un arc allant d'un sommet n1 à un sommet n2 d’un graphe représenté sous la forme d’une liste d’adjacence.

1
2
3
4
5
6
7
8
9
def nb_tests_existence_liste(graphes,n1,n2):
    nb_tests=0
    for               : # à compléter

        nb_tests+=n1
        if              :
            return nb_tests

    # que fait-on si on a pas trouvé d'arc ?
une réponse si l'arc existe 
1
2
3
4
5
6
7
8
9
def nb_tests_existence_liste(graphes,n1,n2):
    nb_tests=0
    for succ in graphe[n1] :   # à compléter
        for sommet in succ:
            nb_tests += 1
            if sommet == n2 :
                return nb_tests

    # que fait-on si on a pas trouvé d'arc ?
Et que proposez vous si "on a pas trouvé d'arc ? 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def nb_tests_existence_liste(graphe,n1,n2):
    nb_tests =0
    ''' si n1 n'existe pas ou si n2 (en tant que sucesseur de n1) n'existe pas'''
    if n1 not in graphe or n2 not in graphe[n1]:
        return 9999
    for succ in graphe[n1] :   # à compléter
        for sommet in succ:
            nb_tests += 1
            if sommet == n2 :
                return nb_tests

Activité 4 :

Ecrire une fonction AjoutValeurDictionnaire(dic,cle,val) qui permet d'implémenter un graphe sous la forme d'un dictionnaire de liste(s).

une piste

Exemple lors de l'exécution de la fonction : 

AjoutValeurDictionnaire(graph1,"A",["B","C"])

une réponse 
1
2
3
def AjoutValeurDictionnaire(dic,cle,val):
    dic[cle]=val
    return

Ecrire une fonction CalculDensite(graph) qui calcul la densité d'un graphe orienté simple depuis une liste d'adjacence simple de type dictionnaire.

une piste 
1
2
    # Exemple de graphe orienté que l'on peut utiliser
    graphe1={"A":["B","C"],"B":["D"],"C":["D"],"D":[]} # string pour les clés : liste(s) de string(s) pour les valeurs
une réponse 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def CalculDensite(graph): #pour graphe orienté (forme dico de liste)
    S=len(graph) #nb de sommets
    print("nb de sommet",S)
    A=0
    for i in graph :
        A=A+len(graph[i]) #nb des Arcs
    print("nb d'arcs",A)
    D=A/(S*(S-1))# densité graphe orienté
    print("Densité = ",D)
    return

Activité 5 :

Ecrire une fonction CalculDensite2(graph) qui calcul la densité d'un graphe orienté simple depuis une matrice d'adjacence simple de type dictionnaire de dictionnaires

une piste 
1
2
3
4
5
    # Ajout des données type dictionnaires dans un dictionnaire
    # on prendra le booléen True pour signifier le lien (1 dans la matrice)
    # on prendra le booléen False pour signifier l'absence de lien (0 dans la matrice)

    AjoutValeurDictionnaire(graph2,"A",{"B":True,"C":True,"D":False})
une réponse 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
def CalculDensite2(graph): #pour graphe orienté (forme dico de dico)
S=len(graph) #nb de sommets
print("nb de sommet",S)
A=0 
for i in graph : #pour toutes les clés 
    val=graph.get(i)# récupère la valeur
    for j in val:
        if val.get(j)==True:
            A+=1
        else :
            A+=0
print("nb d'Arc",A)
D=A/(S*(S-1))# densité graphe orienté
print("Densité = ",D)
return

Les parcours de graphes

graphe de départ

Le point de départ est le sommet "A", les sommets sont numérotés par ordre de visite.

Le parcours en largeur

Aussi appelé BFS (Breadth-First Search), le parcours en largeur explore un graphe à partir d’un sommet A donné, en s’éloignant progressivement de A. Plus précisément, il consiste à explorer d’abord tous les voisins de A, puis les voisins de chacun de ces voisins (qui n’ont pas encore été visités), et ainsi de suite.

Cela permet d’explorer systématiquement les chemins entre chaque sommet d’un graphe, par exemple pour en déterminer les distances relatives.

Le parcours en profondeur

Aussi appelé DFS (Depth-First Search), le parcours en profondeur explore un graphe en suivant chaque chemin le plus loin possible puis, lorsqu’il rencontre un « cul de sac » (un sommet qui n’a d’arcs que vers des sommets déjà visités), revient en arrière vers le sommet précédent disposant d’arcs non-visités, et recommence.

Cela permet par exemple de déterminer rapidement s’il existe un circuit (ou un cycle) dans un graphe ou de trouver le plus court chemin entre deux sommets.

Le parcours en profondeur peut s’effectuer de façon récursive ou de façon itérative. Comme pour le parcours en largeur, on utilise un dictionnaire pour enregistrer les sommets déjà visités.

Pour aller plus loin

zeste de savoir : bases de la theorie des graphes

graphes réalisées avec graphonline.top