Théorème flot-max/coupe-min

Science formelle
Mathématiques
Mathématiques discrètes
Théorie des graphes

À propos
Confidentialité
Mentions légales

Graph Chatbot

Séances de cours associées (30)

Connectez-vous pour filtrer par séance de cours

Page 2 sur 3

Réseaux de flux : composants fortement connectés

Présente des composants et des réseaux de flux fortement connectés, en discutant des algorithmes et des applications.

Algorithmes de flux réseau

Couvre les algorithmes de flux de réseau, y compris Max Flow, Min Cut, et l'algorithme de cycle de coût négatif, progressant de définitions de base à des algorithmes avancés comme Bellman-Ford et Dijkstra.

Sparsest Cut : le théorème de Bourgain

Explore le théorème de Bourgain sur la coupe la plus clairsemée dans les graphes, en mettant l'accent sur la sémimétrie et l'optimisation des coupes.

Débit maximal : théorie et applications

Explore le débit maximal dans les graphiques, couvrant l'algorithme Ford-Fulkerson, la conservation du débit et la coupe minimale.

Partitionnement aléatoire de faible diamètre

Discute de la décomposition randomisée à faible diamètre et du partitionnement graphique pour les coupes de bord et la coloration.

Max Flav-Min Découpe dans les graphiques dirigés

Couvre le concept de réduction maximale du débit minimal dans les graphiques dirigés avec des contraintes de capacité.

Bounded Network Flow: Problème Solvable Minult-Maxcret

Couvre la résolution des problèmes de flux de réseau borné en ajustant les capacités de flux et les contraintes, y compris les programmes binaires.

Problème de flux maximal

Couvre le problème de débit max, la dualité faible, et l'algorithme Ford-Fulkerson.

Flux de réseau et formulations LP

Explique les flux réseau, les formulations LP, la méthode simplex, la dualité et les applications pratiques.

Flow Networks : la méthode Ford-Fulkerson

Couvre les réseaux de flux et la méthode Ford-Fulkerson dans l'optimisation de flux de réseau.