QCM - Révisions graphes

QCM - Révisions graphes

Question 1. Dans un graphe non orienté à $n$ sommets, le nombre maximum d'arêtes est :

$n$$n^2$$\frac{n(n-1)}{2}$$2^n$

Question 2. La complexité d'un parcours en largeur (BFS) sur un graphe représenté par liste d'adjacence est :

$O(n)$$O(n + p)$$O(n^2)$$O(n \cdot p)$

Question 3. La complexité d'un parcours en profondeur (DFS) sur un graphe représenté par matrice d'adjacence est :

$O(n)$$O(n + p)$$O(n^2)$$O(n \cdot p)$

Question 4. Un graphe est connexe si :

Il existe un chemin entre toute paire de sommetsTous les sommets ont le même degréIl n'a pas de cycleIl a exactement $n-1$ arêtes

Question 5. Un arbre est un graphe :

Connexe avec des cyclesConnexe et acycliqueNon connexe et acycliqueAyant exactement $n$ arêtes

Question 6. Dans un graphe orienté, un sommet de degré sortant 0 est appelé :

Une sourceUn puitsUn sommet isoléUn point d'articulation

Question 7. Le BFS depuis un sommet s permet de calculer :

Les distances pondérées depuis sLes distances non pondérées (nombre d'arêtes) depuis sUn tri topologiqueLes composantes fortement connexes

Question 8. La représentation par liste d'adjacence est préférable quand :

Le graphe est dense ($p \approx n^2$)Le graphe est creux ($p \ll n^2$)On veut tester rapidement si une arête existeLe graphe est complet

Question 9. Le degré d'un sommet dans un graphe non orienté est :

Le nombre de sommets adjacentsLe nombre de chemins passant par ce sommetLa distance maximale à un autre sommetLe nombre de composantes connexes

Question 10. Dans un graphe non orienté, la somme des degrés de tous les sommets vaut :

$n$$p$$2p$$n^2$