загрузка...
загрузка...
На головну

Теорема про максимальний потік і мінімальному розрізі

  1. Аксіома Больцано-Вейєрштрасса і теорема про стягують системі відрізків
  2. У функціональному розрізі
  3. В) Теорема про зміну моментів кількості руху для матеріальної системи (теорема моментів)
  4. Валовий зовнішній борг Республіки Білорусь в розрізі секторів економіки та фінансових інструментів, млн. Доларів США
  5. ВЗАЄМОДІЯ ЗВУКОВ У МОВНОМУ ПОТОЦІ
  6. ВЗАЄМОДІЯ ЗВУКОВ У МОВНОМУ ПОТОЦІ
  7. Питання 2 Особливості аналізу звітної інформації в розрізі операційних сегментів

У додатках теорії графів при аналізі потоків в мережах з одним джерелом s і одним стоком r і обмеженою пропускною спроможністю основним завданням є пошук максимального потоку в мережі з постійними пропускними здатностями дуг і змінними інтенсивностями джерела і стоку (тобто потоку максимальної величини, що впадає в стік, а не потоку максимальної узагальненої вартості в сенсі виразу (2)). Алгоритм пошуку максимального потоку будується на базі того найпростішого факту, що потік через розріз не може бути більше його пропускної здатності, що, в свою чергу, призводить до теоремі Форда і Фалкерсона (про максимальний потік і мінімальному розрізі):

 в будь-якій мережі з одним джерелом і одним стоком величина максимального потоку від джерела до стоку дорівнює величині мінімального розрізу.

Так, для мережі (рис. 6) мінімальний розріз Cmin = {[1,2]; (1, 3)}; а його величина Rc = 3 + 2 = 5 дорівнює величині максимально можливого потоку з вузла 1 до вузла 4 (див. Рис. 7).

 



Попередня   1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   Наступна

Вступ | Перелік використовуваних надалі позначень | визначення | Дерева і деревовидних | Матричні уявлення мереж | Постановка задачі | Алгоритм рішення (алгоритм Дейкстри) | приклад рішення | Приклади економічних задач, що зводяться до задачі про найкоротшою ланцюга | Алгоритм рішення (алгоритм Літтла) |

загрузка...
© um.co.ua - учбові матеріали та реферати