Теорема Менгера
| Лемма: |
x, y вершины G, существует k вершинно непересекающихся пути из x в y. Тогда все остальные пути пересекают выбранные k следующим образом:
а) существуют вершины, принадлежащие первым k путям, такие, что любой новый путь проходит через одну из них. б) на каждом из путей не более одной такой вершины |
| Доказательство: |
| Пусть, существуют пути, не проходящие через одну из таких вершин , и тогда последние 2 пути не пересекаются с первыми k, а по условию у нас всего k непересекающихся путей, а не |
| Теорема: |
Пусть G - конечный, неориентированный граф, для всех пар вершин существует k вершинно непересекающихся путей из x в y |
| Доказательство: |
|
Пусть, существует лишь вершинно непересекающихся путей. Тогда все остальные пути будут пересекать эти m, причем по лемме можно удалить вершин так, чтобы разорвать все добавленные пути и l из выбранных изначально.. Тогда удалив m вершин (l и по одной из оставшихся путей) мы разорвем все пути из x в y. Однако, по условию необходимо удалить k вершин, чтобы граф потерял связность. Значит, предположение неверно. Прямое следствие доказано. Докажем обратное: Между x и y существует k вершинно неперескающихся путей, очевидно, нельзя удалить вершин так, чтобы граф потерял связность. Покажем, что достаточно удалить k вершин, чтобы граф потерял связность. Возьмем все пути из x в y, они пересекут выбранные k, причем по лемме можно выбрать не более k точек пересечения. Удалив все вершины пересечения и произвольные вершины из оставшихся путей (всего не более k) мы порвем все пути. Теорема доказана. |
| Теорема: |
Пусть G - конечный, неориентированный граф, для всех пар вершин существует k реберно непересекающихся путей из x в y |
