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

Определения

Определение:

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

Определение:

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

Связь между [math]\varkappa[/math], [math]\lambda[/math] и минимальной степенью вершины

Пускай минимальная степень вершины графа G обозначается буквой [math]\delta[/math]. Тогда:

Теорема:

Для любого графа G справедливо следующее неравенство: [math]\varkappa \le\lambda \le \delta [/math]

Доказательство:

[math]\triangleright[/math]

1) Проверим второе неравенство. Если в графе G нет ребер, то [math] \lambda = 0 [/math]. Если ребра есть, то несвязный граф получаем из данного, удаляя все ребра, инцидентные вершине с наименьшей степенью. В любом случае [math] \lambda \le \delta [/math]. 2) Чтобы проверить первое неравенство нужно рассмотреть несколько случаев. Если G - несвязный или тривиальный граф, то [math] \varkappa = \lambda = 0 [/math]. Если G связен и имеет мост x, то [math]\lambda = 1 [/math]. В последнем случае [math] \varkappa = 1 [/math], поскольку или граф G имеет точку сочленения, инцидентную ребру x, или же G = K2. Наконец, предположим, что граф G содержит множество из [math] \lambda \ge 2 [/math] ребер, удаление которых делает его несвязным. Ясно, что удаляя [math]\lambda - 1 [/math] ребер из этого множества получаем граф, имеющий мост x = uv. Для каждого из этих [math]\lambda - 1 [/math] ребер выберем какую-либо инцидентную с ним вершину отличную от u и v. Удаление выбранных вершин приводит к удалению [math]\lambda - 1 [/math] (а возможно, и большего числа) ребер. Если получаемый после такого удаления граф не связен, то [math]\varkappa \lt \lambda [/math]; если же он связен, то в нем есть мост x, и поэтому удаление вершины u или v приводит либок несвязному, либо к тривиальному графу. в любом случае [math] \varkappa \le \lambda[/math].

[math]\triangleleft[/math]

Теорема:

Для любых натуральных чисел a, b, c, таких что a ≤ b ≤ c, существует граф G, у которого [math]\varkappa = a, \lambda = b[/math] и [math]\delta = c [/math].

Доказательство:

[math]\triangleright[/math]

Рассмотрим граф 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], причем не осталось ни одной помеченной вершины, у которой не появилось хотя бы одно новое ребро, инцидентное ей. Тогда: 1) Поскольку b ≤ c, то было как минимум две непомеченные вершины, поэтому [math] \delta[/math] = с, так как минимальные степени вершин графов [math]G_1[/math] и [math]G_2[/math] была c, а степени их вершин не уменьшались. 2) Заметим, что между двумя вершинами графа G существует не меньше a вершинно-непересекающихся простых цепей, следовательно по теореме Менгера [math]\varkappa [/math] ≥ a. Однако если удалить из графа G помеченные вершины его подграфа [math]G_2[/math], то граф G потеряет связность. Значит, [math]\varkappa [/math] = a. 3) Аналогично рассуждению пункта 2, легко убедится, что [math]\lambda [/math] = b.

[math]\triangleleft[/math]

Литература

• Харари Фрэнк Теория графов = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6