Разре́з гра́фа в задачах о потоке — такая пара множеств вершин (S,T), что
- , где — множество вершин графа
- , где — исток, — сток.
Величиной разреза называется сумма пропускных способностей таких рёбер , что .
Энциклопедичный YouTube
-
1/3Просмотров:48612 497449
-
Лекция 5. Теория графов. Задачи о максимальном потоке и минимальном разрезе.
-
Задача о максимальном потоке в сети, часть 1
-
Семинар 5. Теория графов. Задачи о максимальном потоке и минимальном разрезе.
Субтитры
Другие определения разреза (сечения) графа
- Разрез графа — множество рёбер, образующих двудольный подграф, удаление которых делит граф на две или более компоненты, которые, в частности, могут быть изолированными узлами. А также линия, проходящая через все рёбра разреза графа.
Характеристики
- Линии сечения могут пересекать произвольное число рёбер и хорд.
- Для получения главного сечения графа нужно линию сечения графа провести таким образом, чтобы она пересекала только одну ветвь графа при произвольном пересечении хорд.
См. также
Эта страница в последний раз была отредактирована 24 декабря 2022 в 15:16.
Как только страница обновилась в Википедии она обновляется в Вики 2.
Обычно почти сразу, изредка в течении часа.
Обычно почти сразу, изредка в течении часа.