Numérique et sciences informatiques (NSI) · Terminale

Exercices : les graphes : représentations et parcours

22 exercices avec correction détaillée, en 3 séries. Aucune inscription : ta progression reste sur ton appareil.

ULUMINE · Numérique et sciences informatiques (NSI) · Terminale

Les graphes : représentations et parcours — S’entraîner

Feuille d’exercices

Prénom : ……………………………Date : ……………………Score : ……… / 8

Sauf mention contraire, les questions portent sur le graphe G du cours, et les voisins sont examinés dans l’ordre alphabétique.

Exercice 1 — Relie chaque élément de gauche à celui de droite.
Associe chaque terme à sa définition.
1. 1. Degré d’un sommet
2. 2. Chemin
3. 3. Cycle
4. 4. Graphe connexe
- A. Suite de sommets dont deux consécutifs sont reliés
- B. Chemin qui revient à son sommet de départ
- C. Deux sommets quelconques sont toujours reliés par un chemin
- D. Nombre de voisins de ce sommet
Exercice 2
Quel est le degré du sommet D dans le graphe G ?
```
A --- B
|     |
C --- D
|     |
E --- F

Arêtes : A–B, A–C, B–D, C–D, C–E, D–F, E–F
```
Texte
Écris tes calculs :
Réponse : ………………
Exercice 3
Un graphe non orienté a 5 sommets de degrés 1, 2, 2, 3 et 4. Combien a-t-il d’arêtes ?
Écris tes calculs :
Réponse : ………………
Exercice 4 — Coche la bonne réponse.
Quelle structure de données utilise le parcours en largeur ?
- Une pile
- Une file
- Un arbre binaire de recherche
- Une matrice

Exercice 5

Donne l’ordre de visite des sommets lors d’un parcours en largeur de G depuis A (lettres séparées par des espaces).

g = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "D", "E"],
    "D": ["B", "C", "F"],
    "E": ["C", "F"],
    "F": ["D", "E"],
}

Python

Exercice 6 — Coche « Vrai » ou « Faux ».
La matrice d’adjacence d’un graphe non orienté est toujours symétrique.
VraiFaux
Exercice 7
Quelle est la distance (en nombre d’arêtes) entre A et F dans G ?
```
A --- B
|     |
C --- D
|     |
E --- F

Arêtes : A–B, A–C, B–D, C–D, C–E, D–F, E–F
```
Texte
Écris tes calculs :
Réponse : ………………
Exercice 8
Écris une fonction degre_max(g) qui reçoit un graphe non orienté sous forme de dictionnaire de listes d’adjacence et renvoie un sommet de degré maximal.

ulumine.com — exercices corrigés gratuits

ULUMINE · Numérique et sciences informatiques (NSI) · Terminale

Les graphes : représentations et parcours — S’entraîner

Corrigé détaillé — pour les parents et les enseignants

Exercice 1
Réponse : 1 → D · 2 → A · 3 → B · 4 → C
Ces notions décrivent la structure d’un graphe ; les parcours permettent de les étudier par programme.
Exercice 2
Réponse : 3
D est relié à B, C et F : il a 3 voisins.
Exercice 3
Réponse : 6
La somme des degrés vaut 1 + 2 + 2 + 3 + 4 = 12. Chaque arête compte deux fois (une par extrémité) : 12 ÷ 2 = 6 arêtes.
Exercice 4
Réponse : Une file
Les sommets découverts sont enfilés et traités dans l’ordre de découverte (FIFO) : on visite ainsi les sommets par distance croissante.
Exercice 5
Réponse : A B C D E F
A ; puis ses voisins B, C ; puis D (découvert depuis B) et E (découvert depuis C) ; enfin F (découvert depuis D).
Exercice 6
Réponse : Vrai
Si i et j sont reliés, j et i le sont aussi : M[i][j] = M[j][i]. Ce n’est pas le cas en général pour un graphe orienté.
Exercice 7
Réponse : 3
A et F ne sont ni voisins, ni à distance 2 (les sommets à distance 1 de A sont B et C, aucun n’est voisin de F). Le chemin A, B, D, F a 3 arêtes.
Exercice 8
Exemple de réponse : On initialise le meilleur sommet à None et le meilleur degré à −1. On parcourt les clés du dictionnaire : le degré d’un sommet s est len(g[s]). Si ce degré dépasse le meilleur degré, on met à jour les deux variables. On renvoie le meilleur sommet. Sur G, la fonction renvoie C (degré 3, premier rencontré).
C’est une recherche de maximum classique, où la valeur comparée est la longueur de la liste des voisins.
```
def degre_max(g):
    meilleur = None
    dmax = -1
    for s in g:
        if len(g[s]) > dmax:
            meilleur = s
            dmax = len(g[s])
    return meilleur
```
Python
- Parcours de toutes les clés du dictionnaire.
- Degré obtenu par len(g[s]).
- Mise à jour correcte du maximum.
- Valeur renvoyée : un sommet, pas un degré.

Sauf mention contraire, les questions portent sur le graphe G du cours, et les voisins sont examinés dans l’ordre alphabétique.

Exercices corrigés : 0 / 8

Exercice 1 sur 8
Association
Associe chaque terme à sa définition.
- Degré d’un sommet
- Chemin
- Cycle
- Graphe connexe
Aide d’ULU pour cet exercice
Exercice 2 sur 8
Calcul
Quel est le degré du sommet D dans le graphe G ?
```
A --- B
|     |
C --- D
|     |
E --- F

Arêtes : A–B, A–C, B–D, C–D, C–E, D–F, E–F
```
Texte
Ta réponse
Aide d’ULU pour cet exercice
Exercice 3 sur 8
Calcul
Un graphe non orienté a 5 sommets de degrés 1, 2, 2, 3 et 4. Combien a-t-il d’arêtes ?
Ta réponse
Aide d’ULU pour cet exercice
Exercice 4 sur 8
QCM
Quelle structure de données utilise le parcours en largeur ?
Choisis une réponse
Une pileUne fileUn arbre binaire de rechercheUne matrice
Aide d’ULU pour cet exercice
Exercice 5 sur 8
Réponse à écrire
Donne l’ordre de visite des sommets lors d’un parcours en largeur de G depuis A (lettres séparées par des espaces).
```
g = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "D", "E"],
    "D": ["B", "C", "F"],
    "E": ["C", "F"],
    "F": ["D", "E"],
}
```
Python
Ta réponse
Aide d’ULU pour cet exercice
Exercice 6 sur 8
Vrai ou faux
La matrice d’adjacence d’un graphe non orienté est toujours symétrique.
Vrai ou faux ?
VraiFaux
Aide d’ULU pour cet exercice
Exercice 7 sur 8
Calcul
Quelle est la distance (en nombre d’arêtes) entre A et F dans G ?
```
A --- B
|     |
C --- D
|     |
E --- F

Arêtes : A–B, A–C, B–D, C–D, C–E, D–F, E–F
```
Texte
Ta réponse
Aide d’ULU pour cet exercice
Exercice 8 sur 8
Question ouverte
Écris une fonction degre_max(g) qui reçoit un graphe non orienté sous forme de dictionnaire de listes d’adjacence et renvoie un sommet de degré maximal.
Ta réponse
Aide d’ULU pour cet exercice

À découvrir aussi

Terminale · Numérique et sciences informatiques (NSI)

La récursivité

Fonctions récursives en Python : cas de base, appels récursifs, pile d’appels, terminaison et comparaison avec l’itératif. Cours et exercices de NSI Terminale.

Terminale · Numérique et sciences informatiques (NSI)

La programmation orientée objet

Classes, objets, attributs et méthodes en Python : constructeur __init__, self, interface et références. Cours et exercices de programmation objet en NSI Terminale.

Terminale · Numérique et sciences informatiques (NSI)

Listes, piles, files et dictionnaires

Interface et implémentation des structures linéaires : listes chaînées, piles (LIFO), files (FIFO) et dictionnaires en Python. Cours et exercices de NSI Terminale.