Algorithm and program for finding minimal and quasi-minimal cuts in graphs

It was found, that the set of minimum cuts, separating two chosen vertices in graph, have the structure of distributive lattice. It was developed an effective procedure for finding the set of 1, 2 and 3 elements cuts in graph based on the consideration of distributive lattice of the set of minimum cuts. The procedure consists of first, the algorithm for finding indecomposable minimal cuts of distributive lattice. Second, algorithm for synthesis, using resulting subset from stage one, of the entire set of minimum cuts. The third, is the algorithm for describing the set of quasi-minimum (close to the minimum, next to minimum) cuts in the form of sum of distributive lattices of minimal cuts found for the modified function of weight. The computer program, implementing these algorithms, is presented with examples.

Ustalono, że zbiór minimalnych przekrojów, rozdzielających dwa zadane wierzchołki grafu, z wprowadzonymi na i operacjami ma strukturę kraty dystrybutywnej. Opracowano skuteczną algorytmiczną procedurę znajdowania zbioru jed dwu i trzy elementowych przekrojów grafu bazującą na rozpatrzeniu dystrybutywnych krat zbioru minimalnych przekrojów grafu. Procedura składa się z, po pierwsze, algorytmu szukania nierozkładalnych minimalnych przekrojów Dystrybutywnej, po drugie, algorytmu syntezy po tym podzbiorze w kracie dystrybutywnej całego poszukiwanego zbioru minimalnych przekrojów i, po trzecie, algorytmu opisu zbioru quasi-minimalnych (bliskich do minimalnych, następnych po minimalnych) przekrojów w formie sumy krat dystrybutywnych minimalnych przekrojów, znalezionych dla zmodyfikowanej funkcji wagi. Przedstawiono zrealizowany program komputerowy i przedstawiono przykłady pracy programu.