Меню Главная Случайная статья Настройки Разрез (теория графов) Материал из https://ru.wikipedia.org Разрез графа в задачах о потоке — такая пара множеств вершин (S,T), что ${\displaystyle S\cup T=V}$, где ${\displaystyle V}$ — множество вершин графа ${\displaystyle S\cap T=\emptyset }$ ${\displaystyle s\in S,t\in T}$, где ${\displaystyle s}$ — исток, ${\displaystyle t}$ — сток. Величиной разреза называется сумма пропускных способностей таких рёбер ${\displaystyle (i,j)}$, что ${\displaystyle i\in S,j\in T}$. Другие определения разреза (сечения) графа Разрез графа — множество рёбер, образующих двудольный подграф, удаление которых делит граф на две или более компоненты, которые, в частности, могут быть изолированными узлами. А также линия, проходящая через все рёбра разреза графа. Характеристики Линии сечения могут пересекать произвольное число рёбер и хорд. Для получения главного сечения графа нужно линию сечения графа провести таким образом, чтобы она пересекала только одну ветвь графа при произвольном пересечении хорд. См. также Наименьший разрез Граф (математика) Поток в графе Теорема Форда — Фалкерсона