Ch24 – Graphes et ordonnancement – QCM

Question 1

Dans un graphe \(G=(V,E)\), comment appelle-t-on les éléments de \(V\) ?

Les arêtes Les sommets Les chemins Les degrés

Question 2

D'après le lemme des poignées de mains, la somme des degrés des sommets d'un graphe est égale à :

\(|V|\) \(|E|\) \(2|E|\) \(|V| + |E|\)

Question 3

Pour un graphe orienté avec les arcs \(1\to 2\), \(1\to 3\), \(2\to 4\), \(3\to 4\), \(4\to 1\), quelle est la première ligne de la matrice d'adjacence (sommet 1 vers 1,2,3,4) ?

\((0,\ 1,\ 1,\ 0)\) \((1,\ 1,\ 0,\ 0)\) \((0,\ 0,\ 1,\ 1)\) \((1,\ 0,\ 0,\ 1)\)

Question 4

Un arbre est un graphe connexe sans cycle. Combien d'arêtes possède un arbre à \(n\) sommets ?

\(n\) \(2n\) \(n+1\) \(n-1\)

Question 5

Un graphe connexe admet un cycle eulérien si et seulement si :

tous ses sommets sont de degré impair tous ses sommets sont de degré pair il possède un sommet isolé il est biparti

Question 6

L'algorithme de Dijkstra trouve le plus court chemin. Quelle condition doivent vérifier les poids des arêtes ?

ils doivent être entiers ils doivent être tous égaux ils doivent être positifs (\(\ge 0\)) ils peuvent être négatifs

Question 7

Dans un réseau de câblage à 5 sites, l'algorithme de Kruskal trie les arêtes par poids croissant. Parmi A-C:2, C-D:3, A-B:4, B-C:5, D-E:7, laquelle est rejetée car elle créerait un cycle A-B-C-A ?

B-C:5 A-C:2 C-D:3 D-E:7

Question 8

Dans la méthode PERT, comment calcule-t-on la date au plus tôt \(T^+_i\) d'une étape ?

par propagation arrière, en prenant le minimum par propagation avant, en prenant le maximum des chemins arrivant par propagation avant, en prenant le minimum en faisant la moyenne des durées

Question 9

Une tâche \(ij\) de durée \(d_{ij}\) a une marge totale donnée par :

\(MT = T^+_j + T^+_i + d_{ij}\) \(MT = T^+_j - T^+_i + d_{ij}\) \(MT = d_{ij} - T^-_j\) \(MT = T^-_j - T^+_i - d_{ij}\)

Question 10

Une tâche est dite critique lorsque sa marge totale vaut :

la durée du projet une valeur maximale zéro un nombre négatif

Question 11

Dans le réseau PERT du projet de réhabilitation, le chemin critique a une durée totale de :

\(57\) jours \(42\) jours \(63\) jours \(50\) jours

Question 12

Que représente une barre horizontale dans un diagramme de Gantt ?

un sommet du graphe une tâche, positionnée à sa date de début, de longueur égale à sa durée le coût total du projet le nombre de couleurs nécessaires