Flashcard: Optimisation des Flots en Réseaux — 22 carte

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.