Consignes

Le TP est à rendre (par email) pour le mercredi 23 décembre à 8h00.

Pour ce TP comme pour les suivants, la pièce la plus importante sera un fichier tp2-nom-prenom.c contenant votre programme. Le seul fait que votre programme fonctionne ne suffit pas pour avoir une bonne note. Les points suivants seront également pris en compte :

1. la lisibilité de votre programme (choix pertinent pour les noms de variables, indentation etc.),
2. la présence de commentaires aux endroits appropriés,
3. ...

Les réponses aux questions posées dans le TP (complexité de vos fonctions par exemple) seront insérées comme commentaires dans votre fichier principal.

Liens utiles

• le wiki du cours
• l'archive contenant les fichiers nécessaires pour le TP
• le TP1, avec quelques explications sur la bibliothèque fournie
• une correction possible pour le TP1
• le TP2

1. Préliminaires

Avant de commencer

1. Téléchargez l'archive du TP.

2. La compilation se fait avec le fichier Makefile fourni comme pour le TP1. Il suffit de modifier la variable NOM pour prendre en compte votre propre fichier.

3. Je ne fournis pas de fonction de test pour ce TP. Vous devrez donc vous débrouiller pour tester vos fonctions au fur et à mesure. (Par contre, ce n'est pas la peine de m'envoyer votre fonction principale.)

1.1. Problème du flot maximum

Soit G un graphe orienté avec des poids (entiers) strictement positifs sur les arc ; soit entrée et sortie deux sommets particuliers de G.

Un flot de entrée vers sortie est la donnée, pour chaque arc e de G, d'un nombre entier f(e) qui satisfait les contraintes suivantes :

1. f(e) est plus petit que le poids de e,
2. le flot sur l'arc (a,b) est l'opposé du flot sur l'arc (b,a),
3. les flots satisfont une « loi de Kirchoff » : si a est un sommet et b₁ , b₂ , ..., b_k sont ses voisins, alors f(a,b₁) + f(a,b₂) + ... + f(a,b_k) = 0,
4. la dernière condition n'est pas vérifiée pour le sommets entrée et sortie.

La valeur du flot est définie comme la somme précédente lorsque le sommet a est entrée. (C'est aussi l'opposé de la somme pour le sommet sortie.)

Le poids d'un arc est souvent appelé sa capacité.

On recherche le flot maximum qui peut traverser le graphe en entrant par le sommet entrée et en sortant par le sommet sortie.

Les applications sont nombreuses. Les sommets peuvent par exemple représenter des routeurs dans un réseau, des gares ferroviaire, des échangeurs autoroutiers, des robinets etc. ; les arcs peuvent être des câbles, des voies ferrées, des routes, des tuyaux etc.

Dans tous les cas, on essaie de maximiser la circulation d'une quantité entre deux noeuds.

1.2. Algorithme

Ce problème a une solution en temps « raisonnable », c'est à dire polynomiale en la taille du graphe de entrée. L'idée de l'algorithme est la suivante :

1. on part du flot vide, càd qui vaut 0 sur tous les arcs,
2. on cherche un chemin du sommet entrée vers le sommet sortie à ajouter (en respectant les contraintes des flots) au flot précédent,
3. quand on ne peut plus ajouter de chemin, on s'arrête : on a trouvé un flot maximum.

Comme pour les autres algorithmes, il faut faire une preuve mathématique que cette méthode abouti effectivement à un flot maximal. (La valeur du flot maximum est unique, mais il peut y avoir plusieurs flots avec cette même valeur.)

On peut se servir de graphes pour :

• le graphe initial G,
• le flot courant F,
• le graphe résiduel G\F, où le poids d'un arc e est donné par g(e)-f(e).

La recherche d'un chemin du sommet entrée vers le sommet sortie se fait simplement en cherchant un chemin dans le graphe résiduel. Pour cela, le plus simple est de faire un parcours en largeur de G\F. Une fois un tels chemin trouvé, on choisit de faire passer un flot égal poids minimal d'un arc de ce chemin. (C'est donc un flot maximal pour ce chemin.)

Remarque : le graphe résiduel peut contenir des arcs qui ne sont pas présents dans le graphe G. C'est par exemple le cas quand il y un arc de u vers v mais pas de v vers u. Si le flot f(u,v) est positif, alors c(v,u) - f(v,u) = 0 + f(u,v) est positif. Un tels arc représente en fait la possibilité de diminuer le flot dans l'arc (u,v)...

2. Le TP

int flotMaximal(GrapheListe G, int entree, int sortie, GrapheListe Flot) ;

Conseils : réfléchissez avant à la représentation des graphes que vous voulez utiliser et aux fonctions auxiliaires dont vous aurez besoin.