8.2. Реберная связность
Реберная связность
графа G — это минимальное число ребер, удаление которых из графа приводит к несвязному или тривиальному графу. Другими словами,
— число ребер в разрезе с минимальным числом ребер. Например, для графа на рис. 8.4 реберная связность равна 2, поскольку удаление двух ребер
делает граф несвязным, а удаление произвольного одного ребра не приводит к несвязному графу.
Рис. 8.4. 2-реберно-связный граф.
Граф G называется
-реберно-связным, если
Таким образом, чтобы сделать несвязным реберно-связный граф, необходимо удалить хотя бы k ребер.
Поскольку ребра, инцидентные любой вершине v графа G, образуют разрез, то
В следующей теореме мы связываем величины
Теорема 8.5. Для простого графа
Доказательство. Второе неравенство мы уже доказали. Первое неравенство можно доказать следующим образом:
Если G — несвязный граф, то
. В этом случае условие
выполняется.
Если G — связный граф и
то граф G имеет мост
.
Если мы удалим в этом случае одну из вершин, с которыми инцидентен мосте, то получится несвязный или тривиальный граф. Следовательно, и в этом случае условие к
выполняется.
Предположим,
. Тогда в графе G имеется
ребер, удаление которых делает его несвязным. Удаление любых
из этих ребер приводит к графу с мостом
Для каждого из этих
ребер выберем концевую вершину, отличную от вершин
. Удаление этих вершин приведет к удалению из графа
ребер и, возможно, еще некоторых. Предположим, что получившийся граф несвязный. Тогда
. В противном случае граф будет иметь мосте, и поэтому удаление вершины
или
приведет к несвязному или тривиальному графу. В этом случае
Таким образом, во всех случаях
Сейчас мы представим достаточные условия того, что
равно
Этот результат получен Чартрэндом [8.3].
Теорема 8.6. Пусть G — простой граф на
вершинах. Если
то
Доказательство. Можно показать, что G — связный граф (упражнение 1.14). Поэтому
Так как
теорема будет доказана, если мы покажем, что
Допустим, что
Тогда существует такой разрез
что
. Пусть ребра из разреза
инцидентны q вершинам множества
вершинам множества
Допустим,
. Тогда каждая вершина множества
является концевой вершиной по крайней мере одного ребра разреза 5. Если обозначить через
порожденный подграф графа G на множестве вершин множества
то
имеет по крайней мере
ребер. Поскольку
то
так как
Это противоречит тому, что в простом графе не может быть больше чем
ребер, соединяющих q вершин. Поэтому
Аналогично доказываем, что
Если
то во множествах
имеются вершины, смежные только с вершинами множеств
соответственно. Следовательно, каждое из множеств
содержит по крайней мере по
вершин. Таким образом, граф G содержит не менее
вершин. Но
что противоречит условию. Следовательно, не существует разреза 5 с