Flot maximal
Réseau de transport, flot admissible, graphe résiduel et chaînes améliorantes, algorithme de Ford-Fulkerson, coupes et théorème flot maximal, coupe minimale.
- 26 cartes
- 6 thèmes
- Gratuit
Le programme, thème par thème
Le poids de chaque thème suit celui que lui donne l'examen.
- Notions
- Questions
- Ranger et relier
- Les chiffres
- Mises en situation
- Comprendre
Quelques cartes du deck
Réseau de transport : de quoi s'agit-il ?
Voir la réponse
Graphe orienté dont chaque arc porte une capacité, avec une source d'où le flot part et un puits où il arrive.
Il modélise des conduites, des routes, des câbles : la capacité d'un arc est le débit maximal qu'il supporte.
Dans ce réseau (arcs S→A de capacité 10, S→B 8, A→B 2, A→T 7, B→T 9), quelle est la capacité de la coupe {S, A} contre {B, T} ?
17181636
Voir la réponse
17Les arcs qui vont de {S, A} vers {B, T} sont S→B (8), A→B (2) et A→T (7) : 17. S→A reste à l'intérieur du premier ensemble. 18 compterait les arcs sortant de S seuls, 16 ceux qui entrent dans T, 36 tous les arcs.
La loi de conservation impose qu'en tout sommet autre que la source et le puits, la somme des flots … égale la somme des flots ….
Voir la réponse
La loi de conservation impose qu'en tout sommet autre que la source et le puits, la somme des flots entrants égale la somme des flots sortants.
Un sommet intermédiaire ne stocke rien et ne crée rien : ce qui y arrive repart. Seuls la source (qui émet) et le puits (qui absorbe) y font exception.
Flot admissible : de quoi s'agit-il ?
Voir la réponse
Valeur attribuée à chaque arc qui ne dépasse jamais sa capacité et qui, en tout sommet autre que la source et le puits, laisse sortir autant que ce qui entre.
Deux contraintes à vérifier : la capacité sur chaque arc, la conservation à chaque sommet intermédiaire. La valeur du flot est ce qui sort de la source.