Exercice 3 - Coût des algorithmes et tris · Bac Numérique et Sciences Informatiques Amérique du Nord 2025 (jour 1)

Partie B: graphes et algorithmique

Afin de faciliter en amont les préparations des sorties, on souhaite construire le graphe non orienté des mésententes entre les enfants de l'association. Le graphe est représenté par un dictionnaire dont les clés sont les sommets du graphe, et qui associe à chaque sommet le tableau (type List en Python) de ses voisins.

Par exemple, le graphe g1 de la figure 2 est représenté par le dictionnaire suivant:

g1 = {'Elise': ['Octavie', 'Virgile'],

'Octavie': ['Elise', 'Pierre', 'Virgile'],

'Pierre': ['Octavie', 'Raphael'],

'Raphael': ['Pierre', 'Virgile'],

'Sixtine': [],

'Virgile': ['Elise', 'Octavie', 'Raphael']

}

13.

Recopier et compléter les lignes 7 à 10 de la fonction sommets_tries, qui prend en paramètre un dictionnaire g représentant un graphe, et qui renvoie la liste des sommets du graphe triés dans l'ordre décroissant de leur degré.

def sommets_tries(g):

sommets = [sommet for sommet in g]

n = len(sommets)

for i in range(1, n):

sommet_courant = sommets[i]

j = i - 1

# Compléter les lignes 7 à 10 ci-dessous:

return sommets

14.

Préciser le tri utilisé dans la question précédente, ainsi que son coût d'exécution en temps dans le pire des cas selon le nombre $n$ de sommets (constant, logarithmique soit en $\log_2(n)$, linéaire soit en $n$, quasi-linéaire soit en $n \log_2(n)$, quadratique soit en $n^2$, cubique soit en $n^3$, exponentiel soit en $2^n$,...). On fait l'hypothèse pour cette question que la fonction degre est de coût constant.