Réseaux de flux : composants fortement connectés

Cette séance de cours couvre le concept de composants fortement connectés (SCC) dans les graphes dirigés, expliquant l'algorithme pour trouver des SCC en utilisant la première recherche en profondeur (DFS). Il introduit ensuite les réseaux de flux, définissant les flux, les capacités et la conservation des flux. La séance de cours traite également de la valeur d'un flux et présente une définition formelle d'un réseau de flux. Diverses applications des réseaux de flux sont explorées, telles que la modélisation du transfert de fromage entre les villes et les réseaux ferroviaires. L'importance d'éviter les contours antiparallèles dans les réseaux de flux est mise en évidence, ainsi que le processus de transformation des réseaux pour éliminer ces contours.