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.
Flot de données — qu’est-ce ?
Quantité de données circulant sur un arc.
Arc saturé — signification ?
Flux égal à la capacité de l’arc.
Source s — rôle ?
Sommet émetteur dans un réseau.
Puits p — rôle ?
Sommet récepteur dans un réseau.
Arête bidirectionnelle — différence ?
Liaison non orientée ou deux arcs dans chaque sens.
Flux maximum — définition ?
Plus grand flot possible de s à p.
Demande de transfert — qu’est-ce ?
Quantité à acheminer de s à p.
Flot complet — caractéristique ?
Un arc saturé sur tout chemin s→p.
Procédure gloutonne — principe ?
Construire un flot en augmentant par chemins non saturés.
Chemin augmentant — mécanisme ?
Chemin non saturé permettant d’augmenter le flot.
Construction flot complet — étape clé ?
Trouver un chemin non saturé et pousser le flot.
Solveur GLPK — utilité ?
Résoudre un programme linéaire pour flot maximum.
Programmation linéaire — rôle ?
Modéliser et optimiser un flot via PLNE.
Problème de type 2 — définition ?
Décider efficacement l’existence d’une solution.
Problème de type 1 — définition ?
Vérifier efficacement l’existence d’une solution.
Complexité P — qu’est-ce ?
Problèmes décidables en temps polynomial.
NP — qu’est-ce ?
Problèmes vérifiables efficacement, incluant P.
NP-complet — exemple ?
SUDOKU, problème difficile dans NP.
Différence flot max et flot complet — ?
Max est la valeur maximale, complet implique arc saturé sur tout chemin.
Teste tes connaissances avec un QCM de 22 questions sur Optimisation des Flots en Réseaux.
1. Qu’est-ce qu’un graphe orienté ?
2. Quand dit-on qu’un arc est saturé ?
Révisez le cours complet dans la fiche de révision de Optimisation des Flots en Réseaux.
Voir la fiche →Importe ton cours et l'IA génère des flashcards en 30 secondes.
Générateur de flashcards