PARTIE II : Ponts d'un graphe⚓︎
Info
Cet article utilise, pour sa mise en forme, de petites boites pour encapsuler les différents éléments structurels. La plupart sont repliables, facilitant la navigation.
Convention de nommage : dans toute la suite, nous nommons \(G_x\) où \(x\) est un entier, le graphe relatif à la figure x du sujet (la variable python associée sera donc Gx), \(B_x\) (Bx) pour le bloc union find correspondant et enfin \(F_x\) (Fx) pour les forêts. Chacun de ces graphes pourra présenter plusieurs variantes b, c etc. (par exemple G4 et G4b, F3 et F3b, F3c).
Bonne lecture...
Ponts et Blocs dans un graphe non orienté⚓︎
Commençons par le reproduire \(G_1\), le graphe de la Figure 1 :
Graphe de la Figure 1
Voici les instructions Python pour l'obtenir et le visualiser, dans un notebook Jupyter :
import PyGraph.pygraph as pg
G1 = pg.Graph(16)
G1_EDGES = [(0, 2), (0, 3), (2, 3), (1, 3), (3, 4), (4, 5), (4, 6), (5, 6), (6, 7),
(6, 8), (6, 9), (8, 9), (10, 11), (10, 12), (11, 12), (11, 15), (13, 14),
(13, 15), (14, 15)]
G1.add_edges_from(G1_EDGES)
G1_POS = [(0, 0, 0), (3, 1, 0), (4, 2, 0), (6, 3, 0), (9, 4, 0), (10, 5, 0), (11, 6, 0),
(15, 7, 0), (1, 0.5, 1), (5, 2.5, 1), (7, 3.5, 1), (12, 5.5, 1), (2, 0.5, -1),
(8, 3.5, -1), (13, 6.5, -1), (14, 7.5, -1)]
G1.position(G1_POS, ech=0.6)
G1.view
Ce graphe servira de support à l'ensemble du sujet où l'on s'intéresse aux :
- ponts qui sont des arêtes du graphe dont la suppression fait croitre le nombre de composantes connexes ;
- blocs qui sont les composantes connexes restantes lorsqu'on a supprimé tous les ponts d'un graphe.
Ponts et blocs du graphe \(G_1\)
- Parmi les arêtes suivantes, lesquelles sont des ponts ?
- \((0, 2)\)
- \((1, 3)\)
- \((5, 6)\)
- \((3, 4)\)
- \((8, 9)\)
- \((6, 7)\)
- \((11, 15)\)
- Combien de blocs \(G_1\) possède-il ?
- 3
- 2
- 6
- 5
- Parmi les arêtes suivantes, lesquelles sont des ponts ?
- \((0, 2)\)
- \((1, 3)\)
- \((5, 6)\)
- \((3, 4)\)
- \((8, 9)\)
- \((6, 7)\)
- \((11, 15)\)
- Combien de blocs \(G_1\) possède-il ?
- 3
- 2
- 6
- 5
La solution en image
La Figure 2 du sujet, met en avant ponts et blocs du graphe exemple, nous le faisons ici, avec un peu plus de couleurs. On retrouve les \(6\) blocs et les \(4\) ponts (les arêtes en bleu).
Nous définissons deux petites fonctions pour colorier les blocs d'un graphe et les ponts :
def colorier_blocs(graphe, blocs):
"""colorie les sommets de l'itérable blocs via color_on méthode du module pygraph
on se sert du numéro du bloc dans l'énumération comme numéro de couleur
"""
for color_id, set_of_nodes in enumerate(blocs):
for node_id in set_of_nodes:
graphe.color_on(node_id, color_id)
def colorier_ponts(graphe, ponts, color='lightblue'):
for a, b in ponts:
graphe.color_on_edge(a, b, color)
Et finalement,
G1b = G1.copy()
BLOCS_G1 = [[1], [0, 2, 3], [4, 5, 6, 8, 9], [7], [10, 11, 12], [13, 14, 15]]
PONTS_G1 = [(1, 3), (3, 4), (6, 7), (11, 15)]
colorier_blocs(G1b, BLOCS_G1)
colorier_ponts(G1b, PONTS_G1)
Représentation sous la forme de forêt⚓︎
Le sujet propose de représenter un graphe à l'aide d'une forêt qui sera une structure de type union find appelée bloc union find ou buf. Cette structure repose sur trois tableaux :
- repr pour les représentants de blocs (chaque bloc a 1 représentant choisi arbitrairement)
- parents pour les parents de chacun des nœuds : si \(s\) est le représentant d'un bloc \(b\) alors soit
parents[s] == set alors \(s\) est racine d'un des arbres de la forêt, soitparents[s]indique un somment d'un bloc \(b'\) tel qu'il existe un pont entre un sommet de \(b\) et un sommet de \(b'\) ; sinon en remontant, on arrive au représentant du bloc de \(s\) - rang la taille du bloc de chaque représentant.
Exemple et premières questions⚓︎
On considère le graphe \(G_4\) ci-dessous :
Graphe de la Figure 4
G4 = pg.Graph(8)
G4_EDGES = [(0, 1), (1, 2), (2, 3), (2, 4), (3, 4), (4, 6), (5, 6), (5, 7), (6, 7)]
G4.add_edges_from(G4_EDGES)
G4_POS = [(0, 0, 0), (2, 1, 0), (4, 2, 0), (6, 3, 0), (1, 0.5, 1), (3, 1.5, 1),
(5, 2.5, 1), (7, 3.5, 1)]
G4.position(G4_POS, ech=0.6)
G4.view
Question 2.1
Indiquer les blocs et les ponts du graphe \(G_4\).
G4bis = G4.copy()
BLOCS_G4 = [[0], [1], [2, 3, 4], [5, 6, 7]]
PONTS_G4 = [(0, 1), (1, 2), (4, 6)]
colorier_blocs(G4bis, BLOCS_G4)
colorier_ponts(G4bis, PONTS_G4)
G4bis.view
Question 2.2
Représenter graphiquement une structure buf correspondant à \(G_4\)
On utilise les graphes orientés disponibles dans pygraph et la colorisation des sommets, pris dans chacun des blocs :
F4 = pg.DiGraph(8)
F4_EDGES = [(0, 1), (2, 1), (3, 2), (4, 2), (6, 4), (5, 6), (7, 6)]
F4.add_edges_from(F4_EDGES)
F4_POS = [(0, 0, 3), (1, 0.5, 4), (2, 1, 3), (3, 0.5, 2), (4, 1.5, 2), (5, 1, 0),
(6, 1.5, 1), (7, 2, 0)]
F4.position(F4_POS, ech=0.6)
F4_REPR = [bloc[0] for bloc in BLOCS_G4]
for node_id in F4_REPR:
F4.color_on(node_id, 4)
F4.view
Quelques classes Python⚓︎
La structure buf peut être vue comme une spécialisation d'une structure union find plus classique. Voici la classe Partition, qui modélise cette union find et utilisée dans d'autres sujets de cette agrégation 2023, la classe VizPartition pour visualiser ces partitions et la classe Buf qui spécialise Partition pour en faire une structure bloc union find. Dans la suite des questions, nous reprendrons certaines méthodes des classes Partition et Buf. Vous pouvez télécharger ces trois classes :
- la classe
Partition: partition.py - la classe
VizPartition: viz_partition.py - la classe
Buf: buf.py
encore en cours de finalisation
Avertissement
La modélisation POO de la structure buf peut servir de support à des exercices guidés ou à un projet en classe de Terminale NSI. Il faudra penser à quelques aménagements par rapport à ce qui est dit ici, comme par exemple, supprimer la notion d'héritage en ne faisant qu'une classe Buf reprenant le contenu de Partition.
Suite de la première section⚓︎
Question 2.3
Il s'agit d'écrire une fonction pour initialiser une structure buf vide comportant \(n\) nœuds. Compte tenu de notre structuration, cela correspond aux deux méthodes __init__ des classes Partition et Buf.
Le tableau des parents est la liste de identifiants de nœuds (chaque nœud est son propre parent) ; le tableau des représentants est initialisé à True pour tous les nœuds (chaque nœud est le représentant du groupe où il est le seul individu) ; enfin les rangs sont à \(1\).
class Partition:
def __init__(self, n):
self.parents = list(range(n))
self.repr = [True] * n
self.size = n
class Buf(Partition):
def __init__(self, n):
Partition.__init__(self, n)
self.rang = [1] * n
Avant de passer aux deux dernières questions de cette première section, voyons l'utilisation de nos classes Buf et VizPartition pour créer et visualiser les forêts données en exemple dans le sujet.
Forêt de la Figure 3
B3 = Buf(16)
B3.parents = [3, 3, 3, 3, 3, 4, 4, 6, 4, 8, 11, 11, 11, 11, 13, 13]
B3.repr = [False, True, False, True, True, False, False, True, False, False, False, True, False, True, False, False]
B3.rang = [3, 1, 3, 3, 5, 5, 5, 1, 5, 5, 3, 3, 3, 3, 3, 3]
F3 = VizPartition(B3)
F3.position = [(0, 0, 2), (1, 1, 2), (2, 2, 2), (3, 1.5, 3), (4, 3, 2), (5, 2, 1), (6, 3, 1),
(7, 3, 0), (8, 4, 1), (9, 4, 0), (10, 6, 2), (11, 7, 3), (12, 7, 2), (13, 8, 2),
(14, 7.5, 1), (15, 8.5, 1)]
Et comme avec ce positionnement, la composante connexe comportant le nœud \(11\) se trouve un peu éloignée, on la rapproche en déplaçant de \(1\) vers la gauche le nœud \(11\) et tous ceux qui lui sont rattachés (la signification du True à la fin) ; et on visualise :
F3.move(11, -1, 0, True)
F3.sagittal
Question 2.4
La méthode find dans une structure de type union find permet de retrouver le représentant d'un sommet. Lors de la remontée vers ce représentant, une compression à lieu : chaque sommet se voit rattaché directement au représentant. Cette méthode se trouve dans la classe Partition. La solution est récursive :
- si le nœud est lui-même un représentant alors on renvoie ce nœud,
- sinon, on recherche (récursivement) le représentant du parent et, avant de renvoyer ce représentant, on l'affecte comme parent du nœud (compression)
class Partition:
...
def find(self, node_id):
"""recherche et renvoie le représentant du nœud node_id, et réalise la compression"""
if self.repr[node_id]:
return node_id
else:
repr_id = self.find(self.parents[node_id])
self.parents[node_id] = repr_id
return repr_id
Question 2.5
La méthode blocs de la classe Buf doit renvoyer les informations sur les blocs de la structure. le sujet (codé en OCaml) préconise des tableaux de tableaux. On perd alors l'information du représentant de chaque bloc, ce qui est dommage. Le fait d'utiliser un tableau est aussi embêtant pour le caractère ordonné, ce que n'est pas l'ensemble des nœuds d'un bloc. Pour ces raisons, nous choisissons de renvoyer un dictionnaire dont les clés sont les représentants et les valeurs associées des ensembles (set) de nœuds.
Adaptation NSI : remplacer les set par de simples list.
À noter que cette méthode modifie la structure puisqu'on recherche les représentants (phénomène de compression).
class Buf(Partition):
...
def blocs(self):
resultat = {node_id:set() for node_id in range(self.size) if self.repr[node_id]}
for node_id in range(self.size):
repr_id = self.find(node_id)
resultat[repr_id].add(node_id)
return resultat
D'autres forêts possible pour le graphe \(G_1\)
B3 est le buf à l'origine de F3 et de F3b. On peut demander le représentant de \(9\) :
>>> B3c = B3.copy()
>>> B3c.find(9)
4
Mais alors la forêt représentante change :
Ajout d'arêtes⚓︎
Cette section s'intéresse à l'ajout d'arêtes dans la structure buf. On commence par calculer une information : la chaine des représentants d'un nœud, que l'on utilisera par la suite.
Question 2.6
Il s'agit d'écrire une méthode chaine_racine qui, pour un nœud \(s\) donné, renvoie la liste des représentants depuis la racine de l'arbre du nœud \(s\) jusqu'au représentant de \(s\).
Là encore, sans surprise, on adopte une solution récursive adaptée à notre structure :
- si \(s\) est son propre parent alors il est représentant et on renvoie la liste constituée uniquement de \(s\)
- sinon, on calcule la chaine à partir du parent de \(s\) puis, on y ajoute \(s\) si ce dernier est un représentant ; on renvoie la chaine
class Buf:
...
def chaine_racine(self, node_id):
parent_id = self.parents[node_id]
if parent_id == node_id:
return [node_id]
else:
chaine = self.chaine_racine(parent_id)
if self.repr[node_id]:
chaine.append(node_id)
return chaine
L'ajout est une opération délicate et la fin du sujet consiste à nous guider vers la modélisation de celle-ci. On distingue plusieurs cas suivant que les nœuds de l'arête appartiennent ou pas à la même composante connexe.
Arêtes entre sommets de composantes connexes distinctes⚓︎
Lorsqu'on ajoute une arête entre deux sommets de deux composantes connexes distinctes, cette arête est un pont. Voici comment il faut procéder pour ajouter par exemple une arête entre les sommets \(u\) et \(v\) :
- on calcule la chaine des représentants d'un des sommets (disons \(u\)),
- on retourne le sens des arcs de la chaine, faisant de \(u\) la nouvelle racine de son arbre,
- on change le parent du représentant de \(u\) pour le faire pointer vers le représentant de \(v\).
La forêt \(F_5\) un exemple d'ajout d'arête
La Figure 5 du sujet montre le résultat de la connexion des sommets \(5\) et \(14\) depuis le buf \(B_3\).
À votre avis, quelle chaine a été retournée ?
Question 2.7
Dessiner la forêt obtenue en connectant les sommets \(7\) et \(12\) et en supposant que c'est la chaine issue de \(7\) qui est retournée :
Question 2.8
On nous demande de coder les points 1 et 2 de la méthode pour connecter deux sommets de deux composantes connexes distinctes :
class Buf:
...
def retourner_chaine(self, u, v):
chaine_u = self.chaine_racine(u)
dernier = chaine_u[-1]
for i in range(len(chaine_u) - 1):
node_id, suivant_id = chaine_u[i], chaine_u[i+1]
self.parents[node_id] = suivant_id
return dernier
Avec une ligne de plus on obtient la méthode complète :
def ajout_non_connexe(self, u, v):
dernier = self.retourner_chaine(u, v)
self.parents[dernier] = self.find(v)
On peut alors donner le code utilisé pour la création de la forêt de la question 2.7 :
Code de la forêt 2.7
Le buf de départ est \(B_3\).
B3d = B3.copy()
B3d.ajout_non_connexe(7, 12)
F3d = VizPartition(B3d)
F3d.position = [(0, 0, 0), (1, 1, 0), (2, 2, 0), (3, 1, 1), (4, 2.5, 2), (5, 2, 1), (6, 3, 1),
(7, 2.5, 3), (8, 4, 1), (9, 4, 0), (10, 3.5, 3), (11, 4, 4), (12, 4.5, 3),
(13, 5.5, 3), (14, 5, 2), (15, 6, 2)]
F3d.sagittal
Arêtes entre blocs distincts d'une même composante connexe⚓︎
Lorsqu'on connecte deux sommets de deux blocs de la même composante connexe, il va falloir fusionner les deux blocs et tous les blocs compris entre les deux.
La forêt \(F_6\), issue de \(F_5\)
À partir de \(F_5\), on connecte les sommets \(1\) et \(15\). Les blocs \(1\), \(3\), \(4\) et \(13\) sont donc fusionnés. Voici le résultat si on garde \(4\) comme représentant :
Question 2.9
À l'instar de l'exemple précédent, on demande de représenter la forêt issue de \(F_5\), après connexion des sommets \(7\) et \(12\). On fusionne les blocs \(7\), \(4\), \(13\) et \(11\). Là encore on a gardé \(4\) comme représentant :
Question 2.10
Il s'agit d'écrire l'opération élémentaire de la connexion : l'union de deux blocs dont on passe les représentants en paramètres. La question précise qu'on ne se souci pas de la valeur du parent du bloc obtenu. On garde comme représentant, le représentant ayant le rang le plus petit. Le rang du bloc augmente de \(1\).
Notons que la méthode doit renvoyer le sommet qui a été retenu comme représentant.
class Buf:
...
def union(self, repr_i, repr_j):
"""réalise l'union de deux blocs"""
if repr_i != repr_j:
# repr_j est censé être le bloc le plus petit,
# on switche si ce n'est pas le cas
if self.rang[repr_j] > self.rang[repr_i]:
repr_i, repr_j = repr_j, repr_i
self.parents[repr_i] = repr_j
self.repr[repr_i] = False
self.rang[repr_j] += 1
return repr_j
Visualisons l'union
Pour l'instant, l'opération d'union est incomplète. En effet, souvenez-vous de la Figure 5 :
Si on réalise l'union telle que décrite entre les sommets \(4\) et \(7\), alors \(7\) devient le représentant du bloc. \(4\) pointera donc vers \(7\) qui lui continuera de pointer sur \(6\) et on a perdu le lien avec le bloc \(3\) :
Les dernières questions sont là pour terminer cette opération de fusion incomplète.
Question 2.11
Maintenant qu'on sait faire l'union de deux représentants, il s'agit d'étendre à une chaine, en faisant attention au parent du représentant du bloc final.
On suppose que la chaine passée est ordonnée, un peu au sens de la chaine de représentants produite par chaine_racine. Ainsi le parent du premier représentant (qui peut être le représentant lui-même si on a affaire à une racine d'arbre) deviendra le parent du représentant du bloc issu de la fusion. Pour la fusion elle-même, voici la procédure :
- extraire les deux derniers sommets de la chaine,
- faire l'union des sommets,
- replacer le sommet issu de l'union à la fin de la chaine,
- recommencer jusqu'à n'avoir plus qu'un sommet.
Cela donne le code suivant :
class Buf:
...
def fusion_chaine(self, chaine):
futur_parent = self.find(self.parents[chaine[0]])
while len(chaine) > 1:
v = chaine.pop()
u = chaine.pop()
if self.union(u, v) == u:
chaine.append(u)
else:
chaine.append(v)
repr_final = chaine[0]
if self.repr[futur_parent]:
self.parents[repr_final] = futur_parent
else:
self.parents[repr_final] = repr_final
Question 2.12
Nous arrivons au terme de ce sujet avec l'opération ultime : l'ajout d'une arête dans la structure buf. La méthode ajout résume les cas traités jusqu'ici. Dans le cas d'une liaison intra composante connexe, il nous faut construire la chaine de représentants à fusionner. Cela se fait de la façon suivante :
- on calcule les chaines racines de chacun des deux sommets,
- on calcule ensuite la chaine constituée des parties distinctes, en prenant comme départ l'ancêtre commun le plus profond
Ce qui donne la méthode suivante :
class Buf:
...
def ajout(self, u, v):
r_u = self.find(u)
r_v = self.find(v)
if r_u != r_v:
chaine_u = self.chaine_racine(u)
chaine_v = self.chaine_racine(v)
if chaine_u[0] != chaine_v[0]:
# cas 1 : 2 composantes connexes distinctes (voir 2.8)
dernier = chaine_u[-1]
for i in range(len(chaine_u) - 1):
node_id, suivant_id = chaine_u[i], chaine_u[i+1]
self.parents[node_id] = suivant_id
self.parents[dernier] = r_v
else:
# cas 2 : même composante
k, n = 0, min(len(chaine_u), len(chaine_v))
while k < n and chaine_u[k] == chaine_v[k]:
k += 1
chaine = chaine_u[k-1:] + chaine_v[k:]
self.fusion_chaine(chaine)
Conclusion⚓︎
Ce sujet manipulant des arbres et des graphes est très visuel, et se prête à une adaptation pour un beau sujet de projet en Terminale NSI. En guise de conclusion, voici la reconstruction d'une forêt représentants les blocs et les ponts de \(G_1\), en partant d'un buf vide et en y ajoutant (au sens de la question 2.12) les arêtes, une par une.
Reconstruction d'une forêt possible pour \(G_1\)
>>> B3 = Buf(16)
>>> B3.ajout(0, 2)
>>> B3.ajout(0, 3)
>>> B3.ajout(2, 3)
>>> B3.ajout(4, 5)
>>> B3.ajout(4, 6)
>>> B3.ajout(5, 6)
>>> B3.ajout(6, 8)
>>> B3.ajout(8, 9)
>>> B3.ajout(6, 9)
>>> B3.ajout(10, 11)
>>> B3.ajout(10, 12)
>>> B3.ajout(11, 12)
>>> B3.ajout(13, 14)
>>> B3.ajout(13, 15)
>>> B3.ajout(14, 15)
>>> B3.ajout(3, 4)
>>> B3.ajout(11, 15)
>>> B3.ajout(7, 6)
