Теорема Форда-Фалкерсона о максимальном потоке

Дата публикации PostDateIcon 12.03.2012 |

Теорема (Форда-Фалкерсона) о максимальном потоке: всякая транспортная сеть имеет максимальный поток и его величина Mf = cmin.

Доказательство: Построим полный поток сети S по теореме 1. Тогда всякий направленный путь в S от s к t насыщен (имеет насыщенную дугу). По теореме 2 (см. потоки в транспортных сетях) построим поток, для которого всякая ненаправленная цепь от s к t, имеющая обратные дуги не допускает увеличение потока. По теореме 3 построенный поток максимален и его величина Mf = cmin.

Похожие записи
  1. Класс самодвойственных функций и его замкнутость относительно суперпозиции. Критерий самодвойственности. Лемма о несамодвойственной функции.
  2. Класс линейных функций и его замкнутость относительно суперпозиции
  3. Раскрашивание планарных графов. Теорема о пяти красках. Теорема о четырех красках
  4. СДНФ и СКНФ
  5. Булевы свойства логических операций. Эквивалентные преобразования формул
  6. Класс функций, сохраняющих константу
  7. Теорема об устойчивости. Теорема об неустойчивости
  8. Матричная теорема Кирхгофа о деревьях
  9. Теорема Поста о функциональной полноте
  10. Нормальные подгруппы, фактор группы, теорема групповом гомоморфизме
  11. Многочлен циклов (цикловой индекс), теорема Пойа
  12. Теорема Кэли о числе помеченных деревьев с р вершинами
  13. Сравнение мощностей. Теорема Кантора-Бернштейна.
  14. Двойственные функции. Теорема о суперпозиции двойственных функций. Принцип двойственности
  15. Системы различных представителей, теорема Холла о совершенном паросочетании в двудольном графе
  16. Булевы решетки и булевы алгебры
  17. Решетки в дискретной математике
PostCategoryIcon Рубрика: Математика

Комментарии запрещены.


Поиск
Категории


Статистика

Образовательный блог разработан в 2009 году.