Discussion :

[LePtitBen]

Bonjour,

J'ai une question vis à vis de cette question :

Soit G un graphe orienté avec une source s (un sommet sans arc entrant) et un puits
t (un sommet sans arc sortant). Deux chemins reliant s à t sont dits arc-disjoints, s'ils ne
partagent pas d'arc (cependant, ils peuvent passer tous les deux par un même sommet).

On souhaite connaître le plus grand nombre possible de chemins élémentaires arc disjoints reliant s à t. Soit (G, s, t, c) le réseau de flot correspondant au graphe donné G, où
la capacité c de tout arc du graphe est égale à 1.

" Montrer que s'il existe k chemins arc-disjoints reliant s à t dans un graphe G, alors
il existe un flot de valeur k dans le réseau de flot G. "

Quand ils disent : " Il existe un flot de valeur k dans le réseau de flot de G ", vis vis à des informations données, c'est le flot maximal du graphe, non ? J'ai peur de mal interpréter l'informations.

[Flodelarab]

Bonjour

Un graphe qui a 23 chemins disjoints a 16 chemins disjoints.
Un graphe pour lequel il existe 16 chemins disjoints a un flot de valeur au moins 16.
Or ce n'est pas le maximum puisque le maximum c'est 23.

[LePtitBen]

Bonjour !

Merci de ta réponse. Mais le flot maximal d'un graphe, n'est pas le flot arrivant au puits ? Dans notre cas ,ici à t ?

Edit : Méa culpa, tu veux dire qu'il existe 23 chemins dont 16 avec leur flot à 1, c'est ça ?

[tbc92]

ici, on a des mots 'compliqués' pour des notions simples.
On a un système de tuyaux, avec des intersections. Chaque tuyau a un débit maximal de 1 (la capacité c de tout arc du graphe est égale à 1 en langage théorie des graphes).
On calcule le nombre de 'circuits' qui ne se superposent pas (arc-disjoints dans l'énoncé) . Donc la meme portion de tuyau ne peut pas être utilisée 2 fois.

On suppose qu'on arrive à trouver k circuits qui ne superposent pas.
Et on nous demande de montrer qu'on peut avoir un débit au moins égal à k avec notre système de tuyaux. Il se trouve que le k en question, c'est aussi le débit maximal. Mais on nous demande de montrer que k est inférieur ou égal au débit maximal.
Si tu montres que k est égal au débit maximal, alors parfait, ça répond à la question.

[Flodelarab]

Ne faites vous pas une utilisation légère du mot "maximal" alors qu'il n'est pas dans l'énoncé ?

Il y a 3 choses bien différentes :

• Flot
• Flot complet
• Flot complet maximal

Et toujours cette vidéo de l'algorithme de Ford-Fulkerson que je trouve excellente pour comprendre les nuances :

[LePtitBen]

Si j'ai bien compris, le flot est complet quand on a saturé tous nos chemins. Mais cela ne veut pas dire que l'ensemble de nos flots sont saturés. En revanche, si on sature toutes nos capacités sur chaque chemin, le flot est complet maximal, c'est bien cela ?

[Flodelarab]

Le flot complet devient maximal quand tu as saturé les arcs inverses, suite à la recherche de chaînes non saturées.
C'est facile d'obtenir un flot complet. Il suffit de bourriner en saturant tes capacités d'arc direct. Mais tu n'auras pas le max.
La seconde étape de saturation des arcs inverses (qui désaturent éventuellement les arcs direct) est la clé.

Si j'ai bien compris, le flot est complet quand on a saturé tous nos chemins.

Oui !

Mais cela ne veut pas dire que l'ensemble de nos flots sont saturés.

Saturés, si. Mais maximal, non.

En revanche, si on sature toutes nos capacités sur chaque chemin, le flot est complet maximal, c'est bien cela ?

Non. Tu persistes dans le sens direct. Il n'y a pas que le sens direct qui compte.

Tu peux très bien saturer un arc direct maladroitement pour aller vite... et tout bloquer.
Et en fait, en déchargeant ce premier chemin pour charger un chemin alternatif, tu vas augmenter ton flot... Jusqu'au max.
C'est ce qu'il fait dans la vidéo en baissant l'arc 3-4.