Les graphes

Les graphes sont des structures de données qui permettent de représenter les relations qui existent entre différentes informations.

Un plan de métro ou une carte routière peut être vu comme un graphe modélisant les routes qui relient une station ou une ville à une autre.

Tout réseau informatique peut par exemple être représenté par un graphe, indiquant les liaisons qui existent entre les différentes machines, routeurs, etc... du réseau.

On peut également représenter par un graphe les relations qui existent entre des personnes dans un groupe donné ( entreprises par exemple ) ou sur un réseau social.

Mais les graphes se retrouvent dans d'autres situations où on s'attend moins à les trouver, comme par exemple la recherche du chemin dans un labyrinthe, la résolution de certains jeux ou la coloration des cartes géographiques !

Les bases sur les graphes

Vocabulaire

Un graphe est constitué :

• d’un ensemble de sommets (parfois appelés nœuds). Les sommets ont souvent une étiquette.
• d’un ensemble de relations entre ces sommets.
  Les relations peuvent être à double sens, ou à sens unique (par exemple on peut aller de Sommet 1 vers Sommet 2 mais pas de Sommet 2 vers Sommet 1 ).
  Dans le premier cas, le graphe n’est pas orienté et les relations s’appellent des arêtes. Dans le deuxième cas, le graphe est dit orienté et les relations s’appellent des arcs.
  

• Dans un graphe non orienté, deux sommets sont voisins ( ou adjacents ) si ils sont reliés par une arête.
  Sommet 1 et Sommet 4 sont voisins, Sommet 2 et Sommet 3 ne le sont pas.

  On appelle degré le nombre de voisins d'un sommet.
  Le degré de Sommet 1 est 3, celui de Sommet 3 est 2.

• Dans le cas d'un graphe orienté, on parlera plutôt de successeurs ou prédécesseurs d'un sommet selon le sens de l'arc joignant les sommets.
  Ainsi, Sommet 4 est un successeur de Sommet 1, Sommet 2 est un prédécesseur de Sommet 4.

• Un sommet peut très bien être relié à lui-même par une boucle.

• un graphe-non orienté est connexe, si il existe un chemin qui permet d'aller de n'importe lequel de ses sommets à n'importe quel autre.
  C'est la même chose dans un graphe orienté si on ne tient pas compte de l'orientation des arcs.
  Dans un graphe non connexe, ou partiellement connexe, le graphe est un ensemble de sous-graphes indépendants les uns des autres.

Un graphe peut être valué ou pondéré. On associe dans ce cas à chaque arc ou arête une valeur numérique. Cela permet d'indiquer que certaines relations ont plus de "poids" que les autres dans le graphe, comme par exemple dans un réseau informatique une liaison entre deux routeurs plus rapide que les autres.

Exercices d'application

A l'origine des graphes : les ponts de Königsberg

La ville de Königsberg était une ville de Prusse puis une des principales villes de l'Empire Allemand avant d'être cédée à l'URSS en 1945. Cette ville est désormais appelée Kaliningrad et fait partie de la Fédération de Russie.

Cette ville s'étendait au XVIII^e siècle autour de deux îles situées sur le fleuve Pregel. Ces deux îles étaient reliées entre elles par un pont. Six autres ponts reliaient les rives de la rivière à l'une ou l'autre des deux îles, comme représenté sur le plan ci-contre.

La légende raconte que certains habitants de cette ville cherchaient lors de promenade à passer une fois et une seule par chacun des ponts pour revenir au point de départ.

Est-ce possible ? Si oui, par quel chemin ?

Les habitants ont cherché des solutions et l'un d'eux, le grand mathématicien Euler, a réussi en 1735 à répondre à la question précédente.
Pour cela, il a développé des outils mathématiques à la base de la théorie des graphes.

La visite au musée

Voici ci-contre le plan d’un musée : les parties grisées matérialisent les portes et les visiteurs partent de l’accueil, visitent le musée et doivent terminer leur visite à la boutique.

Le tournoi de foot

On souhaite organiser un tournoi de football avec 4 équipes ( numérotées de 1 à 4).

Chaque équipe rencontre une seule fois toutes les autres.

Une journée en enfer...

Dans ce film de 1995, Bruce Willis et Samuel Jackson sont confrontés à un méchant qui les oblige à résoudre des énigmes afin de sauver la vie de milliers de personnes...

Un des problèmes est le suivant : les deux personnages ont, en leur possession, deux bidons non gradués, un pouvant contenir cinq litres, et l'autre trois litres.
Il y a une fontaine à proximité. Comment faire pour avoir quatre litres dans le bidon de cinq litres, sans bien sûr avoir recours à un instrument de mesure ?

Le problème peut être modélisé par un graphe, dont les sommets sont les états des deux seaux ( c'est à dire le volume d'eau qu'ils contiennent à un moment donné ), et les relations, la possibilité de passer d'un état à l'autre.

L'énigme consiste donc à trouver un chemin entre les sommets (0,0) et (4,0) en effectuant des passages "permis" par la contenance des deux seaux. On peut ainsi passer de l'état (5,0) à l'état (3,2) en remplissant le seau de 3 L avec une partie de celui de 5L; par contre, on ne peut pas passer de l'état (2,3) à celui de (4,2) ( par exemple ) car on ne sait pas transvaser un volume de 1 L d'un seau à l'autre...

Le graphe comporte 24 sommets correspondant aux 24 états possibles selon le remplissage de chacun des seaux; ces sommets sont représentés ci-dessous :

A vous de trouver l'ensemble des relations à suivre dans ce graphe ( en respectant bien entendu les contraintes ! ) pour résoudre l'énigme.

SOLUTION

Un problème de planning...

Un Proviseur cherche à établir un planning de salles pour faire passer un Bac Blanc sur deux journées.
Les doublettes de spécialité des élèves concernés sont données dans le tableau ci-dessous :

Les contraintes sont les suivantes :

• utiliser le minimum de salles : on regroupe donc des spécialités dans une même salle ( que l'on supposera suffisamment grande 😌... );
• un élève ne peut pas, bien entendu, passer ses deux spécialités en même temps : il est dans une salle le premier jour, puis il change de salle le deuxième jour.

La question est : combien de salles faudra-t-il au minimum, et quelles seront les spécialités que l'on pourra regrouper dans une même salle ?

Ce genre de problème appartient aux problèmes de coloration de graphe : on cherche à donner à chaque sommet d'un graphe une "couleur" ( ce peut être un nombre...), de telle façon que des sommets adjacents dans le graphe n'ait pas la même couleur. On visualise ainsi les "groupes" de sommets que l'on peut identifier dans le graphe.

1. représenter le graphe associé à la situation décrite :
   • les sommets sont les spécialités
   • les arêtes relient les sommets correspondant aux spécialités appartenant à une même doublette ( les arêtes modélisent donc les contraintes sur les spécialités qui ne peuvent pas être dans la même salle )
2. colorier le graphe, en donnant à chaque sommet une couleur, de façon à minimiser le nombre de couleurs nécessaires et à ce que des sommets adjacents n'ait pas la même couleur
3. Faire le planning des salles pour ce Bac Blanc !

Ordonnancement de taches dans un projet

La réalisation d'un projet passe souvent pas l'exécution de différentes tâches. Certaines de ces tâches peuvent être réalisées simultanément, mais d'autres nécessitent d'être réalisées dans un ordre précis.

Faire l'ordonnancement d'un projet consiste à organiser ce projet en respectant les contraintes d'antériorité des tâches, tout en minimisant la durée totale de réalisation.

On s'intéresse par exemple à un projet de développement d'un robot, dont les différentes taches à réaliser, ainsi que leur durée, sont données dans le tableau ci-dessous :

La question est : quelle est la durée minimale de réalisation de ce projet ?

Une des méthodes pour répondre est la méthode MPM ( Méthode des Potentiels Métra ), qui consiste à représenter le problème sous la forme d'un graphe d'ordonnancement :

1. On commence par déterminer le niveau de chaque tâche : une tache de niveau 0 n'a pas de prédécesseur; une tache de niveau 1 a au moins un prédécesseur parmi les taches de niveau 0, et ainsi de suite.
2. On représente alors le projet par un graphe orienté pondéré, dans lequel :
   • chaque tâche est représentée par un sommet,
   • les sommets sont alignés verticalement par niveau,
   • les arcs représentent les contraintes d'antériorité ( un arc va de X à Y si il est indispensable d'avoir terminé X pour faire Y),
   • la valeur de chaque arc est la durée de la tâche à l'origine de l'arc,
   • deux sommets (ne correspondant pas à des tâches) sont placés aux extrémités du graphe : Début et Fin.

Structure de données graphe

Il faut maintenant réfléchir à la manière de représenter un graphe en mémoire d'un ordinateur.

De quoi a-t-on besoin de pour décrire des graphes ?

De toute évidence, il nous faut pouvoir représenter :

• les sommets
• les arêtes ( ou les arcs )

Lors de notre représentation des arbres binaires, nous avions choisi de ne considérer que les nœuds et nous avions essentiellement une structure sous forme de triplet :

arbre = (étiquette, fils_gauche, fils_droit).

Cela ne fonctionne plus ici, il n’y a généralement pas de sommet privilégié dans un graphe, tous les nœuds jouent le même rôle.

Il faut donc envisager un moyen de représenter l’ensemble des relations entre sommets.

Représentation par listes d'adjacence

La méthode la plus simple et la plus courante pour décrire les arêtes/les arcs est d’en donner une liste pour chacun des sommets.

• Pour le graphe non orienté ci-contre, on aurait ainsi :

  Ensemble des sommets	Ensemble des arêtes
  A	B, C, D
  B	A, D
  C	A, D
  D	B, C, A

  

• Pour le graphe orienté ci-contre, on n'indiquera que les successeurs de chaque sommet :

  Ensemble des sommets	Ensemble des arcs
  A	B, C, D
  B	D
  C	D
  D	B

  

  Remarque : une alternative serait aussi bien de représenter la liste des prédécesseurs de chaque sommet.

• Et pour un graphe pondéré ?

  Dans ce cas, il faut indiquer une information en plus dans la liste des arêtes/des arcs, à savoir le poids de chaque relation, par exemple sous forme d'un n-uplet :

  Ensemble des sommets	Ensemble des arcs
  A	(B, 5), (C, 2), (D, 6)
  B	(A, 5), (D, 3)
  C	(A, 2), (D, 9)
  D	(B, 3), (C, 9), (A, 6)

  

Représentation par matrice d'adjacence

L'avantage de cette représentation est que l'on "voit" immédiatement quels sont les voisins de tel ou tel sommet.
L'inconvénient est que la matrice d'adjacence est souvent "vide", c'est à dire qu'elle occupe une grande place en mémoire pour finalement peu d'information...

• Dans le cas du graphe non orienté ci-contre, la matrice d'adjacence serait :

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

  On remarque qu'un sommet n'est pas "relié à lui-même" ( attention, sauf si il existe une boucle ! ).

  

• Pour un graphe orienté, on prendra par exemple la convention suivante :

  • les lignes correspondent aux prédécesseurs des sommets
  • les colonnes correspondent aux successeurs.

  Les arcs sont donc orientés des lignes vers les colonnes.

  Dans le cas du graphe orienté ci-contre, la matrice d'adjacence serait :

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

  

• Pour un graphe pondéré, on remplacera les booléens par le poids respectif de chaque arête/arc :

  ↱	A	B	C	D
  A	0	5	2	6
  B	5	0	0	3
  C	2	0	0	9
  D	6	3	9	0

  

Et dans la pratique, que préférer comme implémentation ?

Ce paragraphe est tiré de la page http://www.monlyceenumerique.fr/nsi_terminale/sd/sd5_graphe.php ( © CC-BY-NC-SA )

Cela dépend de :

1. la structure du graphe : plus un graphe est "dense", c'est-à-dire plus il y a d'arêtes (ou d'arcs) pour un nombre donnés de sommets, plus la matrice d'adjacence est pertinente.

   En effet, considérons un graphe avec n sommets et m arêtes :

   • la complexité en mémoire d'une matrice d’adjacence est en O(n²).

   • la complexité en mémoire d'un tableau de tableaux d’adjacence est en O(n+m).

2. le travail à faire sur ce graphe : vous verrez dans un prochain chapitre des algorithmes pour étudier et travailler avec des graphes. Certains algorithmes nécessiteront d'implémenter le graphe d'une manière plutôt qu'une autre.

   Dès maintenant, vous pouvez comprendre que pour un graphe à n sommets :

   • si on veut tester que deux sommets sont adjacents ou non :

     on a une complexité en temps en O(1) pour une matrice d'adjacence (lecture directe d'un terme de la matrice)

     mais en O(d) pour une liste d'adjacence où d correspond au nombre de voisins du sommet testé ( on doit, dans le cas où il n'y a pas d'arête reliant les sommets, balayer toute la liste des sommets voisins )

     L'implémentation sous forme de matrice d'adjacence est préférable alors.

   • si on veut itérer sur les voisins d'un sommet :

     on a une complexité en temps en O(n) pour une matrice d'adjacence (lecture de tous les termes d'un même ligne (ou colonne) pour connaître quels sont les sommets voisins)

     mais en O(d) pour une liste d'adjacence ( on doit balayer toute la liste des sommets voisins )

     L'implémentation sous forme de liste d'adjacence est préférable alors.

Exercices d'application

Les figures ci-dessous tracent des graphes aléatoires; vous pouvez zoomer le graphe, le déplacer, déplacer les nœuds pour mieux le voir.

Du graphe à sa représentation

De sa représentation au graphe

D'une représentation à l'autre