Задача остовных деревьев в k–связном графе
Обозначим через Buv максимальный по числу вершин блок графа Guv, а через tuv– число вершин в этом блоке . Теперь выберем ребро uv так, чтобы число tuv было наибольшим.
Покажем,
что в этом случае
tuv
3.
Пусть tuv=2
и а
– висячая вершина
графа Guv
(являющегося
деревом). Так
как n
5,
то существует
ребро cd
EGuv.
Из свойства
1) вытекает, что
в графе Gcd
существует
цикл (u,a,v,u),
т.е. tcd>tuv.
Получено
противоречие,
следовательно,
tuv
3.
Через Duv обозначим bc-дерево графа Guv и рассмотрим следующие случаи.
Дерево Duv не является цепью. Выберем в этом дереве цепь, соединяющую пару висячих вершин и проходящую через вершину, соответствующую блоку Buv. Этой цепи соответствует последовательность B1,…,Bp блоков графа Guv, среди которых содержится блок Buv, причем блоки B1 и Bp являются висячими (рис. 5.6).
Пусть
B'– произвольный
висячий блок
графа Guv,
отличный от
B1 и Bp.
Из свойств 1) и
2) вытекает
существование
таких отличных
от точек сочленения
графа Guv
вершин a
VB1,
b
VBp,
c
VB',
uc
EG,
va
EG,
vb
EG.
Тогда в графе
Guc
вершины множества
входят в один
блок и, следовательно,
tuv<tuc.
Последнее
противоречит
выбору ребра
uv.
Дерево Duv–цепь и Buv–блок графа Guv, не являющийся висячим. Пусть B1,…,Bp – последовательность всех блоков графа G, причем блоки B1 и Bp–висячие, Bi
Bi+1
Ш
(i=
),
Buv=Bk
(1<k<p)
(рис.
5.7). Cогласно
свойству 3) найдется
вершина b
VBuv
отличная от
точек сочленения
графа Guv,
смежная с u
или с v.
Пусть ub
EG.
Согласно свойствам
1) и 2)

существует
такие отличные
от точек сочленения
графа Guv
вершины a
VB1,
c
VBp,
что
ua
EG,
vc
EG.
Легко видеть,
что в графе Gvc
имеется блок,
содержащий
все вершины
множества
.
Поэтому tvc>tuv,
и снова получаем
противоречие.
Дерево Duv – цепь и Buv – висящий блок графа Guv. Если граф Guv содержит такое ребро xy, что VBuv
{x,
y}=Ш,
то, используя
свойство 2), легко
показать, что
в графе Gxy
есть блок,
содержащий
множество
вершин VBuv
{x,
y},
а, значит tuv<txy.
Так как Buv
–
висячий блок
графа

Guv,
то последнее
означает, что
граф Guv
состоит из
блока Buv
и ребер ab1,ab2,…abl
(рис 5.8). Из 3–связности
графа G
следует, что
граф G
– а
не имеет точек
сочленения.
Поскольку в
графе G–
a
вершина b1
смежна только
с вершинами
u
и v,
a
uv
EG,
то граф
также не имеет
точек сочленения,
что противоречит
предположению.
Таким образом , показано ,что во всяком связном графе G существует такое ребро uv, что граф Guv не имеет точек сочленения. Доказано.
Следствие
5.8.
Всякий
3–связный граф
с числом вершин
n
5
содержит ребро,
стягивание
которого приводит
к 3–связному
графу.
Доказательство
также проведем
от противного.
Пусть, стягивая
некоторое ребро
x=uv
3–связного
графа G
в вершину
,
получаем граф
Gx,
для которого
(Gx)=2
(Равенство
(Gx)=1
невозможно
в силу 3–связности
графа G).
Тогда в графе
Gx
существуют
две вершины,
удаление которых
делают его
несвязным.
Одной из них
должна быть
(в
противном
случае
(Gx)=2).
Удалению вершины
из Gx
соответствует
удаление вершины
u
и v
из графа G.
Поэтому для
любого ребра
x=uv
EG
граф G
имеет такую
вершину w,
что граф G–u–v–w
несвязен. Вершина
w
является точкой
сочленения
графа Guv,
что противоречит
предыдущей
теореме. Доказано.
Отметим без доказательства следующую теорему.
Теорема 5.9. Почти все ребра двусвязны.
Поскольку каждый мост инцидентен точкам сочленения графа, то из этой теоремы вытекает
Следствие 5.10. Почти все графы не содержат мостов.
§6 Теорема Менгера.
Из теоремы 5.1 следует, что 2–граф связен тогда и только тогда, когда любые две его несовпадающие вершины a и b соединены парой простых (a, b) цепей, не имеющих общих вершин, за исключением a и b. Аналогичный критерий k–связности справедлив при произвольном k.
Говорят, что множество вершин S разделяет несмежные вершины a и b связного графа G, если в графе G – S вершины a и b принадлежат различным связным компонентам. В этой ситуации множество S называют также сепаратором или (a, b)–сепаратором. Две (a, b)–цепи графа G называют непересекающимися, если у них нет общих вершин, за исключением a и b, и реберно–непересекающимися, если у них нет общих ребер. Очевидно, непересекающиеся цепи являются и реберно–непересекающимися, а обратно, вообще говоря, неверно.
К. Менгер доказал в 1927 году следующую теорему, устанавливающую соотношение между числом непересекающихся простых цепей, соединяющих две несмежные вершины графа, и его связностью.
Теорема Менгера. Наименьшее число вершин, разделяющих две несмежные вершины графа a и b, равно наибольшему числу попарно непересекающихся простых (a, b)–цепей этого графа.
Приведем доказательство принадлежащее В. Маквайгу (1982 г.).
Ясно,
что если k
вершин разделяют
a и b,
то существует
не более k
попарно непересекающихся
(a, b)–цепей.
Остается показать,
что если в графе
G нет множества,
содержащего
менее чем k
вершин, разделяющих
несмежные
вершины a
и b, то
в нем имеется
k попарно
непересекающихся
цепей. Используем
индукцию по
k. утверждение
правильно при
k=1. Предположим,
что оно верно
для некоторого
k
1.
Рассмотрим
граф G, в
котором несмежные
вершины a
и b нельзя
разделить
множеством,
содержащим
менее чем k+1
вершин. По
предположению
индукции в G
имеется k
попарно непересекающихся
(a, b)–цепей
P1, P2,
…, Pk.
Рассмотрим
множество
вторых (считая
а первой) вершин
в этих цепях.
Это множество
состоит из k
вершин и, следовательно,
но оно не разделяет
вершины a
и b. Значит,
имеется (a,
b)–цепь
Р, первое ребро
которой не
принадлежит
ни одной из
цепей Pi
(i=
).
Пусть v–первая,
считая от а,
вершина Р,
принадлежащая
одной из Pi
(i=
),
и пусть Pk+1
обозначает
(a, v)–подцепь
цепи Р. Цепи
P1, …,
Pk,
Pk+1
могут быть
выбраны, вообще
говоря, многими
различными
способами.
Выберем их так,
чтобы в графе
G – a
расстояние
v до b
было минимально.
Если окажется,
что v=b,
то P1,
P2, …,
Pk+1
будет требуемым
набором k+1
цепей. Допустим,
что v
b.
Тогда в графе
G – v
вершины a
и b нельзя
разделить
множеством,
содержащим
менее чем k
вершин. По
индуктивному
предположению
в этом имеется
k непересекающихся
(a, b)
– цепей Q1,
Q2, …,
Qk,
которые могут
быть выбраны
разными способами.
Выберем их так,
чтобы множество

включало
минимальное
число ребер
этих цепей.
Иначе говоря,
цепи Qi
должны состоять
«в основном»
из ребер цепей
Pi.
Рассмотрим
теперь граф
H, состоящий
из вершин и
ребер цепей
Q1, Q2,
…, Qk
и вершины v
(эта вершина
будет в графе
H изолированной).
Пусть Pr
– одна из цепей
Pi
(i=
),
у которой ребро,
инцидентно
вершине а, не
принадлежит
EH. Ясно,
что такая цепь
среди Pi
(i=
)
найдется,
поскольку число
их равно k+1,
а цепей Qi,
составляющих
H, только
k. Пусть, далее,
x–первая,
считая от а,
вершина Pr,
входящая в VH.
Если
x=b,
то, добавив
цепь Pr
к Q1, Q2,
…, Qk,
получим требуемый
набор из k+1
(a, b)
цепей. Допустим,
что x
b,
и рассмотрим
другие возможности
для x.
Если
x=v, то обозначим
через R
кратчайшую
(v, b)
– цепь и G
– a. Пусть
z – первая,
считая от v,
вершина цепи
R, лежащая
на некоторой
Qj
(j=
).
Объединим цепь
Pr
c (v,
z) – подцепью
цепи R и
обозначим
полученную
(a, z)
– цепь через
Qk+1.
Цепи Q1,
Q2, …,
Qk,
Qk+1
обладают тем
свойством, что
расстояние
в графе G
– a от z
до b меньше,
чем расстояние
от v до b
, а это противоречит
выбору P1,
P2, …,
Pk,
Pk+1.
Рассмотрим
теперь последнюю
возможность:
x принадлежит
некоторой цепи
Qj
(j=
).
В этом случае
(a, x)
– подцепь цепи
Qi
имеет ребра
в L, иначе
бы две цепи в
{ P1,
P2, …,
Pk,
Pk+1}
пересекались
в вершинах,
отличных от
a, b,
v. Заменив
теперь (a,
x) – подцепь
Qi
на (a, x)
– подцепь Pr,
получим непересекающиеся
(a, b) –
цепи в графе
G – v,
и эти цепи будут
использовать
меньше ребер
из L, чем
Q1, …,
Qk.
Снова получаем
противоречие,
которое и завершает
доказательство
теоремы.
Из теоремы Менгера непосредственно вытекает
Теорема 6.1. (Х. Уитни, 1932 г.). граф k–связен тогда и только тогда, когда любая пара его несовпадающих вершин соединена по крайне мере k непересекающимися цепями.
Имеется несколько аналогов и обобщений теоремы Менгера. Здесь мы остановимся на реберном варианте этой теоремы.
Во многих прикладных задачах приходится рассматривать множество ребер (а не вершин, как ранее), разделяющих вершины a и b графа G, т.е. такое множество ребер R, что входит в различные компоненты графа G – R. Минимальное относительно включения множество R с этими свойствами называется (a, b) – разрезом графа.
Теорема 6.2. Наибольшее число реберно–непересекающихся цепей, соединяющих две вершины графа, равно наименьшему числу ребер, разделяющих эти вершины.
Доказательство
этой теоремы
легко получить,
используя
теорему Менгера.
С этой целью
сопоставим
графу G
граф G',
который получается
из G следующим
образом. Каждая
вершина v
VG
заменяется
группой из deg
v

попарно смежных вершин, а ребра графа 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}
выполняется
соотношение
(x,
y, Gz)=(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.
Назовем
новыми
ребра графа
G1,
добавленные
при разрезе
по вершине z.
Пусть этo ребра
e1,
…, em.
Поскольку при
построении
разреза было
добавлено k
ребер, после
чего были удалены
петли, то m
k.
По индукционному
предположению,
у графа G1
существуют
непересекающиеся
по ребрам остовные
деревья
T1,
T2,
…, Tk.
Опишем метод
построения
по каждому из
этих k деревьев
остовного графа
G. Все ребра, которые
могут входить
в деревья T1,
T2,
…, Tk,
либо являются
ребрами графа
G, либо новыми
ребрами. Пусть
дерево Ti
содержит mi
новых ребер,
тогда
m1+m2+…+mk
m
k
(1)
Если дерево Ti не содержит ни одного нового ребра, то оно является подграфом мультиграфа G. Поскольку множество вершин дерева Ti содержит все вершины графа G, кроме z, то добавив к Ti вершину z и любое ребро графа G с концом в z, мы получим остовное дерево T'i графа G. Отметим, что в этом случае для построения дерева T'i потребовалось одно ребро графа G, инцидентное вершине z (причем это ребро можно выбрать произвольно).
Предположим,
что mi>0,
то есть дерево
Ti
содержит новые
ребра. Поставим
в соответствие
дереву Ti
подграф Ti*
графа G,
в котором каждое
новое ребро
xy
дерева Ti
заменим
на два ребра
xy
и yz
графа G.
Каждое новое
ребро в дереве
Ti
соответствует
двум ребрам
в графе Ti*,
при этом, к вершинам
дерева добавляется
вершина z.
Следовательно,
мы получили
связный остовный
подграф Ti*
графа G,
в котором количество
ребер на mi-1
больше , чем в
дереве. Таким
образом, в графе
Ti*
ровно mi-1
цикл, причем
не трудно заметить,
что каждый из
этих циклов
проходит через
вершину z.
Следовательно,
из графа Ti*
можно удалить
mi-1
инцидентных
вершине z
ребер так, что
получится
отстовное
дерево Ti'
графа G.
В дерево Ti'
входит mi+1
ребро, инцидентное
вершине z.
По построению
очевидно, что
при i
j,
mi>0
и mj>0
остовные деревья
Ti'
и
Tj'
графа не имеют
общих ребер.
Пронумеруем
k
непересекающихся
по ребрам остовных
деревьев графа
G
таким образом,
чтобы деревья
T1,
…, Tn
содержали новые
ребра, а деревья
Tn+1,
…, Tk
не содержали
новых ребер
(где 0
).
С помощью описанного
выше способа
построим по
остовным деревьям
T1,
…, Tn
графа G1
остовные деревья
T'1,
…, T'n
графа G,
никакие два
из этих деревьев
не будут иметь
общих ребер.
Всего при построении
этих n деревьев
использовано
(m1+1)+…+(mn+1)
ребер графа
G,
инцидентных
вершине z.
В силу неравенства
(1), мы получаем,
что
(m1+1)+…+(mn+1)=(m1+m1+…+m1)+n
(2)
Следовательно,
в силу неравенства
(2), и так как dG(z)
,
остались
неиспользованными
еще хотя бы
n-k
ребер графа
G,
инцидентных
вершине z.
Для дополнения
каждого из
оставшихся
деревьев Tn+1,
…, Tk
до остовного
дерева графа
G требуется