Un ensemble de sommets reliés par des arcs orientés
Explication
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é.
Quand son flux atteint sa capacité maximale
Explication
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.
Le nœud émetteur du réseau
Explication
La source s est le sommet émetteur d’où part le flot. Le puits p est, lui, le nœud récepteur.
La bande passante maximale du lien
Explication
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.
Par une arête bidirectionnelle
Explication
Une arête bidirectionnelle correspond au cas non orienté, où la liaison peut aller dans les deux sens. Un arc, au contraire, est orienté.
Il ne doit pas dépasser la capacité de l’arc
Explication
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.
Par la somme des flux sortant de la source, égale à la somme entrant au puits
Explication
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.
Un flot de valeur maximale entre la source et le puits
Explication
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.
La quantité cible de données à acheminer de la source vers le puits
Explication
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.
Parce qu’un flot de valeur 85 Mo/s existait
Explication
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.
Un flot qui sature au moins un arc sur tout chemin de la source vers le puits
Explication
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.
Elle cherche un chemin non saturé, envoie du flux jusqu’à saturer un arc, puis recommence
Explication
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.
Lorsqu’il n’existe plus de chemin de la source vers le puits en utilisant uniquement des arcs non saturés
Explication
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.
Parce qu’il peut rester de la capacité disponible sur certains chemins de la source vers le puits
Explication
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.
Permettre à un solveur de déterminer automatiquement une solution optimale
Explication
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.
En additionnant, pour chaque arc, le coût unitaire multiplié par le flux envoyé
Explication
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.
On peut décider efficacement s’il existe une solution dépassant une certaine valeur
Explication
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.
Tout problème de type 2 est aussi un problème de type 1
Explication
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.
Le biflot maximum est généralement plus difficile, alors que le flot maximum est informatiquement facile
Explication
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.
Les problèmes décidables efficacement sont aussi vérifiables efficacement
Explication
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.
Le modéliser en programmation linéaire en nombres entiers puis utiliser un solveur
Explication
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.
Un algorithme efficace pour l’un donnerait un algorithme efficace pour tous les problèmes de NP
Explication
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.
Mémorisez les réponses avec 22 flashcards sur Optimisation des Flots en Réseaux.
Graphe orienté — définition ?
Sommets reliés par des arcs dans un sens.
Réseau de transport — rôle ?
Modélise un graphe orienté avec source et puits.
Capacité d’un arc — définition ?
Entier positif représentant la limite de flux.
Consultez la fiche de révision complète sur Optimisation des Flots en Réseaux.
Voir la fiche →Importe ton cours et l'IA génère des QCM avec corrections en 30 secondes.
Générateur de QCM