Разрез (теория графов)

Материал из Википедии — свободной энциклопедии
(перенаправлено с «Разрез графа»)
Перейти к навигации Перейти к поиску

Разре́з гра́фа в задачах о потоке — такая пара множеств вершин (S,T), что

  1. , где  — множество вершин графа
  2. , где  — исток,  — сток.

Величиной разреза называется сумма пропускных способностей таких рёбер , что .

Другие определения разреза (сечения) графа

[править | править код]
Разрез графа
  • Разрез графа — множество рёбер, образующих двудольный подграф, удаление которых делит граф на две или более компоненты, которые, в частности, могут быть изолированными узлами. А также линия, проходящая через все рёбра разреза графа.

Характеристики

[править | править код]
  • Линии сечения могут пересекать произвольное число рёбер и хорд.
  • Для получения главного сечения графа нужно линию сечения графа провести таким образом, чтобы она пересекала только одну ветвь графа при произвольном пересечении хорд.