j'ai du mal à comprendre le lemme suivant de CLRS:Dans les algorithmes Push Relabel pour un débit maximum, pourquoi n'y a-t-il pas de chemin de la source s à la descente t?
Soit G un réseau d'écoulement, s et t être des noeuds de source et de puits, f une prégaz de s à t, et h une fonction de la hauteur sur G. Ensuite, il n'y a pas de chemin d'augmentation de s à t dans le graphe résiduel G f.
Pourquoi est-ce?
Ce qui suit est une version paraphrasée et développée de la preuve dans CLRS, deuxième édition. L'intuition derrière la preuve est que si h est une fonction de hauteur, alors nous devons avoir que dans tout chemin de s à t, la hauteur des nœuds le long du chemin peut diminuer d'au plus un dans chaque étape (depuis les fonctions de hauteur satisfont la propriété que h (u) ≤ h (v) + 1, signifiant que h (v) ≥ h (u) - 1). Supposons maintenant que vous ayez un chemin d'augmentation dans le graphe résiduel qui va de s à t. Dans ce cas, s'il existe un chemin d'augmentation, il doit y avoir un chemin simple augmentant de s vers t, donc nous n'avons pas besoin de nous inquiéter des cycles. Alors, réfléchissons à ce à quoi ce chemin simple doit ressembler. S'il y a | V | sommets dans le graphe, notre chemin simple doit avoir au plus | V | des sommets, ce qui veut dire qu'il a au plus | V | - 1 bords dedans. Parce qu'il y a au plus | V | - 1 arêtes, et la hauteur de chaque nœud peut chuter d'au plus un par pas, la diminution maximale possible de la hauteur à partir du nœud de départ s est | V | - 1. Maintenant, nous savons que h est une fonction hauteur, ce qui signifie que h (s) = | V | et h (t) = 0. Mais maintenant nous avons une contradiction - puisque nous commençons à la hauteur | V | et diminuer la hauteur d'au plus | V | - 1, la hauteur à la fin du chemin doit être au moins 1, et puisque h (t) = 0, nous savons que ce chemin ne peut pas réellement se terminer à t. Cette contradiction garantit que notre hypothèse était fausse et qu'il n'y a pas vraiment de chemin d'augmentation de s vers t.
Espérons que cela aide!