Coupe minimale avec un nombre minimum de bords

Question

Je suis sûr que beaucoup de gens connaissent ici le célèbre théorème de flux maximum de la coupe min - la capacité de la coupe minimale est égale à l'écoulement maximum d'une source donnée, s, à un puits donné, t, dans un graphique.

Tout d'abord, déclarons (pour l'exhaustivité) qu'une coupe ST est la partition des sommets dans le graphique, en deux parties, de sorte que la source est dans une partition et que l'évier est dans l'autre. L'ensemble de coupe est l'ensemble des bords qui vont des sommets dans la partition qui contient S à ceux de l'autre partition.

Il peut y avoir plusieurs coupes ST qui ont la même capacité que la coupe min (avec des ensembles de coupes de différentes tailles). Le problème que je souhaite résoudre est de trouver la coupe minimale de ST qui a également l'ensemble de coupe de taille minimale?

Par exemple, dans le graphique suivant où s = 0 et t = 4:

Nous pouvons clairement voir que la capacité de la coupe minimale est de 2. Une façon possible d'y parvenir est de prendre des bords 0-2 et 1-3 (cet ensemble de coupe a la taille 2). Une autre façon possible de le faire est de prendre le bord 3-4 à la place (cet ensemble de coupe a la taille 1) qui est la réponse optimale.

J'ai fait des recherches sur cette question et certaines personnes disent que nous devons transformer la capacité de bord, c, de chaque bord à c * (| e | + 1) - 1, où | e | est le nombre de bords dans le graphique.

Une telle discussion ici: https://codeforces.com/blog/entry/51748
Une autre discussion de ce type ici: https://stackoverflow.com/questions/38408852/finding-the-lowest-amount-of-edges-in-all-mimimum-cuts-in-flow-network

Le problème est que je ne comprends pas pourquoi cette formule fonctionne. En particulier, pourquoi avons-nous besoin de multiplier par (| e | + 1) et pas un autre nombre? Je ne vois pas comment la multiplication par un autre nombre "changerait" les chemins d'augmentation du graphique comme indiqué dans les liens cités.

Quelqu'un pourrait-il me conseiller?

Éditer: Le décalage dans la formule doit être +1 et non -1 afin d'obtenir l'ensemble de coupe de la plus petite taille.