САНКТ-Петербурзький державний політехнічний університет
ІПММ
Кафедра Телематика при ЦНДІ РТК
Курсова робота з Теорії графів
за темою «Потоки в мережах»
Зміст
Завдання
Опис математичної моделі
Особливості реалізації
Розподіл Пойа - 1
Формування зв'язкового ациклического графа
Алгоритм пошуку потоку мінімальної вартості
Алгоритм Фалкерсона
Алгоритм Беллмана - Форда
Алгоритм Дейкстри
Результати роботи програми
Висновок
Список використаної літератури
Завдання
Сформувати зв'язний ациклічний граф випадковим чином відповідно до заданим розподілом (Пойа - 1).
Для заданих графів обчислити потік мінімальної вартості.
В якості величини потоку брати значення, рівне [2/3 * max], де max - максимальний потік.
Матриці пропускних спроможностей та вартості згенерувати випадковим чином.
Реалізувати алгоритми Фалкерсона, Дейкстри і Беллмана - Форда.
Опис математичної моделі
потік граф алгоритм матриця
Нехай - мережа, і - відповідно джерело і стік мережі. Дуги мережі навантажені ненегативними речовими числами, Якщо і - вузли мережі, то число - називається пропускною здатністю дуги Нехай задана функція дивергенції функції у вузлі називається число, яке визначається наступним чином:
Функція називається потоком в мережі, якщо:
. тобто потік через дугу неотрицателен і не перевершує пропускної здатності дуги;
. тобто дивергенція потоку дорівнює нулю у всіх вершинах, крім джерела і стоку.
Кількість називається величиною потоку f. Якщо то дуга називається насиченою.
Нехай paзpeз,.
Всякий розріз визначається розбиттям множини вершин V на дві підмножини S і Т, так що, а в Р потрапляють всі дуги, що з'єднують S і Т. Тоді, де - дуги від S до Т, - дуги від Т до S.
Сума потоків через дуги розрізу Р позначається F (P).
Сума пропускних спроможностей дуг розрізу Р називається пропускною здатністю розрізу і позначається С (Р):
Аналогічно, і суми потоків через відповідні частини розрізів.
Для завдань з потоками, граф G (V, E) повинен задовольняти умовам: - зв'язний граф без петель.
Існує один витік.
Існує один стік.
Кожній дузі поставлена ??у відповідність пропускна здатність дуги.
Теорема Фалкерсона. Максимальний потік в мережі дорівнює мінімальній пропускної здатності розрізу:
Шукаємо максимальний потік мінімальної вартості: якщо, то рішення немає (? - величина потоку, який хочемо знайти).
Якщо навпаки, то мінімізуємо суму:
Модифікація мережі щодо даного потоку:
модифікують щодо даного потоку мережа будується наступним чином:
(- безліч модифікованих вершин)
(- безліч фіктивних дуг)
Якщо (u, v) Е і, то; при цьому (тільки для дуг, по яких проходить потік).
; і. (Тільки для всіх ненасичених дуг, де немає протилежної потоку, в тому числі і для ненасичених дуг з потоком, щодо якого відбувається модифікація мережі).
Для всіх насичених дуг:; вважають, що
Особливості реалізації
Завдання полягає в реалізації обчислення потоку мінімальної вартості для сформованого графа відповідно із заданим розподілом (Пойа - 1). Спочатку мною формується зв'язний граф відповідно до розподілу. Потім обчислюється максимальний потік, за допомогою реалізованого алгоритму Фалкерсона і, в кінцевому підсумку, обчислюється потік мінімальної вартості, за допомогою алгоритму Беллмана - Форда і Дейкстри.
Розподіл Пойа - 1
Розподіл Пойа 1 - розподіл випадкової величини, приймаючої цілі невід'ємні значення, відповідно до формулами:
Де n gt; 0, b gt; 0, r gt;...
