143
правки
Изменения
разделяющий набор
Наименьшее число вершин, разделяющих две несмежные вершины s и t, равно наибольшему числу непересекающихся простых (s-t) цепей
|proof=
{{Определение
statement=
Множество S вершин, ребер или вершин и ребер разделяет u и v, если u и v принадлежат различным компонентам графа <math>G-S</math>
}}
Очевидно, что если k вершин разделяют s и t, то сущесвует не более k непересекающихся простых (s-t) цепей.
Теперь покажем, что k вершин графа разделяют s и t, существует k непересекающихся простых (s-t) цепей. Для k=1 это очевидно.
любой набор W, содержащий h вершин и разделяющий s и t является смежным с s или t
|proof=
Пусть W - произвольный набор h вершин, разделяющих s и t в G. Цепь, соединяющую s с некоторой вершиной <math>w_i \in W</math> и не содержащую других вершин из W будем называть (s-W) цепью. Аналогично назовем (W-t) цепь. Обозначим наборы всех (s-W) и (W-t) цепей <math>P_s</math> и <math>P_t</math> соответственно.Тогда каждая (s-t) цепь начинается с элемента из <math>P_s</math> и заканчивается элементом из <math>P_t</math>, поскольку любая цепь содержит вершину из W. Общие вершины цепей из <math>P_s</math> и <math>P_t</math> принадлежат набору W, так как по крайней мере одна цепь из каждого набора <math>P_s</math> и <math>P_t</math> содержит (любую) вершину <math>w_i</math>, и если бы существовала некоторая вершина, не принадлежащая набору W, но содержащаяся сразу и в (s-W) и в (W-t) цепи, то нашлась бы (s-t) цепь, не имеющая вершин из W. Наконец, выполняется либо равенство <math>P_s-W={s}</math>, либо равенство <math>P_t - W={t}</math>, поскольку в противном случае либо <math>P_s</math> вместе с ребрами <math>\{w_1t,w_2t...\}</math>, либо <math>P_t</math> вместе с ребрами <math>\{sw_1,sw_2...\}</math> образуют связные графы с меньшим числом вершин, чем у G, в которых s и t не смежны, и, следовательно, в каждом из них имеется h непересекающихся (s-t) цепей. Объединяя (s-W) и (W-t) части этих цепей, образуем в графе G h непересекающихся (s-t) цепей. Мы пришли к противоречию. Утверждение доказано.
}}
Пусть <math>P=\{s, u_1, u_2 ... t\}</math> - кратчайшая (s-t) цепь в G, <math>u_1u_2=x</math> Заметим, что из(I) <math>u_1 <> t</math> Образуем множество <math>S(x)=\{v_1, ... , v_{h-1}\}</math>, разделяющее в <math>G-x</math> вершины s и t. Из (I) следует, что <math>u_1t \notin G</math> Используя (II) и беря <math>W=S(x)\cup {u_1}</math>, получаем <math>\forall i sv_i \in G</math> Таким образом в силу (I) <math>\forall v_it \notin G</math>. Однако, если выбрать <math>W=S(x) \cup {u_2}</math>, то в силу (II) получим <math>su_2 \in G</math>, что противоречит выбору P как кратчайшей (s-t) цепи. Из полученного противоречия следует, что графа G, удовлетворяющего указанным условиям не существует, а значит не существует и графа F, для которого теорема не верна
Пусть G - конечный, неориентированный граф, <math>\lambda(G) = k</math> <math>\Leftrightarrow</math> для всех пар вершин <math>x, y \backepsilon G</math> существует k реберно непересекающихся путей из x в y
|proof=
Аналогично вершинному случаю
}}
