Изменения
Новая страница: «{{Определение |definition= '''''Вершинной связностью''''' <math>\varkappa = \varkappa ( G )</math> графа <math>G</math> назыв…»
{{Определение
|definition=
'''''Вершинной связностью''''' <math>\varkappa = \varkappa ( G )</math> графа <math>G</math> называется наименьшее число вершин, удаление которых приводит к несвязному или тривиальному графу.
}}
{{Определение
|definition=
'''''Реберной связностью''''' <math>\boldsymbol\lambda = \boldsymbol\lambda ( G )</math> графа <math>G</math> называется наименьшее количество ребер, удаление которых приводит к несвязному или тривиальному графу.
}}
{{Теорема
|statement=
Для любого графа '''G''' справедливо следующее неравенство:<br/>
<math>\varkappa ( G ) \le \boldsymbol\lambda ( G ) \le \boldsymbol \delta (G)</math><ref><math>\boldsymbol\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=
}}
<references/>
|definition=
'''''Вершинной связностью''''' <math>\varkappa = \varkappa ( G )</math> графа <math>G</math> называется наименьшее число вершин, удаление которых приводит к несвязному или тривиальному графу.
}}
{{Определение
|definition=
'''''Реберной связностью''''' <math>\boldsymbol\lambda = \boldsymbol\lambda ( G )</math> графа <math>G</math> называется наименьшее количество ребер, удаление которых приводит к несвязному или тривиальному графу.
}}
{{Теорема
|statement=
Для любого графа '''G''' справедливо следующее неравенство:<br/>
<math>\varkappa ( G ) \le \boldsymbol\lambda ( G ) \le \boldsymbol \delta (G)</math><ref><math>\boldsymbol\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=
}}
<references/>
