Actualité

[[{"text":"

On a coutume de dire que pour sortir d'un labyrinthe il suffit de toujours suivre le mur situé sur notre droite.

En particulier, on emprunte ainsi toujours la première porte que l'on rencontre sur notre droite et, si on arrive à un cul de sac, cela a pour effet de nous faire faire un demi-tour.

Ceux qui ont un peu réfléchi à cette idée, voire qui ont essayé de la mettre

en pratique, savent plusieurs choses.

D'une part, cette méthode peut échouer

dans certains cas, où on se retrouve à « tourner en rond » autour d'un bloc.

Pour y remédier, ü suffit de marquer au sol les endroits par lesquels on est déjà passé.

Dès lors, quand on revient sur un embranchement qui est marqué, on procède comme s'il s'agissait d'un cul de sac.

D'autre part, on peut tout aussi bien suivre le mur sur la gauche plutôt que sur la droite.

On peut même changer d'avis à chaque nouvelle salle et emprunter à sa guise

n'importe laquelle des portes qui la quittent.

Ces deux idées combinées, à savoir emprunter les embranchernents de façon arbitraire et marquer les endroits par lesquels on est déjà passé, constituent un algorithme fondamental appelé parcours en profondeur. Il s'applique à n'importe quel graphe et permet de déterminer tous les sommets

$\"graphe10.png$

sommet
visité

action

..C

...E

....B

...E

..C

...F

..C

..E

marquer A, emprunter arc A—>B

marquer B, emprunter arc B—>C

marquer C, emprunter arc C—>E

marquer E, emprunter arc E—>B

déjà vu, terminé

pas d'autre arc, terminé

emprunter arc C—>F

marquer F, aucun arc, terminé

pas d'autre arc, terminé

emprunter arc A—>D

marquer D, emprunter arc D—>E

déjà vu, terminé

pas d'autre arc, terminé

Figure 1 — Parcours en profondeur, à partir du sommet A.

","title":"S.D. : Parcours en profondeur et en largeur un graphe","tagtitle":"h1"},{"edit":"

"}],[{"text":"

Avant de programmer le parcours en profondeur en Python, illustrons

son fonctionnement en détail sur un exemple. La figure 1 détaille les

différentes étapes du parcours en profondeur du graphe à partir du sommet A.

$\"graphe10.png$

La première chose que l'on fait est de marquer le sommet A comme déjà vu. En effet, il pourrait y avoir un cycle qui nous ramènerait sur le sommet A (ce n'est pas le cas ici, mais on ne peut pas le

savoir a priori) et avoir marqué le sommet A nous permettra d'interrompre

le parcours et de revenir en arrière.

On considère ensuite les arcs sortants du

sommet A. Il y en a deux, à savoir A—>B et A—>D. Comme on l'a expliqué dans l'introduction, on choisit de façon arbitraire un arc à considérer en premier.

Choisissons par exemple d'emprunter l'arc A—>B. On se retrouve donc maintenant à visiter le sommet B. On commence par le marquer puis on examine ses arcs.

Ici, il n'y en a qu'un seul, à savoir B—>C. On l'emprunte donc et on se retrouve à visiter le sommet C, que l'on commence par marquer.

Il y a 2 arcs sortants du sommet C et là encore on choisit arbitrairement celui qui est considéré en premier.

Ici, on choisit l'arc C—>E, ce qui nous

conduit à marquer E puis à considérer l'unique arc E—>B issu de E.

On se retrouve alors dans une situation nouvelle, où pour la première fois on retombe sur un sommet déjà marqué, à savoir B. On revient donc en arrière, pour se retrouver sur le sommet E.

Comme il n'y avait pas d'autre arc issu

de E, on revient une fois de plus en arrière, pour se retrouver sur le sommet C.

Là, on avait considéré l'arc C—>E mais il y a également l'arc C—>F, que l'on emprunte donc maintenant.

On visite donc le sommet F, que l'on marque.

Comme il n'y a aucun arc sortant du sommet F, on a terminé et on revient

au sommet C.

Cette fois, tous les arcs issus de C ont été examinés, et on a donc terminé la visite de C.

On revient donc au sommet B, donc la visite est également terminée.

On revient donc au sommet A.

Là, il y avait encore l'arc A->D à considérer.

On visite donc le sommet D, que l'on marque avant de considérer l'arc D—>E.

On retombe alors sur le sommet E, déjà visité.

On revient donc en arrière, sur le sommet D, puis encore en arrière, sur le sommet A.

Là, il n'y a plus d'arc à considérer et la visite de A est terminée, ce qui achève notre parcours en profondeur.

Une fois le parcours terminé, tous les sommets atteignables à partir de A

ont été marqués, à savoir A, B, C, D,E et F.

Inversement, le sommet G, qui n'est pas atteignable à partir de A, n'a pas été marqué. C'est là une propriété fondamentale du parcours en profondeur.

Venons-en à la programmation du parcours en profondeur. Le code, ci-dessous repose sur deux ingrédients. Le premier est l'utilisation d'un ensemble pour le marquage des sommets, que l'on appelle vus. Le second ingrédient est l'utilisation d'une fonction récursive pour réaliser le parcours proprement dit.

Cette fonction appelée parcours reçoit en arguments le graphe g, l'ensemble vus et un sommet s à partir duquel réaliser le parcours.

En quatre lignes seulement, elle s'écrit comme elle s'énonce :

«si le sommet s n'est pas dans vus, l'y ajouter et parcourir récursivement tous ses voisins».

Programme — Parcours en profondeur

def parcours(g, vus, s):

\"\"\"parcours en profondeur depuis le sommet s\"\"\"

if s not in vus:

vus.add(s)

for v in g.voisins(s):

parcours(g, vus, v)

def existe_chemin(g, u, v):

\"\"\"existe-t-il un chemin de u à v?\"\"\"

vus = set()

parcours(g, vus, u)

return v in vus

Tester le programme existe_chemin sur le graphe suivant:

$\"graphe10.png$

#réalisation du graphe

g2 = Graphe2()

g2.ajouter_arc(\"A\",\"B\")

g2.ajouter_arc(\"B\",\"C\")

g2.ajouter_arc(\"A\",\"D\")

g2.ajouter_arc(\"D\",\"E\")

g2.ajouter_arc(\"E\",\"B\")

g2.ajouter_arc(\"C\",\"E\")

g2.ajouter_arc(\"C\",\"F\")

g2.ajouter_arc(\"G\",\"C\")

g2.afficher()

#Test si il existe un chemin

print(\"A->F?\",existe_chemin(g2,\"A\",\"F\"))

print(\"A->G?\",existe_chemin(g2,\"A\",\"G\"))

print(\"D->F?\",existe_chemin(g2,\"D\",\"F\"))

","title":"Parcours en profondeur","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Déterminer l'existence d'un chemin entre deux sommets

Une application immédiate du parcours en profondeur consiste à déterminer s'il existe un chemin entre deux sommets u et v. En effet, il suffit de lancer un parcours en profondeur à partir du sommet u puis, une fois qu'il est terminé, de regarder si le sommet v fait partie de l'ensemble des sommets marqués.

Le progrannne contient une fonction existe_chemin qui réalise cette idée.

Elle crée un nouvel ensemble vus, appelle la fonction parcours à partir du sommet u puis vérifie enfin si le sommet v à été visité pendant le parcours.

Bien entendu, on pourrait interrompre le parcours en profondeur dès que le sommet v est atteint. Mais il faudrait modifier pour cela la fonction parcours.

","title":""},{"edit":"

"}],[{"text":"

Construire le chemin

Si on veut construire le chemin, il faut se fatiguer un peu plus.

Au lieu d'un ensemble vus, on prend un dictionnaire, qui associe à chaque sommet le sommet qui à permis de l'atteindre (la

première fois) pendant le parcours en profondeur.

Pour le sommet de départ u, on lui associe None dans ce dictionnaire.

Une fois le parcours en profondeur terminé, on ne se contente pas de regarder si le sommet d'arrivée v est dans vus, mais on «remonte» le dictionnaire, en partant de v, jusqu'à arriver à u.

Vous réaliserez ce programme dans les exercices.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Utilisation

Illustrons l'utilisation de notre parcours en profondeur sur le graphe des régions de la figure ci-dessous:

On a la variable regions qui contient une représentation de ce graphe.

******

On peut tester la présence de chemins, par exemple comme ceci :

assert existe_chemin(regions, \"Bretagne\", \"Occitanie\")

assert not existe_chemin(regions, \"Bretagne\", \"Mayotte\")

Ici, où vérifie l'existence d'un chemin entre la région Bretagne et la région

Occitanie et l'absence d'un chemin entre la région Bretagne et la région Mayotte.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Efficacité

Le parcours en profondeur est un algorithme très efficace, dont

******

pendant ce parcours.

En effet, l'arc u—>v est examiné au plus une fois, à savoir la première fois que la fonction parcours est appelée sur le sommet u.

En effet, si la fonction parcours est rappelée plus tard sur ce même sommet u, alors il sera trouvé dans l'ensemble vus et la fonction se terminera immédiatement, sans rien faire.

Dans le pire des cas, tous les sommets sont atteignables et tout le graphe est donc parcouru.

Le coût est moindre lorsque certains sommets ne sont pas atteignables depuis le sommet de départ.

Le coût en mémoire est celui de l'ensemble vus, qui contient au final tous les sommets atteignables.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Limites de la récursion

La fonction parcours étant récursive, il y a un risque de provoquer RecursionError si le graphe contient beaucoup de sommets.

Ainsi, un parcours en profondeur à partir du sommet 1 sur le graphe

1 -> 2 ... <> 2000

va provoquer cette erreur, car on va dépasser le nombre maximal d'appels récursifs imbriqués (1000 par défaut).

Comme expliqué dans la séquence sur les fonctions récursives, on peut modifier cette limite avec la fonction setrecursionlimit.

Une autre solution consiste à réécrire la fonction parcours avec une boucle while.

Pour cela, on utilise une pile dans laquelle on stocke les sommets qu'il faut parcourir.

Le programme ci-dessous donne le code de cette nouvelle fonction parcours.

On n'a pas besoin de savoir ici comment la pile est réalisée.

C'est un exemple de modularité. La fonction existe_chemin reste inchangée.

Programme — Parcours en profondeur avec une pile

from modPile import *

def parcours2(g, vus, s):

\"\"\"parcours en profondeur depuis le sommet s\"\"\"

pile = Pile()

pile.empiler(s)

while not pile.est_vide():

s = pile.depiler()

if s in vus:

continue

vus.add(s)

for v in g.voisins(s):

pile.empiler(v)

def existe_chemin2(g, u, v):

\"\"\"existe-t-il un chemin de u à v?\"\"\"

vus = set()

parcours2(g, vus, u)

return v in vus

Tester avec :

g2 = Graphe2()

g2.ajouter_arc(\"A\",\"B\")

g2.ajouter_arc(\"B\",\"C\")

g2.ajouter_arc(\"A\",\"D\")

g2.ajouter_arc(\"D\",\"E\")

g2.ajouter_arc(\"E\",\"B\")

g2.ajouter_arc(\"C\",\"E\")

g2.ajouter_arc(\"C\",\"F\")

g2.ajouter_arc(\"G\",\"C\")

g2.afficher()

print(\"A->F?\",existe_chemin2(g2,\"A\",\"F\"))

print(\"A->G?\",existe_chemin2(g2,\"A\",\"G\"))

print(\"D->F?\",existe_chemin2(g2,\"D\",\"F\"))

Conclure sur k'avantage de l'utilisation d'une pile par rapport à une fonction récursive.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Le parcours en profondeur permet également de détecter la présence d'un

cycle dans un graphe orienté.

En effet, puisque l'on marque les sommets

avant de considérer leurs voisins, pour justement éviter de tourner en rond dans un cycle, alors on doit pouvoir être à même de détecter la présence d'un cycle.

Il y a cependant une petite subtilité, car lorsqu'on retombe sur un sommet déjà marqué, on ne sait pas pour autant si on vient de découvrir un cycle.

Considérons par exemple le parcours en profondeur des deux graphes suivants, à partir du sommet A à chaque fois:

Dans le graphe de gauche, on retombe sur le sommet C.

Il n'y a pas de cycle pour autant, mais seulement un chemin parallèle.

Dans le graphe de droite, on retombe sur le sommet B, cette fois à cause d'un cycle.

Tel qu'il est écrit, notre parcours en profondeur ne nous permet pas de distinguer ces deux situations.

Dans les deux cas, on constate que le sommet est déjà dans l'ensemble vus, sans pouvoir en tirer de conclusion quant à l'existence d'un cycle.

Pour y remédier, on va distinguer dans l'ensemble vus deux sortes de sommets:

ceux pour lesquels le parcours en profondeur n'est pas encore terminé et ceux pour lesquels il est au contraire terminé.

On pourrait utiliser pour cela deux ensembles, ou encore un dictionnaire qui associe à chaque sommet déjà rencontré un booléen indiquant si son parcours en profondeur est terminé.

Mais traditionnellement on utilise un marquage à trois couleurs:

- on marque en blane les sommets non encore atteints par le parcours en profondeur,

- en gris les sommets déjà atteints dont le parcours en profondeur est en cours

- et enfin en noir les sommets atteints dont le parcours est terminé.

Dans l'exemple de gauche ci-dessus, le sommet C sera colorié en noir quand on retombera dessus la deuxième fois.

Dans l'exemple de droite, en revanche, il sera encore gris quand on retombera dessus et on en déduira la présence d'un cycle.

Nous adoptons ici cette solution utilisant trois couleurs.

Le parcours en profondeur est modifié de la façon suivante.

Lorsque l'on visite un sommet s, on procède ainsi :

s'il est gris, c'est qu'on vient de découvrir un cycle;
s'il est noir, on ne fait rien;
sinon, c'est qu'il est blanc, et on procède ainsi:

on colore le sommet s en gris;
on visite tous ses voisins, récursivement;
enfin, on colore le sommet s en noir.

Comme on le voit, les voisins du sommet s sont examinés après le moment où s est colorié en gris et avant le moment où s est colorié en noir.

Ainsi, s'il existe un cycle nous ramenant sur s, on le trouvera comme étant gris et

le cycle sera signalé.

Le programme ci-dessous contient une fonction cycle qui réalise cette détection de cycle. Il s'agit 1à d'une modification du parcours en profondeur où un dictionnaire couleur remplace l'ensemble vus.

Programme — Détecter la présence d'un cycle dans un graphe

BLANC, GRIS, NOIR = 1, 2, 3

def parcours_cy(g, couleur, s):

\"\"\"parcours en profondeur depuis le sommet s\"\"\"

if couleur[s] == GRIS:

return True

if couleur[s] == NOIR:

return False

couleur[s] = GRIS

for v in g.voisins(s):

if parcours_cy(g, couleur, v):

return True

couleur[s] = NOIR

return False

def cycle(g):

couleur = {}

for s in g.sommets():

couleur[s] = BLANC

for s in g.sommets():

if parcours_cy(g, couleur, s):

return True

return False

La fonction parcours est toujours une fonction récursive, mais elle renvoie désormais un résultat, à savoir un booléen indiquant la présence d'un cycle.

Enfin, la fonction cycle colorie tous les sommets en blanc puis lance un parcours en profondeur à partir de tous les sommets du graphe.

Si l'un de ces parcours renvoie True, on transmet re résultat. Sinon. on renvoie False.

Dans cette version, on cherche à détecter la présence d'un cycle n'importe où dans le graphe. C'est pourquoi on lance un parcours en profondeur à partir de tous les sommets du graphe,

Pour beauconp de ces sommets, le parcours est passé par là, car ils étaient accessibles depuis des sommets déjà parcourus, et la fonction parcours se termine immédiatement sans rien faire.

Le temps total passé dans la détection de cycle reste proportionnel à la taille du graphe. Si on lance un parcours en profondeur à partir d'un seul sommet s, alors on détecte uniquement la présence d'un cycle atteignable à partir de s.

Tester avec les graphes suivants:

g1 = Graphe2()

g1.ajouter_arc(\"A\",\"B\")

g1.ajouter_arc(\"B\",\"C\")

g1.ajouter_arc(\"A\",\"D\")

g1.ajouter_arc(\"D\",\"C\")

g1.afficher()

print(cycle(g1))

g2 = Graphe2()

g2.ajouter_arc(\"A\",\"B\")

g2.ajouter_arc(\"B\",\"C\")

g2.ajouter_arc(\"D\",\"B\")

g2.ajouter_arc(\"C\",\"D\")

g2.afficher()

print(cycle(g2))

Conclure sur les résultats donnés par la fonction cycle.

","title":"Détecter la présence d'un cycle dans un graphe orienté"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Le parcours en profondeur nous permet de déterminer l'existence d'un chemin entre deux sommets, et même d'en construire un, mais il ne détermine pas pour autant la distance entre deux sommets, c'est-à-dire la longueur minimale d'un chemin entre ces deux sommets.

Si on considère par exemple le graphe des régions et que l'on cherche un chemin entre la région Bretagne et la région Grand Est avec notre parcours en profondeur, alors on trouve le chemin suivant :

Bretagne—>Normandie—>Hauts-de-France—>Île-de-France—>Bourgogne-Franche-Comté —> Grand Est

Ce chemin à la longueur 5, alors qu'il existe un chemin de longueur 3, à savoir

Bretagne—>Normandie—>Île-de-France—>Grand Est

Le fait est que le parcours en profondeur détermine un chemin arbitraire parmi tous les chemins possibles (sans répétitions), car il emprunte les arcs dans un ordre arbitraire.

Si on veut en revanche déterminer la distance entre deux sommets, c'est-à-dire un plus court chemin entre ces deux sommets, alors il faut utiliser un autre algorithme, à savoir le parcours en largeur.

Comme pour le parcours en profondeur, on se donne un sommet de départ, pour initier le parcours. On l'appelle la source.

Et comme pour le parcours en profondeur, on va déterminer peu à peu tous les sommets atteignables à partir de ce sommet de départ.

Ce qui diffère, c'est l'ordre dans lequel ces sommets vont être visités.

Dans le parcours en largeur, on explore le graphe «en cercles concentriques» à partir de la source, c'est-à-dire qu'on visite d'abord tous les sommets à distance 1 de la source, puis tous les sommets à distance 2 de la source, et ainsi de suite, jusqu'à ce que tous les sommets atteignables depuis la source aient été visités.

","title":"Parcours en largeur"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

$\"graphe10.png$

Si on reprend l'exemple du graphe ci-dessus et qu'on effectue un parcours en largeur à partir du sommet A,

alors on va examiner d'abord les sommets B et D, situés à distance 1 de A,
puis les sommets C et E, situés à distance 2,
puis enfin le sommet F, situé à distance 3.

Comme pour le parcours en profondeur, le sommet G n'est pas visité, car il n'est pas atteignable depuis A.

Pour mettre en œuvre le parcours en largeur, et l'idée de cercles concentriques, on peut se servir de deux ensembles.

Le premier, appelé courant, contient des sommets situés à distance d de la source.

C'est notamment dans cet ensemble qu'on pioche le prochain sommet à examiner.

Le second ensemble, appelé suivant, contient des sommets situés à distance d de la source, que l'on examinera après ceux de l'ensemble courant.

À côté de ces deux ensembles, on utilise également un dictionnaire, appelé dist, qui associe à chaque sommet déjà atteint sa distance à la source.

Le parcours en largeur procède ainsi :

initialement, la source est placée dans l'ensemble courant et sa distance est fixée à D:
tant que l'ensemble courant n'est pas vide,
(a) on en retire un sommets,

(b) pour chaque voisin v de s qui n'est pas encore dans dist

* on ajoute v à l'ensemble suivant,

* on fixe dist[v] à dist[s]+1

suivant.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

La figure 2 détaille les différentes étapes de cet algorithme sur l'exemple

du graphe

$\"graphe10.png$

en partant du sommet A. La figure illustre le contenu des deux ensembles, ainsi que les différentes affectations effectuées dans le dictionnaire dist.

courant	suivant	action
A		initialisation, dist[A]=0
	B,D	on retire le sommet A, dist\|B]=1. dist[D]=1
B,D		l'ensemble suivant est vide => échange
D	C	on retire le sommet B, dist\|C]=2
	C,E	on retire le sommet D, dist[E]=2
C,E		l'ensemble suivant est vide => échange
E		on retire le sommet C, dist[F]=3
F		on retire le sommet E
		on retire le sommet F terminé

Figure 2 — Parcours en largeur, à partir du sommet A.

On prendra le temps de bien comprendre cet algorithme.

Le programme ci-dessous réalise cet algorithme en Python. La fonction parcours_largeur réalise un parcours en largeur en partant du sommet

source, à l'aide d'une boucle while.

Programme — Parcours en largeur

def parcours_largeur(g, source):

\"\"\"parcours en largeur depuis le sommet source\"\"\"

dist = {source: 0}

courant = {source}

suivant = set()

while len(courant) > 0:

s = courant.pop()

for v in g.voisins(s):

if v not in dist:

suivant.add(v)

dist[v] = dist[s] + 1

if len(courant) == 0:

courant, suivant = suivant, set()

return dist

def distance(g, u, v):

\"\"\"distance de u à v (et None si pas de chemin)\"\"\"

dist = parcours_largeur(g, u)

return dist[v] if v in dist else None

Les deux ensembles courant et suivant sont des variables locales à la fonction parcours. Une fois le parcours terminé, la fonction parcours renvoie le dictionnaire dist.

Une seconde fonction distance renvoie la distance entre deux sommets u et v, en lançant un parcours en largeur à partir de u puis en consultant la valeur de dist[v].

Si v n'a pas été atteint, on renvoie None.

Tester le programme avec les instructions suivantes :

g2 = Graphe2()

g2.ajouter_arc(\"A\",\"B\")

g2.ajouter_arc(\"B\",\"C\")

g2.ajouter_arc(\"A\",\"D\")

g2.ajouter_arc(\"D\",\"E\")

g2.ajouter_arc(\"E\",\"B\")

g2.ajouter_arc(\"C\",\"E\")

g2.ajouter_arc(\"C\",\"F\")

g2.ajouter_arc(\"G\",\"C\")

g2.afficher()

print(\"distance A F\",distance(g2,\"A\",\"F\"))

print(\"distance A F\",distance(g2,\"A\",\"G\"))

justifier les résultats.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Une file, pour quoi faire une file?

$\"pile_file1.png$

Le parcours en largeur est traditionnellement réalisé avec une file, dans laquelle on ajoute à la fin les nouveaux sommets (ceux que notre code met dans l'ensemble suivant) et dans laquelle on retire au début le prochain sommet à examiner (celui que notre code retire de l'ensemble courant).

Dans cette file, des sommets à la distance d de la source précède des sommets à distance d + 1, ce que l'on peut visualiser ainsi :

L'ordre des sommets situés à une même distance de la source important peu, notre solution avec deux ensembles convient tout aussi bien. Mais surtout, elle explicite la raison pour laquelle notre parcours en largeur est correct, ce que ne montre absolument pas la file.

En terme d'efficacité, il n'y à absolument aucune différence.

","title":""},{"edit":"

"}],[{"text":"

Utilisation

Illustrons l'utilisation de notre parcours en largeur sur le graphe des régions.

Nous avons la variable regions qui contienne la représentation de ce graphe:

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\")

On peut vérifier la distance entre des régions:

assert distance(regions, \"Bretagne\", \"Occitanie\") == 3

assert distance(regions, \"Bretagne\", \"Bretagne\") == 0

assert distance(regions, \"Bretagne\", \"Mayotte\") == None

Ici, on vérifie que la distance d'une région a elle-même est bien 0 et que la fonction distance renvoie bien None pour deux régions entre lesquelles il n'existe pas de chemin.

Tester les codes et conclure sur les résultats.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Efficacité

Comme pour le parcours en profondeur, le parcours en largeur a un coût directement proportionnel à la taille de la partie du graphe qui a été explorée. En effet, chaque sommet est placé au plus une fois dans l'ensemble suivant, la première fois qu'il est rencontré, c'est-à-dire lorsqu'il n'est pas encore dans le dictionnaire dist.

À ce moment-là, on fixe sa distance, ce qui fait qu'il ne sera pas considéré de nouveau.

De même, chaque arc s —> v est examiné au plus une fois, lorsque le sommet s est retiré de l'ensemble courant.

Le coût en mémoire est celui des deux ensembles et du dictionnaire, au pire proportionnel au nombre total de sommets du graphe.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Étant donnés un graphe et un sommet dans ce graphe, le parcours eu profondeur et le parcours en largeur sont deux algorithimes fondamentaux pour explorer le graphe en partant de ce sommet.

Ces deux parcours déterminent l'ensemble des sommets accessibles depuis le sommet de départ.

Le parcours en profondeur permet de détecter la présence d'un cycle dans un graphe orienté.

Le parcours en largeur permet de déterminer la distance entre le sommet de départ et tout sommet accessible, c'est-à-dire le plus petit nombre d'arcs pour

relier ces deux sommets.

","title":"Conclusion","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Dérouler à la main le parcours en profondeur sur le graphe

pour différentes valeurs du sommet de départ.

Donner à chaque fois la valeur finale de l'ensemble vus, c'est-à-dire l'ensemble des sommets atteints par le parcours.

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

sommet | valeur finale

de départ de vus

0 {0,1,3,2}

1 {1,2}

2 C2}

3 {3,1,2}

"}],[{"text":"

Dérouler à la main le parcours en largeur sur le graphe suivant

pour différentes valeurs du sommet de départ.

Donner à chaque fois la valeur finale du dictionnaire dist, c'est-à-dire la distance à la source de chaque sommet atteint par le parcours.

","title":"Exercice","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

sommet valeur finale

de départ de dist

0 {0H0,1H1,38m1,2r 2}

1 {1H0,2H 1}

2 {25 0}

3 {3-0,1H1,2r 2}

"}],[{"text":"

On peut se servir d'un parcours en profondeur pour déterminer si un graphe non orienté est connexe, c'est-à-dire si tous ses sommets sont reliés entre eux par des chemins.

Pour cela, il suffit de faire un parcours en profondeur à partir d'un sommet quelconque, puis de vérifier que tous les sommets ont été atteints par ce parcours.

Écrire une fonction est_connexe() qui réalise cet algorithme.

On pourra se servir de la méthode sommets() de la classe Graphe et de la fonction parcours.

Tester avec les 2 graphes suivants :

g1 :

g2:

print(\"g1 connexe?\",est_connexe(g1))

print(\"g2 connexe?\",est_connexe(g2))

Résultat :

True

False

","title":"Exercice","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

g1 = Graphe3()

g1.ajouter_arc(\"A\",\"B\")

g1.ajouter_arc(\"B\",\"C\")

g1.ajouter_arc(\"A\",\"D\")

g1.ajouter_arc(\"D\",\"C\")

g2 = Graphe3()

g3.ajouter_arc(\"A\",\"B\")

g3.ajouter_arc(\"B\",\"C\")

g3.ajouter_arc(\"A\",\"D\")

g3.ajouter_arc(\"D\",\"C\")

g2.ajouter_arc(\"E\",\"F\")

On suit l’algorithme proposé, en faisant uniquement attention au cas d’un graphe qui ne contiendrait aucun

sommet.

def est_connexe(g):

\"\"\"le graphe est-il connexe?

(uniquement pour un graphe non orienté)\"\"\"

ts = g.sommets()

if len(ts) == 0:

return True

s = ts.pop()

vus = set()

parcours(g, vus, s)

for s in ts:

if s not in vus:

return False

return True

"}],[{"text":"

Dans cet exercice, on se propose d'utiliser le parcours en profondeur pour construire un chemin entre deux sommets, lorsque c'est possible.

On le fait avec deux fonctions, comme dans le programme parcours en profobdeur.

def parcours_ch(g, vus, org, s):

\"\"\"parcours depuis Le sommet s, en venant de org\"\"\"

...

def chemin(g, u, v):

\"\"\"un chemin de u à v, Le cas échéant, None sinon\"\"\"

...

L'idée est que l'attribut vus n'est plus un ensemble mais un dictionnaire, qui associe à chaque sommet visité le sommet qui a permis de l'atteindre pendant le parcours en profondeur.

La fonction parcours_ch prend un argument supplémentaire, org (pour origine), qui est justement le sommet qui a permis d'atteindre s, en empruntant l'arc org —>s.

Écrire le code de la fonction parcours_ch.

Il est très semblable à celui de la fonction parcours du programme parcours en profondeur.

Écrire ensuite le code de la fonction chemin qui renvoie un chemin entre les sommets u et v, le cas échéant, None s'il n'existe pas de chemin entre ces deux sommets.

Pour cela, lancer un parcours en profondeur à partir du sommet u, en donnant à org la valeur None, puis, si

le sommet v a été atteint, construire le chemin dans un tableau en «remontant» le dictionnaire vus de v jusqu'à u.

Tester avec le graphe suivant:

$\"graphe10.png$

print(\"A->F?\",chemin(g2, \"A\", \"F\"))

print(\"A->G?\",chemin(g2, \"A\", \"G\"))

Résultat:

A->F? ['A', 'D', 'E', 'B', 'C', 'F']

A->G? None

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

Pour parcours_ch, l'ajout dans un ensemble de-

vient un ajout dans un dictionnaire.

def parcours_ch(g, vus, org, s):

\"\"\"parcours depuis le sommet s, en venant de org\"\"\"

if s not in vus:

vus[s] = org

for v in g.voisins(s):

parcours_ch(g, vus, s, v)

Pour chemin, on prend soin de tester si v a été atteint par le parcours. Dans

le cas contraire, on renvoie None. Sinon, on construit le chemin avec une

boucle while.

def chemin(g, u, v):

\"\"\"chemin de u à v, le cas échéant, None sinon\"\"\"

vus = {}

parcours_ch(g, vus, None, u)

if v not in vus:

return None

ch = []

s=v

while s is not None:

ch.append(s)

s = vus[s]

ch.reverse()

return ch

De fait, le chemin est construit à l'envers. On prend soin de le renverser avec

la méthode reverse avant de le renvoyer.

"}],[{"text":"

Dans cet exercice, on se propose d'utiliser le parcours en largeur pour construire un chemin de longueur minimale entre deux sommets.

On le fait avec deux fonctions, comme dans le programme parcours en largeur.

def parcours_largeur_ch(g, source):

\"\"\"parcours depuis le sommet source\"\"\"

...

def chemin(g, u, v):

\"\"\"un chemin de u à v, le cas échéant, None sinon\"\"\"

L'idée est qu'un dictionnaire vus remplace le dictionnaire dist.

Ce dictionnaire vus associe à chaque sommet visité le sommet qui à permis de l'atteindre pendant le parcours en largeur.

Écrire le code de la fonction parcours_largeur_ch.

Il est très semblable à celui de la fonction parcours_largeur du programme parcours en largeur.

Pour le sommet source, on lui associe la valeur None dans le dictionnaire vus.

Écrire ensuite le code de la fonction chemin qui renvoie un chemin réalisant la distance entre les sommets u et v, le cas échéant, et None s'il n'existe pas de chemin entre ces deux sommets.

Pour cela, lancer un parcours en largeur à partir du sommet u puis, si le sommet v a été atteint, construire le chemin dans un tableau en «remontant» le dictionnaire vus de v jusqu'à u.

Tester avec le graphe suivant:

$\"graphe10.png$

print(\"A->F?\",chemin(g2, \"A\", \"F\"))

print(\"A->G?\",chemin(g2, \"A\", \"G\"))

Résultat:

A->F? ['A', 'B', 'C', 'F']

A->G? None

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

On garde la structure du programme 42, le diction-

naire vus prenant la place du dictionnaire dist.

def parcours_largeur_ch(g, source):

\"\"\"parcours depuis Le sommet source\"\"\"

vus = {source: None}

courant = {source}

suivant = set()

while len(courant)>0:

s = courant.pop()

for v in g.voisins(s):

if v not in vus:

suivant.add(v)

vus[v] = s

if len(courant) == 0:

courant, suivant = suivant, set()

return vus

La seconde partie, à savoir la reconstruction du chemin, n’est pas différente

de celle effectuée dans l’exercice précédent pour un parcours en profondeur.

def chemin(g, u, v):

\"\"\"chemin de u à v, Le cas échéant, None sinon\"\"\"

vus = parcours_largeur_ch(g, u)

if v not in vus:

return None

ch = []

s=v

while s is not None:

ch.append(s)

s = vus[s]

ch.reverse()

return ch

"}],[{"text":"

Les nœuds d'un arbre binaire peuvent être vus comme les sommets d'un graphe non orienté.

En particulier, on peut donc parcourir les nœuds d'un arbre avec un parcours en profondeur ou en largeur.

Pour le parcours en profondeur, il s'agit d'un parcours que nous avons déjà présenté, à savoir le parcours préfixe.

Dans cet exercice, on se propose de parcourir les nœuds d'un arbre binaire avec un parcours en largeur.

Écrire une fonction largeur(a) qui reçoit un arbre binaire a en argument et imprime les valeurs de ses différents nœuds dans un ordre donné par un parcours en largeur, c'est-à-dire la valeur contenue dans la racine, puis les valeurs contenues dans les nœuds immédiatement en-dessous (niveau 1), puis celles contenues dans les nœuds encore en-dessous (niveau 2), etc.

Tester le programme avec l'arbre ci-dessus et le code suivant:

largeur(a1)

Résultat:

Indication : Il faut utiliser les classes suivantes pour construire l'arbre a1:

class Noeud:

\"\"\"un noeud d'un arbre binaire\"\"\"

def __init__(self, g, v, d):

self.gauche = g

self.valeur = v

self.droit = d

def __eq__(self, n):

return n is not None \\

and self.gauche == n.gauche \\

and self.valeur == n.valeur \\

and self.droit == n.droit

class ABR:

\"\"\"arbre binaire de recherche\"\"\"

def __init__(self):

self.racine = None

def ajouter(self, x):

if self.racine is None :

self.racine = Noeud(None,x,None)

else :

self.__ajoute__(x,self.racine)

def contient(self, x):

return self.__appartient__(x, self.racine)

def affiche(self):

self.__afficher__(self.racine)

print(\"\\n\")

def __afficher__(self,a):

if a is None:

return

print (\"(\", end=\"\")

self.__afficher__(a.gauche)

print(a.valeur, end=\"\")

self.__afficher__(a.droit)

print(\")\", end=\"\")

def __ajoute__(self,x,a):

if x < a.valeur:

if a.gauche is None:

a.gauche = Noeud(None, x, None)

else:

self.__ajoute__(x,a.gauche)

elif x > a.valeur:

if a.droit is None:

a.droit = Noeud(None, x, None)

else:

self.__ajoute__(x,a.droit)

def __appartient__(self,x, a):

\"\"\"détermine si x apparaît dans l'ABR\"\"\"

if a is None:

return False

if x < a.valeur:

return self.__appartient__(x, a.gauche)

elif x > a.valeur:

return self.__appartient__(x, a.droit)

else:

return True

","title":"Exercice","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

On crée l'arbre a1:

a1 = ABR()

a1.ajouter(8)

a1.ajouter(4)

a1.ajouter(12)

a1.ajouter(2)

a1.ajouter(6)

a1.ajouter(10)

a1.ajouter(14)

a1.ajouter(1)

a1.ajouter(3)

a1.ajouter(7)

a1.ajouter(9)

a1.ajouter(13)

a1.ajouter(15)

a1.affiche()

Le programme en largeur est le suivant:

def largeur(a):

h = hauteur(a.racine)

for i in range(1, h+1):

affiche_niveau(a.racine, i)

print()

def affiche_niveau(Noeud, niveau):

if Noeud is None:

return

if niveau == 1:

print(Noeud.valeur)

elif niveau > 1:

affiche_niveau(Noeud.gauche, niveau-1)

affiche_niveau(Noeud.droit, niveau-1)

def hauteur(Noeud):

if Noeud is None:

return 0

else:

lheight = hauteur(Noeud.gauche)

rheight = hauteur(Noeud.droit)

return 1+max(lheight, rheight)

"}],[{"text":"

Nous avons le labyrinthe suivant:

Il est représenté part un liste à 2 dimensions en Python

grid = [[1, 0, 1, 1, 1, 1, 1 ,1],

[1, 0, 0, 0, 0, 0, 1 ,1],

[1, 1, 1, 0, 0, 0, 1 ,1],

[1, 0, 0, 0, 1, 0, 0 ,1],

[1, 0, 1, 1, 0, 0, 1 ,1],

[1, 0, 1, 0, 0, 1, 0 ,1],

[1, 0, 1, 0, 0, 0, 0 ,1],

[1, 1, 1, 1, 1, 1, 0 ,1]]

Avec :

O pour un passage;
1 pour un mur;
l'entrée est en haut à gauche en (1,0);
la sortie est en bas à droite en (len(grid[0])-2,len(grid)-1).

En le modélisant par un graphe et en le parcourant en largeur à l'aide de la fonction chemin, on détermine le moyen pour en sortir:

Vous allez donc écrire une fonction generer_graphe qui a comme argument une grille de labyrinthe et qui retourne son graphe non orienté (Graphe3).

En effet, grace au graphe du labyrinthe et à la fonction chemin, vu précédemment, nous pourrons déterminer le chemin pour en sortir.

Indications : Pour déterminer le graphe, il faut parcourir le labyrinthe et pour chacune des cases ajouter ou non des arcs.

Par exemple :

on ajoute pour cette cellule l'arc correspondant :

glaby.ajouter_arc((x,y),(x+1,y))

et pas :

glaby.ajouter_arc((x,y),(x,y+1))

car il y a un mur.

Tester avec le code suivant :

graphe_laby = generer_graphe(grid)

itineraire = chemin(graphe_laby,(1,0),(len(grid[0])-2,len(grid)-1))

print(itineraire)

Pour notre grille le résultat est le suivant:

[(1, 0), (1, 1), (2, 1), (3, 1), (3, 2), (4, 2), (5, 2), (5, 3), (5, 4), (4, 4), (4, 5), (4, 6), (5, 6), (6, 6), (6, 7)]

Donc avec les fonctions generer_graphe et chemin, nous pouvons déterminer les parcours pour des labyrinthe plus complexes:

","title":"Exercice","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

def generer_graphe(grille):

glaby = Graphe3()

for i in range(0,len(grille)-1):

for j in range(0,len(grille[0])-1):

if grille[i][j] == 0 and grille[i][j+1]==0:

glaby.ajouter_arc((j,i),(j+1,i))

if grille[i][j] == 0 and grille[i+1][j]==0:

glaby.ajouter_arc((j,i),(j,i+1))

j+=1

if grille[i][j]==0 and grille[i+1][j]==0:

glaby.ajouter_arc((j,i),(j,i+1))

i+=1

for j in range(0,len(grille[0])-1):

if grille[i][j] == 0 and grille[i][j+1]==0:

glaby.ajouter_arc((j,i),(j+1,i))

return glaby

"}]]

Détails: Écrit par : Richard GAUTHIER; Création : 18 Octobre 2020; Mis à jour : 23 Novembre 2020; Clics : 1689

[[{"text":"

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

"}],[{"text":"

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$

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.

","title":"Définitions"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

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$

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$

Figure 1 : Le graphe des régions françaises.

C'est un autre exemple de graphe non orienté.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

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).

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

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$

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.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

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

$\"graphe1.png$

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.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

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

$\"graphe1.png$

le chemin A->B—>A n'est pas simple et n'est donc pas un cycle.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

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.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

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

$\"graphe1.png$

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$

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.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

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.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

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.

","title":""},{"edit":"

"}],[{"text":"

É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).

"}],[{"text":"

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?

","title":"Exemples de graphes"},{"edit":"

"}],[{"text":"

Réseau

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.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Carte

$\"graphe1.png$

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.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Labyrinthe

$\"Labyrinthe\"$

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.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Jeu

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.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Arbre

$\"graphe1.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»).

","title":""},{"edit":"

"}],[{"text":"

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.

","title":"Représentation d'un graphe en Python"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

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$

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.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

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.

$\"graphe1.png$

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.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

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.

","title":""},{"edit":"

"}],[{"text":"

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;

$\"graphe1.png$

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.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

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.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

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.

$\"graphe1.png$

Créons le graphe des régions: