МЕТОД НАЙКОРОТШИХ ЗБІЛЬШУЮЧИХ ШЛЯХІВ У ЗАДАЧАХ ПРО ПАРОСПОЛУЧЕННЯ
DOI:
https://doi.org/10.26642/tn-2015-3(74)-101-112Ключові слова:
паросполучення, максимальне паросполучення, задача про зважене паросполученняАнотація
У застосуваннях теорії графів широку популярність отримала задача про паросполучення. Вона полягає в знаходженні в заданому графі паросполучення з найбільшою кількістю ребер – максимального паросполучення. Узагальненям цієї задачі є задача про зважене паросполучення. Класичний алгоритм Едмондса для знаходження найбільшого зваженого паросполучення у недводольному графі характеризується трудомісткістю ( ). 4 O V Відома задача про зважене паросполучення у довільному графі H з n вершинами зводиться до однієї з задач про паросполучення для дводольного графа з 2n вершинами. Максимальне паросполучення графа H з мінімальною сумою ваг ребер, заданих матрицею nij c ][ , знаходиться за час ( ) 3 O n після впорядкування за незменшенням значень ij c , розташованих над головною діагоналлю.Посилання
Пападимитриу Х. Комбинаторная оптимизация : Алгоритмы и сложность / Х.Пападимитриу, К.Стайглиц. – М. : Мир, 1985. – 510 с.
Ловас Л. Прикладные задачи теории графов. Теория паросочетаний в математике, физике, химии / Л.Ловас, М.Пламмер. – М. : Мир, 1998. – 653 с.
Харари Ф. Теория графов / Ф.Харари. – М. : Мир, 1973. – 300 с.
Маций О.Б. Быстрый алгоритм нахождения 2-фактора минимального веса / О.Б. Маций, А.В. Морозов, А.В. Панишев // Кибернетика и системный анализ. – 2015. – Т. 52, № 4. – С. 119–127.
Касьянов В.Н. Графы в программировании: обработка, визуализация и применение / В.Н. Касьянов, В.А. Евстигнеев. – С-Пб. : БХВ-Петербург, 2003. – 1104 с.
Кристофидес Н. Теория графов. Алгоритмический подход / Н.Кристофидес. – М. : Мир, 1978. – 432 с.
Майника Э. Алгоритмы оптимизации на сетях и графах / Э.Майника. – М. : Мир, 1981. – 323 с.
Нечипуренко М.И. Алгоритмы и программы решения задач на графах и сетях / М.И. Нечипуренко, В.К. Попков, С.М. Маймагалиев и др. – Новосибирск : Наука, Сиб. отд-ние, 1990. – 515 с.
Свами Т. Графы, сети, алгоритмы / Т.Свами, К.Тхуласараман. – М. : Мир, 1984. – 454 с.
Саати Т. Целочисленные методы оптимизации и связанные с ними экстремальные проблемы/ Т.Саати. – М. : Мир, 1973. – 330 с.
##submission.downloads##
Опубліковано
Як цитувати
Номер
Розділ
Ліцензія
Авторське право (c) 2020 Надія Олександрівна Кушнір, Ольга Борисівна Мацій, Володимир Олександрович Скачков
Ця робота ліцензується відповідно до Creative Commons Attribution-NonCommercial 4.0 International License.
Автор, який подає матеріали до друку, зберігає за собою всі авторські права та надає відповідному виданню право першої публікації, дозволяючи розповсюджувати даний матеріал із зазначенням авторства та джерела первинної публікації, а також погоджується на розміщення її електронної версії на сайті Національної бібліотеки ім. В.І. Вернадського та у відкритому доступі в електронному архіві університету та на сайті журналу.
