Главная > Математика > Теория графов. Алгоритмический подход
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

6.5. Графы с выигрышами в вершинах

Задача о максимальном потоке (от для случая, когда пропускными способностями обладают вершины, была решена в разд. 3.2 с помощью простой замены каждой вершины парой вершин Аналогичным образом, если вершинам графа приписаны выигрыши и, следовательно, условия (11.14) непрерывности потока не выполняются, то мы можем образовать другой граф заменяя каждую вершину парой вершин с дугой между ними. Выигрыш этой дуги считается равным выигрышу вершины Для дуги из мы тогда имеем дугу а для дуги из дугу Задача после этого сводится к нахождению оптимальных потоков в графе в котором выигрыши приписаны только дугам.

7. Задачи

(см. скан)

(см. скан)

(см. скан)

8. Список литературы

(см. скан)

<< Предыдущий параграф Следующий параграф >>
Оглавление