Quiz: Fondamentaux des graphes et connexité — 10 questions

1. Quelle est la conséquence principale de la recherche de composantes fortement connexes dans un graphe orienté ?

A. Elle permet d'identifier toutes les arêtes du graphe.

B. Elle calcule la distance minimale entre deux sommets.

C. Elle détecte la présence de cycles dans le graphe.

D. Elle facilite la décomposition du graphe en sous-ensembles où chaque sommet est accessible depuis tout autre.

Answer: (D)

Explanation

La recherche de composantes fortement connexes permet de décomposer le graphe en sous-ensembles maximaux où chaque sommet est accessible depuis tout autre, ce qui révèle la structure cyclique et la connectivité interne du réseau.

2. Qu'est-ce que la théorie des graphes ?

A. Une technique de programmation pour optimiser les parcours dans un réseau.

B. Une branche des mathématiques qui modélise et analyse la connectivité et la structure des réseaux à l'aide de sommets et d'arêtes.

C. Une branche de l'informatique qui étudie uniquement les réseaux informatiques.

D. Une méthode pour représenter des données sous forme de tableaux ou de matrices.

Answer: (B)

Explanation

La théorie des graphes est une branche des mathématiques qui modélise et analyse la connectivité et la structure des réseaux en utilisant des concepts comme sommets, arêtes, degrés, et connexité, ce qui correspond à la deuxième option.

3. Quand l'algorithme de Kosaraju pour la recherche des composantes fortement connexes a-t-il été publié ou établi ?

A. 2002

B. 1990

C. 1985

D. 1978

Answer: (D)

Explanation

L'algorithme de Kosaraju a été publié en 1978 par S. Rao Kosaraju, ce qui en fait la réponse correcte. Les autres dates correspondent à d'autres événements ou publications dans le domaine des graphes ou sont incorrectes.

4. Quelle est la principale fonction de l'algorithme de Bellman-Ford et de Floyd-Warshall dans le traitement des graphes pondérés?

A. Trouver le chemin le plus court entre deux sommets spécifiques dans un graphe non pondéré.

B. Optimiser la connectivité d’un graphe en supprimant les arcs inutiles.

C. Calculer toutes les distances minimales possibles entre toutes les paires de sommets d’un graphe pondéré.

D. Détecter la présence de cycles de poids négatif dans un graphe.

Answer: (C)

Explanation

L'algorithme de Bellman-Ford et celui de Floyd-Warshall ont pour objectif principal de déterminer les distances minimales dans un graphe pondéré. Bellman-Ford calcule le plus court chemin depuis une source vers tous les autres sommets, tout en détectant les cycles négatifs, tandis que Floyd-Warshall calcule la matrice de toutes les distances minimales entre chaque paire de sommets. La réponse correcte est donc la deuxième, qui reflète leur rôle dans le calcul de toutes les distances minimales possibles.

5. Dans un réseau routier représenté par un graphe pondéré, comment doit-on procéder pour déterminer le trajet le plus court entre deux villes en utilisant un algorithme standard ?

A. Utiliser un parcours en largeur (BFS) en ignorant les poids pour trouver le chemin le plus court.

B. Calculer la moyenne des poids de toutes les arêtes pour estimer une distance approximative.

C. Appliquer l'algorithme de Dijkstra en partant de la ville de départ pour trouver le chemin de coût minimal vers la destination.

D. Utiliser l'algorithme de Floyd-Warshall pour calculer toutes les distances minimales en une seule étape.

Answer: (C)

Explanation

L'algorithme de Dijkstra est spécifiquement conçu pour trouver le chemin de coût minimal entre deux sommets dans un graphe pondéré avec des poids positifs, ce qui correspond à la situation décrite. Floyd-Warshall permet de connaître toutes les distances minimales entre toutes les paires de sommets, mais n'est pas optimal pour une seule paire. La moyenne des poids ne donne pas une solution précise, et BFS, sans considération des poids, ne garantit pas le chemin de coût minimal dans un graphe pondéré.

6. Quel est le rôle principal des représentations graphiques et matricielles dans l’étude des graphes ?

A. Remplacer complètement l’analyse manuelle des chemins et cycles

B. Simplifier la résolution de tous les problèmes liés aux graphes

C. Modéliser et analyser la connectivité et la structure des réseaux

D. Créer des visualisations esthétiques sans autre utilité

Answer: (C)

Explanation

Les représentations graphiques et matricielles permettent de modéliser et d’analyser la connectivité et la structure des réseaux, facilitant ainsi leur étude et la résolution de problèmes liés à leur organisation.

7. Qui a formulé ou popularisé l'algorithme de parcours en largeur (BFS) dans le contexte de la théorie des graphes ?

A. Edsger Dijkstra

B. Robert Tarjan

C. Claude Shannon

D. Alan Turing

Answer: (B)

Explanation

Robert Tarjan est reconnu pour ses contributions fondamentales à la théorie des graphes et à la formalisation des algorithmes de parcours, notamment le BFS. Dijkstra est associé aux algorithmes de plus courts chemins, Shannon à la théorie de l'information, et Turing à la machine de Turing. La question porte sur la personne ayant formulé ou popularisé le BFS, ce qui correspond à Robert Tarjan.

8. Quelle est la caractéristique principale de l'algorithme de Kosaraju pour la recherche de composantes fortement connexes dans un graphe orienté ?

A. Il utilise uniquement la matrice d’adjacence pour détecter les cycles.

B. Il repose sur la transposition du graphe et deux parcours en profondeur pour identifier les composantes.

C. Il se base sur la recherche de chemins les plus courts entre tous les sommets.

D. Il utilise une seule traversée en profondeur sur le graphe original.

Answer: (B)

Explanation

L'algorithme de Kosaraju repose sur deux parcours en profondeur : un sur le graphe original pour déterminer l’ordre de fin des sommets, puis un sur la transposée du graphe dans cet ordre pour extraire les composantes fortement connexes, ce qui le distingue des autres méthodes.

9. Quel nom est donné au type de graphe où chaque lien possède une direction?

A. Graphe simple

B. Graphe complet

C. Graphe non orienté

D. Graphe orienté

Answer: (D)

Explanation

Le terme 'graphe orienté' désigne un graphe où chaque lien (arc) possède une direction, représentée par une flèche, ce qui le différencie du graphe non orienté où les liens n'ont pas de direction.

10. En quoi la notion de connexité diffère-t-elle de celle de composantes fortement connexes dans un graphe orienté ou non orienté ?

A. La connexité concerne la présence d’au moins une arête ou arc entre deux sommets, alors que la forte connexité concerne uniquement les graphes complets.

B. La connexité implique qu'il existe une chaîne reliant deux sommets, sans tenir compte de la direction, alors que la forte connexité exige une double accessibilité entre chaque paire de sommets dans un graphe orienté.

C. La connexité et la forte connexité sont deux termes synonymes, mais la forte connexité est utilisée dans un contexte plus formel.

D. La connexité concerne uniquement les graphes non orientés, tandis que la forte connexité s'applique uniquement aux graphes orientés.

Answer: (B)

Explanation

La différence essentielle est que la connexité dans un graphe non orienté ne considère pas la direction des liens, tandis que la forte connexité dans un graphe orienté exige que chaque sommet soit accessible depuis tout autre dans les deux sens, ce qui est une propriété plus stricte.