Worldlex Wiki En théorie des graphes , une coupe est une partition des sommets d'un graphe en deux sous-ensembles disjoints . Toute coupe définit un ensemble de coupe , c'est-à-dire l'ensemble des arêtes dont une extrémité appartient à chaque sous-ensemble de la partition. Ces arêtes sont dites traverser la coupe. Dans un graphe connexe , chaque ensemble de coupe définit une coupe unique, et dans certains cas, les coupes sont identifiées à leurs ensembles de coupe plutôt qu'à leurs partitions de sommets.
Dans un réseau de flux , une coupe source-puits est une coupe qui exige que la source et le puits appartiennent à des sous-ensembles différents, et son ensemble de coupe ne comprend que les arêtes allant du côté source au côté puits. La capacité d'une coupe source-puits est définie comme la somme des capacités de chaque arête de son ensemble de coupe .
Définition
Une coupe est une partition de en deux sous-ensembles L' ensemble de coupe d'une coupe est l'ensemble des arêtes ayant une extrémité dans Si sont des sommets donnés du graphe - appartient à l'ensemble appartient à l'ensemble
Une coupe est minimale si sa taille ou son poids n'excède pas celui de toute autre coupe. L'illustration de droite montre une coupe minimale : sa taille est de 2, et il n'existe pas de coupe de taille 1 car le graphe est sans pont .
Le théorème du flot maximal et de la coupe minimale démontre que le flot maximal du réseau et la somme des poids des arêtes de toute coupe minimale séparant la source et le puits sont égaux. Il existe des méthodes polynomiales pour résoudre le problème de la coupe minimale, notamment l' algorithme d'Edmonds-Karp .
Coupe maximale
Il convient de noter que les problèmes de coupe minimale et de coupe maximale ne sont pas duaux au sens de la programmation linéaire , même si l'on passe de l'un à l'autre en remplaçant min par max dans la fonction objectif . Le problème .
Coupe la plus clairsemée
Le problème de la coupe la plus clairsemée consiste à bipartitionner les sommets de manière à minimiser le rapport entre le nombre d'arêtes traversant la coupe et le nombre de sommets dans la plus petite moitié de la partition. Cette fonction objectif privilégie les solutions à la fois clairsemées (peu d'arêtes traversant la coupe) et équilibrées (proches d'une bissection). Le problème est connu pour être NP-difficile, et le meilleur algorithme d'approximation connu est un Vazirani (2009) .
Espace réduit
L'ensemble de toutes les coupes d'un graphe non orienté est appelé l' espace des coupes du graphe. Il forme un espace vectoriel sur le corps fini à deux éléments de l'arithmétique modulo deux, dont l'addition vectorielle est la différence symétrique de deux coupes, et est le complément orthogonal de l' espace des cycles . Si les arêtes du graphe sont pondérées positivement, la base de poids minimal de l'espace des coupes peut être décrite par un arbre sur le même ensemble de sommets que le graphe, appelé arbre de Gomory-Hu . Chaque arête de cet arbre est associée à une liaison dans le graphe initial, et la coupe minimale entre deux nœuds s et t est la liaison de poids minimal parmi celles associées au chemin de s à t dans l'arbre.