Alice est sur Wikipedia, en train de lire la page Algorithme du lièvre et de la tortue. Trois clics plus tard, elle se surprend à lire la page Cathédrale Saint-Étienne de Metz et se demande soudain comment elle en est arrivée là.
D'autres questions se précipitent alors dans sa tête.
Est-il possible de revenir à la page Algorithme du lièvre et de la tortue en suivant uniquement des liens entre articles de Wikipedia?
Combien de clics seraient nécessaires
pour cela?
Certains article de Wikipedia sont-ils tout simplement inatteignables à partir de cette page?
Immédiatement, Alice comprend qu'il lui faudra écrire un programme si elle veut répondre à de telles questions, car tenter d'y répondre par une exploration manuelle lui prendrait bien trop de temps.
Mais Alice sait également qu'il y a plus de deux millions de pages sur fr.wikipedia.org, et des dizaines de liens dans chaque page, alors elle se demande légitimement si un tel programme a simplement une chance de répondre dans un délai raisonnable.
En cherchant à écrire des programmes pour répondre à ces questions, Alice découvre la théorie des graphes, inventée il y a presque 300 ans par le mathématicien Leonhard Euler, et qu'elle peut effectivement déterminer s'il existe un chemin d'une page à une autre dans Wikipedia avec un algorithme qui s'écrit en seulement cinq lignes de code.
","title":"S.D. : Graphes","tagtitle":"h1","posi":0},{"edit":"Nous allons commencer par fixer les notions et le vocabulaire de base de
la théorie des graphes.
Sommets, arcs, orientation
Un graphe est un ensemble de sommets reliés entre eux par des arcs.
Dans l'exemple de Wikipedia chaque page forme un sommet, et les liens permettant de naviguer d'une page à l'autre constituent les arcs.
Graphe orienté
Voici un exemple plus petit de graphe possédant quatre sommets, notés A, B, C et D, et six arcs, dessinés par des flèches.
![\"graphe1.png](\"https://sciencesappliquees.com/images/nsi/graphe1.png\")
Dans ce graphe il y à un arc du sommet A vers le sommet B, ce que l'on note A—>B , mais pas du sommet B vers le sommet A.
On parle de graphe orienté lorsque l'on distingue ainsi un sens pour les arcs.
En particulier, il y a un arc du sommet B vers le sommet D et un autre du sommet D vers le sommet B.
Mettre le résultat ici (code et figure).
Graphe non orienté
Lorsqu'en revanche le sens des arcs n'est pas significatif, c'est-à-dire que l'on s'intéresse uniquement à la présence d'un arc entre deux sommets, on parle de graphe non orienté.
On dessine alors les arcs non pas comme des flèches mais comme de simples traits reliant les sommets.
![\"graphe1.png](\"https://sciencesappliquees.com/images/nsi/graphe2.png\")
Sur cet exemple, on a toujours quatre sommets mais seulement cinq arcs maintenant.
La figure ci-dessous représente un graphe où les sommets sont les dix-huit régions françaises et où on a relié entre elles les régions limitrophes (par la terre).
![\"graphe1.png](\"https://sciencesappliquees.com/images/nsi/graphe3.png\")
Figure 1 : Le graphe des régions françaises.
C'est un autre exemple de graphe non orienté.
Mettre le résultat ici (code et figure).
Voisinage
Lorsqu'il y a un arc d'un sommet s vers un sommet t, on dit que t est adjacent à s.
Les sommets adjacents à s sont également appelés les voisins de s.
Dans les exemples précédents, le voisinage de A est l'ensemble {B,D} et le voisinage de D est le singleton {B} dans le cas orienté et l'ensemble {A,B, C} dans le cas non orienté.
Dans tout cette séquence, on se limite à des graphes simples, dans lesquels il y a au plus un arc entre deux sommets (pas d'arcs multiples) et pas d'arc reliant un sommet à lui-même (pas de boucles).
Mettre le résultat ici (code et figure).
Dessins
Il est important de comprendre que c'est l'ensemble des sommets et la relation d'adjacence, c'est-à-dire l'ensemble des arcs, qui définissent le graphe, et non pas la façon dont on le dessine.
Ainsi, les trois graphes suivants sont identiques, bien que dessinés différemment.
![\"graphe1.png](\"https://sciencesappliquees.com/images/nsi/graphe5.png\")
Notons qu'un graphe n'est pas nécessairement fini. Il peut contenir une
infinité de sommets et, dans ce cas, possiblement une infinité d'arcs. Ainsi, on peut considérer le graphe dont les sommets sont les entiers naturels et où il y a un arc n — m dès lors que m est un diviseur strict de n.
Mettre le résultat ici (code et figure).
Chemin dans un graphe
Dans notre exemple de Wikipedia, Alice a visité plusieurs pages l'une après l'autre, navigant de l'une à la suivante à l'aide de liens.
On appelle ceci un chemin.
Chemin
Dans un graphe donné, un chemin reliant un sommet u à un sommet v est une séquence finie de sommets reliés deux à deux par des arcs et menant de u à v.
Ainsi, dans le graphe
il existe un chemin reliant A à C, à savoir A —> B —> C. Mais il y en a d'autres, comme par exemple A —> D —> B —> C ou encore A —> B -> C —> D —> B ->C.
En fait, il y a ici une infinité de chemins reliant A à C, car on peut emprunter le chemin D —> B —> C —> D ou encore B —> D —> B autant de fois que l'on veut.
Pour un graphe non orienté, on à un chemin reliant u à v si et seulement
si on à un chemin reliant v à u. Mais pour un graphe orienté, on peut avoir
un chemin reliant u à v mais pas de chemin reliant v à u.
Ainsi, dans le graphe ci-dessus, il n'y a pas de chemin reliant C à A.
Mettre le résultat ici (code et figure).
Cycle
Un chemin est dit simple s'il n'emprunte pas deux fois le même arc, et élémentaire s'il ne passe pas deux fois par le même sommet.
Ainsi, dans le graphe précédent il n'y a que trois chemins simples reliant A à C, et seulement deux chemins élémentaires.
Un chemin simple reliant un sommet à lui-même et contenant au moins un arc est appelé un cycle.
C'est le cas par exemple de D—>B->C->D ici.
Notez que, dans le cas d'un graphe non orienté, la restriction imposant aux cycles d'être des chemins simples empêche de revenir sur ses pas.
Ainsi dans le graphe
le chemin A->B—>A n'est pas simple et n'est donc pas un cycle.
Mettre le résultat ici (code et figure).
Distance
La longueur d'un chemin est définie comme le nombre d'arcs qui constituent ce chemin.
La distance entre deux sommets est la longueur du plus court chemin reliant ces deux sommets, le cas échéant.
Ainsi, dans l'exemple ci-dessus, le chemin A->D->B->C a pour longueur 3, mais la distance entre A et C est 2, obtenue pour le chemin plus court A->B->C.
La distance d'un sommet s à lui-même est 0, obtenue pour le chemin allant de s à s en n'empruntant aucun arc.
La distance entre deux sommets n'est pas définie s'il n'existe aucun chemin entre les deux sommets.
Mettre le résultat ici (code et figure).
Connexité
On dit qu'un graphe non orienté est connexe si, pour toute paire u,v de sommets, il existe un chemin de u à v.
Pour un graphe orienté, on dit qu'il est connexe si le graphe non orienté obtenu en oubliant le sens des arcs est connexe.
On dit qu'un graphe orienté est fortement connexe lorsqu'il existe un chemin de u à v et un chemin de v à u pour toute paire u,v de sommets.
Ainsi, le graphe
est connexe mais pas fortement connexe. En effet, il existe un chemin reliant A à B mais pas de chemin reliant B à A.
Le graphe
![\"graphe1.png](\"https://sciencesappliquees.com/images/nsi/graphe4.png\")
n'est pas connexe, car il n'y a pas de chemin reliant C à E une fois qu'on
a oublié le sens des arcs.
On dit qu'il possède deux composantes conneres, l'une formée des sommets A, B, C et D et l'autre formée des sommets E et F.
De même, le graphe des régions de la figure 11.1 n'est pas connexe. Il contient sept composantes connexes, dont six sont réduites à un unique sommet.
Dans la séquence suivant, nous verrons des algorithmes pour déterminer si un graphe est connexe et plus généralement pour déterminer s'il existe un chemin entre deux sommets.
Mettre le résultat ici (code et figure).
Vocabulaire
Le vocabulaire des graphes varie selon le contexte et notamment selon le caractère orienté ou non des graphes.
Ainsi, on parle parfois de nœuds et d'arêtes plutôt que de sommets et d'arcs pour les graphes non orientés.
De même, on parle parfois de chaîne plutôt que de chemins dans les graphes non orientés.
Mettre le résultat ici (code et figure).
Autres caractérisations des chemins
Un chemin peut également être caractérisé par la succession des arcs qu'il emprunte.
C'est notamment pertinent lorsque l'on ne considère pas un graphe simple, et que plusieurs arcs peuvent aller d'un sommet s à un sommet t.
Cette caractérisation peut cependant également comporter une ambiguïté dans le cas des graphes non orientés.
Dans ce cas, on peut aller jusqu'à une description complète donnant la succession des sommets et des arcs.
Étiquetage
Il est fréquent d'associer une information à chaque sommet et/ou à chaque arc d'un graphe. On parle alors de graphe étiqueté.
Pour ce qui est des sommets, on peut confondre un sommet et son étiquette dès lors que celle-ci est unique.
Ainsi, dans nos exemples précédents, on
peut dire « le sommet «A» ou «le sommet étiqueté par A».
Pour ce qui est des arcs, on peut adopter la notation u -e-> v pour indiquer
que l'arc entre les sommets u et v porte l'étiquette e.
Si la nature de cette étiquette est numérique, alors on peut définir une notion de coût pour un chemin, comme la somme des étiquettes des arcs constituant ce chemin.
On peut alors parler de plus court chemin au sens de ce coût plutôt qu'au sens du nombre d'arcs.
","title":""},{"edit":"Mettre le résultat ici (code et figure).
Maintenant que nous savons ce qu'est un graphe, on peut en donner de nombreux exemples.
Sur tous ces exemples, on peut se poser des questions comme :
- le graphe est-il connexe?
- existe-t-il un chemin entre le
sommet A et le sommet B?
- ou encore : quelle est la distance entre les sommets A et B?
Réseau
![](\"https://sciencesappliquees.com/images/snt/itineraire.png\")
Un réseau routier est naturellement un graphe. Ce peut être par exemple un réseau routier à grande échelle, avec des sommets qui sont des villes, reliés par des arcs qui représentent des routes entre ces villes.
Si toutes les routes sont à double sens, le graphe sera naturellement non orienté.
Mais on peut également imaginer un réseau routier à l'intérieur d'une même ville, où les sommets sont plutôt les intersections entre les rues ct les
arcs des portions de rues reliant une intersection à une autre.
Dans ce cas, le graphe sera naturellement orienté dès lors que certaines rues sont à sens unique.
Un navigateur GPS implémente un algorithme de recherche de chemin dans un tel graphe. Il prend en compte des informations supplémentaires, telles que la longueur des routes, la vitesse maximale autorisée, la présence de péages, etc pour calculer des chemins qui minimisent la distance totale, le temps de trajet, etc. La recherche d'un tel chemin minimal n'est pas au programme de terminale.
Un réseau n'est pas nécessairement un réseau routier. On peut ainsi considérer un réseau informatique, où des machines sont reliées entre elles, ou encore un réseau social, où des personnes sont reliées entre elles, par exemple par leurs contacts respectifs.
Dans ce domaine, les mathématiciens ont défini le nombre d'Erdös d'un mathématicien X comme la distance entre le mathématicien Paul Erdös et le mathématicien X dans un graphe non orienté où les arcs relient entre eux les mathématiciens qui sont coauteurs d'un même article.
Toujours dans le domaine des réseaux sociaux, la propriété de «petit monde» énonce que la distance entre deux personnes est très petite (logarithmique, pour être précis) comparativement au nombre d'individus.
Mettre le résultat ici (code et figure).
Carte
Le graphe des régions françaises de la figure 1 est une façon de concevoir la carte des régions. On pourrait faire la même chose avec les départements, les pays du monde, etc.
Un très célèbre théorème de mathématiques, le théorème des quatre couleurs, énonce que les pays d'une carte
planaire peuvent toujours être coloriés avec quatre couleurs seulement sans que deux pays limitrophes aient la même couleur.
Ce théorème s'énonce en termes de graphes en disant que tout graphe qui peut être dessiné dans le plan (i.e., sans que deux arcs ne se croisent) peut voir ses sommets coloriés avec quatre couleurs au plus sans que deux sommets reliés par un are n'aient la même couleur.
Mettre le résultat ici (code et figure).
Labyrinthe
![\"Labyrinthe\"](\"https://omnilogie.fr/images/O/0e6e1fcc31f8281e7d1445bd64714aa2.jpg\")
Source : https://omnilogie.fr/O/Labyrinthe
Un labyrinthe constitué de salles reliées entre elles par des portes peut être vu comme un graphe non orienté.
Les sommets sont les salles du labyrinthe et deux sommets sont reliés par un arc s'il existe une porte entre ces deux salles.
Dans la séquence suivant, nous étudierons un algorithme efficace pour déterminer s'il existe un chemin entre deux sommets donnés d'un graphe et même le construire, le cas échéant.
On peut en particulier se servir d'un tel algorithme pour trouver un chemin qui mène de l'entrée à la sortie d'un labyrinthe.
Mettre le résultat ici (code et figure).
Jeu![](\"https://www.lapouleapois.fr/24976-thickbox_default/jeu-de-dames-pliant-jeujura.jpg\")
Source:https://www.lapouleapois.fr/jeux-traditionnels/8490-jeu-de-dames-pliant-jeujura-3225280813103.html?gclid=CjwKCAiAtK79BRAIEiwA4OskBo1Rmxf0xpVrd0RXq8lOrdTi5JBVE0xvO4Wh081AX_qOdZxG8NzBGxoCkG4QAvD_BwE
De nombreux jeux consistent à modifier une configuration donnée, typiquement en déplacement des pièces, jusqu'à obtenir une configuration particulière.
Dans cette catégorie, on peut citer des jeux à un joueur de type casse-tête, comme l'âne rouge, le solitaire où encore le taquin, mais aussi à plusieurs joueurs, comme les échecs ou les dames.
Pour un tel jeu, on peut concevoir un graphe où les sommets sont les configurations possibles du jeu et les arcs les coups valides qui permettent de passer d'une configuration à une autre.
Un tel graphe est typiquement gigantesque, voire infini, et de
multiples chemins peuvent mener d'une configuration à une autre. Nous verrons que cela n'empêche pas néanmoins de chercher des chemins et en particulier des chemins menant à une configuration gagnante.
Mettre le résultat ici (code et figure).
Arbre
![\"graphe1.png](\"https://sciencesappliquees.com/images/nsi/arbre1.png\")
Un arbre peut être naturellement vu comme un graphe où chaque nœud constitue un sommet et est relié aux racines de ses sons-arbres, le cas échéant. On peut le voir au choix comme un graphe non orienté ou comme un graphe orienté, deux solutions étant alors envisageables (arcs dirigés «vers le haut» ou «vers le bas»).
Il existe de multiples façons de représenter un graphe en machine, selon la nature du graphe mais aussi selon la nature des opérations et des algorithmes
à effectuer sur ce graphe.
Quelle que soit la représentation, on souhaite proposer des opérations de deux sortes :
- d'une part des opérations de construction de graphes, comme l'obtention d'un graphe vide, l'ajout de sommets ou d'arcs, etc. ;
- d'autre part des opérations de parcours d'un graphe, comme parcourir tous les sommets, tous les arcs, ou encore tous les arcs issus d'un
sommet donné.
À priori, on ne souhaite pas fixer le type des sommets d'un graphe.
Ce pourrait être des entiers, des chaînes de caractères ou encore des objets.
Cependant, nous allons commencer par une représentation où les sommets sont des entiers, avant de proposer une représentation plus souple où les sommets peuvent être d'un type quelconque.
On se focalise pour l'instant sur des graphes orientés et on expliquera, à la fin de cette section, comment représenter des graphes non orientés.
Mettre le résultat ici (code et figure).
Matrice d'adjacence
Dans cette première représentation, les sommets du graphe sont supposés être les entiers 0,1,...,N — 1 pour un certain entier N, qui se trouve donc être le nombre total de sommets.
On peut alors représenter le graphe par une matrice adj de booléens de taille NxN, c'est-à-dire un tableau de N tableaux de booléens de taille N, où le booléen adj[i][j] indique la présence d'un arc entre les sommets i et j.
On appelle cela une matrice d'adjacence.
Pour construire un certain graphe, on peut commencer par construire une telle matrice où tous les booléens sont initialisés à False, par exemple de la manière suivante :
adj = [[False] * N for _ in range(N)]
Ensuite, on peut ajouter des arcs au graphe, en donnant la valeur True à certains éléments de cette matrice.
Ainsi, on peut ajouter un arc entre les
sommets 2 et 7 avec une simple affectation :
adj[2][7] = True
Et ainsi de suite.
Une telle représentation à le mérite d'être relativement simple. En particulier, on peut parcourir tous les sommets du graphe avec une simple boucle:
for s in range(N):
Programme 36 — Graphe représenté par une matrice d'adjacence
class Graphe:
l'un graphe représenté par une matrice d''adjacence, où les sommets sont les entiers 0,1,...,n-1\"\"\"
def __init__(self, n):
self.n=n
self.adj = [(False] * n for _ in range(n)]
def ajouter arc(self, si, 82):
self.adj{sii[s?2] = True
def arc(self, s1, 52):
return self.adj[s1] [s2]
def voisins(self, s):
v =
for i in range(self.n):
if self.adjfs]lil:
v.append(i)
return v
De même, on peut parcourir tous les voisins du sommet s avec une boucle for et un test :
for v in range(N):
if adj[s][v]:
...
Le programme ci-dessous encapsule une telle matrice d'adjacence dans une classe Graphe.
class Graphe1:
\"\"\"un graphe représenté par une matrice d'adjacence,
où les sommets sont les entiers 0,1,...,n-1\"\"\"
def __init__(self, n):
self.n = n
self.adj = [[False] * n for _ in range(n)]
def ajouter_arc(self, s1, s2):
self.adj[s1][s2] = True
def arc(self, s1, s2):
return self.adj[s1][s2]
def voisins(self, s):
v = []
for i in range(self.n):
if self.adj[s][i]:
v.append(i)
return v
def afficher_matrice(self) :
for l in self.adj:
print(l)
Le constructeur de cette classe prend en argument le nombre de sommets et alloue la matrice.
Une méthode ajouter_arc permet d'ajouter un arc au graphe. Ainsi, on peut écrire
g1 = Graphe1(4)
g1.afficher_matrice()
print(\"Ajout des arcs:\")
g1.ajouter_arc(0,1)
g1.ajouter_arc(0,3)
g1.ajouter_arc(1,2)
g1.ajouter_arc(3,1)
print(g1.voisins(0))
print(g1.voisins(1))
g1.afficher_matrice()
pour construire le graphe représenté ci-dessous:
![\"graphe1.png](\"https://sciencesappliquees.com/images/nsi/graphe6.png\")
Une méthode arc permet de tester la présence d'un arc entre deux sommets et une méthode voisins renvoie l'ensemble des voisins d'un sommet donné, sous forme d'un tableau.
Efficacité
La matrice d'adjacence est indéniablement simple à mettre en œuvre, mais elle a néanmoins quelques défauts.
D'une part, elle occupe un espace mémoire proportionnel à N x N. Ainsi, un graphe de mille sommets nécessite une matrice d'un million de booléens, ce qui représente déjà quelques mégaoctets, et ce, même si le graphe contient très peu d'arcs.
D'autre part, parcourir tous les voisins d'un sommet donné exige de parcourir toute une ligne de la matrice, c'est-à-dire N booléens, alors même qu'il peut y avoir très peu de voisins.
Enfin, elle limite les sommets à des entiers, qui plus est consécutifs et d'un nombre connu à l'avance. Dans la section suivante, nous présentons une autre façon de représenter un graphe, qui s'affranchit de tous ces défauts.
Mettre le résultat ici (code et figure).
Dictionnaire d'adjacence
Dans cette nouvelle représentation, un graphe est un dictionnaire, qui associe à chaque sommet l'ensemble de ses voisins. On appelle cela un dictionnaire d'adjacence.
La première conséquence est que les sommets ne sont pas limités à des entiers et qu'il n'est pas nécessaire de les connaître tous a priori.
En effet, il suffit d'ajouter une nouvelle entrée dans le dictionnaire
pour ajouter uu nouveau sommet au graphe.
L'ensemble des sommets du graphe est exactement l'ensemble des clés du dictionnaire.
En particulier, on peut parcourir tous les sommets d'un graphe stocké dans la variable graphe avec la boucle suivante :
for s in graphe:
Les voisins du sommet s sont donnés par l'ensemble graphe[s]. On peut donc les parcourir avec la boucle suivante :
for v in graphe[s]:
La deuxième conséquence de cette nouvelle représentation est que ce parcours est maintenant d'une complexité directement proportionnelle au nombre de voisins de s, indépendamment du nombre total de sommets du graphe.
Le programme ci-dessous encapsule un tel dictionnaire d'adjacence dans une classe Graphe.
Programme — Graphe représenté par un dictionnaire d'adjacence
class Graphe2:
\"\"\"un graphe comme un dictionnaire d'adjacence\"\"\"
def __init__(self):
self.adj = {}
def ajouter_sommet(self, s):
if s not in self.adj:
self.adj[s] = set()
def ajouter_arc(self, s1, s2):
self.ajouter_sommet(s1)
self.ajouter_sommet(s2)
self.adj[s1].add(s2)
def arc(self, s1, s2):
return s2 in self.adj[s1]
def sommets(self):
return list (self.adj)
def voisins(self, s):
return self.adj[s]
Le constructeur de cette classe alloue un dictionnaire vide.
Une méthode ajouter_sommet permet d'ajouter un nouveau sommet et une
méthode ajouter_arc permet d'ajouter un arc.
Ainsi, on peut écrire
g2 = Graphe2()
g2.ajouter_arc(0,1)
g2.ajouter_arc(0,3)
g2.ajouter_arc(1,2)
g2.ajouter_arc(3,1)
print(g2.voisins(0))
print(g2.voisins(1))
pour construire le graphe représenté ci-dessous.
On note que le constructeur ne prend pas d'argument (contrairement à la matrice d'adjacence, où on avait passé le nombre de sommet, 4, en argument).
On note également qu'on n'a pas pris la peine d'ajouter les quatre sommets au graphe, parce que la méthode ajouter_arc le fait déjà.
Mais si un sommet n'est relié à aucun autre, alors il faut le rajouter explicitement au graphe, avec la méthode
aïouter_sommet.
On n'est nas censé annuler la méthode arc aver un sam-met si qui ne serait pas dans le graphe, sans quoi l'accès au dictionnaire adj avec la clé s1 provoquerait l'exception KeyError.
Efficacité
En ce qui concerne le coût des opérations, le dictionnaire d'adjacence est optimal:
ajouter un sommet, ajouter un arc ou tester la présence d'un arc se fait en temps constant (les dictionnaires et les ensembles de Python étant réalisés par des tables de hachage) et parcourir les voisins d'un sommet donné sc fait en un temps proportionnel au nombre de ces voisins.
Le seul intérêt de la matrice d'adjacence peut résider dans l'espace mémoire qu'elle occupe, qui peut être inférieur à celui d'un dictionnaire d'adjacence dans certains cas.
Ainsi, un graphe de 400 sommets qui contient presque tous les arcs possibles occupe dix fois moins d'espace quand il est représenté par une matrice d'adjacence que lorsqu'il est représenté par un dictionnaire d'adjacence. Mais s'il contient au contraire très peu d'arcs, alors c'est le dictionnaire d'adjacence qui occupe moins de mémoire, jusqu'à 13 fois moins.
Ën pratique, on suggère de privilégier le dictionnaire d'adjacence, car il permet des sommets d'un type quelconque, et de ne retenir la matrice d'adjacence que dans le cas extrême d'un graphe dont le dictionnaire d'adjacence ne tiendrait pas en mémoire.
Mettre le résultat ici (code et figure).
Autres représentations
Dans la littérature, on rencontre souvent une autre représentation des graphes, dite de liste d'adjacence, où chaque sommet est associé à une liste ordonnée de ses voisins.
En Python, une telle liste pourrait être réalisée par une liste chaînée ou
encore un tableau.
Cependant, une telle représentation n'offre aucun avantage sur la solution à base d'ensembles que nous avons proposée.
En effet, pour déterminer s'il existe un arc entre les sommets s1 et s2, il faudrait parcourir linéairement la liste des voisins de s1, là où l'ensemble
d'adjacence offre une réponse en temps constant.
De même, on rencontre souvent des représentations des graphes utilisant
non pas un dictionnaire mais un tableau. Cela impose cependant que les sommets soient les entiers 0,1...,N — 1.
Là encore, notre solution utilisant un dictionnaire est meilleure:
elle est plus souple quant à la nature des sommets et fournit des opérations tout aussi efficaces (un dictionnaire, comme un tableau, offre des opérations en temps constant).
On aura compris qu'il y a de multiples façons de représeuter un graphe. Ainsi, on peut imaginer d'autres combinaisons, comme un tableau d'ensembles ou encore un dictionnaire de listes. Dans tous les cas, la représentation est relativement secondaire, dès lors que lon peut accéder à tous les sommets du graphe et à tous les voisins d'un sommet donné d'une façon ou d'une autre.
Représenter un graphe non orienté
La façon la plus simple de représenter un graphe non orienté consiste à le représenter exactement comme un graphe orienté, avec l'une ou l'autre des deux solutions que nous venons de présenter, et d'assurer en permanence l'invariant suivant :
- il y a un arc reliant le sommet u au sommet v si et seulement si il y à un arc reliant le sommet v au sommet u.
Dit autrement, on a systématiquement un double arc, orienté dans les deux sens.
Pour maintenir cet invariant, il suffit que les opérations ajouter_arc et supprimer_arc ajoutent et enlèvent systématiquement la paire d'arcs.
Ainsi, pour une matrice d'adjacence, on modifie la méthode ajouter_arc comme ceci:
self.adj[s1][s2] = True
self.adj[s2][s1] = True
Et pour un dictionnaire d'adjacence, on la modifie comme ceci:
self.ajouter_sommet(si)
self.ajouter_sommet(s2)
self.adj[s1].add(s2)
self.adj[s2].add(s1)
Avec ce choix de représentation des graphes non orientés, les algorithmes de
parcours de graphe que nous étudions à la séquence suivante s'écrivent exactement de la même façon que les graphes soient ou non orientés.
La seule subtilité est éventuellement le décompte des arcs, où l'on peut vouloir diviser par deux le nombre d'arcs obtenu au total.
En modifiant la classe Graphe2 on obtient la classe suivante pour les graphes non orientés:
class Graphe3:
\"\"\"un graphe non orienté comme un dictionnaire d'adjacence\"\"\"
def __init__(self):
self.adj = {}
def ajouter_sommet(self, s):
if s not in self.adj:
self.adj[s] = set()
def ajouter_arc(self, s1, s2):
self.ajouter_sommet(s1)
self.ajouter_sommet(s2)
self.adj[s1].add(s2)
self.adj[s2].add(s1)
def arc(self, s1, s2):
return s2 in self.adj[s1]
def sommets(self):
return list (self.adj)
def voisins(self, s):
return self.adj[s]
Donc le graphe ci-dessous;
est représenté de la manière suivante :
g3 = Graphe3()
g3.ajouter_arc(\"A\",\"B\")
g3.ajouter_arc(\"A\",\"D\")
g3.ajouter_arc(\"B\",\"C\")
g3.ajouter_arc(\"D\",\"C\")
g3.ajouter_arc(\"B\",\"D\")
print(g3.voisins(\"B\"))
Tester le code et conclure.
Mettre le résultat ici (code et figure).
Représenter un graphe infini
Si un graphe est infini, il reste néanmoins possible de le représenter en machine. En effet, beaucoup d'algorithmes ont uniquement besoin d'une fonction voisins qui énumère les voisins d'un sommet donné (sous la forme d'un tableau, d'un ensemble, etc.).
C'est le cas notamment des algorithmes de recherche de chemin que nous détaillons dans la séquence suivante. Ainsi, même si le graphe est infini, il suffit que les voisins d'un sommet donné soient en nombre fini pour que la fonction voisins puisse être réalisée.
Mettre le résultat ici (code et figure).
L'algorithme étudié va colorie un graphe à l'aide d'un algorithme glouton.
Colorier un graphe veut dire associer
une couleur à chacun de ses sommets, de façon à ce que deux sommets reliés par un arc n'aient pas la même couleur.
Colorier un graphe avec un minimum de couleurs est un problème difficile, mais si on accepte l'idée d'utiliser éventuellement plus de couleurs que nécessaire, alors on peut colorier un graphe efficacement.
Le principe d'un coloriage glouton est simple. On parcourt les sommets dans un ordre arbitraire et, pour chaque sommet, on lui attribue la première couleur qui n'est pas utilisée par ses voisins.
Le programme ci-dessous réalise cet algorithme. Il est décomposé en deux fonctions.
La fonction principale, coloriage, reçoit un graphe g en argument et renvoie un couple constituée d'un coloriage et du nombre total de couleurs utilisées.
Le coloriage est représenté par un dictionnaire, couleur, qui associe à tout sommet une couleur.
Une couleur est ici un entier naturel.
La variable n maintient le nombre total de couleurs utilisées.
Pour attribuer une couleur à un sommet, on utilise une seconde fonction, appelée mex (pour minimum exclus), qui reçoit en arguments l'ensemble des voisins du sommet et le coloriage courant couleur.
Cette fonction cherche la plus petite couleur qui n'est pas encore utilisée par les voisins.
Pour cela, elle utilise un tableau dispo qui indique, pour chaque couleur, si elle est encore disponible.
La taille de ce tableau est n+1 où n est le nombre de voisins.
On sera en effet assuré de trouver au moins une couleur disponible parmi les n+1 premiers entiers.
Une première boucle commence par marquer
toutes les couleurs utilisées.
IL faut être soigneux ici, en ne considérant que les sommets déjà coloriés d'une part et uniquement ceux pour lesquels la couleur est inférieure ou égale à n d'autre part, sans quoi on accéderait au tableau dispo en dehors de ses bornes.
Ensuite, une seconde boucle parcourt le tableau dispo à la recherche d'une couleur disponible. Il y en a forcément une et par conséquent la toute dernière ligne de la fonction est inatteignable, ce que l'on manifeste avec l'instruction assert False.
On pourrait se contenter de ne rien faire, mais une programmation défensive est une bonne pratique.
Cet algorithme est efficace, car il parcourt chaque sommet une seule fois et, pour chaque sommet, il parcourt l'ensemble de ses voisins une seule fois.
Dit autrement, le temps de calcul de cet algorithme est directement proportionnel à la taille du graphe, c'est-à-dire à la somme du nombre de ses sommets et de ses arcs.
Programme — Coloriage glouton d'un graphe
def mex(voisins, couleur):
\"\"\"la plus petite couleur non utilisée par les voisins\"\"\"
n = len(voisins)
dispo = [True] * (n + 1)
for v in voisins:
if v in couleur and couleur[v] <= n:
dispo[couleur[v]] = False
for c in range(n + 1):
if dispo[c]:
return c
assert False # on n'arrivera jamais ici
def coloriage(g):
\"\"\"colorie graphe g avec un algorithme glouton\"\"\"
couleur = {}
n = 0
for s in g.sommets():
c = mex(g.voisins(s), couleur)
couleur[s] = c
n = max(n, c + 1)
return couleur, n
On ne peut pas faire mieux, car il faut examiner tout sommet pour lui donner une couleur et il faut examiner tout arc pour prendre en compte toutes les contraintes.
Créons le graphe des régions:
regions = Graphe3() #non orienté
regions.ajouter_sommet(\"Guadeloupe\")
regions.ajouter_sommet(\"Martinique\")
regions.ajouter_sommet(\"Guyane\")
regions.ajouter_sommet(\"Corse\")
regions.ajouter_sommet(\"Mayotte\")
regions.ajouter_sommet(\"La Reunion\")
regions.ajouter_arc(\"Hauts-de-France\",\"Normandie\")
regions.ajouter_arc(\"Hauts-de-France\",\"Ile-de-France\")
regions.ajouter_arc(\"Hauts-de-France\",\"Grand Est\")
regions.ajouter_arc(\"Ile-de-France\",\"Grand Est\")
regions.ajouter_arc(\"Ile-de-France\",\"Hauts-de-France\")
regions.ajouter_arc(\"Pays de la Loire\",\"Bretagne\")
regions.ajouter_arc(\"Normandie\",\"Bretagne\")
regions.ajouter_arc(\"Normandie\",\"Pays de la Loire\")
regions.ajouter_arc(\"Pays de la Loire\",\"Centre-Val de Loire\")
regions.ajouter_arc(\"Centre-Val de Loire\",\"Normandie\")
regions.ajouter_arc(\"Pays de la Loire\",\"Nouvelie-Aquitaine\")
regions.ajouter_arc(\"Nouvelie-Aquitaine\",\"Centre-Val de Loire\")
regions.ajouter_arc(\"Ile-de-France\",\"Centre-Val de Loire\")
regions.ajouter_arc(\"Bourgogne-Franche Comte\",\"Centre-Val de Loire\")
regions.ajouter_arc(\"Bourgogne-Franche Comte\",\"Grand Est\")
regions.ajouter_arc(\"Auvergne-Rhone-Alpes\",\"Centre-Val de Loire\")
regions.ajouter_arc(\"Auvergne-Rhone-Alpes\",\"Bourgogne-Franche Comte\")
regions.ajouter_arc(\"Ile-de-France\",\"Bourgogne-Franche Comte\")
regions.ajouter_arc(\"Ile-de-France\",\"Normandie\")
regions.ajouter_arc(\"Auvergne-Rhone-Alpes\",\"Occitanie\")
regions.ajouter_arc(\"Auvergne-Rhone-Alpes\",\"Provence-Alpes-Cote d'Azur\")
regions.ajouter_arc(\"Occitanie\",\"Provence-Alpes-Cote d'Azur\")
regions.ajouter_arc(\"Occitanie\",\"Nouvelie-Aquitaine\")
regions.ajouter_arc(\"Auvergne-Rhone-Alpes\",\"Nouvelie-Aquitaine\")
print(\"Voisins Bretagne\",regions.voisins(\"Bretagne\"))
print(\"Voisins Ile-de-France\",regions.voisins(\"Ile-de-France\"))
Faisons tourner cet algorithme sur le graphe des régions.
print(coloriage(regions))
Tester et mettre le résultat ci-dessous.
On obtient combien de couleurs pour le graphe. Ceci correspond-il au théorème des quatres couleurs?
Avec notre algorithme glouton, au moment d'affecter une couleur à la Normandie, ses cinq voisins utilisaient déjà quatre couleurs différentes.
D'une manière plus générale, le coloriage obtenu dépend de l'ordre dans lequel les sommets ont été parcourus, qui est ici fixé par ce que nous donne la méthode sommets.
Comme on le voit, le programme est indépendant de la façon dont le graphe est représenté.
Il a uniquement besoin des deux méthodes sommets et voisins. On peut en particulier l'utiliser sans changement avec les deux représentations étudiées dans la section précédente.
Mais on pourrait également l'utiliser avec d'autres représentations encore, dès lors que ces deux méthodes sont fournies. C'est là une application du principe de modularité.
Mettre le résultat ici (code et figure).
Un graphe est un ensemble de sommets reliés entre eux par des arcs.
Un graphe peut être orienté ou non orienté, selon que les arcs sont ou non considérés comme symétriques.
Un graphe peut être représenté en machine par une matrice d'adjacence ou par un
dictionnaire d'adjacence.
Exercice 93 Dessiner tous les graphes non orientés ayant exactement trois sommets. Solution page 469 D
Mettre le résultat ici (code et figure).
Il y en a 8 au total :
![\"graphe1.png](\"https://sciencesappliquees.com/images/nsi/graphe7.png\")
Exercice 94 Combien y a-t-il de graphes orientés ayant exactement trois sommets ?
On ne demande pas de les dessiner tous, mais seulement de les dénombrer.
","title":"Exercice"},{"edit":"Mettre le résultat ici (code et figure).
Il y a six arcs possibles (0—>1, 1—>0, 1—>2, 2—>1,2—>0, 0—>2), chacun pouvant être présent ou absent, soit 26=64 possibilités au total.
![\"graphe1.png](\"https://sciencesappliquees.com/images/nsi/graphe8.png\")
class Graphe1:
\"\"\"un graphe représenté par une matrice d'adjacence,
où les sommets sont les entiers 0,1,...,n-1\"\"\"
def __init__(self, n):
self.n = n
self.adj = [[False] * n for _ in range(n)]
def ajouter_arc(self, s1, s2):
self.adj[s1][s2] = True
def arc(self, s1, s2):
return self.adj[s1][s2]
def voisins(self, s):
v = []
for i in range(self.n):
if self.adj[s][i]:
v.append(i)
return v
Ajouter à cette classe Graphe (matrice d'adjacence) une méthode afficher pour afficher le graphe sous la forme suivante :
0 -> 1 3
1 -> 2
2 -> 3
3 -> 1
c'est-à-dire une ligne par sommet, avec pour chacun la liste de ses voisins.
Tester avec:
g1 = Graphe1(4)
g1.ajouter_arc(0,1)
g1.ajouter_arc(0,3)
g1.ajouter_arc(1,2)
g1.ajouter_arc(2,3)
g1.ajouter_arc(3,1)
g1.afficher()
Mettre le résultat ici (code et figure).
def afficher(self) :
for s in range(self.n):
print(s, \"->\", end=\"\")
for v in range(self.n):
if self.adj[s][v]:
print(\"\", v, end=\"\")
print()
class Graphe2:
\"\"\"un graphe comme un dictionnaire d'adjacence\"\"\"
def __init__(self):
self.adj = {}
def ajouter_sommet(self, s):
if s not in self.adj:
self.adj[s] = set()
def ajouter_arc(self, s1, s2):
self.ajouter_sommet(s1)
self.ajouter_sommet(s2)
self.adj[s1].add(s2)
def arc(self, s1, s2):
return s2 in self.adj[s1]
def sommets(self):
return list (self.adj)
def voisins(self, s):
return self.adj[s]
Ajouter à la classe Graphe (dictionnaire d'adjacence) une méthode afficher pour afficher le graphe sous la forme suivante:
0 {1, 3}
1 {2}
3 {1}
2 {3}
c'est-à-dire une ligne par sommet, avec pour chacun l'ensemble de ses voisins.
L'ordre des sommets n'est pas important. L'ensemble des voisins peut être affiché directement avec print.
Tester avec :
g2 = Graphe2()
g2.ajouter_arc(0,1)
g2.ajouter_arc(0,3)
g2.ajouter_arc(1,2)
g2.ajouter_arc(2,3)
g2.ajouter_arc(3,1)
g2.afficher()
Mettre le résultat ici (code et figure).
On fait un cas particulier pour ’ensemble vide, histoire qu’il ne soit pas affiché comme set() mais comme {}.
def afficher(self):
for s in self.adj:
if len(self.adj[s]) == 0:
print(s, \"{}\")
else:
print(s, self.adj[s])
Ajouter à la classe Graphe2 une méthode
nb_sommets() qui donne le nombre de sommets du graphe.
Tester avec :
g2 = Graphe2()
g2.ajouter_arc(0,1)
g2.ajouter_arc(0,3)
g2.ajouter_arc(1,2)
g2.ajouter_arc(2,3)
g2.ajouter_arc(3,1)
print(g2.nb_sommets())
Résultat:
4
Mettre le résultat ici (code et figure).
Le nombre de sommets est égal au nombre d’entrées
dans le dictionnaire :
def nb_sommets(self):
return len(self.adj)
Ajouter à la classe Graphe1 une méthode
degre(s) qui donne le nombre d'arcs issus du sommet s.
On appelle cela le degré du sommet s.
Tester avec:
g1 = Graphe1(4)
g1.ajouter_arc(0,1)
g1.ajouter_arc(0,3)
g1.ajouter_arc(1,2)
g1.ajouter_arc(2,3)
g1.ajouter_arc(3,1)
print(g1.degre(0))
Résultat:
2
Mettre le résultat ici (code et figure).
Le code est très semblable à celui de la méthode voisins:
def degre(self, s):
d=0
for i in range(self.n):
if self.adj[s][i]:
d += 1
return d
En utilisant l'exercice précédent, ajouter à la classe Graphe1 une méthode nb_arcs() qui donne le nombre total d'arcs du graphe.
Tester avec:
g1 = Graphe1(4)
g1.ajouter_arc(0,1)
g1.ajouter_arc(0,3)
g1.ajouter_arc(1,2)
g1.ajouter_arc(2,3)
g1.ajouter_arc(3,1)
print(g1.nb_arcs())
Résultat:
5
Mettre le résultat ici (code et figure).
Il suffit de faire la somme de tous les degrés.
def nb_arcs(self):
n=0
for s in range(self.n):
n += self.degre(s)
return n
Ajouter à la classe Graphe2 une méthode degre(s) qui donne le nombre d'arcs issus du sommet s.
On appelle cela le degré du sommet s.
Tester avec:
g2 = Graphe2()
g2.ajouter_arc(0,1)
g2.ajouter_arc(0,3)
g2.ajouter_arc(1,2)
g2.ajouter_arc(2,3)
g2.ajouter_arc(3,1)
print(g2.degre(0))
Résultat :
2
Mettre le résultat ici (code et figure).
C’est exactement le cardinal de l’ensemble adj [s] :
def degre(self, s):
return len(self.adj[s])
En utilisant l'exercice précédent, ajouter à la classe Graphe2 une méthode nb_arcs() qui donne le nombre total d'arcs du graphe.
Tester avec:
g2 = Graphe2()
g2.ajouter_arc(0,1)
g2.ajouter_arc(0,3)
g2.ajouter_arc(1,2)
g2.ajouter_arc(2,3)
g2.ajouter_arc(3,1)
print(g2.nb_arcs())
Résultat:
5
Mettre le résultat ici (code et figure).
Comme dans l'exercice 99, on fait la somme de tous
les degrés.
def nb_arcs(self):
n=0
for s in self.adj:
n += self.degre(s)
return n
Ajouter à la classes Graphe1 une méthode supprimer_arc(s1,s2) pour supprimer l'arc entre les sommets s1 et s2.
S'il n'y a pas d'arc entre ces sommets, la méthode n'a aucun effet.
Tester avec:
g1.ajouter_arc(0,1)
g1.ajouter_arc(0,3)
g1.ajouter_arc(1,2)
g1.ajouter_arc(2,3)
g1.ajouter_arc(3,1)
g1.afficher()
print(\"Suprime arc 1->2\")
g1.supprimer_arc(1,2)
g1.afficher()
Résultat:
0 -> 1 3
1 -> 2
2 -> 3
3 -> 1
Suprime arc 1->2
0 -> 1 3
1 ->
2 -> 3
3 -> 1
Mettre le résultat ici (code et figure).
Pour la matrice d’adjacence, on affecte le booléen à False dans la matrice:
def supprimer_arc(self,s1,s2):
self.adj[s1][s2] = False
Ajouter à la classes Graphe2 une méthode supprimer_arc(s1,s2) pour supprimer l'arc entre les sommets s1 et s2.
S'il n'y a pas d'arc entre ces sommets, la méthode n'a aucun effet.
On supprime un élément d'un ensemble avec sa méthode remove.
Tester avec:
g2 = Graphe2()
g2.ajouter_arc(0,1)
g2.ajouter_arc(0,3)
g2.ajouter_arc(1,2)
g2.ajouter_arc(2,3)
g2.ajouter_arc(3,1)
g2.afficher()
print(\"Suprime arc 1->2\")
g2.supprimer_arc(1,2)
g2.afficher()
Résultat:
0 {1, 3}
1 {2}
3 {1}
2 {3}
Suprime arc 1->2
0 {1, 3}
1 {}
3 {1}
2 {3}
Mettre le résultat ici (code et figure).
Pour le dictionnaire d’adjacence, on supprime s2 de l’ensemble des voisins
de s1:
def supprimer_arc(self, s1, s2):
self.adj[s1].remove(s2)