Таким чином, матриця інцидентності для орієнтованого графа завдання має вигляд:
Впорядкування вершин графа. алгоритм Фалкерсона
Зміна нумерації вузлів і дуг графів, рівно, як і їх конфігурацій, не змінює природної сутності явищ і процесів, які графи описують. У даній роботі - процес виробництва молочної продукції. Це властивість графів називається изоморфизмом. Рішення задач з залученням графів спрощується, якщо вершини і дуги графів розташувати в певному порядку.
Вважається, що з пари вершин орграфа вершина i є попередньої, а вершини j - наступної, якщо існує шлях з i в j, а шляху з j в i не існує.
Під упорядкуванням вершин орграфа розуміють таку нумерацію його вершин, при якій:
вершини першої групи не мають попередніх, а вершини останньої групи - наступних;
вершини будь-який інший групи не мають попередніх, а вершини останньої групи - наступних;
вершини одних і тих же груп дугами б не з'єднувалися.
Після впорядкування вершин виходить граф, ізоморфний вихідного.
Впорядкування вершин орграфа можна здійснити, дотримуючись алгоритму Фалкерсона, що включає в себе наступні кроки:
1. Знаходять вершини графа, в які не входять дуги. Це перший рівень вершин. Після нумерації вони разом з інцидентними їм дугами подумки видаляються з графа.
2. В останньому графі, як і в початковому, знаходять вершини, в які не входять дуги. Ці вершини в довільному порядку нумеруються натуральними числами, наступними після номерів вершин першого рівня. Це вершини другого рівня.
Виділення рівнів і нумерація продовжується аж до останньої вершини.
Впорядкуємо нумерацію вершин графа, слідуючи даним алгоритмом:
Малюнок 4.6 - ізоморфні граф
У вузол 1 графа завдання (рис. 4.2) не входить жодної дуги, а виходять дуги (1,3), (1,4). Надаємо вузлу 1 номер 1, зображуємо цей вузол на рис. 4.6 разом з виходять з нього дугами і подумки видаляємо цю вершину з вихідного графа.
Серед решти вузлів графа в вузол 2 тепер не входить жодної дуги. Надаємо вузлу номера 2 відповідно і зображуємо на рис.4.6. Подумки видаляємо цю вершину разом з інцидентними їй дугами з графа.
Тепер в вузол 3 не входить жодної дуги. Надаємо цій вершині номера 3 і переносимо її на рис. 4.6 і подумки видаляємо з графа.
Далі ми бачимо, що в вузол 4 не входить жодної дуги. Надаємо йому номер 4 і переносимо на новий малюнок, подумки видаливши його з вихідного графа.
Після виконаної операції залишився вузол 5 без назв дуг. Надаємо йому номер 5 і переносимо на новий малюнок, подумки видаливши його з вихідного графа.
Серед решти вузлів графа в вузол 6 тепер не входить жодної дуги. Надаємо вузлу номера 6 відповідно і зображуємо на рис.4.6. Подумки видаляємо цю вершину разом з інцидентними їй дугами з графа.
Тепер в вузол 7 не входить жодної дуги. Надаємо цій вершині номера 7. переносимо її на рис. 4.6 і подумки видаляємо з графа.
Залишився єдиний вузол 8 без входять і виходять з нього дуг. Надаємо із сайтом номер 8 і зображуємо на рис. 4.6.
Таким чином, у нас вийшов новий упорядкований граф (рис. 4.6), ізоморфний вихідного графу (рис. 4.2).
Максимальна потужність потоку.
Алгоритм визначення максимального потоку:
1. Будується початковий потік
Виявляються підмножини А вершин, досяжних з витоку I по ненасиченим ребрах. Якщо при цьому стік S не потрапить в підмножина А, то побудований потік є максимальним, і задача вирішена. Якщо ж стік S потрапляє в підмножина А, то слід перейти до наступного пункту алгоритму.