Связность и реберная связность

Связность

Связность графов — понятие в теории графов довольно интуитивное, обобщающее такие ранее введенные понятия, как точка сочленения, мост и блок. При исследовании вопроса о том, какой из двух графов «более связен», полезны два инварианта, называемые связностью и реберной связностью.

Относительно связности получено довольно много результатов. Некоторые из них являются вариантами классической теоремы Менгера, в которой говорится о числе непересекающихся цепей, соединяющих данную пару вершин графа. Мы покажем, что подобные утверждения справедливы и в других областях математики, отличных от теории графов.

Связностью æ=æ(G) графа G называется наименьшее число вершин, удаление которых приводит к несвязному или тривиальному графу. Из определения следует, что связность несвязного графа равна 0, а связность связного графа, имеющего точку сочленения, равна 1. Полный граф Кр нельзя сделать несвязным, сколько бы вершин из него ни удалять, а тривиальный граф получается из Кр после удаления р-1 вершин; поэтому к(Кр)=р-1. Иногда æ называют вершинной связностью.

Аналогично реберная связность l=l(G) графа G определяется как наименьшее количество ребер, удаление которых приводит к несвязному или тривиальному графу. Ясно, что l(K₁)=0, и вообще реберная связность несвязного графа равна 0, а реберная связность связного графа, имеющего мост, равна 1. Связность, реберная связность и наименьшая степень графа связаны неравенством, найденным Уитни.

Теорема. Для любого графа G

æ(G)<l(G)<d(G).

Доказательство. Проверим сначала второе неравенство. Если в графе G нет ребер, то l=0. Если ребра есть, то несвязный граф получаем из данного, удаляя все ребра, инцидентные вершине с наименьшей степенью. В любом случае l<d.

Чтобы получить первое неравенство, нужно рассмотреть несколько случаев. Если G — несвязный или тривиальный граф, то æ = l = 0. Если G связен и имеет мост х, то l=1. В последнем случае æ = 1, поскольку или граф G имеет точку сочленения, инцидентную ребру х, или же G=K2. Наконец, предположим, что граф G содержит множество из l > 2 ребер, удаление которых делает его несвязным. Ясно, что удаляя l - 1 ребер из этого множества, получаем граф, имеющий мост x = uv. Для каждого из этих l - 1 ребер

выберем какую-либо инцидентную с ним вершину, отличную от u и v. Удаление выбранных (выделенных) вершин приводит к удалению l - 1 (а возможно, и большего числа) ребер. Если получаемый после такого удаления граф не связен, то æ < l; если же он связен, то в нем есть мост, и поэтому удаление вершины u или v приводит либо к несвязному, либо к тривиальному графу. В любом случае æ<l

Чартрэнд и Харари построили семейство графов с заданными связностями, а также с данной наименьшей степенью. Полученный ими результат показывает, что ограничения, налагаемые на æ, l, и d теоремой, нельзя улучшить.

Теорема. Для любых целых чисел a,b, с (0<a<b<c) существует граф G, у которого æ(G)=a, l(G) = b и d(G)=c.

Чартрэнд установил, что если d достаточно велико, то второе неравенство теоремы становится равенством.

Теорема. Если граф G имеет р вершин и d(G)>[p/2], то l (G)=d(G).

Например, если G - регулярный граф степени r > р/2, то l(G) = r. В частности, l(Кр)=р-1.