Вершинная, рёберная связность, связь между ними и минимальной степенью вершины
Версия от 11:34, 18 января 2011; 192.168.0.2 (обсуждение) (→Связь между \varkappa, \lambda и минимальной степенью вершины)
Определения
Определение: |
Вершинной связностью | графа называется наименьшее число вершин, удаление которых приводит к несвязному или тривиальному графу.
Определение: |
Реберной связностью | графа называется наименьшее количество ребер, удаление которых приводит к несвязному или тривиальному графу.
Связь между , и минимальной степенью вершины
Пускай минимальная степень вершины графа
обозначается буквой . Тогда:Теорема: |
Для любого графа справедливо следующее неравенство: |
Доказательство: |
1) Проверим второе неравенство. Если в графе 2) Чтобы проверить первое неравенство нужно рассмотреть несколько случаев. Если нет ребер, то . Если ребра есть, то несвязный граф получаем из данного, удаляя все ребра, инцидентные вершине с наименьшей степенью. В любом случае . - несвязный или тривиальный граф, то . Если связен и имеет мост , то . В последнем случае , поскольку или граф имеет точку сочленения, инцидентную ребру , или же . Наконец, предположим, что граф содержит множество из ребер, удаление которых делает его несвязным. Ясно, что удаляя ребер из этого множества получаем граф, имеющий мост . Для каждого из этих ребер выберем какую-либо инцидентную с ним вершину отличную от и . Удаление выбранных вершин приводит к удалению (а возможно, и большего числа) ребер. Если получаемый после такого удаления граф не связен, то ; если же он связен, то в нем есть мост , и поэтому удаление вершины или приводит либок несвязному, либо к тривиальному графу. в любом случае . |
Теорема: |
Для любых натуральных чисел , таких что , существует граф , у которого и |
Доказательство: |
Рассмотрим граф , являющийся объединением двух полных графов и , содержащих вершину. Отметим вершин, принадлежащих подграфу и вершин, принадлежащих подграфу . Добавим в граф ребер так, чтобы каждое ребро было инцидентно помеченной вершине, лежащей в подграфе и помеченной вершине, лежащей в подграфе , причем не осталось ни одной помеченной вершины, у которой не появилось хотя бы одно новое ребро, инцидентное ей. Тогда:1) Поскольку , то было как минимум две непомеченные вершины, поэтому , так как минимальные степени вершин графов и были равны , а степени их вершин не уменьшались.2) Заметим, что между двумя вершинами графа теореме Менгера . Однако если удалить из графа помеченные вершины его подграфа , то граф потеряет связность. Значит, . 3) Аналогично рассуждению пункта 2, легко убедится, что существует не меньше a вершинно-непересекающихся простых цепей, следовательно по . |
Литература
- Харари Ф. Теория графов: Пер. с англ. / Предисл. В. П. Козырева; Под ред. Г.П.Гаврилова. Изд. 4-е. — М.: Книжный дом "ЛИБРОКОМ", 2009. — 60 с.