Вершинная, рёберная связность, связь между ними и минимальной степенью вершины — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''''Вершинной связностью''''' <math>\varkappa = \varkappa ( G )</math> графа ''G'' называется наименьшее число вершин, удаление которых приводит к несвязному или тривиальному графу.
+
'''''Вершинной связностью''''' <math>\varkappa = \varkappa ( G )</math> графа '''G''' называется наименьшее число вершин, удаление которых приводит к несвязному или тривиальному графу.
 
}}
 
}}
  
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''''Реберной связностью''''' <math>\boldsymbol\lambda = \boldsymbol\lambda ( G )</math> графа ''G'' называется наименьшее количество ребер, удаление которых приводит к несвязному или тривиальному графу.
+
'''''Реберной связностью''''' <math>\boldsymbol\lambda = \boldsymbol\lambda ( G )</math> графа '''G''' называется наименьшее количество ребер, удаление которых приводит к несвязному или тривиальному графу.
 
}}
 
}}
  

Версия 02:59, 4 октября 2010

Определение:
Вершинной связностью [math]\varkappa = \varkappa ( G )[/math] графа G называется наименьшее число вершин, удаление которых приводит к несвязному или тривиальному графу.


Определение:
Реберной связностью [math]\boldsymbol\lambda = \boldsymbol\lambda ( G )[/math] графа G называется наименьшее количество ребер, удаление которых приводит к несвязному или тривиальному графу.


Теорема:
Для любого графа G справедливо следующее неравенство:
[math]\varkappa ( G ) \le \boldsymbol\lambda ( G ) \le \boldsymbol \delta (G)[/math][1]
Доказательство:
[math]\triangleright[/math]

1) Проверим второе неравенство. Если в графе G нет ребер, то [math] \mathcal\lambda = 0 [/math]. Если ребра есть, то несвязный граф получаем из данного, удаляя все ребра, инцидентные вершине с наименьшей степенью. В любом случае [math] \lambda ( G ) \le \delta ( G )[/math].

2) Чтобы проверить первое неравенство нужно рассмотреть несколько случаев. Если G - несвязный или тривиальный граф, то [math] \varkappa = \lambda = 0 [/math]. Если G связен и имеет мост x, то [math] \mathcal\lambda = 1 [/math]. В последнем случае [math] \varkappa = 1 [/math], поскольку или граф G имеет точку сочленения, инцидентную ребру x, или же G = K2. Наконец, предположим, что граф 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 \lt \lambda [/math]; если же он связен, то в нем есть мост x, и поэтому удаление вершины u или v приводит либок несвязному, либо к тривиальному графу. в любом случае [math] \varkappa ( G ) \le \lambda ( G )[/math].
[math]\triangleleft[/math]
Теорема:
Для любых натуральных чисел a, b, c, таких что a ≤ b ≤ c, существует граф G, у которого [math]\varkappa ( G ) = a, \lambda ( G ) = b[/math] и [math]\mathcal\delta ( G ) = c [/math].
  1. [math]\boldsymbol\delta ( G )[/math] - минимальная степень вершины графа G