мо, ставимо мітки. p> Зміна потоку: В
Тому замінимо величину первісного потоку:
на
на,
Етап 2.
Переглянемо вершину V1, вершини V4 і V2 отримують мітки і Переглянемо V3, V2 вже оглядена,. Переглянемо V2, V4 вже позначена,
Зміна потоку:
В
Вносимо зміни потоку. Дуга (V2, t) стала насиченою. br/>В
Етап 3.
Переглянемо вершину V1. Вершини V4 і V2 отримують мітки
Переглянемо V3, V2 вже позначена, Переглянемо V2, V4 вже позначена, Переглянемо V4,
Зміна потоку:
В
Вносимо зміни потоку. Дуга (V3, V2) стала насиченою. br/>
Етап 4.
Переглянемо вершину V3. Вершини V2 і V3 отримують мітки
Переглянемо V2. Вершини V4, V5 і t отримують мітки
Зміна потоку:
Вносимо зміни потоку. Дуга (V3, V2) стала насиченою. br/>В
Етап 5.
Переглянемо вершину V3. Вершина V6 отримує мітку p> Переглянемо V6
Зміна потоку:
В
Вносимо зміни потоку. Дуга (S, V3) стала насиченою. br/>В
В
Потік f = 21 є максимальним, а безліч дуг складають мінімальний розріз мережі. Мінімальний розріз на малюнку позначений хвилястою лінією. br/>
Висновок.
Бурхливий розвиток дискретної математики обумовлено прогресом комп'ютерної техніки, необхідністю створення засобів обробки і передачі інформації, а також представлення різних моделей на комп'ютерах, що є за своєю природою кінцевими структурами.
Транспортної мережею називається кінцевий Зв'язний орграф G (V, E) без петель, кожній дузі якого поставлено у відповідність деяке невід'ємне число c (), зване пропускною здатністю дуги, і існує:
1) рівно одна вершина, до якої не заходит жодна дуга, звана джерелом або початком мережі ;
2) рівно одна вершина, з якої не виходить жодної дуги; ця вершина називається стоком або кінцем мережі .
В В В В В В В В В В В В В В В
Список використаної літератури
В
1. А.М. Аллавердіев, І.В. Платонова В«Прикладна математика. Елементи теорії графів В»М.2000
2. Лекції з прикладної математики І.В. Платонової
3. В.Н. Нефедов, В.А. Осипова В«Курс дискретної математики В»М. 1992
4. С.В. Судоплатов, Є.В. Овчинникова В«Елементи дискретної математикиВ» М. 2002
