RO-CM4-Flots

Un réseau de transport est un graphe de flot

• VRAI

• FAUX

La capacité d'un arc désigne le flux minimum qui peut passer sur cet arc :

• FAUX

• VRAI

Dans un graphe de flot il faut :

• Que le flux qui arrive sur un sommet soit égal à celui qui en ressort

• Que les arêtes adjacentes à un sommet soient saturées

• Que le flux des arcs ne dépasse pas la capacité des arcs

Si le flot est maximal dans G :

• Le flux sortant de la source doit être égal au flux entrant dans le puit

• Il n'existe plus de chaîne améliorante dans G

• Il n'existe plus de chemin entre la source et le puit dans le graphe d'écart associé à G

Dans un graphe de flot le débit total est égal :

• A la somme du flot entrant

• A la somme du flot sortant

• Aux 2

Un couplage est un ensemble d'arêtes :

• Avec au moins un sommet commun entre deux arêtes

• Deux à deux sans sommet commun

On peut transformer un problème de couplage en un problème de flot si le graphe est :

• planaire

• biparti

• dense