Geek or not

Accueil du site > MOCA > Exercice 17

Aller à ...

OMFG

Informations

Dans la rubrique MOCA , cet article a été écrit par b3nj et publié le 5 avril 2006.
1385 personnes ont affiché cette page et sa popularité est de 11.

Pebkac

Mots clefs

I see dead pixels.

Outils

SYN

Exercice 17

Réponses

Application de l’algorithme de Ford-Fulkerson :

On applique un flot de retour $\varphi_{0}$ sur le graphe


Application d’un flot de retour

1. $\overline{G}(\varphi^{0})$ :


Graphe d’écart déduit

2. $k=0$
$P^{0} = (E,b,c,a,d,f)=(u_{2}^{+},u_{6}^{+},u_{8}^{-} ,u_{7}^{+},u_{13}^{+},u_{15}^{+})=(1,2,1,6,2,2)$

3. $\varepsilon^{0} =1$
$\varphi'_{u_{2}} = 10$
$\varphi'_{u_{6}} = 7$
$\varphi'_{u_{8}} = 0$
$\varphi'_{u_{7}} = 5$
$\varphi'_{u_{13}} = 1$
$\varphi'_{u_{15}} = 5$
$\varphi_{u_{0}}^{'1} = 20$


Graphe déduit de l’augmentation du flot

1. $\overline{G}(\varphi^{1})$ :


Graphe d’écart déduit

Il n’existe pas de chemin entre $E$ et $S$ , l’algorithme s’arrête, $\varphi_0$ est maximal et vaut 20.

pages : << 1 2

Poster un message