Теорема Менгера — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Лемма)
(Фикс доказательств)
Строка 1: Строка 1:
 
{{Лемма
 
{{Лемма
−
|statement=x, y вершины G, существует k вершинно непересекающихся пути из x в y. Тогда каждый из выбранных k путей будет иметь не более, чем одну точку пересечения с остальными путями.
+
|statement=x, y вершины G, существует k вершинно непересекающихся пути из x в y. Тогда все остальные пути пересекают выбранные k следующим образом:
 +
а) существуют вершины, принадлежащие первым k путям, такие, что любой новый путь проходит через одну из них.
 +
б) на каждом из путей не более одной такой вершины
 
|proof=
 
|proof=
−
Пусть, существуют пути <math>x, u_1 ...q...p... u_n, y</math>, <math>x, v_1 ...q... v_m, y</math> и <math>x, w_1 ...p... w_p, y</math> тогда последние 2 пути не пересекаются с первыми k, а по условию у нас всего k непересекающихся путей, а не <math>k + 1</math>
+
Пусть, существуют пути, не проходящие через одну из таких вершин <math>x, u_1 ...q...p... u_n, y</math>, <math>x, v_1 ...q... v_m, y</math> и <math>x, w_1 ...p... w_p, y</math> тогда последние 2 пути не пересекаются с первыми k, а по условию у нас всего k непересекающихся путей, а не <math>k + 1</math>
 
}}
 
}}
  
Строка 9: Строка 11:
 
Пусть G - конечный, неориентированный граф, <math>\kappa(G) = k</math> <math>\Leftrightarrow</math> для всех пар вершин <math>x, y \backepsilon G</math> существует k вершинно непересекающихся путей из x в y
 
Пусть G - конечный, неориентированный граф, <math>\kappa(G) = k</math> <math>\Leftrightarrow</math> для всех пар вершин <math>x, y \backepsilon G</math> существует k вершинно непересекающихся путей из x в y
 
|proof=
 
|proof=
−
Пусть, существует лишь <math>m < k</math> вершинно непересекающихся путей. Тогда все остальные пути будут пересекать эти m, причем с каждым из m все пересечения будут происходить в одной точке(если это не так, то можно было бы выбрать больше, чем m путей). Тогда удалив m точек пересечения (если с путем не пересекаются другие пути - то любую вершину) мы разорвем все пути из x в y. Однако, по условию необходимо удалить k вершин, чтобы граф потерял связность. Значит, предположение неверно. Прямое следствие доказано.
+
Пусть, существует лишь <math>m < k</math> вершинно непересекающихся путей. Тогда все остальные пути будут пересекать эти m, причем по лемме можно удалить <math>l \le m</math> вершин так, чтобы разорвать все добавленные пути и l из выбранных изначально.. Тогда удалив m вершин (l и по одной из оставшихся <math>m - l</math> путей) мы разорвем все пути из x в y. Однако, по условию необходимо удалить k вершин, чтобы граф потерял связность. Значит, предположение неверно. Прямое следствие доказано.
 
Докажем обратное:
 
Докажем обратное:
−
Между x и y существует k вершинно неперескающихся путей, очевидно, нельзя удалить <math>m < k</math> вершин так, чтобы граф потерял связность. Покажем, что достаточно удалить k вершин, чтобы граф потерял связность. Возьмем все пути из x в y, они пересекут выбранные k, причем каждый из них в одной точке. Удалив точки пересечения мы порвем все пути. Теорема доказана.
+
Между x и y существует k вершинно неперескающихся путей, очевидно, нельзя удалить <math>m < k</math> вершин так, чтобы граф потерял связность. Покажем, что достаточно удалить k вершин, чтобы граф потерял связность. Возьмем все пути из x в y, они пересекут выбранные k, причем по лемме можно выбрать не более k точек пересечения. Удалив все вершины пересечения и произвольные вершины из оставшихся путей (всего не более k) мы порвем все пути. Теорема доказана.
  
 
}}
 
}}
Строка 19: Строка 21:
 
Пусть G - конечный, неориентированный граф, <math>\lambda(G) = k</math> <math>\Leftrightarrow</math>  для всех пар вершин <math>x, y \backepsilon G</math> существует k реберно непересекающихся путей из x в y
 
Пусть G - конечный, неориентированный граф, <math>\lambda(G) = k</math> <math>\Leftrightarrow</math>  для всех пар вершин <math>x, y \backepsilon G</math> существует k реберно непересекающихся путей из x в y
 
|proof=
 
|proof=
 +
 
}}
 
}}

Версия 16:16, 10 октября 2010

Лемма:
x, y вершины G, существует k вершинно непересекающихся пути из x в y. Тогда все остальные пути пересекают выбранные k следующим образом:

а) существуют вершины, принадлежащие первым k путям, такие, что любой новый путь проходит через одну из них.

б) на каждом из путей не более одной такой вершины
Доказательство:
[math]\triangleright[/math]
Пусть, существуют пути, не проходящие через одну из таких вершин [math]x, u_1 ...q...p... u_n, y[/math], [math]x, v_1 ...q... v_m, y[/math] и [math]x, w_1 ...p... w_p, y[/math] тогда последние 2 пути не пересекаются с первыми k, а по условию у нас всего k непересекающихся путей, а не [math]k + 1[/math]
[math]\triangleleft[/math]
Теорема:
Пусть G - конечный, неориентированный граф, [math]\kappa(G) = k[/math] [math]\Leftrightarrow[/math] для всех пар вершин [math]x, y \backepsilon G[/math] существует k вершинно непересекающихся путей из x в y
Доказательство:
[math]\triangleright[/math]

Пусть, существует лишь [math]m \lt k[/math] вершинно непересекающихся путей. Тогда все остальные пути будут пересекать эти m, причем по лемме можно удалить [math]l \le m[/math] вершин так, чтобы разорвать все добавленные пути и l из выбранных изначально.. Тогда удалив m вершин (l и по одной из оставшихся [math]m - l[/math] путей) мы разорвем все пути из x в y. Однако, по условию необходимо удалить k вершин, чтобы граф потерял связность. Значит, предположение неверно. Прямое следствие доказано. Докажем обратное:

Между x и y существует k вершинно неперескающихся путей, очевидно, нельзя удалить [math]m \lt k[/math] вершин так, чтобы граф потерял связность. Покажем, что достаточно удалить k вершин, чтобы граф потерял связность. Возьмем все пути из x в y, они пересекут выбранные k, причем по лемме можно выбрать не более k точек пересечения. Удалив все вершины пересечения и произвольные вершины из оставшихся путей (всего не более k) мы порвем все пути. Теорема доказана.
[math]\triangleleft[/math]
Теорема:
Пусть G - конечный, неориентированный граф, [math]\lambda(G) = k[/math] [math]\Leftrightarrow[/math] для всех пар вершин [math]x, y \backepsilon G[/math] существует k реберно непересекающихся путей из x в y
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Теорема_Менгера&oldid=3482»