Fiche de révision : Optimisation des Flots en Réseaux

📋 Plan du Cours

1. Graphes et réseaux
2. Modélisation des réseaux
3. Graphes orientés et réseaux
4. Flot maximum en transport
5. Flot avec demandes
6. Flot complet et procédure gloutonne
7. Construction d’un flot complet
8. Programmation linéaire et solveurs
9. Multiflots et biflots
10. Difficulté des problèmes d’optimisation
11. Méthodes du reste du cours

📖 1. Graphes et réseaux

🔑 Notions clés & Définitions

• Graphe orienté : Le graphe orienté est un ensemble de sommets reliés par des arcs qui relient des paires de sommets dans un sens donné.
• Réseau de transport : Le réseau de transport est un graphe orienté avec une source s et un puits p, où chaque arc porte une capacité entière positive.
• Capacité d’un arc : La capacité d’un arc est un entier positif associé à l’arc, représentant la limite de bande passante du lien correspondant.
• Flot de données : Un flot de données attribue à chaque arc un flux entier et positif représentant la quantité de données qui circule sur ce lien.
• Arc saturé : Un arc est saturé quand le flux qui y circule atteint exactement la capacité maximale de cet arc.

📝 Points essentiels

• Un réseau de transport contient deux sommets remarquables, la source s et le puits p, dans un graphe orienté.
• La capacité d’un arc est un entier positif, et peut correspondre à une bande passante exprimée par exemple en Mo/s ou en Go/s.
• Le flux sur chaque arc est un entier positif et ne dépasse pas la capacité de l’arc.
• Un arc est dit saturé lorsque son flux est égal à sa capacité.
• Dans un flot valide, pour tout nœud x différent de la source s et du puits p, la somme des flux entrants en x égale la somme des flux sortants de x, sans perte de données.

📖 2. Modélisation des réseaux

🔑 Notions clés & Définitions

• Source s : La source s est le sommet remarquable d’un réseau de transport qui joue le rôle de nœud émetteur.
• Puits p : Le puits p est le sommet remarquable d’un réseau de transport qui joue le rôle de nœud récepteur.

📝 Points essentiels

• Un réseau de transport contient exactement deux sommets remarquables, la source s et le puits p, avec une capacité entière positive sur chaque arc.
• Dans une modélisation télécommunication, les sommets correspondent aux nœuds et les arcs correspondent aux liaisons permettant la communication entre nœuds.
• La capacité d’un arc modélise la bande passante du lien, exprimée par exemple en Mo/s ou en Go/s.

📖 3. Graphes orientés et réseaux

🔑 Notions clés & Définitions

• Arête bidirectionnelle : Une arête relie deux sommets avec une liaison bidirectionnelle, correspondant au cas non orienté du graphe.
• Flux de données : Un flux de données est une quantité entière et positive circulant sur un arc, interprétée comme une bande passante utilisée sur la liaison.

📝 Points essentiels

• Dans un réseau de transport, la capacité de chaque arc est un entier positif représentant la bande passante du lien.
• Sur chaque arc, le flux ne peut pas dépasser la capacité de l’arc.
• Un arc est saturé lorsque le flux qui y circule est égal à sa capacité.
• Dans un graphe non orienté, les liaisons peuvent être représentées par des arêtes bidirectionnelles plutôt que par des arcs orientés.

💡 Astuce mémo

Arc = flèche (sens de circulation) ; arête = trait (aller-retour).

📖 4. Flot maximum en transport

🔑 Notions clés & Définitions

• Valeur d’un flot : Un flot a une valeur égale à la quantité totale qui circule, soit la somme des flux sortant de la source et aussi la somme des flux entrant au puits.
• Débit maximum : Le débit maximum de s vers p est la plus grande valeur de flot possible, limitée par la bande passante des liaisons du réseau.
• Flot maximum : Un flot maximum est un flot de valeur maximale dans un réseau, pour transporter le plus possible de la source vers le puits.

📝 Points essentiels

• Calculer le débit maximum de s vers p revient à chercher un flot de valeur maximale, où chaque lien limite le flux par sa capacité.
• La capacité de chaque liaison (bande passante) borne la quantité de données pouvant être transportée sur l’arc correspondant.
• Calculer un flot avec demandes revient à déterminer si une certaine quantité peut être acheminée de s à p, et ce cas peut se ramener au flot maximum entre s et p.
• Dans l’exemple, un flot précédent atteignait 80 Mo/s et était complet mais pas maximum, car le flot maximum y vaut 85 Mo/s.

💡 Astuce mémo

Débit max = flot maximum : on maximise la valeur du flot de s vers p.

📖 5. Flot avec demandes

🔑 Notions clés & Définitions

• Demande de transfert : La demande de transfert est la quantité cible de données à acheminer de la source vers le puits, ici exprimée en Mo/s.
• Flot complet : Un flot complet est un flot qui force au moins un arc saturé sur tout chemin de la source vers le puits, sans garantir qu’il s’agit du meilleur possible.

📝 Points essentiels

• Pour une demande de 80 Mo/s, le flot complet construit permet d’acheminer les données de S vers P en respectant les capacités.
• Pour une demande supérieure à 80 Mo/s, il faut calculer un flot maximum pour savoir si c’est possible.
• Le flot complet obtenu n’est pas nécessairement maximum : dans l’exemple, sa valeur est 80 mais le flot maximum atteint 85.
• Le calcul du flot maximum peut être formulé comme un programme linéaire et résolu avec un solveur, par exemple GLPK.

💡 Astuce mémo

Complet ≠ Maximum : 80 passe, mais 85 montre que le complet construit peut laisser de la capacité inutilisée.

📖 6. Flot complet et procédure gloutonne

🔑 Notions clés & Définitions

• Chemin augmentant : Un chemin augmentant est un chemin trouvé du sommet source vers le sommet puits en suivant des arcs encore non saturés, servant à augmenter progressivement le flot.
• Procédure gloutonne : Une procédure gloutonne est une méthode heuristique qui construit d’abord un biflot partiel, met à jour les capacités restantes, puis complète avec le deuxième envoi.
• Biflot : Un biflot est un multiflot à deux paires émetteur-récepteur, où les flux issus de s1 doivent atteindre p1 et ceux issus de s2 doivent atteindre p2.

📝 Points essentiels

• Pour construire un flot complet, on recherche un chemin de S vers P en ne traversant que des arcs non saturés, sinon on s’arrête.
• On fait ensuite circuler sur ce chemin un flux jusqu’à saturer au moins un arc (ou plusieurs), en modifiant le réseau.
• On supprime ensuite les arcs saturés (ou on les interdit lors des parcours suivants), puis on recommence tant qu’un chemin de S à P existe.
• Dans l’exemple, le flot complet obtenu a une valeur 80 Mo/s (somme des flux sortant de la source égale à la somme des flux arrivant au puits).
• Une solution construite comme flot complet peut ne pas être maximale : la valeur du flot maximum vaut 85 dans cet exemple, donc 80 n’était pas maximum.

💡 Astuce mémo

Chemin S→P non saturé : on pousse jusqu’à saturer, on enlève, et on recommence (glouton : d’abord (s1,p1) puis (s2,p2), ou l’inverse).

📖 7. Construction d’un flot complet

🔑 Notions clés & Définitions

• Solveur GLPK : Un solveur comme GLPK est un logiciel qui permet de résoudre des programmes linéaires pour obtenir, notamment, une valeur optimale de flot.
• Coût total : Le coût total d’un flot est la somme des coûts unitaires $c(x,y)$ multipliés par les quantités de données envoyées sur chaque arc.

📝 Points essentiels

• Dans l’exemple évoqué, un flot complet de valeur 80 n’était pas maximum car il existait un flot maximum de valeur 85.
• Le calcul d’un flot maximum peut être formulé comme un programme linéaire et résolu par un solveur tel que GLPK.
• Le coût total d’un flot complet se calcule en sommant, pour chaque type d’arcs, coût unitaire multiplié par le total des flux empruntant des arcs de ce type.
• Dans l’exemple, avec coût unitaire 10 pour les arcs partant de la source, 30 pour ceux arrivant au puits et 20 pour les autres, le flot complet de valeur 80 a un coût total égal à 4800.

📖 8. Programmation linéaire et solveurs

🔑 Notions clés & Définitions

• Efficacité algorithmique : Propriété d’un algorithme mesurée par la croissance du nombre d’opérations de base avec la taille des entrées, et non par le temps sur une machine donnée.
• Problèmes d’optimisation de type 1 : Catégorie où l’on peut, efficacement, vérifier l’existence d’une solution dépassant (ou restant sous) une valeur donnée, en fournissant la solution si besoin.
• Problèmes d’optimisation de type 2 : Catégorie où l’on peut, efficacement, décider s’il existe une solution dépassant (ou restant sous) une valeur donnée.
• Implication type2 vers type1 : Relation entre catégories où toute résolution efficace du type 2 permet aussi de résoudre efficacement le type 1 correspondant.

📝 Points essentiels

• Un biflot maximum (avec flux entiers) peut être obtenu à l’aide d’un solveur, par exemple GLPK.
• L’efficacité ne se juge pas au temps d’exécution réel car ce temps dépend de la machine, tandis que l’objectif est une croissance intrinsèque du nombre d’étapes de calcul.
• Le nombre d’étapes d’un algorithme efficace augmente quand la taille des données $n$ augmente, mais pas trop en fonction de $n$.
• Tout problème de type 2 est aussi de type 1, car une décision efficace implique une vérification efficace avec solution si nécessaire.
• Le problème du biflot maximum (flux entiers) est de type 1 mais n’est pas de type 2.
• Le problème du flot maximum (flux entiers ou non) est de type 2, donc aussi de type 1.

💡 Astuce mémo

Type 2 ⇒ Type 1 : décider efficacement donne aussi vérifier efficacement.

📖 9. Multiflots et biflots

🔑 Notions clés & Définitions

• Biflot maximum : Problème d’optimisation où l’on cherche un flot maximal tout en imposant deux flot(s) structurés, et il n’est pas considéré “facile” en général.
• Problèmes de type 1 : Catégorie de problèmes d’optimisation où l’on peut vérifier efficacement l’existence d’une solution au-dessus ou au-dessous d’une valeur donnée.
• Problèmes de type 2 : Catégorie de problèmes d’optimisation où l’on peut décider efficacement s’il existe une solution au-dessus ou au-dessous d’une valeur donnée.
• Complexité P et NP : Cadre de complexité où les problèmes “décidables efficacement” forment P et les problèmes vérifiables efficacement forment NP, avec une relation encore non tranchée.

📝 Points essentiels

• Calculer un flot maximum (ou avec demandes) est informatiquement facile, alors que calculer un biflot maximum ne l’est généralement pas.
• Les problèmes de type 2 sont aussi de type 1, car décider l’existence d’une solution implique de pouvoir vérifier une borne si on fournit la solution.
• Le biflot maximum (avec flux de données entiers) est de type 1 mais pas de type 2, alors que le flot maximum (entiers ou non) est de type 2 donc de type 1.
• Les problèmes de type 2 forment P, et ceux de type 1 forment NP qui contient P, avec la question ouverte P = NP ou P ≠ NP.
• Le Sudoku est donné comme exemple d’un problème dans NP et NP-complet, au même titre que le biflot max. pour la difficulté théorique évoquée.

💡 Astuce mémo

Biflot : Type 1 seulement ; Flot : Type 2 donc Type 1 (plus “facile” à décider).

📖 10. Difficulté des problèmes d’optimisation

🔑 Notions clés & Définitions

• Complexité temporelle : Notion de difficulté liée à la croissance du nombre d’étapes de calcul quand la taille des données augmente.
• Ensemble P : Ensemble de problèmes appartenant au cas type 2, caractérisé par l’existence d’algorithmes en temps polynomial.
• Ensemble NP : Ensemble de problèmes de type 1, qui contient aussi l’ensemble P.

📝 Points essentiels

• Le temps de calcul d’un algorithme augmente en général avec la taille des données d’entrée.
• Un algorithme efficace est celui dont le nombre d’étapes n’augmente pas trop quand la taille des données augmente.
• Pour n = 100, n^2 donne 10 000 étapes tandis que 2n donne 2100 ≃ 10^30 étapes, ce qui illustre une croissance explosive.
• À 1 GHz (10^9 étapes/s), 2100 ≃ 10^30 étapes correspondent à environ 30 000 milliards d’années.
• Tout problème de type 2 est aussi de type 1, donc P ⊂ NP, et on ne sait pas si P = NP.
• Le biflot maximum (flux entiers) est de type 1 mais pas de type 2, tandis que le flot maximum (entiers ou non) est de type 2 donc de type 1.

💡 Astuce mémo

Type 2 ⟶ Type 1 : décider (type 2) est plus fort que vérifier (type 1).

📖 11. Méthodes du reste du cours

🔑 Notions clés & Définitions

• Classe P : La classe P regroupe les problèmes pour lesquels on peut décider efficacement l’existence d’une solution de meilleure/pires valeur donnée.
• Classe NP : La classe NP regroupe les problèmes pour lesquels on peut, efficacement, vérifier l’existence d’une solution de meilleure/pires valeur donnée.
• Problèmes NP-complets : Les problèmes NP-complets sont une sous-classe de NP pour laquelle l’existence d’un algorithme efficace pour l’un impliquerait l’existence pour tous les autres.
• SUDOKU : Le SUDOKU est un problème apparaissant comme exemple à la fois dans la classe NP et dans la classe NP-complet.

📝 Points essentiels

• Tout problème de type 2 est aussi de type 1, donc l’ensemble des “faciles” (type 2) est inclus dans l’ensemble des problèmes décidables efficacement (type 1).
• NP contient des problèmes NP-complets tous équivalents au sens où un algorithme efficace pour l’un entraînerait un algorithme efficace pour chacun des autres.
• Le SUDOKU (où toutes les solutions ont la même valeur) appartient à NP et est NP-complet.
• Personne ne sait si P = NP, et l’énoncé reste ouvert même pour des problèmes cités comme le SUDOKU et le biflot maximum.
• Pour résoudre en pratique un problème NP-complet, on peut soit modéliser en PLNE puis utiliser des solveurs comme GLPK (biflot), soit employer une programmation dynamique, soit utiliser une solution approchée via heuristiques ou méta-heuristiques.

💡 Astuce mémo

Type 2 → Type 1 ; dans NP, les NP-complets forment un “tout pareil” : un succès efficace pour l’un donne le succès pour tous.

📊 Tableaux de synthèse

Flot complet vs flot maximum

Problèmes type 1 vs type 2 (P vs NP)

⚠️ Pièges & confusions fréquents

1. Confondre arc et arête : un arc est orienté (sens de circulation), alors qu’une arête est bidirectionnelle (non orientée).
2. Oublier la loi de conservation : pour tout nœud sauf s et p, somme des flux entrants = somme des flux sortants.
3. Croire qu’un flot complet est automatiquement maximum : le cours précise que l’inverse n’est pas vrai.
4. Mélanger capacité et flot : un arc ne peut pas avoir un flux supérieur à sa capacité ; saturé signifie flux = capacité.
5. Se tromper sur la valeur d’un flot : c’est la somme des flux sortant de la source (et aussi la somme des flux entrant au puits).
6. Mauvaise formulation du flot avec demandes : il faut déterminer si/ comment une quantité peut être acheminée de s à p (se ramène à un flot maximum).
7. Confondre type 1 et type 2 : type 2 (décider) implique type 1 (vérifier avec solution si besoin), mais pas l’inverse.

✅ Checklist Examen

1. Définir un graphe orienté et reconnaître que les arcs modélisent des liaisons avec sens.
2. Définir un réseau de transport : source s, puits p, capacité entière positive sur chaque arc.
3. Définir le flux sur un arc (entier positif) et la contrainte : flux ≤ capacité.
4. Définir un arc saturé et le relier à la capacité atteinte.
5. Énoncer la loi de conservation : pour tout nœud x≠s,p, somme entrants = somme sortants.
6. Définir la valeur d’un flot comme somme des flux sortant de s (égale à somme entrants en p).
7. Relier débit maximum de s vers p et flot maximum de valeur maximale.
8. Expliquer le flot avec demandes : déterminer si/comment une quantité peut aller de s à p, et le ramener à un flot maximum.
9. Définir un flot complet et la condition “arc saturé sur tout chemin s→p”, puis donner le lien avec “flot maximum ⇒ complet”.
10. Maîtriser la procédure gloutonne de flot complet : départ flot NUL, chercher un chemin s→p non bloqué, pousser jusqu’à saturer, supprimer/interdire arcs saturés, recommencer.
11. Définir “chemin augmentant” utilisé pour construire/completer progressivement un flot, et comprendre le rôle des arcs non saturés.
12. Donner les bases de P vs NP via type 2 vs type 1 : type 2 décide efficacement, type 1 vérifie (et fournir si nécessaire), et citer les exemples flot maximum/biflot maximum/SUDOKU.