Разрез графа

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

  1. S \cup T=V, где V — множество вершин графа
  2. S\cap T=\emptyset
  3. s \in S, t \in T, где s — исток, t — сток.

Величиной разреза называется сумма пропускных способностей таких рёбер (i, j), что i \in S, j \in T.

Другие определения разреза (сечения) графа[править | править исходный текст]

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

Характеристики[править | править исходный текст]

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

См. также[править | править исходный текст]