TP Python – Matrice d’adjacence et chemins en Python

BTS SIO SISR 1re année – Mathématiques pour l'informatique – S16

Note

Comment ce TP fonctionne. Chaque exercice a un éditeur Python intégré à la page (il s'exécute dans ton navigateur, rien à installer). Avant de lancer, écris sur ta feuille ce que tu anticipes (« J'anticipe »). Puis lance et compare. Le bouton Valider exécute des tests : un test réussi ne dispense pas de comprendre pourquoi.

Un graphe à \(n\) sommets numérotés de 0 à \(n - 1\) est représenté par sa matrice d'adjacence (liste de listes de 0 et de 1).

Exercice A – Matrice d'adjacence

Écris matrice_adjacence(n, arcs) (liste de couples), successeurs(m, i) (liste triée) et demi_degres(m) qui renvoie (exterieurs, interieurs).

J'anticipe. Pour les arcs [(0, 1), (0, 2), (1, 3)] avec n = 4, écris la matrice puis les demi-degrés.

###

m = matricepy-undadjacence(4, [(0, 1), (0, 2), (1, 3)])bksl-nlassert m == [[0, 1, 1, 0], [0, 0, 0, 1], [0, 0, 0, 0], [0, 0, 0, 0]]bksl-nlassert successeurs(m, 0) == [1, 2] and successeurs(m, 3) == []bksl-nlassert demipy-unddegres(m) == ([2, 1, 0, 0], [0, 1, 1, 1])bksl-nlg = matricepy-undadjacence(6, [(0, 1), (0, 2), (1, 3), (2, 3), (2, 4), (3, 5), (4, 5)])bksl-nlassert demipy-unddegres(g) == ([2, 1, 2, 1, 1, 0], [0, 1, 1, 2, 1, 2])bksl-nlassert matricepy-undadjacence(2, []) == [[0, 0], [0, 0]]bksl-nlbksl-nl ∞/∞

def matricepy-undadjacence(n, arcs):bksl-nl m = []bksl-nl for i in range(n):bksl-nl m.append([0] py-str n)bksl-nl for (a, b) in arcs:bksl-nl pass # À compléter : mettre 1 dans la case (a, b)bksl-nl return mbksl-nlbksl-nldef successeurs(m, i):bksl-nl liste = []bksl-nl for j in range(len(m)):bksl-nl # À compléter : ajouter j si m[i][j] vaut 1bksl-nl passbksl-nl return listebksl-nlbksl-nldef demipy-unddegres(m):bksl-nl n = len(m)bksl-nl ext = []bksl-nl inte = []bksl-nl for i in range(n):bksl-nl ext.append(0) # À compléter : somme de la ligne ibksl-nl for j in range(n):bksl-nl s = 0bksl-nl for i in range(n):bksl-nl pass # À compléter : ajouter m[i][j]bksl-nl inte.append(s)bksl-nl return (ext, inte)bksl-nlbksl-nl

Exercice B – Compter les chemins

Écris produit(a, b) et nb_chemins(m, p, i, j) (nombre de chemins de longueur p de i à j, par la puissance p de la matrice).

Je comprends. Que renvoie nb_chemins(m, 0, i, j) ?

###

g = [[0, 1, 1, 0, 0, 0], [0, 0, 0, 1, 0, 0], [0, 0, 0, 1, 1, 0], [0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 0, 0]]bksl-nlassert nbpy-undchemins(g, 2, 0, 3) == 2bksl-nlassert nbpy-undchemins(g, 3, 0, 5) == 3bksl-nlassert nbpy-undchemins(g, 2, 2, 5) == 2bksl-nlassert nbpy-undchemins(g, 4, 0, 5) == 0bksl-nlassert nbpy-undchemins(g, 0, 1, 1) == 1 and nbpy-undchemins(g, 0, 1, 2) == 0bksl-nlc = [[0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1], [1, 0, 0, 0]]bksl-nlassert nbpy-undchemins(c, 4, 0, 0) == 1 and nbpy-undchemins(c, 2, 0, 2) == 1 and nbpy-undchemins(c, 3, 0, 2) == 0bksl-nlbksl-nl ∞/∞

def produit(a, b):bksl-nl n = len(a)bksl-nl resultat = []bksl-nl for i in range(n):bksl-nl ligne = []bksl-nl for j in range(n):bksl-nl s = 0bksl-nl for k in range(n):bksl-nl # À compléter : ajouter a[i][k] py-str b[k][j]bksl-nl passbksl-nl ligne.append(s)bksl-nl resultat.append(ligne)bksl-nl return resultatbksl-nlbksl-nldef nbpy-undchemins(m, p, i, j):bksl-nl n = len(m)bksl-nl r = []bksl-nl for a in range(n):bksl-nl r.append([1 if a == b else 0 for b in range(n)]) # matrice identitébksl-nl for py-und in range(p):bksl-nl pass # À compléter : multiplier r par mbksl-nl return r[i][j]bksl-nlbksl-nl

Exercice C – Détecter un circuit

Écris a_un_circuit(m) : le graphe a un circuit si et seulement si la puissance \(n\) de m (\(n\) = nombre de sommets) n'est pas la matrice nulle. Justifie-le dans un commentaire : un chemin de longueur \(n\) passe par \(n + 1\) sommets.

###

assert apy-undunpy-undcircuit([[0, 1, 0, 0], [0, 0, 1, 0], [1, 0, 0, 1], [0, 0, 0, 0]]) is Truebksl-nlassert apy-undunpy-undcircuit([[0, 1, 1, 0, 0, 0], [0, 0, 0, 1, 0, 0], [0, 0, 0, 1, 1, 0], [0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 0, 0]]) is Falsebksl-nlassert apy-undunpy-undcircuit([[1]]) is Truebksl-nlassert apy-undunpy-undcircuit([[0]]) is Falsebksl-nlassert apy-undunpy-undcircuit([[0, 1], [1, 0]]) is Truebksl-nlassert apy-undunpy-undcircuit([[0, 1], [0, 0]]) is Falsebksl-nlbksl-nl ∞/∞

def produit(a, b):bksl-nl n = len(a)bksl-nl resultat = []bksl-nl for i in range(n):bksl-nl ligne = []bksl-nl for j in range(n):bksl-nl s = 0bksl-nl for k in range(n):bksl-nl s = s + a[i][k] py-str b[k][j]bksl-nl ligne.append(s)bksl-nl resultat.append(ligne)bksl-nl return resultatbksl-nlbksl-nldef apy-undunpy-undcircuit(m):bksl-nl """Un chemin de longueur n passe par n + 1 sommets : l'un d'eux se répète, donc il y a un circuit."""bksl-nl n = len(m)bksl-nl p = mbksl-nl for py-und in range(n - 1):bksl-nl pass # À compléter : calculer la puissance n de m (p = p py-str m)bksl-nl for ligne in p:bksl-nl for x in ligne:bksl-nl pass # À compléter : renvoyer True si un coefficient est non nulbksl-nl return Falsebksl-nlbksl-nl

Exercice D – Fermeture transitive

Écris fermeture(m) : somme booléenne de \(M, M^{[2]}, \dots, M^{[n-1]}\) (produit booléen : ou de et).

###

g = [[0, 1, 1, 0, 0, 0], [0, 0, 0, 1, 0, 0], [0, 0, 0, 1, 1, 0], [0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 0, 0]]bksl-nlassert fermeture(g) == [[0, 1, 1, 1, 1, 1], [0, 0, 0, 1, 0, 1], [0, 0, 0, 1, 1, 1], [0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 0, 0]]bksl-nlassert fermeture([[0, 1, 0, 0], [0, 0, 1, 1], [0, 0, 0, 1], [1, 0, 0, 0]]) == [[1] py-str 4] py-str 4bksl-nlassert fermeture([[0, 1], [0, 0]]) == [[0, 1], [0, 0]]bksl-nlassert fermeture([[0, 0], [0, 0]]) == [[0, 0], [0, 0]]bksl-nlassert g == [[0, 1, 1, 0, 0, 0], [0, 0, 0, 1, 0, 0], [0, 0, 0, 1, 1, 0], [0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 0, 0]]bksl-nlbksl-nl ∞/∞

def produitpy-undbool(a, b):bksl-nl n = len(a)bksl-nl resultat = []bksl-nl for i in range(n):bksl-nl ligne = []bksl-nl for j in range(n):bksl-nl v = 0bksl-nl for k in range(n):bksl-nl # À compléter : v vaut 1 si a[i][k] et b[k][j] valent 1bksl-nl passbksl-nl ligne.append(v)bksl-nl resultat.append(ligne)bksl-nl return resultatbksl-nlbksl-nldef fermeture(m):bksl-nl n = len(m)bksl-nl t = [ligne[:] for ligne in m]bksl-nl p = [ligne[:] for ligne in m]bksl-nl for py-und in range(n - 1):bksl-nl p = produitpy-undbool(p, m)bksl-nl for i in range(n):bksl-nl for j in range(n):bksl-nl pass # À compléter : si p[i][j] vaut 1, mettre 1 dans t[i][j]bksl-nl return tbksl-nlbksl-nl

Exercice E – Niveaux

Écris niveaux(m) qui renvoie la liste des niveaux (chaque niveau est une liste de sommets) ou None si le graphe a un circuit. Méthode : retirer à chaque tour les sommets sans prédécesseur parmi ceux qui restent.

Je comprends. Pourquoi la boucle est-elle sûre de s'arrêter ?

###

g = [[0, 1, 1, 0, 0, 0], [0, 0, 0, 1, 0, 0], [0, 0, 0, 1, 1, 0], [0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 0, 0]]bksl-nlassert niveaux(g) == [[0], [1, 2], [3, 4], [5]]bksl-nlassert niveaux([[0, 1, 0, 0], [0, 0, 1, 0], [1, 0, 0, 1], [0, 0, 0, 0]]) is Nonebksl-nlassert niveaux([[0, 0], [0, 0]]) == [[0, 1]]bksl-nlassert niveaux([[0, 1, 0], [0, 0, 1], [0, 0, 0]]) == [[0], [1], [2]]bksl-nlassert niveaux([[1]]) is Nonebksl-nlbksl-nl ∞/∞

def niveaux(m):bksl-nl """Niveaux d'un graphe sans circuit, ou None s'il y a un circuit."""bksl-nl n = len(m)bksl-nl restants = list(range(n))bksl-nl resultat = []bksl-nl tours = 0bksl-nl while len(restants) > 0 and tours < n:bksl-nl tours = tours + 1bksl-nl niveau = []bksl-nl for j in restants:bksl-nl sanspy-undpred = Truebksl-nl for i in restants:bksl-nl pass # À compléter : si m[i][j] vaut 1, j a un prédécesseur parmi les restantsbksl-nl if sanspy-undpred:bksl-nl niveau.append(j)bksl-nl # À compléter : si le niveau est vide, renvoyer None (circuit) ;bksl-nl # sinon l'ajouter au résultat et retirer ses sommets de restantsbksl-nl breakbksl-nl return resultatbksl-nlbksl-nl