Нахождение одно-, двух- и трехэлементных разрезов графа

На основе оригинальной процедуры нахождения всех минимальных разрезов графа предложен эффективный метод перечисления одно-, двух- и трехэлементных разрезов, т.е. метод перечисления разрезов, не являющихся минимальными.

Ключевые слова

граф, минимальный разрез, квазиминимальный разрез, неразложимый разрез, дистрибутивная решетка, алгоритм

Литература

1. Дэвис, Д. Сети связи для вычислительных машин / Д. Дэвис, Д. Барбер. - М.: Мир, 1976.
2. Фрэнк, Г. Сети, связь и потоки / Г. Фрэнк, И. Фриш. - М.: Связь, 1978.
3. Герасимов, В.Г. Электротехнический справочник. В 4 т. Т.3: Производство, передача и распределение электрической энергии / В.Г. Герасимов и др. - М.: Изд-во МЭИ, 2002.
4. Picard, J.C. Selected applications of minimum cuts in networks / J.C. Picard, M. Queyranne // INFOR. Can. J. Oper. Res. And Inf. Process. - 1982. - Т. 20, № 4. - С. 394 - 422.
5. Форд, Л. Потоки в сетях / Л. Форд, Д. Фалкерсон. - М.: Мир, 1966.
6. Ху, Т. Целочисленное программирование и потоки в сетях / Т. Ху. - М.: Мир, 1974.
7. Hamacher, H.W. On finding the K best cuts in a network / H.W. Hamacher, J.C. Picard, M. Queyranne // Operations Research Letters. - 1984. - Т. 2, № 6. - С. 303 - 304.
8. Vazirani, V.V. Suboptimal cuts - their enumeration, weight and number / V.V. Vazirani, M. Yannakakis // Lect. Nites Comput. - 1992. - Т. 623. - С. 366 - 377.
9. Allan, R.N. An efficient algorithm for deducing the minimal cuts and reliability indices of a general network configuration / R.N. Allan, R. Billinton, M.F. De Oliveira // IEEE Trans. - 1976. - Т. R-25, № 4. - С. 226 - 233.
10. Методы оценки структурной надежности сложных схем электроэнергетических систем при меняющихся коммутационных состояниях / Ю.А Фокин, Р.С. Алиев, А.Н. Туманин, О.В. Файницкий // Изв. АН. Энергетика. - 1997. - № 4. - С. 111 - 118.
11. Гришкевич, А.А. Комбинаторные методы исследования экстремальных структур математических моделей электрических цепей и систем / А.А. Гришкевич. - Челябинск: Изд-во ЮУрГУ, 2004.
12. Айгнер, М. Комбинаторная теория / М. Айгнер. - М.: Мир, 1982.
13. Гретцер, Г. Общая теория решеток / Г. Гретцер. - М.: Мир, 1982.
14. Grishkevich, А.А. Algorrithm for finding minimal 3-elements cuts in graph / А.А. Grishkevich, L. Piatek // Polish J. of Environmental Studies. - 2007. - Т. 16, № 4a. - С. 218 - 222.
15. Grishkevich, А.А. Перечисление квазиминимальных разрезов графа / А.А. Grishkevich, L. Piatek // Обозрение прикладной и промышленной математики. - 2007. - Т. 14, № 3. - С. 530.