- Разрез графа
-
Разре́з гра́фа в задачах о потоке — такая пара множеств вершин (S,T), что
- , где — множество вершин графа
- , где — исток, — сток.
Величиной разреза называется сумма пропускных способностей таких рёбер , что .
Другие определения разреза (сечения) графа
- Разрез графа — множество рёбер, удаление которых делит граф на два изолированных подграфа, один из которых, в частности, может быть отдельным узлом.
- Разрез графа — линия, делящая граф на две несвязанные части.
Характеристики
- Линии сечения могут пересекать произвольное число ребер и хорд.
- Для получения главного сечения графа нужно линию сечения графа провести таким образом, чтобы она пересекала только одну ветвь графа при произвольном пересечении хорд.
См. также
Категория:- Теория графов
Wikimedia Foundation. 2010.