Разрез (теория графов)
-
Определение разреза в теории графов
- Разрез — это разбиение вершин графа на два подмножества.
- Разрез определяет множество ребер, которые пересекают его.
- В связном графе каждый набор разрезов определяет уникальный разрез.
-
Разрез s-t в потоковой сети
- Разрез s-t требует, чтобы источник и приемник были в разных подмножествах.
- Его набор разрезов состоит из ребер, идущих от источника к приемнику.
- Пропускная способность разреза s-t равна сумме пропускных способностей ребер в его наборе.
-
Размер и вес разреза
- В невзвешенном графе размер разреза равен количеству ребер, пересекающих его.
- На взвешенном графе вес разреза равен сумме весов ребер, пересекающих его.
-
Связь и минимальный разрез
- Связь — это набор разрезов, который не имеет других наборов разрезов в качестве подмножества.
- Минимальный разрез — это разрез с наименьшим размером или весом.
-
Максимальный разрез
- Разрез считается максимальным, если его размер не меньше размера любого другого разреза.
- Нахождение максимального разреза является сложной задачей.
-
Задача о максимальном расходе
- Задача о максимальном расходе — это двойственная задача к задаче о минимальном расходе.
-
Самый редкий срез
- Задача о самом редком срезе — это задача минимизации отношения числа ребер к числу вершин в меньшей половине разреза.
- Эта задача является NP-сложной и имеет аппроксимацию O(log n).
-
Сократить пространство
- Срезанные множества образуют векторное пространство над конечным полем с симметричной разностью в качестве операции сложения.
- Минимальный весовой базис пространства разрезов может быть описан деревом Гомори-Ху.
Полный текст статьи: