Задача остовных деревьев в k–связном графе (стр. 8 из 10)
Из теоремы Менгера непосредственно вытекает
Теорема 6.1. (Х. Уитни, 1932 г.). граф k–связен тогда и только тогда, когда любая пара его несовпадающих вершин соединена по крайне мере k непересекающимися цепями.
Имеется несколько аналогов и обобщений теоремы Менгера. Здесь мы остановимся на реберном варианте этой теоремы.
Во многих прикладных задачах приходится рассматривать множество ребер (а не вершин, как ранее), разделяющих вершины a и b графа G, т.е. такое множество ребер R, что входит в различные компоненты графа G – R. Минимальное относительно включения множество R с этими свойствами называется (a, b) – разрезом графа.
Теорема 6.2.Наибольшее число реберно–непересекающихся цепей, соединяющих две вершины графа, равно наименьшему числу ребер, разделяющих эти вершины.
Доказательство этой теоремы легко получить, используя теорему Менгера. С этой целью сопоставим графу G граф G', который получается из G следующим образом. Каждая вершина v 
VG заменяется группой из degv
попарно смежных вершин, а ребра графа G', соединяющие вершины из разных групп, находятся в биективном соответствии с ребрами графа G' (рис. 6.1). Если в графе G нет (a, b) – разреза, содержащего менее чем k ребер, то в G' нет множества, имеющего менее чем k вершин, разделяющего какую-либо пару вершин a', b' из групп, соответствующих a и b. Тогда по теореме Менгера вершины a', b' соединены в G' по крайней мере k вершинно-непересекающимися цепями , которым соответствует столько же реберно-непересекающихся (a, b) – цепей графа G.
С другой стороны, ясно, что граф, имеющий (a, b) – разрез из k ребер, может содержать не более k реберно- непересекающихся (a, b) – цепей.
Глава III
Выделение k непересекающихся остовных деревьев
2k–реберно связном графе
Из классического результата теории графов – теоремы Менгера– известно, что для любых двух вершин x и y графа G локальная реберная связность 
(x, y, G) равняется наибольшему количеству непересекающихся по ребрам путей от x до y в графе G. Однако, при k>1 не во всяком графе G с реберной связностью
(G) 
k существуют k непересекающихся по ребрам связных остовов. Из ранее известных результатов «глобальным ананлогом» теоремы Менгера в некоторой степени является доказанный результат: в графе G с реберной связностью (G) k существуют k остовных деревьев T1, T2, …, Tk такие, что для любого j от 1 до k объединение деревьев T1, T2, …, Tj дает j–реберно связный граф.В настоящей работе мы рассматриваем еще один глобальный аналог теоремы Менгера: будет доказано, что при (G) 2k в графе G существует k остовных деревьев, не имеющих общих ребер. Мы докажем необходимость условия (G) 2k при k>1. Более того, мы построим примеры (2k-1)–связныцх графов, у котороых минимальная степень вешины больше любого заданного числа, но среди любых k связных остовов какие–то два имеют общее ребро.
В нашей работе используется редукционная техника, которую разработал . Введем необходимые понятия и обозначения.
Пусть W– множество из нескольких вершин графа G. Через G-W мы, как обычно, будем обозначать граф, полученный из G при удалении всех вершин множества W и всех выходящих из них ребер. Пусть F– множество из нескольких ребер графа G. Через G-F мы , будем обозначать граф, полученный из G при удалении вcех ребер множества F.
Для произвольной вершины x графа G через dG(x) мы будем обозначать степень вершины x в графе G(V, E). Для x 
V, A 
V через dG(x, A) обозначим количество ребер, соединяющих вершину x с вершинами множества A (с учетом кратных ребер). Минимальную степень вершины в графе G будем обозначать через 
(G), a максимальную степень– через 
(G).
Пусть z–вершинa четной степени в графе G. Рассмотрим граф G-z, разобъем на пары все вершины, смежные в графе G с z и соединим вершины в парах. Полученный граф Gz назовем разрезом графа G по вершине z.
§7. Построение k непересекающихся остовных деревьев.
Теорема 7.1.Пусть граф G(V, E) таков что
(G)=k, а вершина z V не является точкой сочленения. Тогда существует такой разрез Gz графа G по вершине z, что для любых x,y V\{z} выполняется соотношение l(x, y, Gz)=l(x, y, G) и, в частности (Gz) (G).Замечание. Доказательство обобщается на случай , когда вершина z–точка сочленения, но ни одно из ребер с концами в z не является мостом. В частности, при (G) 2 для любой вершины z существует разрез по z такой, что (Gz) (G).
Теорема 7.1 позволяет редуцировать граф, не уменьшая реберной связности. Это открывает широкие возможности для построения различных конструкций. В наших конструкциях также использует последовательные разрезы графа по вершинам опирается на теорему 7.1.
Для построения нам также потребуется классический результат относительно минимально k–связных графов.
Теорема 7.2.Пусть степени всех вершин мультиграфа G(V, E) строго более k и (G) k. Тогда существует ребро e E такое, что (G-e) k.
Замечание. Впервые результат теоремы 7.2 для графов без кратных ребер доказал . Это доказательство обобщается на случай мультиграфа .
Перейдем к доказательству основного результата настоящей работы.
Теорема 7.3.Пусть мультиграф G(V, E) (в нем допускается наличие кратных ребер, но запрещены петли) таков, что (G) 2k. Тогда у мультиграфа G существуют попарно k непересекающиеся ребра остовных дерева.
Доказательство. Будем доказывать теорему индукцией по количеству вершин в мультиграфе G0. База для мультиграфа с двумя вершинами очевидна. Предположим, что теорема доказана для любого 2k– реберно связного мультиграфа, у которого меньше вершин, чем у G. По теореме 7.2, у графа G(V, E) существует остовный подграф G0(V, E0), такой, что (G0)=2k и одна из его вершин z
V имеет степень d 
(z)=2k. Очевидно , что граф G0–z связен, следовательно, по теореме 7.1 существует разрез G 
графа G0 по вершине z такой, что (G ) 2k. Если в графе G есть петли, то уберем их. Из условия (G ) 2k следует, что графа G1, полученного из G в результате удаления петель, выполняется условие (G1) 2k.