Теорема Менгера
В математической дисциплине теории графов теорема Менгера утверждает, что в конечном графе размер минимального набора разрезов равен максимальному количеству непересекающихся путей, которые можно найти между любой парой вершин. Доказанная Карлом Менгером в 1927 году, она характеризует связность графа . Он обобщается теоремой о максимальном потоке и минимальном разрезе , которая является взвешенной краевой версией и которая, в свою очередь, является частным случаем сильной теоремы двойственности для линейных программ.
Все эти утверждения (как в реберной, так и в вершинной версии) остаются верными в ориентированных графах (при рассмотрении направленных путей).
Большинство прямых доказательств рассматривают более общее утверждение, позволяющее доказать его по индукции. Также удобно использовать определения, включающие некоторые вырожденные случаи. Следующее доказательство для неориентированных графов работает без изменений для ориентированных графов или мультиграфов, если мы берем путь к среднему ориентированному пути.
Для наборов вершин A,B ⊂ G (не обязательно непересекающихся) AB-путь — это путь в G с начальной вершиной в A , конечной вершиной в B и без внутренних вершин в A или B . Мы допускаем путь с одной вершиной в A ∩ B и нулевыми ребрами. AB -сепаратор размера k — это множество S из k вершин (которые могут пересекаться с A и B ), такое что G−S не содержит AB - пути. AB -соединитель размера kявляется объединением k вершинно-непересекающихся AB -путей.
Другими словами, если никакие k −1 вершин не отделяют A от B , то существует k непересекающихся путей из A в B . Этот вариант влечет указанное выше утверждение о связности вершин: для x,y ∈ G из предыдущего раздела применим текущую теорему к G− { x,y } с A = N(x) , B = N(y) , соседним вершины х, у . Тогда множество вершин, разъединяющих x и y , есть то же самое, что и AB -разделитель, а удаление концевых вершин в множестве независимых xy-paths дает AB -соединитель.
Доказательство теоремы: [1] Индукция по числу ребер в G . Для G без ребер минимальным AB - сепаратором является A ∩ B , который сам является AB -коннектором, состоящим из одновершинных путей.
