Теорема Менгера

Две простых цепи называются непересекающимися на рёбрах, если они не имеют ни одного общего ребра, и непересекающимися на вершинах, если они не имеют ни одной общей вершины, кроме начальной и конечной.

Пусть G – связный граф и v, u – две разные его вершины. vu –разделяющим множеством в G называется множество R рёбер такое, что всякая цепь из v в u проходит через ребро из R. Аналогично, vu– отделяющим множеством в G называется множество S его вершин, которому не принадлежат вершины v и u и которое имеет то свойство, что всякая цепь из v в u проходит через вершину из множества S.

Теорема Менгера в рёберной форме.

Максимальнеое число простых цепей, которые не пересекаются на рёбрах и соединяют две разные вершины v и u связного графа G, равно минимальному числу k рёбер в vu–разделяющем множестве.

Теорема Менгера в вершинной форме.

Максимальное число простых цепей, которые не пересекаются на вершинах и соединяют две несмежные вершины v и u связного графа G, равно минимальному числу вершин в vu–отделяющем множестве.

Сравните теоремы Менгера, Холла и Форда–Фалкерсона!