Degré des Sommets

Algorithmique classique

Exercice Débutant · Algo Express · prepa scientifique et economique (CPGE)

Enonce

Calculer le degré de chaque sommet d'un graphe non orienté représenté par un dictionnaire de listes d'adjacence.

Signature attendue

def degres(graphe: dict) -> dict:

Exemples

degres({0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2]}) → {0: 2, 1: 2, 2: 2, 3: 2}
degres({0: [1, 2, 3], 1: [0], 2: [0], 3: [0]}) → {0: 3, 1: 1, 2: 1, 3: 1}

📖 Rappel de cours

Le degré d'un sommet est son nombre de voisins. Sur une liste d'adjacence, c'est la longueur de sa liste.

⚠ Le piège : Lemme des poignées de main : la somme des degrés vaut deux fois le nombre d'arêtes, chacune étant comptée à ses deux extrémités. C'est ainsi qu'on compte les arêtes sans les énumérer.

← Exercices Python pour la prépa — CPGE scientifique et ECG

Exercices du meme theme

La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.