Задача остовных деревьев в k–связном графе (стр. 7 из 10)
существует такие отличные от точек сочленения графа Guv вершины a 
VB1, c VBp, чтоua EG, vc EG. Легко видеть, что в графе Gvc имеется блок, содержащий все вершины множества
. Поэтому tvc>tuv, и снова получаем противоречие.3. Дерево 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, auv 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= ). Объединим цепь Prc(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. Снова получаем противоречие, которое и завершает доказательство теоремы.