Quiz: Optimisation des Flots en Réseaux — 22 perguntas

1. Qu’est-ce qu’un graphe orienté ?

A. Un ensemble de sommets reliés par des arcs orientés

B. Un ensemble de sommets reliés par des arêtes bidirectionnelles

C. Un ensemble de sommets reliés uniquement par des capacités

D. Un ensemble de sommets sans liaisons entre eux

Answer: (A)

Explicação

Un graphe orienté est constitué de sommets reliés par des arcs qui imposent un sens de circulation. Les arêtes bidirectionnelles correspondent au cas non orienté.

2. Quand dit-on qu’un arc est saturé ?

A. Quand il relie directement la source au puits

B. Quand son flux est strictement inférieur à sa capacité

C. Quand il ne transporte aucun flux

D. Quand son flux atteint sa capacité maximale

Answer: (D)

Explicação

Un arc est saturé lorsque le flux qui y circule est égal à sa capacité. S’il est inférieur à sa capacité, il reste de la marge.

3. Dans un réseau de transport, quel rôle joue la source s ?

A. Le nœud récepteur du réseau

B. Un sommet intermédiaire sans rôle particulier

C. Un arc de capacité maximale

D. Le nœud émetteur du réseau

Answer: (D)

Explicação

La source s est le sommet émetteur d’où part le flot. Le puits p est, lui, le nœud récepteur.

4. Que représente la capacité d’un arc dans la modélisation d’un réseau ?

A. La valeur totale du flot dans le réseau

B. La bande passante maximale du lien

C. La longueur géométrique du trajet

D. Le nombre de sommets voisins de l’arc

Answer: (B)

Explicação

La capacité modélise la limite de bande passante que le lien peut transporter. Elle borne donc le flux qui peut circuler sur l’arc.

5. Dans un graphe non orienté, comment peut-on représenter une liaison entre deux sommets ?

A. Par une arête bidirectionnelle

B. Par une source et un puits

C. Par un arc orienté unique

D. Par un flot saturé

Answer: (A)

Explicação

Une arête bidirectionnelle correspond au cas non orienté, où la liaison peut aller dans les deux sens. Un arc, au contraire, est orienté.

6. Quelle contrainte doit respecter le flux sur chaque arc d’un réseau de transport ?

A. Il doit être identique sur tous les arcs

B. Il doit être nul sur les arcs entrants

C. Il ne doit pas dépasser la capacité de l’arc

D. Il doit dépasser la capacité pour être valide

Answer: (C)

Explicação

Le flux sur un arc est borné par sa capacité et ne peut pas la dépasser. Dépasser la capacité rendrait le flot invalide.

7. Comment définit-on la valeur d’un flot ?

A. Par le nombre de sommets du réseau

B. Par le nombre d’arcs saturés uniquement

C. Par la somme des flux sortant de la source, égale à la somme entrant au puits

D. Par la somme des capacités de tous les arcs

Answer: (C)

Explicação

La valeur d’un flot est la quantité totale transportée, égale au total sortant de la source et au total entrant au puits. Les capacités ou le nombre d’arcs saturés ne définissent pas cette valeur.

8. Que cherche-t-on en calculant un débit maximum de s vers p ?

A. Un chemin sans aucun arc orienté

B. Un flot qui minimise le nombre d’arcs utilisés

C. Une répartition aléatoire des flux

D. Un flot de valeur maximale entre la source et le puits

Answer: (D)

Explicação

Le débit maximum consiste à maximiser la valeur du flot de s vers p sous contrainte de capacité. Ce n’est pas un critère de minimisation du nombre d’arcs.

9. Qu’est-ce qu’une demande de transfert dans un problème de flot avec demandes ?

A. Le nombre de chemins possibles entre deux sommets

B. La quantité cible de données à acheminer de la source vers le puits

C. La quantité de flux déjà saturée sur un arc

D. La capacité totale de tous les arcs du réseau

Answer: (B)

Explicação

La demande de transfert est la quantité de données que l’on souhaite acheminer de la source vers le puits. Elle se distingue des capacités portées par les arcs.

10. Dans l’exemple, pourquoi un flot complet de 80 Mo/s n’était-il pas maximum ?

A. Parce qu’aucun arc n’était saturé

B. Parce que la demande était de 100 Mo/s

C. Parce qu’un flot de valeur 85 Mo/s existait

D. Parce que le flot complet devait être nul

Answer: (C)

Explicação

Le flot complet obtenu valait 80 Mo/s, mais un flot maximum de 85 Mo/s existait encore. Cela montre qu’un flot complet n’est pas forcément optimal.

11. Qu’est-ce qu’un flot complet dans un réseau de transport ?

A. Un flot qui sature au moins un arc sur tout chemin de la source vers le puits

B. Un flot qui maximise nécessairement la valeur totale entre la source et le puits

C. Un flot qui ne circule que sur un seul chemin simple de la source vers le puits

D. Un flot qui respecte les capacités mais peut laisser tous les chemins partiellement libres

Answer: (A)

Explicação

Un flot complet impose qu’il existe au moins un arc saturé sur tout chemin allant de la source vers le puits. Cela ne signifie pas qu’il soit maximum, car un flot complet peut encore laisser de la capacité inutilisée.

12. Que fait la procédure gloutonne utilisée pour construire un flot complet ?

A. Elle calcule directement le flot de valeur maximale sans modifier le réseau

B. Elle choisit d’abord tous les arcs les plus coûteux puis les remplit intégralement

C. Elle cherche un chemin non saturé, envoie du flux jusqu’à saturer un arc, puis recommence

D. Elle conserve tous les chemins possibles et répartit le flux uniformément sur chacun

Answer: (C)

Explicação

La procédure gloutonne suit un chemin de la source vers le puits en évitant les arcs saturés, pousse du flux jusqu’à saturation, puis recommence sur le réseau modifié. Cette démarche construit un flot complet sans garantir qu’il soit optimal.

13. Quel critère permet d’arrêter l’algorithme de construction d’un flot complet ?

A. Lorsqu’un sommet intermédiaire reçoit autant de flux qu’il en émet

B. Lorsqu’il n’existe plus de chemin de la source vers le puits en utilisant uniquement des arcs non saturés

C. Lorsqu’on a envoyé un flux égal à la capacité totale de tous les arcs

D. Lorsqu’aucun arc du réseau n’a encore été utilisé au moins une fois

Answer: (B)

Explicação

On s’arrête quand il n’existe plus de chemin de la source vers le puits qui évite les arcs saturés. C’est exactement le signe que la construction gloutonne ne peut plus augmenter le flot complet.

14. Pourquoi un flot complet obtenu par cette construction peut-il ne pas être maximum ?

A. Parce qu’un flot complet interdit toute conservation du flux aux sommets intermédiaires

B. Parce qu’il peut rester de la capacité disponible sur certains chemins de la source vers le puits

C. Parce qu’un flot complet doit toujours avoir une valeur inférieure à la moitié du maximum

D. Parce qu’un flot complet ne peut utiliser que des arcs de capacité égale à 1

Answer: (B)

Explicação

Un flot complet garantit seulement qu’au moins un arc est saturé sur tout chemin source-puits, pas que toute la capacité exploitable est utilisée. Il peut donc rester du potentiel pour augmenter encore la valeur totale du flot.

15. Quel est l’intérêt de formuler le calcul d’un flot maximum comme un programme linéaire ?

A. Permettre à un solveur de déterminer automatiquement une solution optimale

B. Imposer que chaque arc transporte exactement la même quantité de flux

C. Remplacer la notion de capacité par une contrainte de coût unique

D. Éviter toute contrainte de conservation aux sommets intermédiaires

Answer: (A)

Explicação

La formulation en programmation linéaire permet de confier la recherche de l’optimum à un solveur comme GLPK. Le solveur traite les contraintes de capacité et de conservation pour obtenir une valeur optimale de flot.

16. Comment se calcule le coût total d’un flot ?

A. En comptant seulement le nombre de sommets traversés par le flot

B. En additionnant, pour chaque arc, le coût unitaire multiplié par le flux envoyé

C. En additionnant uniquement les flux qui sortent de la source

D. En multipliant toutes les capacités des arcs empruntés entre elles

Answer: (B)

Explicação

Le coût total est la somme des coûts unitaires pondérés par les quantités de données envoyées sur chaque arc. Ce n’est pas le simple total des flux, mais bien un total pondéré par les coûts.

17. Dans ce cadre, quelle affirmation décrit correctement un problème de type 2 ?

A. On doit obligatoirement résoudre un système non linéaire

B. On ne peut vérifier une solution qu’avec une approximation grossière

C. On peut toujours fournir une solution optimale sans autre calcul

D. On peut décider efficacement s’il existe une solution dépassant une certaine valeur

Answer: (D)

Explicação

Un problème de type 2 consiste à décider efficacement s’il existe une solution meilleure qu’un seuil donné. Cette capacité de décision est plus forte que la simple vérification demandée dans les problèmes de type 1.

18. Quelle relation est donnée entre type 2 et type 1 ?

A. Les deux types sont disjoints et n’ont aucun lien

B. Le type 1 est toujours plus facile à décider que le type 2

C. Tout problème de type 1 est automatiquement un problème de type 2

D. Tout problème de type 2 est aussi un problème de type 1

Answer: (D)

Explicação

La relation indiquée est que décider efficacement une question de type 2 permet aussi de traiter le problème correspondant en type 1. En revanche, l’inverse n’est pas garanti.

19. Quelle affirmation résume la difficulté théorique du biflot maximum par rapport au flot maximum ?

A. Le biflot maximum est toujours plus facile car il impose deux paires source-puits

B. Les deux problèmes appartiennent exactement à la même classe de difficulté

C. Le flot maximum est NP-complet tandis que le biflot maximum est polynomial

D. Le biflot maximum est généralement plus difficile, alors que le flot maximum est informatiquement facile

Answer: (D)

Explicação

Le cours souligne que le flot maximum est informatiquement facile, tandis que le biflot maximum est généralement difficile. Cette différence est précisément mise en relation avec les classes de complexité évoquées.

20. Que signifie l’inclusion P ⊂ NP dans ce cadre ?

A. Les problèmes vérifiables efficacement sont tous décidables inefficacement

B. La vérification efficace implique toujours une impossibilité de décision

C. Les problèmes décidables efficacement sont aussi vérifiables efficacement

D. Les problèmes de type 1 sont exclus de la classe NP

Answer: (C)

Explicação

L’inclusion P ⊂ NP traduit qu’un problème résoluble efficacement peut aussi être vérifié efficacement. Le texte présente cette relation en lien avec la distinction entre type 2 et type 1.

21. Quelle approche pratique peut être utilisée pour résoudre un problème NP-complet ?

A. Le transformer systématiquement en problème de recherche aléatoire

B. Le modéliser en programmation linéaire en nombres entiers puis utiliser un solveur

C. Le résoudre uniquement par un algorithme de tri

D. Le traiter exclusivement par une méthode de calcul parallèle non déterministe

Answer: (B)

Explicação

Une des méthodes citées consiste à modéliser le problème en PLNE puis à le résoudre avec un solveur comme GLPK. Les autres propositions ne correspondent pas aux méthodes mentionnées pour ce type de problème.

22. Que signifie le fait qu’un problème soit NP-complet ?

A. Un algorithme efficace pour l’un donnerait un algorithme efficace pour tous les problèmes de NP

B. Le problème appartient à P et peut être décidé plus vite que tous les autres problèmes

C. Le problème n’a aucun lien avec la classe NP

D. Le problème est forcément facile à vérifier mais impossible à décider

Answer: (A)

Explicação

Les problèmes NP-complets sont les plus durs de NP au sens où, si l’un admettait un algorithme efficace, alors tous les autres problèmes de NP en admettraient aussi un. Cela ne signifie pas qu’ils appartiennent à P.