Capes NSI 2021 épreuve 1

dimanche 28 mars 2021
par  Alain BUSSER , Sébastien HOARAU

Le sujet est ici

Problème 1 : Points proches dans le plan

Points

pyplot

Le sujet adopte l’approche de pyplot :

Le nuage de points est représenté par

  • une liste d’abscisses coords_x
  • une liste d’ordonnées coords_y

Ainsi les coordonnées du point Mi sont


coords_x[i]
coords_y[i]

Pour dessiner les points il suffira donc, sous pyplot, de faire

  1. from matplotlib.pyplot import *
  2. plot(coords_x,coords_y)
  3. show()

Télécharger

Avec ces coordonnées

  1. coords_x = [1.3,0.7,2.2,0.3,2.75,3.75,3.6,2.55]
  2. coords_y = [2.6,2.05,3.25,0.8,1.1,2.33,0.95,3.8]

Télécharger

on a le nuage de points de l’énoncé :

On suppose qu’on a une variable globale

n = len(coords_x)

Approche exhaustive

Question 1

  1. from math import sqrt
  2. def distance(i, j):
  3.     xi, yi = coords_x[i], coords_y[i]
  4.     xj, yj = coords_x[j], coords_y[j]
  5.     return sqrt((xj - xi)**2 + (yj - yi)**2)

Télécharger

Remarque : quitte à utiliser une fonction du module math, on aurait pu faire plus simple avec la fonction hypot qui fait la moitié du travail. Cela aurait donné

  1. from math import hypot
  2. def distance(i, j):
  3.     return hypot(coords_x[i]-coords_x[j], coords_y[i]-coords_y[j])

Télécharger

Question 2

Les flottants [1] sont stockés sous la forme 1,... × 2n dite à virgule flottante. Avec la norme IEEE 754 qui, en simple précision (32 bits) réserve 1 bit pour le signe, 8 pour l’exposant (le n) et 23 pour la mantisse (les points de suspension).

Dans cette écriture, n’existent que les décimaux qui ont un développement dyadique. Les autres sont donc approximés par les premiers. Pour la fonction distance cela peut donc signifier un calcul non exact. Concrètement, on évitera de comparer 2 distances avec ==

Question 3

Il s’agit ici de parcourir intelligemment les listes de points (leurs indices en fait) et de calculer la distance qui les sépare 2 à 2... et de mémoriser la plus petite. Intelligemment signifie qu’on ne va pas calculer 2 fois la même distance pour le couple (i, j) puis pour le couple (j, i) :

  1. def plus_proche():
  2.     proche_i, proche_j = None, None
  3.     min_dist = float('inf')
  4.     for i in range(n-1):
  5.         for j in range(i+1, n):
  6.             d = distance(i, j)
  7.             if d < min_dist:
  8.                 min_dist = d
  9.                 proche_i, proche_j = i, j
  10.     return proche_i, proche_j

Télécharger

Question 4

On va comparer :

M0 à M1… Mn-1 soit n−1 comparaisons, puis
M1 à M2…Mn-1 soit n−2 comparaisons, puis
etc.
Mn−2 à Mn-1 soit 1 comparaison.
Au total le nombre de comparaisons est le n-ème nombre triangulaire : la fonction plus_proche est donc en O(n2) .

Tri

Question 5

Voici la fonction de tri donnée :

  1. def tri(liste):
  2.     n = len(liste)
  3.     for i in range(n):
  4.         pos = i
  5.         while pos > 0 and liste[pos] < liste[pos-1]:
  6.             liste[pos], liste[pos-1] = liste[pos-1], liste[pos]
  7.             pos -= 1

Télécharger

Cette fonction ne retourne rien (ou plutôt None) mais trie en place le tableau qu’on lui passe. La méthode est la suivante : on parcourt les éléments depuis l’indice 0 par une boucle for et à chaque passage on va placer l’élément courant (indice i) à sa place parmi les éléments à gauche de lui (indices 0 à i-1). Il s’agit donc d’un tri par insertion.

L’invariant est donc : à la sortie de la boucle for le tableau est divisé en deux parties : de 0 à i les éléments sont triés par ordre croissant, et le reste pas trié.

Pour i=0 la proposition est trivialement vraie.

Supposons la propriété est vraie pour un i, voyons avec i+1. Appelons e la valeur l[i+1]. On a trois cas pour le passage du while et donc la sortie du for :

  • on n’entre pas dans le while : pos vaut alors i+1 et donc l[i+1] ≥ l[i] notre tableau est alors l[0] ≤ ... ≤ l[i] ≤ l[i+1] la proposition est vraie ;
  • on entre dans le while et on en sort parce que pos > 0 est faux alors on a : e en première position soit e < l[0] ≤ ... ≤ l[i] là encore la proposition est vraie
  • on entre dans le while et on en sort parce que liste[pos] &ge liste[pos-1] c’est-à-dire qu’on a : l[pos-1] ≤ e < l[pos+1] là encore on a un tableau qui reste trié (e est bien placé) et qui a un élément de plus : la proposition est vraie.

Question 6

Raisonnons dans le pire des cas et comptons le nombre de passages dans la boucle while :

Pour i=0 on ne passe pas dans le while
Pour i=1 on passe 1 fois
Pour i=2 on passera 2 fois, poussant liste[pos] en position 0
etc.
Pour i=n−1 on passera là encore n−1 fois au plus.
Au total on a donc n(n−1) sur 2 passages : la fonction tri est en O(n2) .

Question 7

Il faudrait changer le test dans le while :

coords_x[liste[pos]] < coords_x[liste[pos-1]]

Du coup, pour ne pas faire deux fonctions (une pour les x l’autre pour les y) on peut ajouter un paramètre à la fonction de tri :

  1. def tri(liste, coords):
  2.     n = len(liste)
  3.     for i in range(n):
  4.         pos = i
  5.         while pos > 0 and coords[liste[pos]] < coords[liste[pos-1]]:
  6.             liste[pos], liste[pos-1] = liste[pos-1], liste[pos]
  7.             pos -= 1

Télécharger

Ainsi on pourra trier nos points par abscisses croissantes :

  1. pos_x = list(range(n))
  2. tri(pos_x, coords_x)

Télécharger

ou par ordonnées croissantes :

  1. pos_y = list(range(n))
  2. tri(pos_y, coords_y)

Télécharger

Question 8

Le tri fusion (ou mergesort) de complexité O(n×log(n)) est meilleur.

Clusters

Dans la suite, un sous-ensemble de points est appelé un cluster. Par exemple, le nuage de points de l’énoncé devient le cluster suivant :

  1. liste_x = [3,1,0,2,7,4,6,5]
  2. liste_y = [3,6,4,1,5,0,2,7]
  3.  
  4. cluster_a = [[liste_x, liste_y]]

Télécharger

Alors que les points à gauche de la ligne verte pointillée forment le cluster

  1. cluster_b = [ [3,1,0,2,7,4],
  2.               [3,4,1,0,2,7] ]

Télécharger

Question 9

Il s’agit de parcourir les indices des abscisses et des ordonnées et de garder ceux dont le point M correspondant vérifie xmin ≤ coords_x[i] ≤ xmax

  1. def sous_cluster(cl, x_min, x_max):
  2.     sscl = [[], []]
  3.     for i in cl[0]:
  4.         if x_min <= coords_x[i] <= x_max:
  5.             sscl[0].append(i)
  6.     for i in cl[1]:
  7.         if x_min <= coords_x[i] <= x_max:
  8.             sscl[1].append(i)
  9.     return sscl

Télécharger

Question 10

  1. def mediane(cl):
  2.     n = len(cl[0])
  3.     if n%2 == 0:
  4.         return coords_x[cl[0][n//2]]
  5.     else:
  6.         i1 = cl[0][(n-1)//2]
  7.         i2 = cl[0][n//2]
  8.         return (coords_x[i1] + coords_x[i2]) / 2

Télécharger

Récursivité

principe de l’algorithme

On applique la méthode « diviser pour régner » :

  1. Si le cluster contient 2 ou 3 points, on calcule toutes les distances possibles :
    1. S’il n’y a qu deux points, il n’y a qu’une seule distance.
    2. S’il y a trois points, ils forment un triangle et la distance voulue est le plus petit côté de ce triangle.
  2. Sinon, on sépare le cluster en deux sous-clusters de taille moitié suivant la médiane des abscisses (ci-dessus en trait rouge).
  3. Les deux points les plus proches sont tous les deux à gauche du trait rouge, tous les deux à droite du trait rouge, ou de part et d’autre du trait rouge.
  4. On calcule récursivement le couple le plus proche à gauche, et le couple le plus proche à droite. On note d0 la plus petite distance obtenue (en vert à gauche ci-dessous).
  5. On cherche s’il existe une paire de points (M1,M2) telle que M1 est à gauche du trait rouge, M2 est à droite du trait rouge et d(M1,M2)<d0.
  6. Si on en trouve un (ou plusieurs), on renvoie la plus petite de ces distances. Sinon on renvoie d0.

Les algorithmes de cette partie sont de Serge Bays.

Question 11

  1. def gauche(cl):
  2.     med = (len(cl[0])+1) // 2
  3.     clg0 = []
  4.     for i in range(med):
  5.         clg0.append(cl[0][i])
  6.     clg1 = list(clg0)
  7.     tri(clg1,coords_y)
  8.     return [clg0, clg1]

Télécharger

droite

La fonction droite dont on aura également besoin plus loin, est

  1. def droite(cl):
  2.     med = (len(cl[0])+1) // 2
  3.     cld0= []
  4.     for i in range(med, len(cl[0])):
  5.         cld0.append(cl[0][i])
  6.     cld1 = list(cld0)
  7.     tri(cld1,coords_y)
  8.     return [cld0, cld1]

Télécharger

Question 12

M1 est à gauche de la ligne rouge, donc si M2 est en dehors de la bande verte, M2 est à droite de la seconde ligne verte : la différence entre les abscisses des deux points est supérieure à d0 et il en sera de même, a fortiori, pour la distance d(M1,M2).

De même, comme M2 est à droite de la ligne verte, il est inutile de chercher M1 à gauche de la ligne verte de gauche, car là encore d(M1,M2) serait supérieur à d0.

Question 13

Avec la fonction sous_cluster de la question 9, la bande centrale se calcule en quelques lignes de ode, et en O(n) :

  1. def bande_centrale(cl, d0):
  2.     x0 = mediane(cl)
  3.     return sous_cluster(cl, x0-d0, x0+d0)

Télécharger

Question 14

On considère le point dont l’abscisse est la médiane des abscisses (il est sur le trait rouge) et dont l’ordonnée est la moyenne des ordonnées de M1 et M2. On considère le rectangle centré sur ce point, de largeur 2×d0 et de hauteur d0 (ce rectangle contient donc M1 et M2). Si ce rectangle contenait plus de 8 points, deux d’entre eux seraient nécessairement du même côté de la ligne rouge, et à distance inférieure à d0. Ce qui est contraire à la définition de d0.

Donc il y a au maximum, dans le sens des ordonnées croissantes, 6 points entre M1 et M2 dans la bande verte (les 8 points maximum en question, moins M1 et M2).

Question 15

  1. def fusion(cl, d0):
  2.     for ind in cl[0]:
  3.         j = 0
  4.         while cl[1][j] != ind:
  5.             j = j + 1
  6.         k = j + 1
  7.         while k < len(cl[1]) and k < j + 8:
  8.             d = distance(ind, cl[1][k])
  9.             if d < d0:
  10.                 d0 = d
  11.             k = k + 1
  12.     return d0

Télécharger

Question 16

  1. def distance_minimale(cl):
  2.     if len(cl[0]) <= 3:
  3.         d = distance(cl[0][0], cl[0][1])      
  4.         if len(cl[0]) == 3:
  5.             d2 = distance(cl[0][0], cl[0][2])
  6.             if d2 < d:
  7.                 d = d2
  8.             d3 = distance(cl[0][1], cl[0][2])
  9.             if d3 < d:
  10.                 d = d3
  11.         return d
  12.     else:
  13.         x0 = mediane(cl)
  14.         cg = gauche(cl)
  15.         cd = droite(cl)
  16.         d0 = distance_minimale(cg)
  17.         dd0 = distance_minimale(cd)
  18.         if dd0 < d0:
  19.             d0 = dd0
  20.         bc = bande_centrale(cl, d0)
  21.         return fusion(bc, d0)

Télécharger

Question 17

Pour trouver les points les plus proches (et la distance minimale) du cluster de taille n, on

  • cherche la distance minimale dans le cluster de gauche, ce qui prend C(n//2) opérations élémentaires,
  • cherche également la distance minimale dans le cluster de droite, ce qui prend aussi C(n//2) opérations élémentaires,
  • choisit la distance d0 la plus petite parmi celles qu’on vient de calculer récursivement (temps constant),
  • calcule la bande centrale, en O(n) d’après la question 13,
  • fusionne avec la bande de largeur d0 autour de la médiane, en O(n) d’après la question 15.

Le tout est donc en C(n//2)+C(n//2)+O(n)+O(n)=C(n//2)+O(n) cqfd.

Question 18

On en déduit par récurrence que C(n)=O(n×log(n)). Par exemple en ne regardant que les puissances de 2, on a n=2p et on raisonne par récurrence sur p pour montrer que C(2p)≤k×p×2p :

  • si p=1, C(2)=1 alors que 2×log2(2)=2.
  • si C(2p-1)≤k(p-1)×2p-1 alors C(2p)≤2×C(2p-1)+K×2p≤2×k(p-1)×2p-1+K×2p=k×p×2p+(K×2p-k×2p)≤k×p×2p si on a choisi k≥k cqfd

Problème 2 : Composantes connexes et biconnexes

Graphes

Voici les graphes de l’énoncé, au format Nirina974 :

Gex :

(on voit qu’il n’est pas connexe puisque tous ses sommets sont d’excentricité infinie)

G’ex :

Celui-là par contre est connexe. Mais on verra qu’il n’est pas biconnexe.

BDD

Question 19

Internet est un réseau international permettant à deux machines numériques, même distantes, de communiquer entre elles (par TCP/IP par exemple). Alors que le World Wide Web est un système de navigation dans de l’hypertexte.

Par exemple les réseaux P2P, les courriels, les visioconférences utilisent Internet mais pas le web.

Question 20

Le RGPD demande, entre autres, que

  • lors de la création du compte, chaque utilisateur soit informé de l’utilisation des données qu’il postera sur le site.
  • les identifiants des usagers ne soient pas diffusés en dehors du site sans autorisation expresse.

Question 21

Pour connaître le nombre total de ressources de type cours présentes sur le site on peut faire

  1. SELECT COUNT(*) FROM ressources WHERE TYPE='cours';

Question 22

La requête

  1. SELECT ressources.titre, comptes.nom
  2.         FROM chargement
  3.                 JOIN ressources ON ressources.id=chargement.id_r
  4.                 JOIN comptes ON comptes.id=chargement.id_u
  5.         ORDER BY chargement.date DESC LIMIT 1;

Télécharger

renvoie

Machine à décalage|Alan Turing

Plus généralement, elle renvoie le (DESC) plus récent (LIMIT 1) couple formé d’un titre (de ressource) et du nom de celui qui l’a chargé, autrement dit : la dernière ressource chargée et le nom de celui qui l’a chargée.

Les corrigés suivants sont de Rafael Lopez, d’Orsay.

Question 23

  1. SELECT ch.id_u AS x, r.owner AS y, COUNT(*) AS n
  2. FROM ressources r
  3. INNER JOIN chargement ch ON ch.id_r = r.id
  4. GROUP BY ch.id_u, r.owner;

Télécharger

On peut même en faire une « fonction » :

  1. WITH Q23(r1,r2,r3) AS
  2. (SELECT ch.id_u AS x, r.owner AS y, COUNT(*) AS n
  3. FROM ressources r
  4. INNER JOIN chargement ch ON ch.id_r = r.id
  5. GROUP BY ch.id_u, r.owner
  6. )

Télécharger

Question 24

Avec la question précédente :

  1. SELECT r1 AS id1, r2 AS id2
  2. FROM Q23
  3. WHERE id1 IN (SELECT r2 FROM Q23 WHERE r1 = id2)
  4. AND id2 IN (SELECT r1 FROM Q23 WHERE r2 = id1);

Télécharger

connexes

Question 25

avec la représentation

  1. g_ex_a = [
  2.     (0,1), (0,2), (0,3), (1,0), (1,4), (1,8),
  3.     (2,0), (2,3), (3,0), (3,2), (3,6),
  4.     (4,1), (5,6), (6,3), (6,5),
  5.     (7,9), (8,1), (9,7)
  6.     ]

Télécharger

la fonction

  1. def adjacences(n,li):
  2.     la = []
  3.     for i in range(n):
  4.         la.append([])
  5.         for couple in li:
  6.             if couple[0]==i:
  7.                 la[i].append(couple[1])
  8.     return la

Télécharger

crée

  1. g_ex_b =  [[1, 2, 3], [0, 4, 8], [0, 3],
  2.     [0, 2, 6], [1], [6], [3, 5], [9], [1], [7]
  3.     ]

Télécharger

parcours

La classe Arbre est définie ainsi :

  1. class Arbre():
  2.     def __init__(self,sommet):
  3.         self.sommet = sommet
  4.         self.children = []
  5.     def add_child(self,child):
  6.         self.children.append(child)

Télécharger

et le parcours :

  1. def parcours(listes_adjacences):
  2.     n = len(listes_adjacences)
  3.     deja_vu = [False] * n
  4.    
  5.     def explorer(i):
  6.         arbre = Arbre(i)
  7.         voisins = listes_adjacences[i]
  8.         for s in voisins:
  9.             if not deja_vu[s]:
  10.                 deja_vu[s] = True
  11.                 arbre.add_child(explorer(s))
  12.         return arbre
  13.    
  14.     res = []
  15.     for i in range(n):
  16.         if not deja_vu[i]:
  17.             deja_vu[i] = True
  18.             res.append(explorer(i))
  19.     return res

Télécharger

Question 26

Le parcours renvoie une liste d’arbres (c’est-à-dire d’objets de la classe Arbre). Une telle liste modélise une forêt. Le parcours est un parcours en profondeur. Il construit la forêt couvrante que voici :

Cette forêt n’est pas connexe, mais chacune de ses composantes connexes est un arbre. Le plus petit de ces arbres est ⑦-⑨ et tout le reste forme cet arbre :

Question 27

  • La fonction démarre par un appel à la fonction len qui, en général, est en O(|V|) mais en Python elle est en O(1).
  • Idem pour la constitution de la liste deja_vu qui est en O(|V|).
  • Dans la fonction explorer, on boucle sur les voisins d’un sommet. La fonction est donc en O(|E|)
  • La boucle principale est en O(|V|) et dans cette boucle, pour chaque sommet, on boucle sur se voisins. Au total on parcourt 2 fois chaque arête et la boucle principale est en O(|E|)

La fonction parcours est donc en O(|V|)+O(|V|)+O(|E|)=O(|V|)+O(|E|)=O(|V|+|E|) cqfd.

Question 28

Un graphe est connexe si, pour tous sommets x et y du graphe, il existe un chemin joignant x à y.

Alternativement, avec le vocabulaire de SNT, un graphe est connexe si son diamètre est fini.

Question 29

Un graphe est connexe si et seulement si le nombre de ses composantes connexes est 1. Or pour chacune d’entre elles, la fonction parcours renvoie une liste des arbres couvrants, à raison d’un arbre par composante connexe. Il suffit donc, à l’instar d’un sylviculteur, de compter les arbres de la forêt pour avoir le nombe de composantes connexes du graphe. La connexité du graphe est caractérisée par l’égalité entre ce nombre, et 1 :

  1. def connexe(listes_adjacences):
  2.     return len(parcours(listes_adjacences))==1

Télécharger

Question 30

On commence par créer une fonction auxiliaire, qui à un arbre p_graphe, associe la liste de ses sommets :

  1. def liste_sommets(arbre):
  2.         liste = [arbre.sommet]
  3.         for s in arbre.children:
  4.             liste += liste_sommets(s)
  5.         return liste

Télécharger

La fonction

  1. def composantes_connexes(p_graphe):
  2.     return [liste_sommets(c) for c in p_graphe]

Télécharger

renvoie les composantes connexes du graphe, sous forme de listes de sommets.

Avec

composantes_connexes(parcours(g_ex_b))

on obtient cette description des deux composantes connexes :

[[0, 1, 4, 8, 2, 3, 6, 5], [7, 9]]

Question 31

La profondeur de récursion (hauteur de la pile des appels) est la hauteur de l’arbre couvrant construit par la fonction parcours. La fonction parcours ne peut donc pas être appliquée à un graphe trop allongé. Si le nombre de sommets est élevé il faudra augmenter la taille de la pile d’appels ou adopter un algorithme itératif.

biconnexes

Pour Internet, les graphes biconnexes sont intéressants parce qu’une panne d’un seul routeur ne suffit pas à empêcher le réseau de fonctionner.

Question 32

Si un graphe est biconnexe, alors pour tous sommets x et y, il existe un cycle comprenant x et y. Ce cycle comprend lui-même deux chemins, joignant x et y. A fortiori il y a (au moins) un chemin allant de x à y : le graphe est connexe.

Question 33

Le graphe de l’énoncé est connexe mais pas biconnexe (voir question 34 ci-après), et répond donc à la question. Un exemple plus simple est le graphe ⓪-①-② qui est connexe (rayon 1, diamètre 2, centre ①) mais ne comprend aucun cycle, donc ⓪ et ① ne sont dans aucun cycle propre.

Question 34

Avec Nirina974 il est aisé de voir quels sont les points d’articulation du graphe : il suffit d’enlever (puis remettre) l’un après l’autre les sommets et regarder si le graphe est encore connexe, ou pas (cela se voit à la couleur, uniformément rouge si le graphe n’est plus connexe). Les points d’articulation sont donc

  • le sommet 4 :
  • le sommet 6 :
  • le sommet 8 :
  • le sommet 11 :

G’ex possède donc 4 points d’articulation. On en déduira par la suite, qu’il n’est pas biconnexe.

Question 35

Supposons que le graphe G possède un point d’articulation a. Alors il existe deux sommets x et y tels que tout chemin de x à y passe par a. Il ne peut donc pas exister de cycle contenant x et y et G n’est pas biconnexe.

Question 36

  1. Si G n’a pas de point d’articulation, alors G est connexe et il existe une chaîne joignant x à y.
  2. S’il n’existait aucun cycle élémentaire contenant x0 et x1 alors x0 serait un point d’articulation.
  3. Supposons qu’il existe un cycle élémentaire contenant x0 et xi, et que ce cycle ne passe pas par xi+1 (sinon on aurait fini). Alors il existe un autre cycle passant par x0 et xi+1 (sinon x1 serait un point d’articulation).
  4. Par récurrence sur i, on en déduit qu’il existe un cycle élémentaire passant par x et y : G est biconnexe.

Question 37

On effectue un parcours en profondeur, à partir du sommet à tester. Cela construit un arbre couvrant de G. Le sommet de départ est d’articulation si et seulement si plusieurs branches de l’arbre en partent.

Question 38

On boucle sur les |V| sommets du graphe. Pour chacun d’entre eux, on effectue un parcours en profondeur - en O(|V|+|E|) - pour construire un arbre couvrant, puis on compte les branches de l’arbre issues du sommet courant. S’il y a plus d’une branche, l’algorithme s’arrête sur la réponse non (le graphe n’est pas biconnexe). Sinon on continue à boucler, et si à la fin - en O(|V|²+|E|×|V|) - tous les arbres couvrants sont à un seul tronc, le graphe est biconnexe.

algorithme

parcours

Voixi le script de l’énoncé, avec calcul du préfixe :

  1. def parcours(listes_adjacences):
  2.     n = len(listes_adjacences)
  3.     deja_vu = [False] * n
  4.     prefixe = [-1] * n
  5.     count = 1
  6.    
  7.     def explorer(i):
  8.         nonlocal count
  9.         prefixe[i] = count
  10.         count += 1
  11.         arbre = Arbre(i)
  12.         voisins = listes_adjacences[i]
  13.         for s in voisins:
  14.             if not deja_vu[s]:
  15.                 deja_vu[s] = True
  16.                 arbre.add_child(explorer(s))
  17.         return arbre
  18.    
  19.     deja_vu[0] = True
  20.     return explorer(0), prefixe

Télécharger

Question 39

Le parcours du graphe à partir de ⓪ donne l’arbre couvrant suivant :

et la liste prefixe suivante :

[1, 2, 3, 10, 11, 5, 4, 8, 9, 12, 6, 7, 13]

Ce qui correspond à ces préfixes :

0 1 2 3 4 5 6 7 8 9 10 11 12
1 2 3 10 11 5 4 8 9 12 6 7 13

Question 40

Si

prefixe[i] < prefixe[j]

cela signifie que j a été placé dans l’arbre couvrant, plus tard que i. Donc j est plus « haut » que i dans l’arbre : j est un descendant de i cqfd.

Question 41

Pour rappel, voici le graphe :

et ses ord (prefixe minimal parmi les voisins des descendants) :

On constate que

  • 9, qui est le fils de 4, est d’ordre 11 qui est le préfixe de 4.
  • 11, qui est un des fils de 6, est d’ordre 4 qui est le préfixe de 6.
  • 7, qui est le fils de 11, est d’ordre 7 qui est le préfixe de 11.
  • 3, qui est un des fils de 8, est d’ordre 9 qui est le préfixe de 8.

En dehors de ces sommets qui sont les points d’articulation, seule la racine 0 a une propriété similaire : son fils 1 est d’ordre 1 qui est le préfixe de 0.

Calcul de ord

On suppose dans la suite qu’on dispose d’une fonction de ce genre qui soit en O(|V|+|E|) :

  1. def D(s):
  2.     desc = set([s.sommet])
  3.     for t in s.children:
  4.         desc = desc.union(D(t))
  5.     return desc
  6.  
  7. def calcule_ord(listes_adjacences):
  8.  
  9.     def V(S):
  10.         vois = set([])
  11.         for s in S:
  12.             vois = vois.union(set(listes_adjacences[s]))
  13.         return vois
  14.  
  15.     def ordre(s):
  16.         return min([prefixe[j] for j in V(D(s))])
  17.  
  18.     ord = [0] * len(listes_adjacences)
  19.  
  20.     def DFS(arbre,s,vus=[]):
  21.         vus.append(s.sommet)
  22.         ord[s.sommet] = ordre(s)
  23.         for t in s.children:
  24.             if t.sommet not in vus:
  25.                 vus = DFS(arbre,t,vus)
  26.         return vus
  27.    
  28.     a,prefixe = parcours(listes_adjacences)
  29.     DFS(a,a)
  30.    
  31.     return ord

Télécharger

Avec le graphe de l’énoncé cette fonction renvoie

[1, 1, 1, 9, 9, 1, 1, 7, 7, 11, 4, 4, 9]

Question 42

Une fonction qui correspond à la demande est

  1. def points_articulation(listes_adjacences):
  2.     arbre,prefixes = parcours(listes_adjacences)
  3.     ord = calcule_ord(listes_adjacences)
  4.     pa = []
  5.    
  6.     def parcours_prefixe(arbre,s,vus=[]):
  7.         nonlocal pa
  8.         i = s.sommet
  9.         vus.append(i)
  10.         if any(ord[t.sommet]==prefixe[i] for t in s.children):
  11.             pa.append(i)
  12.         for t in s.children:
  13.                 if t.sommet not in vus:
  14.                     vus = parcours_prefixe(arbre,t,vus)
  15.         return vus
  16.     parcours_prefixe(arbre,arbre)
  17.     if len(arbre.children)==1:
  18.         pa.remove(0)
  19.     return pa

Télécharger

Comme elle est basée sur un parcours en profondeur de l’arbre couvrant, elle est en O(|V|+|E|).

Question 43

Les composantes biconnexes du graphe de l’énoncé sont

  • 0,1,2,5,6,10
  • 3,4,8
  • 7,8,11
  • 4,9
  • 6,11
  • 8,12

Soit 6 composantes biconnexes.

Question 44

Comme chaque point d’articulation sépare deux composantes biconnexes, on est tenté de regarder à quoi ressemble le graphe auquel on a enlevé les points d’articulation :

On voit qu’il y a 5 composantes connexes et chacune correspond à une composante biconnexe du graphe de départ. Où est passée la 6e composante biconnexe ?

En fait l’arête 6-11 (une composante biconnexe) joint deux points d’articulation, elle a donc disparu lorsque ses extrémités ont été supprimées.

On suggère donc cet algorithme :

  • calculer les points d’articulation
  • calculer le graphe privé des points d’articulation
  • pour chacune des composantes connexes de ce graphe, remettre le point d’articulation qui y était : cela donne une composante biconnexe du graphe de départ
  • chercher les arêtes joignant deux points d’articulation : ce sont elles aussi des composantes biconnexes.

Cet algorithme est de Hopcroft et Tarjan en 1973 :


[1tout du moins, ceux qui sont normalisés. Sinon c’est plus compliqué.


Commentaires