Quiz — Graphes — Structures et algorithmes de parcours

Question 1

L'agence spatiale européenne utilise un graphe orienté pour modéliser les trajectoires possibles entre des stations spatiales. Voici la liste d'adjacence partielle : 
```python
stations = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['B', 'D'],
    'D': []
}
```
Un astronaute effectue un parcours DFS en partant de la station 'A'. Dans quel ordre les stations sont-elles visitées ?

Accepted Answer

A → C → B → D

Answer

A → B → D → C

Answer

A → B → C → D

Answer

A → C → D → B

Question 2

Un astronaute souhaite modéliser la cartographie des tunnels lunaires non orientés reliant des cratères. Il utilise une matrice d'adjacence $A$ de taille $5 	imes 5$ où $A[i][j] = 1$ si un tunnel relie le cratère $i$ au cratère $j$. Voici la matrice : $$A = \begin{pmatrix} 0 & 1 & 0 & 1 & 0 \ 1 & 0 & 1 & 0 & 1 \ 0 & 1 & 0 & 0 & 1 \ 1 & 0 & 0 & 0 & 0 \ 0 & 1 & 1 & 0 & 0 \end{pmatrix}$$ Quel est le nombre total de tunnels uniques reliant ces cratères ?

Accepted Answer

$6$ tunnels uniques

Answer

$4$ tunnels uniques

Answer

$8$ tunnels uniques

Answer

$10$ tunnels uniques

Question 3

Pour organiser un tournoi de tennis, Clara doit vérifier si son graphe de matchs est connexe. Son graphe non-orienté a 8 sommets et la matrice d'adjacence suivante : $$M = \begin{bmatrix} 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \ 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 \ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 \ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 \ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \end{bmatrix}$$Combien de composantes connexes contient ce graphe ?

Accepted Answer

3

Answer

1

Answer

2

Answer

4

Question 4

Quel est le coût en temps de l'algorithme de Dijkstra lorsque le graphe est représenté par une matrice d'adjacence et que toutes les arêtes ont un poids positif ? On note $n$ le nombre de sommets et $m$ le nombre d'arêtes.

Accepted Answer

$O(n^2)$

Answer

$O(m \log n)$

Answer

$O(n \log n)$

Answer

$O(m)$

Question 5

Identifie la ligne erronée dans ce code Python qui implémente un parcours BFS sur un graphe non orienté. Le graphe est représenté par une liste d'adjacence et on cherche à afficher les sommets dans l'ordre de visite.
```python
from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    
    while queue:
        vertex = queue.popleft()
        print(vertex)
        
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
```

Accepted Answer

Il n'y a pas d'erreur dans ce code

Answer

La ligne `visited.add(start)` est en trop et doit être supprimée

Answer

La ligne `queue = deque([start])` devrait être `queue = deque(start)`

Answer

La ligne `if neighbor not in visited:` devrait être `if neighbor not in queue:`

Graphes — Structures et algorithmes de parcours

Notions à maîtriser

Teste-toi sur ce chapitre

Graphes : structures et parcours en NSI

Garder ta progression ?