Базуючись на розвитку ідеї пошуку в ширину у дводольних графах та основних визначеннях теорії паросполучень, показано, що задача побудови максимального паросполучення в довільному графі може бути зведена до його дводольного випадку. Доведено, що кожному поточному паросполученню в довільному графі взаємно однозначно відповідає паросполучення в дводольному графі. Проілюстровано, що жодний із поточних розв'язків задачі побудови максимального паросполучення в довільному графі не втрачається у випадку переходу до ітераційної схеми побудови максимального паросполучення у дводольному графі. Для знаходження збільшувального шляху відносно фіксованого паросполучення потужності k запропоновано модифікацію відомого алгоритму пошуку шляхів із даної вершини у всі досяжні вершини довільного графу. Роботу запропонованої модифікації проілюстровано на прикладі. На основі викладених ідей, доведених тверджень і запропонованих алгоритмів та їх модифікації побудовано алгоритм знаходження максимального паросполучення з покращеною часовою оцінкою, у порівнянні з відомим алгоритмом Едмонса, що має часову оцінку складності O(n<^>4). Основним недоліком алгоритму Едмонса є використання трудомісткої техніки стиснення циклів непарної довжини, які називають "квітками", що робить алгоритм непридатним для застосування в системах реального масштабу часу. Інші відомі алгоритми відрізняються від алгоритму Едмонса тільки більш досконалою організацією зберігання даних та обчислень, разом із тим зберігаючи складні дії щодо виявлення та упаковки циклів непарної довжини. Запропонований підхід переходу від довільного графу до дводольного графу надав можливість уникнути виникнення циклів непарної довжини, що надало можливість значно підвищити ефективність алгоритму. Подальше підвищення продуктивності є можливим за рахунок побудови паралельних версій алгоритму й оптимальної організації зберігання даних.

 Наукова періодика України 

---

Додаткова інформація про автора(ів) публікації:
(cписок формується автоматично, до списку можуть бути включені персоналії з подібними іменами або однофамільці)

• Морозов Анатолій Олексійович (1939–) (технічні науки)
• Морозов Андрій Юрійович (філософські науки)

  Якщо, ви не знайшли інформацію про автора(ів) публікації, маєте бажання виправити або відобразити більш докладну інформацію про науковців України запрошуємо заповнити "Анкету науковця"