TP — Parcours de graphes

Travaux pratiques · MPSI (tronc commun) · 2021-2022 · Python

Cours : Parcours en profondeur récursif

Principe

Le but de ce TP est de pratiquer les parcours vus en classe. Pour cela, on va suivre assez fidèlement le poly du cours (voir la partie Parcours du cours sur les graphes).

L'objectif n'est pas de réécrire un parcours ex nihilo mais de savoir modifier les parcours vus en classe pour répondre à des questions.

On va donc faire beaucoup de copier-coller en modifiant une ligne ou deux dans le parcours vu en classe.

Graphes exemples

On va considérer ici des graphes donnés sous la forme de listes d'adjacences.

On donne quelques exemples de graphes qui nous serviront à tester les fonctions demandées et qui correspondent aux graphes présentés en classe :

• complet(n) qui renvoie le graphe complet à n sommets \(K_n\) ;
• cycle(n) qui renvoie un cycle non orienté de n sommets et cycle_oriente(n) qui renvoie le cycle orienté dans l'ordre croissant 0 -> 1 -> 2 ... -> 0 ;
• grille(n, d) qui renvoie la grille de dimension \(d\) où les coordonnées sont dans \([\![0; n-1]\!]\). On donne également deux fonctions vecteur_vers_nombre et nombre_vers_vecteur permettant de passer d'un élément de \([\![0; n-1]\!]^d\) à son identifiant dans \([\![0; n^d-1]\!]\).

On considère également un graphe pseudo-aléatoire :

• graphe_alea(germe, n, p) qui renvoie un graphe non orienté pseudo-aléatoire sur \([\![0; n-1]\!]\) en utilisant le germe passé en argument pour que deux appels avec les mêmes valeurs produisent le même graphe (comme les seeds présentes dans certains jeux). Pour déterminer si \(y \in v_+(x)\) on génère aléatoirement un nombre \(r\) dans \([0; 1[\) et on vérifie si \(r \le p\). Cela revient à donner une probabilité \(p\) à chaque arête.

Attention les fonctions suivantes ont été écrites de manière compacte pour ne pas prendre trop de place dans l'énoncé. Il n'est pas nécessaire de comprendre leur fonctionnement.

def complet(n):
    return [ [i for i in range(n) if i != j] for j in range(n) ]

def cycle(n):
    return [ [ (i+1) % n, (i-1) % n ] for i in range(n) ]

def cycle_oriente(n):
    return [ [ (i+1) % n ] for i in range(n) ]

def vecteur_vers_nombre(v, n):
    # prend un vecteur [v0, .., v(d-1)] dans [|0;n-1|]^d
    # et renvoie un entier entre 0 et n^d - 1 l'identifiant uniquement
    return sum( v[i] * n ** i for i in range(len(v)) )

def nombre_vers_vecteur(N, n, d):
    # réalise l'opération inverse
    return [ (N // n**k) % n for k in range(d) ]

def dist(v1, v2):
    return sum( abs(v1[i]-v2[i]) for i in range(len(v1)) )

def grille(n, d):
    return [ [ k for k in range(n**d)
                 if dist(nombre_vers_vecteur(k,n,d), nombre_vers_vecteur(i,n,d)) == 1 ]
             for i in range(n**d) ]

def hypercube(n):
    return grille(2, n)

import random
def graphe_alea(germe, n, p):
    random.seed(germe)
    ladj = [ [] for _ in range(n) ]
    for i in range(n):
        for j in range(i+1,n):
            if random.random() <= p:
                ladj[i].append(j)
                ladj[j].append(i)
    return ladj

>>> grille(3, 2)
[[1, 3],
 [0, 2, 4],
 [1, 5],
 [0, 4, 6],
 [1, 3, 5, 7],
 [2, 4, 8],
 [3, 7],
 [4, 6, 8],
 [5, 7]]
>>> graphe_alea(42, 7, 0.25)
[[2, 4], [3, 5, 6], [0, 4, 5], [1, 5], [0, 2, 6], [1, 2, 3], [1, 4]]

Premiers pas avec le parcours en profondeur

On redonne ici le programme vu en classe pour le parcours en profondeur récursif.

INCONNU = 0
DECOUVERT = 1
TRAITE = 2

def parcours(ladj, x, etat):
    if etat[x] != TRAITE:
        print(x)
        for y in ladj[x]:
            if etat[y] == INCONNU:
                etat[y] = DECOUVERT
                parcours(ladj, y, etat)
        etat[x] = TRAITE

def lance_parcours(ladj, x):
    # État initial inconnu pour tous
    etat = [ INCONNU ] * len(ladj)
    etat[x] = DECOUVERT
    parcours(ladj, x, etat)

Pour bien comprendre ce qu'on vous demande, il faut imaginer que parcours est une sorte de boucle for qui va parcourir un graphe en partant d'un sommet.

Ainsi, il faut comprendre le programme précédent comme :

def lance_parcours(ladj, x):
    for y in accessibles depuis x dans ladj:
        print(y)

La fonction récursive va s'appeler autant de fois que d'itérations dans la pseudo-boucle précédente et etat n'est là que pour permettre à cette fonction de ne pas traiter trop de fois les sommets.

Dans la suite, les fonctions qu'on vous demande de faire vont correspondre à un pseudo-code :

def mafonction(ladj, x):
    for y in accessibles depuis x dans ladj:
        ## TRAITEMENT DU SOMMET y
    ## TRAITEMENT DES RÉSULTATS
    return valeur calculée

qui sera retraduit sous la forme suivante :

def parcours_mafonction(ladj, x, etat):
    if etat[x] != TRAITE:
        ## TRAITEMENT DU SOMMET x
        for y in ladj[x]:
            if etat[y] == INCONNU:
                etat[y] = DECOUVERT
                parcours_mafonction(ladj, y, etat)
        etat[x] = TRAITE

def mafonction(ladj, x):
    # État initial inconnu pour tous
    etat = [ INCONNU ] * len(ladj)
    etat[x] = DECOUVERT
    parcours_mafonction(ladj, x, etat)
    ## TRAITEMENT DES RÉSULTATS
    return valeur calculée

Il est possible qu'on souhaite rajouter des arguments à la fonction réalisant le parcours : exactement comme lorsqu'on rajoute des variables qui seront mises à jour dans une boucle.

Compter les sommets traités

On va modifier le parcours précédent pour écrire une fonction compte_traites(ladj, x) qui renvoie le nombre de sommets traités dans un parcours en profondeur du graphe ladj en partant du sommet x. Vous ne devez modifier ces fonctions qu'en rajoutant du code dans la partie indiquée.

Question 1

INCONNU = 0
DECOUVERT = 1
TRAITE = 2

def parcours_compte(ladj, x, etat):
    if etat[x] != TRAITE:
        for y in ladj[x]:
            if etat[y] == INCONNU:
                etat[y] = DECOUVERT
                parcours_compte(ladj, y, etat)
        etat[x] = TRAITE

def compte_traites(ladj, x):
    # État initial inconnu pour tous
    etat = [ INCONNU ] * len(ladj)
    etat[x] = DECOUVERT
    parcours_compte(ladj, x, etat)

Corrigé

INCONNU = 0
DECOUVERT = 1
TRAITE = 2

def parcours_compte(ladj, x, etat):
    if etat[x] != TRAITE:
        for y in ladj[x]:
            if etat[y] == INCONNU:
                etat[y] = DECOUVERT
                parcours_compte(ladj, y, etat)
        etat[x] = TRAITE

def compte_traites(ladj, x):
    # État initial inconnu pour tous
    etat = [ INCONNU ] * len(ladj)
    etat[x] = DECOUVERT
    parcours_compte(ladj, x, etat)
    compte = 0
    for i in etat:
        if i:
            compte += 1
    return compte

Tests :

from civ import *
init()
test(compte_traites, cycle(5), 0, 5) # parcours de C5 en partant de 0
test(compte_traites, grille(3, 2), 0, 9) # parcours de G32 en partant de 0
test(compte_traites, graphe_alea(42, 10, 0.05), 0, 4)
test(compte_traites, graphe_alea(42, 10, 0.1), 0, 9)
valide()

Si \(G\) est un graphe non orienté, on a vu qu'un parcours depuis \(x\) permettait d'explorer la composante connexe de \(x\), c'est-à-dire \(\overline{x}\) les sommets accessibles depuis \(x\).

On en déduit que \(G\) est connexe \(\iff \forall x \in S, \overline{x} = S\).

Ici, il suffit de vérifier que tous les sommets sont traités après un parcours depuis n'importe quel sommet.

On va donc en déduire une fonction connexe(ladj) qui renvoie un booléen indiquant si un graphe non orienté donné en liste d'adjacence est connexe.

ATTENTION pas la peine de recoder un parcours, on peut utiliser la fonction précédente.

Question 2

def connexe(ladj):

Corrigé

def connexe(ladj):
    return compte_traites(ladj, 0) == len(ladj)

Tests :

from civ import *
init()
test(connexe, cycle(5), True)
test(connexe, grille(3, 2), True)
test(connexe, graphe_alea(42, 10, 0.05), False)
test(connexe, graphe_alea(42, 10, 0.1), False)
test(connexe, graphe_alea(42, 10, 0.25), True)
valide()

Dans le dernier exemple de test, on peut voir que la connexité d'un graphe aléatoire dépend de la probabilité d'existence d'une arête. La dernière partie de ce TP propose d'explorer cette propriété.

Composantes connexes

Pour obtenir les composantes connexes d'un graphe, on va commencer par modifier le parcours pour qu'il renvoie la liste des sommets traités. Pour cela, on va rajouter une liste en paramètre et y ajouter les sommets traités.

Écrire une fonction composante(ladj, x) qui renvoie la liste des sommets de la composante connexe de x triés dans l'ordre croissant.

Pour trier un tableau t en Python, il suffit d'appeler t.sort(). Cette fonction ne renvoie rien, elle va modifier t en place.

Question 3

INCONNU = 0
DECOUVERT = 1
TRAITE = 2

def parcours_comp(ladj, x, etat, comp):
    if etat[x] != TRAITE:
        for y in ladj[x]:
            if etat[y] == INCONNU:
                etat[y] = DECOUVERT
                parcours_comp(ladj, y, etat, comp)
        etat[x] = TRAITE

def composante(ladj, x):
    # État initial inconnu pour tous
    etat = [ INCONNU ] * len(ladj)
    etat[x] = DECOUVERT

Corrigé

INCONNU = 0
DECOUVERT = 1
TRAITE = 2

def parcours_comp(ladj, x, etat, comp):
    if etat[x] != TRAITE:
        comp.append(x)
        for y in ladj[x]:
            if etat[y] == INCONNU:
                etat[y] = DECOUVERT
                parcours_comp(ladj, y, etat, comp)
        etat[x] = TRAITE

def composante(ladj, x):
    # État initial inconnu pour tous
    etat = [ INCONNU ] * len(ladj)
    etat[x] = DECOUVERT
    comp = []
    parcours_comp(ladj, x, etat, comp)
    comp.sort()
    return comp

Tests :

from civ import *
init()
test(composante, cycle(5), 0, [0,1,2,3,4])
test(composante, graphe_alea(42, 10, 0.1), 0, [0, 1, 2, 3, 5, 6, 7, 8, 9])
valide()

Pour obtenir toutes les composantes connexes, il suffit de relancer le parcours depuis le prochain sommet non traité et d'ajouter la composante obtenue à la liste des composantes.

Écrire une fonction composantes(ladj) qui renvoie la liste des composantes connexes du graphe ladj où les composantes connexes sont triées dans l'ordre croissant de leur plus petit élément (normalement, c'est ainsi que vous devriez les calculer naturellement). On appellera parcours_comp et non composante pour conserver le même tableau etat.

Question 4

def composantes(ladj):

Corrigé

def composantes(ladj):
    n = len(ladj)
    etat = [ INCONNU ] * n
    comps = []
    for x in range(n):
        if etat[x] == INCONNU:
            comp = []
            etat[x] = DECOUVERT
            parcours_comp(ladj, x, etat, comp)
            comp.sort()
            comps.append(comp)
    return comps

Tests :

from civ import *
init()
test(composantes, cycle(5), [[0,1,2,3,4]])
test(composantes, graphe_alea(42, 10, 0.1), [[0, 1, 2, 3, 5, 6, 7, 8, 9], [4]])
test(composantes, graphe_alea(42, 10, 0.05), [[0, 1, 2, 5], [3], [4], [6, 9], [7], [8]])
valide()

Arbre du parcours et chemins

Comme vu dans le cours, il est possible de définir des liens de parenté entre deux sommets. On notera parent[y] = x quand c'est l'arête \(x \rightarrow y\) qui a permis de découvrir \(y\).

Question 5

Écrire une fonction arbre(ladj, x) qui renvoie le tableau parent ainsi défini. Quand un sommet n'a pas de parent défini, on mettra None comme valeur. En particulier, comme on part de x, on a forcément parent[x] == None.

INCONNU = 0
DECOUVERT = 1
TRAITE = 2

def parcours_parent(ladj, x, etat, parent):
    if etat[x] != TRAITE:
        etat[x] = TRAITE

def arbre(ladj, x):
    # État initial inconnu pour tous
    etat = [ INCONNU ] * len(ladj)
    etat[x] = DECOUVERT

Corrigé

INCONNU = 0
DECOUVERT = 1
TRAITE = 2

def parcours_parent(ladj, x, etat, parent):
    if etat[x] != TRAITE:
        for y in ladj[x]:
            if etat[y] == INCONNU:
                etat[y] = DECOUVERT
                parent[y] = x
                parcours_parent(ladj, y, etat, parent)
        etat[x] = TRAITE

def arbre(ladj, x):
    # État initial inconnu pour tous
    etat = [ INCONNU ] * len(ladj)
    etat[x] = DECOUVERT
    parent = [ None ] * len(ladj)
    parcours_parent(ladj, x, etat, parent)
    return parent

Tests :

from civ import *
init()
test(arbre, cycle(5), 0, [None, 0, 1, 2, 3])
test(arbre, graphe_alea(42, 10, 0.1), 0, [None, 2, 0, 6, None, 1, 9, 3, 0, 8])
valide()

Question 6

Écrire une fonction chemin(y, parent) qui prend un sommet y dans la composante connexe de x, un tableau parent rendu par la fonction précédente et renvoie un chemin de x vers y donné sous la forme d'une liste de sommets.

Note : on pourra utiliser t.reverse() pour renverser l'ordre des éléments dans un tableau. Car ici, c'est plus simple de remplir en mettant y en premier dans un premier temps.

def chemin(y, parent):

Corrigé

def chemin(y, parent):
    l = [ y ]
    while parent[y] != None:
        y = parent[y]
        l.append(y)
    l.reverse()
    return l

Tests :

from civ import *
init()
test(chemin, 3, [None, 0, 1, 2, 3], [0, 1, 2, 3])
test(chemin, 5, [None, 2, 0, 6, None, 1, 9, 3, 0, 8], [0, 2, 1, 5])
valide()

Affichage du parcours sur une grille

Cette partie est optionnelle.

Si on applique le parcours initial au graphe d'une grille, ce n'est pas très lisible car on obtient le numéro d'un vecteur et pas le vecteur lui-même.

lance_parcours(grille(3, 2), 0)

va afficher :

0
1
2
5
4
3
6
7
8

En utilisant la fonction nombre_vers_vecteur(5, 3, 2) on peut obtenir l'étiquette [2, 1] à la place du nombre 5, ce qui est plus lisible.

Question 7

Modifiez le parcours ci-dessous pour définir une fonction parcours_grille(n, v) qui, étant donné un tableau v représentant un vecteur, effectue l'affichage des vecteurs rencontrés. Par exemple, parcours_grille(3, [1,2]) devrait afficher :

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

Rappel, le graphe \(G_{3,2}\) correspond à la représentation :

ATTENTION ici on vous recommande de renommer la fonction parcours pour que connexe continue de fonctionner.

parcours_grille(3, [1,2])

Corrigé

def parcours2(ladj, x, n, d, etat):
    if etat[x] != TRAITE:
        print(nombre_vers_vecteur(x, n, d))
        for y in ladj[x]:
            if etat[y] == INCONNU:
                etat[y] = DECOUVERT
                parcours2(ladj, y, n, d, etat)
        etat[x] = TRAITE

def parcours_grille(n, v):
    d = len(v)
    g = grille(n, d)
    x = vecteur_vers_nombre(v, n)
    etat = [ INCONNU ] * len(g)
    etat[x] = DECOUVERT
    parcours2(g, x, n, d, etat)

parcours_grille(3, [1,2])

Question 8

Ici, on a effectué un affichage lorsqu'un sommet est traité, mais on veut plutôt indiquer les arêtes suivies. Modifiez le parcours précédent pour afficher les arêtes d'un parcours de grille. L'appel à parcours_grille(3, [1,2]) devra afficher :

[1, 2] -> [1, 1]
[1, 1] -> [1, 0]
[1, 0] -> [0, 0]
[0, 0] -> [0, 1]
[0, 1] -> [0, 2]
[1, 0] -> [2, 0]
[2, 0] -> [2, 1]
[2, 1] -> [2, 2]

parcours_grille(3, [1,2])

Corrigé

def affiche(x, y, n, d):
    print(nombre_vers_vecteur(x, n, d),
          '->',
          nombre_vers_vecteur(y, n, d))

def parcours3(ladj, x, n, d, etat):
    if etat[x] != TRAITE:
        for y in ladj[x]:
            if etat[y] == INCONNU:
                affiche(x, y, n, d)
                etat[y] = DECOUVERT
                parcours3(ladj, y, n, d, etat)
        etat[x] = TRAITE

def parcours_grille(n, v):
    d = len(v)
    g = grille(n, d)
    x = vecteur_vers_nombre(v, n)
    etat = [ INCONNU ] * len(g)
    etat[x] = DECOUVERT
    parcours3(g, x, n, d, etat)

parcours_grille(3, [1,2])

Rappel il est possible d'afficher une matrice de nombres, c'est-à-dire un tableau de tableaux de nombres tous de même longueur, comme une image avec la commande suivante :

import matplotlib.pyplot as plt
plt.imshow( [ [ 1, 2, 3], [0, 1, 2] ] )

Attention les lignes sont affichées comme en mathématiques de haut en bas.

Question 9

Écrire une fonction parcours_grille2d(n, v) qui effectue un parcours de \(G_{n,2}\) à partir du vecteur \(v\) et crée une matrice M où M[i][j] est le numéro de [i,j] dans l'ordre du parcours.

Par exemple, sur la grille \(G_{3,2}\) on a vu que les sommets traités depuis [1,2] sont : [1, 2], [1, 1], [1, 0], [0, 0], [0, 1], [0, 2], [2, 0], [2, 1], [2, 2].

Ce qui correspond à une matrice d'ordre [ [ 3, 4, 5 ], [ 2, 1, 0 ], [6, 7, 8] ] et donc à l'affichage :

plt.imshow([ [ 3, 4, 5 ], [ 2, 1, 0 ], [6, 7, 8] ])

Remarque pour avoir le numéro du sommet, on utilisera une liste de sommets traites dont la longueur indiquera le numéro.

parcours_grille2d(20, [10, 10])

Corrigé

def parcours4(ladj, x, n, etat, traites, mat):
    if etat[x] != TRAITE:
        a, b = nombre_vers_vecteur(x, n, 2)
        mat[a][b] = len(traites)
        traites.append(x)
        for y in ladj[x]:
            if etat[y] == INCONNU:
                etat[y] = DECOUVERT
                parcours4(ladj, y, n, etat, traites, mat)
        etat[x] = TRAITE

def parcours_grille2d(n, v):
    g = grille(n, 2)
    x = vecteur_vers_nombre(v, n)
    etat = [ INCONNU ] * len(g)
    etat[x] = DECOUVERT
    mat = [ ]
    for _ in range(n):
        l = []
        for _ in range(n):
            l.append( -1 )
        mat.append(l)
    parcours4(g, x, n, etat, [], mat)
    plt.imshow(mat)

parcours_grille2d(20, [10, 10])

L'appel précédent doit afficher :

Propriétés du graphe aléatoire

Cette partie est optionnelle.

On va explorer ici des propriétés du graphe aléatoire en fonction du nombre de sommets et de la probabilité d'avoir une arête.

Question 10

Écrire une fonction table_connexe(germe, n, N) qui renvoie un tableau t de N cases telle que t[i] contient un booléen indiquant si le graphe graphe_alea(germe, n, i/N) est connexe.

ATTENTION pour pouvoir utiliser connexe, il faut s'assurer que vous n'avez pas redéfini la fonction parcours qu'elle appelle.

def table_connexe(germe, n, N):

Corrigé

def table_connexe(germe, n, N):
    return [ connexe(graphe_alea(germe, n, i/N)) for i in range(N) ]

Tests :

from civ import *
init()
test(table_connexe, 42, 10, 10, [False, False, False, True, True, True, True, True, True, True])
valide()

On remarque que les tableaux renvoyés par la fonction précédente semblent avoir tous la même forme : une suite de False suivie d'une suite de True. Cela signifierait qu'il existe une probabilité \(p\) telle que les graphes sont connexes avec une probabilité \(p' \ge p\) et non connexes avec \(p' < p\).

En admettant que ce soit le cas, pour obtenir une estimation de \(p\), on peut réaliser une dichotomie.

Écrire une fonction proba_seuil(germe, n, eps) qui renvoie à eps près la probabilité seuil.

Question 11

def proba_seuil(germe, n, eps):

Corrigé

def proba_seuil(germe, n, eps):
    a, b = 0, 1
    while b-a > eps:
        m = (a+b)/2
        if connexe(graphe_alea(germe, n, m)):
            b = m
        else:
            a = m
    return (a+b)/2

Tests :

p = proba_seuil(42, 20, 0.01)
assert( abs(p-0.214) < 0.01 )

On peut tracer un graphe indiquant, pour un germe donné, ici 42, les probabilités seuils :

sommets = []
proba = []
for n in range(10, 100):
    sommets.append(n)
    proba.append(proba_seuil(42, n, 0.001))
plt.plot( sommets, proba )

Le graphe précédent est très bruité, afin de le lisser, écrire une fonction proba_seuil_lisse(n) qui moyenne la fonction précédente pour les germes 0 à 99.

Question 12

def proba_seuil_lisse(n):

Corrigé

def proba_seuil_lisse(n):
    s = 0
    N = 100
    for k in range(N):
        s += proba_seuil(k, n, 0.001)
    return s / N

sommets = []
proba = []
for n in range(10, 50):
    sommets.append(n)
    proba.append(proba_seuil_lisse(n))
plt.plot( sommets, proba )