Главная > Методы обработки данных > Графы, сети и алгоритмы
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

4.5. Связь между подпространствами циклов и разрезов

В данном разделе мы дадим характеризацию подграфов в пространстве циклов графа G в терминах подграфов подпространства разрезов того же графа.

В разд. 2.8 (теорема 2.14) мы доказали, что цикл и разрезающее множество имеют четное количество общих ребер. Используя то, что каждый подграф в подпространстве циклов графа является либо циклом, либо объединением реберно-непересекающихся циклов, а каждый подграф в подпространстве разрезов — разрезающим множеством или объединением реберно-непересекающихся разрезающих множеств, получим следующую теорему как непосредственное следствие теоремы 2.14:

Теорема 4.7. Любой подграф в подпространстве циклов графа G имеет четное число общих ребер с любым подграфом в подпространстве разрезов того же графа. В теореме 4.8 мы докажем обратное утверждение.

Теорема 4.8.

1. Подграф графа G принадлежит подпространству циклов графа G, если он имеет четное число общих ребер с любым подграфом в подпространстве разрезов графа G.

2. Подграф графа G принадлежит подпространству разрезов графа G, если он имеет четное число общих ребер с любым подграфом в подпространстве циклов графа G.

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

2. Доказательство этой части теоремы аналогично.

<< Предыдущий параграф Следующий параграф >>
Оглавление