2.8. Остовы, циклы и разрезающие множества

В этом разделе мы обсудим некоторые интересные результаты, связывающие разрезающие множества и циклы с остовами и кодеревьями соответственно. Эти результаты выявляют двойственную

природу циклов и разрезающих множеств. Они приводят к альтернативным характеризациям разрезающих множеств и циклов в терминах остовов и кодеревьев соответственно.

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

Теорема 2.9. Разрезающее множество связного графа G содержит по крайней мере одну ветвь каждого остова графа

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

Теорема 2.10. Цикл связного графа G содержит по крайней мере одно ребро каждого кодерева графа

Доказательство. Пусть цикл С графа G не содержит ни одного ребра кодерева Т остова Т графа G. Тогда граф будет содержать цикл С. Так как совпадает с остовом Т, то, следовательно, остов Т содержит цикл. Но это противоречит определению остова.

Теорема 2.11. Множество ребер S связного графа G является разрезающим множеством G тогда и только тогда, когда S — минимальное множество ребер, содержащих по крайней мере одну ветвь каждого остова графа

Доказательство.

Необходимость. Если множество ребер S графа G является разрезающим множеством, то по теореме 2.9 оно содержит по крайней мере одну ветвь каждого остова графа G. Если оно не является таким минимальным множеством, то собственное подмножество S множества S будет содержать по крайней мере одну ветвь каждого остова графа G. Тогда не будет содержать ни одного остова графа и будет несвязным. Таким образом, удаление собственного подмножества S разрезающего множества S графа G превращает последний в несвязный граф. Однако это будет противоречить определению разрезающего множества. Следовательно, необходимость доказана.

Достаточность. Пусть S — минимальное множество ребер, содержащее по крайней мере одну ветвь каждого остова графа G. Тогда граф не будет содержать ни одного остова и, следовательно, будет несвязным. Предположим, что S не является разрезающим множеством. Тогда собственное подмножество S множества - S будет разрезающим. Следовательно, из доказательства необходимости этой теоремы S будет минимальным множеством ребер, содержащим по крайней мере одну ветвь каждого остова графа G. Но это противоречит тому, что S — минимальное такое множество. Следовательно, достаточность доказана.

Эта теорема характеризует разрезающее множество в терминах остовов. Сформулируем подобную характеризацию для циклов с использованием кодеревьев.

Рассмотрим множество ребер С, образующее цикл в графе G. По теореме 2.10 множество С содержит по крайней мере одно ребро каждого кодерева графа G. Покажем, что никакое собственное подмножество С множества С не обладает этим свойством. Очевидно, что С не содержит цикл. Тогда по теореме 2.4 можно построить

остов Т, содержащий подмножество С. Кодерево Т, соответствующее Т, не имеет общих ребер с С. Следовательно, для каждого собственного подмножества С множества С существует по меньшей мере одно кодерево Т, не имеющее общих ребер с подмножеством С. В самом деле, это утверждение верно для каждого ациклического подграфа. Таким образом, имеем следующую теорему:

Теорема 2.12. Циклом связного графа G является минимальное множество ребер графа, содержащее по крайней мере одно ребро каждого кодерева графа G. Докажем обратную теорему.

Теорема 2.13. Множество ребер С связного графа G есть цикл в G, если оно является минимальным множеством, содержащим по крайней мере одно ребро каждого кодерева графа G.

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

Теоремы 2.12 и 2.13 устанавливают, что множество ребер С связного графа G будет циклом тогда и только тогда, когда оно является минимальным множеством ребер, содержащим по крайней мере одно ребро каждого кодерева графа G. Новые характеризации разрезающего множества и цикла, полученные с помощью теорем 2.11-2.13, выявляют двойственную природу понятий «цикл» и «разрезающее множество». Эту двойственность мы подробнее исследуем в гл. 10 при обсуждении теории матроидов.

Следующая теорема связывает циклы и разрезающие множества без использования понятия «дерево».

Теорема 2.14. Цикл и разрезающее множество связного графа имеют четное число общих ребер.

Доказательство. Пусть С — цикл, разрезающее множество связного графа — множества вершин двух связных подграфов графа

Если С — подграф графа или то, очевидно, число ребер, общих в С и S, равно нулю, т. е. четному числу.

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

Поскольку передвижение должно кончиться в вершине необходимо, чтобы каждый раз мы встречались с ребром множества S, ведущим нас от вершины в множестве к вершине в множестве ; также должно существовать ребро S, переводящее нас из вершины в множестве назад, к вершине в множестве Это возможно только в том случае, если С и S имеют четное число общих ребер.

Мы доказали очень важную теорему. Она формулирует соотношение ортогональности между разрезающими множествами и циклами. Это соотношение будет позднее рассмотрено в гл. 4.

Следует отметить, что теорема, обратная теореме 2.14, не совсем верна. Однако в гл. 4 мы покажем, что множество S графа G является разрезающим множеством (циклом) или объединением

нескольких реберно-непересекающихся разрезающих множеств (циклов) тогда и только тогда, когда множество S имеет четное число ребер, входящих в пересечение с каждым циклом (разрезающим множеством).

Базисные циклы и разрезающие множества связного графа были определены относительно остова. И не удивительно, что базисные циклы и разрезающие множества связаны между собой следующим образом:

Теорема 2.15. 1. Базисный цикл по отношению к хорде остова Т связного графа состоит точно из тех ветвей Т, которым соответствуют базисные разрезающие множества, включающие эту хорду. 2. Базисное разрезающее множество по отношению к ветви остова Т связного графа состоит точно из тех хорд остова Т, которым соответствуют базисные циклы, включающие эту ветвь.

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

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

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

2. Доказывается аналогично.