11.4. Главное разбиение графа

В этом разделе описывается главное разбиение графа, введенное в работе [11.7]. Как мы увидим, главное разбиение графа G определяет разбиение системы ребер Е графа G, использование которого в методе смешанных переменных приводит к минимальному числу независимых переменных. Наши рассуждения основаны на работах [11.7, 11.8].

Рассмотрим связный граф G. Все его подграфы, которые будут рассматриваться в этом разделе, являются реберно-порожденными подграфами. Поэтому подграф и его система ребер будут обозначаться одним и тем же символом.

Расстояние между двумя остовами графа G определяется как

Таким образом, равно числу ребер, которые имеются в и которых нет в Легко показать, что Число общих ветвей Число общих хорд Говорят, что остовы являются максимально удаленными, если для любой пары остовов и

графа G. Например, образуют пару максимально удаленных остовов графа, представленного на рис. 11.4.

Теорема 11.4. Пусть образуют пару максимально удаленных остовов связного графа

1. Фундаментальный цикл графа G по отношению к или определенный общей хордой не содержит общих ветвей этих остовов.

Рис. 11.4.

2. Фундаментальное сечение графа G по отношению к определенное общей ветвью , не содержит общих хорд этих остовов.

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

Доказательство п. 2 следует из принципа двойственности.

Пусть с — общая хорда, общая ветвь для любых двух остовов Тогда последовательность , где Т означает либо либо называется выводимой последовательностью длиной i от общей хорды с до общей ветви b, если Р имеет следующие свойства:

1. входят в последовательность Р попеременно.

2. находится в фундаментальном цикле по отношению к определяемом хордой с.

3. b находится в фундаментальном сечении по отношению к Т, определяемом

4. Если входят в в виде где или то — хорда , а — ветвь входит в фундаментальный цикл по отношению к , определенный Заменяя в этом определении цикл на разрез, а ветвь на хорду, можно, исходя из принципа двойственности, определить выводимую последовательность от общей ветви к общей хорде. Фактически если Р является выводимой последовательностью от общей хорды с к общей ветви b, то последовательность Р, записанная как и Р, но в обратном порядке, будет выводимой последовательностью от b к с. В качестве примера рассмотрим остовы графа, представленного

на рис. 11.5. Ребро 5 является общей хордой а ребро 2 — общей ветвью Тогда является выводимой последовательностью от 5 к 2, а выводимой последовательностью от 2 к 5.

Рис. 11.5.

Пусть образуют пару максимально удаленных остовов. Предположим, что существует выводимая последовательность Р: длиной 1 от общей хорды с к общей ветви b. Тогда , равные , образуют пару максимально удаленных остовов, для которых с — общая хорда, общая ветвь. Далее, общая ветвь будет входить в фундаментальный цикл по отношению к определенный общей хордой с. Но это противоречит теореме 11.4. Таким образом, не существует выводимой последовательности длиной 1 от с к b. Из принципа двойственности можно показать, что не существует выводимой последовательности длиной 1 от b к с.

Теорема 11.5. Пусть с — общая хорда, общая ветвь пары остовов связного графа. Если являются максимально удаленными, то не существует выводимых последовательностей от с к b и от b к с.

Доказательство. Доказательство проводится по индукции для длины выводимой последовательности по отношению к любой паре максимально удаленных остовов.

Как было показано выше, не существует выводимой последовательности длиной 1 от общей хорды к общей ветви для любой пары максимально удаленных остовов.

Допустим, что не существует такой последовательности длиной меньше чем Предположим, что существует выводимая последовательность длины k от общей хорды с к общей ветви b для некоторой пары максимально удаленных остовов и Тогда она была бы кратчайшей такой последовательностью, так как (исходя из предположения) не существует такой последовательности длины, меньшей

Если , то образуют пару максимально удаленных остовов, для которых с — общая хорда, а — общая ветвь. Так как Р — кратчайшая последовательность длины k, можно показать, что является выводимой последовательностью от с к Однако Р имеет длину и это ведет к противоречию, так как мы предполагаем, что не существует такой последовательности длины

Аналогично если то образуют пару максимально удаленных остовов, для которых с — общая хорда, общая ветвь. Снова можно показать, что — выводимая последовательность от с к . Так как имеет длину приходим к противоречию.

Таким образом, не существует выводимой последовательности любой длины от общей хорды к общей ветви остовов Аналогично не существует выводимой последовательности любой длины от общей ветви к общей хорде.

Пусть с — общая хорда для заданной пары максимально удаленных деревьев

К — подграф графа G по отношению к с — строится следующим образом:

1. Пусть — множество ребер в фундаментальном цикле относительно определенного с. По теореме 11.4 множество не содержит общих ветвей.

2. Пусть — объединение всех фундаментальных циклов по отношению к определенных каждым ребром в По теореме 11.5 объединение не содержит общих ветвей.

3. Используя многократно приведенную выше схему, можно получать последовательность множеств ребер до тех пор, пока не достигнем множества

Тогда подграф, порожденный на множестве ребер называется К-подграфом по отношению к с.

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

Главным подграфом по отношению к общим хордам является объединение -подграфов относительно всех общих хорд. Главным подграфом по отношению к общим ветвям является объединение -подграфов по отношению ко всем общим ветвям. Например, главными подграфами G, и графа, представленного на рис. 11.4 по отношению к паре остовов являются

В работе [11.7] показано, что главные подграфы не имеют общих ребер. Если бы они имели общее ребро, то можно было бы построить выводимую последовательность от общей хорды к общей ветви.

Таким образом, любой граф G состоит из трех подграфов: — главного подграфа по отношению к общим хордам, — главного подграфа по отношению к общим ветвям, — подграфа Это разбиение графа G называется главным разбиением графа G. Интересно отметить [11.7], что главное разбиение графа G единственно и не зависит от выбора максимально удаленных остовов.

Некоторые полезные свойства главных подграфов перечислены ниже. Они следуют из определений этих подграфов.

P1. содержит все общие хорды, ноне содержит общих ветвей, содержит все общие ветви, но не содержит общих хорд.

Р2. Любой фундаментальный цикл по отношению к или определенный ребром в состоит только из ребер

Р3. Любое фундаментальное сечение по отношению к определенное ребром в состоит только из ребер .

Р4. являются остовными лесами

Р5. являются остовами графа полученного стягиванием всех ребер, не входящих в .

Р6. Любое ребро, концевые вершины которого являются компонентами также принадлежит .

Р7. Любое ребро, концевые вершины которого являются компонентами также принадлежит .

Р8. являются остовными лесами графа полученного включением всех ребер и удалением всех ребер (это свойство можно доказать, используя свойство РЗ).

Заметим, что если G не содержит общих хорд, и если G не содержит общих ветвей.

Рис. 11.6.

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

Теорема 11.6. Для графа G, имеющего в качестве главного разбиения, получаем

2) если то где — граф, полученный стягиванием всех ребер в ;

3) , где получен стягиванием всех ребер в G и удалением всех ребер в

4) максимальное расстояние между двумя любыми остовами равно

Доказательство. 1. Из свойства и из того, что получаем если

2. Из свойства и из того, что получаем если

3. Из свойства и из того, что получаем

4. Максимальное расстояние между любыми двумя остовами G равно

Пусть — максимальное расстояние между двумя остовами графа G, пусть — главное разбиение G. Тогда из доказанной выше теоремы имеем Но равно цикломатическому числу графа полученного стягиванием всех ребер в G (рис. 11.6). Следовательно, Пусть образуют произвольное разбиение множества ребер Е графа G. Пусть — подграф на множестве ребер

граф, полученный стягиванием всех ребер в . В работе [11.8] показано, что .

Заметим, что число независимых переменных в анализе со смешанными переменными, если использовать разбиение множества Е. Следовательно, можно заключить, что — минимальное число независимых переменных, требуемых в анализе со смешанными переменными. Это число может быть меньше ранга и цикломатического числа G. Таким образом, число независимых переменных в методе смешанных переменных может быть меньше требуемого для методов контуров и сечений. Например, граф G на рис. 11.4 имеет главное разбиение . Можно проверить, следовательно, . Таким образом, только три независимые переменные требуются для анализа цепи по методу смешанных переменных, тогда как оба метода контуров и сечений требуют по четыре независимых переменных.

В работе называется топологической степенью свободы цепи. Некоторые интересные свойства таких разбиений для которых обсуждаются в работе [11.8].

Авторы работ [11.7, 11.8] внесли несколько глубоких результатов в теорию графов. В работе [11.9] обсуждается алгоритм вычисления главного сечения графа. В работе [11.10] распространяется понятие «главное разбиение на матроиды».