Нахождение одно-, двух- и трехэлементных разрезов графа
Автор: Гришкевич А.А., Piatek L., Бурмутаев А.
Статья в выпуске: 15 (115), 2008 года.
Бесплатный доступ
На основе оригинальной процедуры нахождения всех минимальных разрезов графа предложен эффективный метод перечисления одно-, двух- и трехэлементных разрезов, т.е. метод перечисления разрезов, не являющихся минимальными.
Граф, минимальный разрез, квазиминимальный разрез, неразложимый разрез, дистрибутивная решетка, алгоритм
Короткий адрес: https://sciup.org/147159033
IDR: 147159033
Список литературы Нахождение одно-, двух- и трехэлементных разрезов графа
- Дэвис Д. Сети связи для вычислительных машин/Д. Дэвис, Д. Барбер. М.: Мир, 1976.
- Фрэнк Г. Сети, связь и потоки/Г. Фрэнк, И. Фриш. М.: Связь, 1978.
- Герасимов В.Г. Электротехнический справочник. В 4 т. Т. 3: Производство, передача и распределение электрической энергии/В.Г. Герасимов и др. М.: Изд-во МЭИ, 2002.
- Picard J.C. Selected applications of minimum cuts in networks/J.C. Picard, M. Queyranne//INFOR. Can. J. Oper. Res. and Inf. Process. 1982. Vol. 20, N 4. P. 394-422.
- Форд Л. Потоки в сетях/Л. Форд, Д. Фалкерсон. М.: Мир, 1966.
- Ху Т. Целочисленное программирование и потоки в сетях/Т. Ху. М.: Мир, 1974.
- Hamacher H.W. On finding the К best cuts in a network/H.W. Hamacher, J.C. Picard, M. Queyranne//Operations Research Letters. 1984. Vol. 2, N 6. P. 303-304.
- Vazirani V.V. Suboptimal cuts -their enumeration, weight and number/V.V. Vazirani, M. Yannakakis//Lect. Nites Comput. 1992. Vol. 623. P. 366-377.
- 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. Vol. R-25, N 4. C. 226-233.
- Методы оценки структурной надежности сложных схем электроэнергетических систем при меняющихся коммутационных состояниях/Ю.А Фокин, Р.С. Алиев, А.Н. Туманин, О.В. Файницкий//Изв. АН. Энергетика. 1997. № 4. С. 111-118.
- Гришкевич А.А. Комбинаторные методы исследования экстремальных структур математических моделей электрических цепей и систем/А.А. Гришкевич. Челябинск: Изд-во ЮУрГУ, 2004.
- Айгнер М. Комбинаторная теория/М. Айгнер. М.: Мир, 1982.
- Гретцер Г. Общая теория решеток/Г. Гретцер. М.: Мир, 1982.
- Grishkevich А.А. Algorrithm for finding minimal 3-elements cuts in graph/A.A. Grishkevich, L. Piatek//Polish J. of Environmental Studies. 2007. Vol. 16, N 4a. C. 218-222.
- Grishkevich А.А. Перечисление квазиминимальных разрезов графа/А.А. Grishkevich, L. Piatek//Обозрение прикладной и промышленной математики. 2007. Т. 14, № 3. С. 530.
Статья научная
