Алгоритм знаходження максимального потоку в мережах

Authors

  • Б.П. Балюра Донецький національний університет імені Василя Стуса
  • В.М. Гончар Донецький національний університет імені Василя Стуса

Abstract

Задача знаходження максимального потоку в мережах є однією з фундаментальних задач дискретної математики і теорії графів. Ця задача полягає в пошуку максимального потоку, який може пройти від джерела до стоку в мережі, де дуги між вершинами мережі мають ваги, що відображають їх пропускну здатність. Оптимізація алгоритмів знаходження максимального потоку є важливим завданням, оскільки такі алгоритми використовуються в різних сферах, включаючи транспортні мережі, електричні мережі та інші. Одним з найпоширеніших алгоритмів знаходження максимального потоку є алгоритм Форда-Фалкерсона. Основна ідея полягає в тому, що починаючи з потоку нульової величини, ми постійно шукаємо збільшення потоку з джерела до стоку, використовуючи шляхи, які ще не насичені.

Author Biographies

Б.П. Балюра , Донецький національний університет імені Василя Стуса

студент 1 курсу спеціальності 122 «Комп’ютерні науки»

В.М. Гончар , Донецький національний університет імені Василя Стуса

асистент кафедри інформаційних технологій

References

Ревенчук, І., & Чуприна, А. (2018). Алгоритм Знаходження Максимального Потоку для Управління Комунікаційними Режимами Електричних Мереж в Системі «Smart Сity». «Інформаційні системи та технології» ІСТ-2018, 327.

Стьопкiн, А. В., & Пластун, Д. А. (2016). Алгоритм ФордаФалкерсона. Збiрник наукових праць фiзико-математичного факультету ДДПУ.—Слов’янськ: ДДПУ, 2016.—Випуск № 6—168 с. Для студентiв, аспiрантiв та науковцiв в галузi фiзико-математичних на-ук; вчителiв та викладачiв фiзико-математичних дисциплiн в ЗОШ та ВНЗ. РЕДАКЦIЙНА КОЛЕГIЯ, 84.

Published

2023-07-17

Issue

Section

Секція 2 Алгоритмізація та розробка програмного забезпечення