Разрез (теория графов)
(перенаправлено с «Разрез графа»)
Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 11 августа 2021 года; проверки требуют 3 правки.
Разре́з гра́фа в задачах о потоке — такая пара множеств вершин (S,T), что
- , где — множество вершин графа
- , где — исток, — сток.
Величиной разреза называется сумма пропускных способностей таких рёбер , что .
Другие определения разреза (сечения) графа[править | править код]
- Разрез графа — множество рёбер, образующих двудольный подграф, удаление которых делит граф на две или более компоненты, которые, в частности, могут быть изолированными узлами. А также линия, проходящая через все рёбра разреза графа.
Характеристики[править | править код]
- Линии сечения могут пересекать произвольное число рёбер и хорд.
- Для получения главного сечения графа нужно линию сечения графа провести таким образом, чтобы она пересекала только одну ветвь графа при произвольном пересечении хорд.
См. также[править | править код]
В статье не хватает ссылок на источники (см. рекомендации по поиску). |