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

7.4. Простые потоки

Пусть в данной сети есть множество дуг, образующих простую цепь пли простой цикл в соответствующем неориентированном графе. Предположим,

что мы ориентируем ребра, проходя эти простые цепи и циклы в одном из возможных направлений. Дуга С будет называться нормальной, если ее вновь введенная ориентация совпадает с исходной и обращенной (инвертированной) в противном случае.

Определим на А следующим образом:

На рис. 7.4 показаны простая цепь С, ориентированная от ориентированный простой цикл и соответствующие функции

Легко проверить, что если С — простая цепь, соединяющая и ориентированная от то является потолом из к величина которого равна 1.

Рис. 7.4.

Этот поток называется простым потоком по цепи из и в и. Аналогично, если цикл, ориентированный в одном из двух направлений, то поток в имеющий величину, равную нулю, называется простым потоком по циклу. Потоки этих двух типов (и только этих) называются далее простыми потоками. Простые потоки рассматриваются как элементарные блоки, из которых можно построить и на которые можно разложить любой поток.

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