Degré des sommets d’un graphe ★☆☆
→ Voir fiche n° 2 : Les variables
→ Voir fiche n° 2 bis : Les listes
→ Voir fiche n° 5 : Les boucles bornées
Soit
M la matrice d’adjacence d’un graphe dont les sommets sont des lettres de l’alphabet, les sommets étant rangés dans l’ordre alphabétique.
L’objectif de cet exercice est de classer les sommets par ordre décroissant du degré.
1. Compléter la fonction
degres ci-dessous pour qu’elle retourne la liste des degrés de chaque sommet de la matrice d’adjacence
M.
2. À partir de la fonction
tri donnée dans l’énoncé, classer les sommets du graphe ci-dessous par ordre décroissant de leur degré.
def degres(M):
n = len(M)
degre = n*[0]
for i in range(n):
for j in range(n):
degre[i] = ...
return degre
def tri(sommets, degre):
ordre = len(sommets)
liste_sommets_tries = []
for k in range(ordre):
maximum = max(degre)
index = degre.index(maximum)
degre.pop(index)
sommet_correspondant = sommets[index]
liste_sommets_tries.extend(sommet_correspondant)
sommets.pop(index)
return liste_sommets_tries
sommets = ['A','B','C','D','E']
M = [[0,1,0,0,1],[1,0,1,0,1],[0,1,0,0,1],[0,0,0,0,1],[1,1,1,1,0]]
degre_des_sommets = degres(M)
print(degre_des_sommets)
print(tri(sommets,degre_des_sommets))