7.4. Двойственные графы

Граф является двойственным к графу если существует такое взаимно-однозначное соответствие их ребер, что множество ребер графа — циклический вектор тогда и только тогда, когда соответствующее множество ребер графа — вектор разрезающего множества . Двойственность была впервые определена Уитни [7.11], хотя его определение было дано в другой форме.

Очевидно, чтобы доказать двойственность графа достаточно показать, что векторы, образующие базис подпространства

циклов графа соответствуют векторам, образующим базис подпространства разрезов графа

Рассмотрим, например, графы представленные на рис. 7.8. Ребро - графа соответствует ребру графа Легко видеть, что циклы образуют базис подпространства циклов графа а соответствующие множества ребер образуют базис подпространства разрезов графа

Рис. 7.8. Двойственные графы.

Таким образом, граф двойственный к графу

Изучим теперь некоторые свойства двойственных графов.

Теорема 7.7. Пусть граф двойственный к графу Тогда цикл графа соответствует разрезающему множеству графа и наоборот.

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

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

Поскольку С — объединение то очевидно, что множество С должно содержать более одного цикла. Однако это невозможно, так как С — цикл, а никакое собственное подмножество цикла не является циклом. Следовательно, или, другими словами, С — разрезающее множество графа

Аналогичным образом можно показать, что каждому разрезающему множеству графа соответствует цикл графа

Георема 7.8. Если граф — двойственный к графу то последний — двойственный к графу

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

Пусть С — циклический вектор графа — соответствующее ему множество ребер графа

По теореме 4.7 вектор С имеет четное число общих ребер со всяким вектором разрезающего множества графа Так как граф двойственный к графу то множество С имеет четное число общих ребер со всяким циклическим вектором графа . Поэтому по теореме 4.8 С — вектор разрезающего множества графа

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

Принимая во внимание эту теорему, будем называть графы просто двойственными, если один из них двойственный к другому. Следующий результат вытекает непосредственно из теоремы 7.8 и определения двойственности.

Теорема 7.9. Если — двойственные графы, то ранг одного равен цикломатическому числу другого, т. е.

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

Теорема 7.10. Рассмотрим двойственные графы Пусть — ребро графа — соответствующее ребро графа Пусть — граф, полученный из графа удалением ребра — граф, полученный стягиванием в графе ребра . Тогда — двойственны, а взаимно-однозначное соответствие между их ребрами остается тем же, что и в графах

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

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

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

Полезным будет следующее следствие из теоремы 7.10:

Следствие . Если граф G имеет двойственный граф, то всякий его реберно-порожденный подграф также имеет двойственный граф.

Доказательство. Этот результат следует из теоремы 7.10, если мы заметим, что всякий реберно-порожденный подграф Н графа G можно получить из графа G удалением ребер, не принадлежащих подграфу Н.

Для иллюстрации этого следствия рассмотрим двойственные графы на рис. 7.8. Граф представленный на рис. 7.9, а, получен графа удалением ребер и ей. Граф на рис. 7.9, б получен стягиванием ребер графа Легко видеть, что — двойственные графы.

Замечая, что последовательные ребра графа G соответствуют параллельным ребрам графа, двойственного к графу G, получаем еще одно следствие теоремы 7.10.

Следствие 7.10.2. Если граф G имеет двойственный граф, тогда любой граф, гомеоморфный графу G, также имеет двойственный граф.

Продолжим наше продвижение по пути к характеризации двойственных графов.

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

Если К имеет вершин и компонент связности, то G будет иметь вершии. Следовательно, ранг графа G определяется следующим образом:

Теорема 7.11. Пусть графы с взаимно-однозначным соответствием между ребрами. Пусть Н — произвольный подграф графа — соответствующий подграф графа

Рис. 7.9. Другой пример двойственных графов а — граф б — граф

Пусть К — дополнение Н в графе . В этом случае двойственны тогда и только тогда, когда

Доказательство. Необходимость. Пусть — двойственные графы. Граф получен из графа стягиванием ребер К. Тогда по теореме 7.10 графы Я и являются двойственными. Поэтому по теореме 7.9 , и Но по формуле (7.1) . Следовательно,

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

Так как Н — минимальный подграф графа G с цикломатическим числом, равным дополнение подграфа Н графа то очевидно, что К — максимальный

Рис. 7.10. Иллюстрация определения двойственности Уитни, а — граф б — граф

подграф графа с рангом, равным Из определения разрезающего множества следует, что Н — разрезающее множество графа .

Аналогичным образом можно показать, что разрезающее множество соответствует циклу графа

Таким образом, — двойственные графы.

Первоначальное определение двойственности, данное в работе [7.11], формулировалось так, как в теореме 7.11.

Для иллюстрации этого определения рассмотрим двойственные графы на рис. 7.8. Подграф Н графа и дополнение К соответствующего подграфа в графе приведены на рис. 7.10. Легко видеть, что