QCM : Fondamentaux des graphes et connexité — 10 questions

Questions et réponses du QCM

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

Elle permet d'identifier toutes les arêtes du graphe.
Elle calcule la distance minimale entre deux sommets.
Elle détecte la présence de cycles dans le graphe.
Elle facilite la décomposition du graphe en sous-ensembles où chaque sommet est accessible depuis tout autre.

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

Explication

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 ?

Une technique de programmation pour optimiser les parcours dans un réseau.
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.
Une branche de l'informatique qui étudie uniquement les réseaux informatiques.
Une méthode pour représenter des données sous forme de tableaux ou de matrices.

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.

Explication

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 ?

2002
1990
1985
1978

1978

Explication

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?

Trouver le chemin le plus court entre deux sommets spécifiques dans un graphe non pondéré.
Optimiser la connectivité d’un graphe en supprimant les arcs inutiles.
Calculer toutes les distances minimales possibles entre toutes les paires de sommets d’un graphe pondéré.
Détecter la présence de cycles de poids négatif dans un graphe.

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

Explication

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 ?

Utiliser un parcours en largeur (BFS) en ignorant les poids pour trouver le chemin le plus court.
Calculer la moyenne des poids de toutes les arêtes pour estimer une distance approximative.
Appliquer l'algorithme de Dijkstra en partant de la ville de départ pour trouver le chemin de coût minimal vers la destination.
Utiliser l'algorithme de Floyd-Warshall pour calculer toutes les distances minimales en une seule étape.

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

Explication

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 ?

Remplacer complètement l’analyse manuelle des chemins et cycles
Simplifier la résolution de tous les problèmes liés aux graphes
Modéliser et analyser la connectivité et la structure des réseaux
Créer des visualisations esthétiques sans autre utilité

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

Explication

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 ?

Edsger Dijkstra
Robert Tarjan
Claude Shannon
Alan Turing

Robert Tarjan

Explication

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é ?

Il utilise uniquement la matrice d’adjacence pour détecter les cycles.
Il repose sur la transposition du graphe et deux parcours en profondeur pour identifier les composantes.
Il se base sur la recherche de chemins les plus courts entre tous les sommets.
Il utilise une seule traversée en profondeur sur le graphe original.

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

Explication

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?

Graphe simple
Graphe complet
Graphe non orienté
Graphe orienté

Graphe orienté

Explication

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é ?

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.
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é.
La connexité et la forte connexité sont deux termes synonymes, mais la forte connexité est utilisée dans un contexte plus formel.
La connexité concerne uniquement les graphes non orientés, tandis que la forte connexité s'applique uniquement aux graphes orientés.

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é.

Explication

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.

Révisez avec les flashcards

Mémorisez les réponses avec 20 flashcards sur Fondamentaux des graphes et connexité.

Graphe — définition ?

Représentation mathématique de sommets reliés par des arêtes.

Graphe orienté — rôle ?

Les arêtes ont une direction, indiquée par une flèche.

Degré d’un sommet — dans un graphe orienté ?

Nombre d’arcs entrant ou sortant, séparément.

Voir les flashcards →

Approfondir avec la fiche

Consultez la fiche de révision complète sur Fondamentaux des graphes et connexité.

Voir la fiche →

Cours similaires

Introduction aux probabilités et statistiques

Mathématiques

Introduction aux probabilités et statistiques

Mathématiques

Structure et propriétés de la matière

Chimie

Les dynamiques de la stratification sociale

Les Bases de la Photosynthèse

SVT

Les bases de la production d'énergie cellulaire

Crée tes propres QCM

Importe ton cours et l'IA génère des QCM avec corrections en 30 secondes.

Générateur de QCM