Изменения
Нет описания правки
{{Определение
|definition=
'''''Вершинной связностью''''' <math>\varkappa = \varkappa ( G )</math> графа '''G''' называется наименьшее число вершин, удаление которых приводит к несвязному или тривиальному графу.
}}
{{Определение
|definition=
'''''Реберной связностью''''' <math>\boldsymbolmathcal\lambda = \boldsymbol\lambda ( G )</math> графа '''G''' называется наименьшее количество ребер, удаление которых приводит к несвязному или тривиальному графу.
}}
{{Теорема
|statement=
Для любого графа '''G''' справедливо следующее неравенство:<br/><math>\varkappa ( G ) \le \boldsymbolmathcal\lambda ( G ) \le \boldsymbol mathcal \delta (G)</math><ref><math>\boldsymbolmathcal\delta ( G )</math> - минимальная степень вершины графа '''G'''</ref>
|proof=
1) Проверим второе неравенство. Если в графе '''G''' нет ребер, то <math> \mathcal\lambda = 0 </math>. Если ребра есть, то несвязный граф получаем из данного, удаляя все ребра, инцидентные вершине с наименьшей степенью. В любом случае <math> \lambda ( G ) \le \delta ( G )</math>. <br/>2) Чтобы проверить первое неравенство нужно рассмотреть несколько случаев. Если '''G''' - несвязный или тривиальный граф, то <math> \varkappa = \lambda = 0 </math>. Если '''G''' связен и имеет мост ''x'', то <math> \mathcal\lambda = 1 </math>. В последнем случае <math> \varkappa = 1 </math>, поскольку или граф '''G''' имеет точку сочленения, инцидентную ребру ''x'', или же '''G = K<sub>2</sub>'''. Наконец, предположим, что граф '''G''' содержит множество из <math> \lambda \ge 2 </math> ребер, удаление которых делает его несвязным. Ясно, что удаляя <math>\mathcal\lambda - 1 </math> ребер из этого множества получаем граф, имеющий мост ''x = uv''. Для каждого из этих <math>\mathcal\lambda - 1 </math> ребер выберем какую-либо инцидентную с ним вершину отличную от ''u'' и ''v''. Удаление выбранных вершин приводит к удалению <math>\mathcal\lambda - 1 </math> (а возможно, и большего числа) ребер. Если получаемый после такого удаления граф не связен, то <math>\varkappa < \lambda </math>; если же он связен, то в нем есть мост ''x'', и поэтому удаление вершины ''u'' или ''v'' приводит либок несвязному, либо к тривиальному графу. в любом случае <math> \varkappa ( G ) \le \lambda ( G )</math>.
}}
{{Теорема
|statement=
Для любых натуральных чисел a, b, c, таких что a ≤ b ≤ c, существует граф ''G'', у которого <math>\varkappa ( G ) = a, \lambda ( G ) = b</math> и <math>\mathcal\delta ( G ) = c </math>.
|proof=
Рассмотрим граф G, являющийся объединением двух полных графов <math>G_1</math> и <math>G_2</math>, содержащих c + 1 вершину. Выберем b вершин, принадлежащих подграфу <math>G_1</math> и a вершин, принадлежащих подграфу <math>G_2</math>. Добавим в граф G b ребер так, чтобы каждое ребро было инцидентно помеченной вершине, лежащей в подграфе <math>G_1</math> и помеченной вершине, лежащей в подграфе <math>G_2</math>, причем не осталось ни одной помеченной вершины, у которой не появилось хотя бы одно новое ребро, инцидентное ей.
Тогда: <br>
1) Поскольку b ≤ c, то было как минимум две непомеченные вершины, поэтому <math> \mathcal \delta</math> = с, так как минимальные степени вершин графов <math>G_1</math> и <math>G_2</math> была c, а степени их вершин не уменьшались.<br>
2)Заметим, что между двумя вершинами графа G существует не меньше a вершинно-непересекающихся простых цепей, следовательно по теореме Менгера <math>\varkappa </math> ≥ a. Однако если удалить из графа G помеченные вершины его подграфа <math>G_2</math>, то граф G потеряет связность. Значит, <math>\varkappa </math> = a.<br>
3) Аналогично рассуждению пункта 2, легко убедится, что <math>\mathcal\lambda </math> = b.
}}
<references/>
