Дополнительный граф

В математической области теории графов дополнением или обратным графом графа G $является$ граф $H$ на тех же вершинах, такой, что две различные вершины $H$ являются смежными тогда и только тогда, когда они не являются смежными в $G.$ То есть, чтобы сгенерировать дополнение графа, нужно заполнить все недостающие ребра, необходимые для формирования полного графа , и удалить все ребра, которые были там ранее. ^[1]

Дополнение не является дополнением множества графа; дополняются только ребра.

Определение

Пусть $G = (V, E)$ — простой граф , и пусть $K$ состоит из всех 2-элементных подмножеств $V . Тогда H = ( V , K \ E ) — дополнение G , [2] где K \ E — относительное дополнение E$ $в$ K $. Для ориентированных графов дополнение можно определить таким$ же $образом$ , ^как ориентированный $граф на том$ же множестве вершин , $используя$ множество всех 2-элементных упорядоченных пар V $вместо$ множества $K$ в приведенной выше формуле. В терминах матрицы смежности A графа, если Q — матрица смежности полного графа с тем же числом вершин (т. е. все элементы равны единице, за исключением диагональных элементов, которые равны нулю), то матрица смежности дополнения A равна QA .

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

Приложения и примеры

Несколько концепций теории графов связаны друг с другом посредством дополнения:

Дополнением к графу без ребер является полный граф и наоборот.
Любой индуцированный подграф дополнительного графа графа $G$ является дополнением соответствующего индуцированного подграфа в $G.$
Независимое множество в графе является кликой в дополнительном графе и наоборот. Это частный случай предыдущих двух свойств, поскольку независимое множество является безреберным индуцированным подграфом, а клика является полным индуцированным подграфом.
Группа автоморфизмов графа — это группа автоморфизмов его дополнения.
Дополнением к любому графу без треугольников является граф без клешней ^[3] , хотя обратное неверно.

Самодополнительные графы и классы графов

Самодополнительный граф — это граф, который изоморфен своему собственному дополнению. ^{[1] Примерами являются}граф пути с четырьмя вершинами и граф цикла с пятью вершинами . Не существует известной характеристики самодополнительных графов.

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

Совершенные графы — это графы, в которых для каждого индуцированного подграфа хроматическое число равно размеру максимальной клики. Тот факт, что дополнение совершенного графа также является совершенным, является теоремой о совершенном графе Ласло Ловаса . ^[4]
Кографы определяются как графы, которые могут быть построены из отдельных вершин с помощью операций несвязного объединения и дополнения. Они образуют самодополнительное семейство графов: дополнение любого кографа является другим другим кографом. Для кографов с более чем одной вершиной ровно один граф в каждой дополнительной паре является связным, и одно эквивалентное определение кографов состоит в том, что каждый из их связных индуцированных подграфов имеет несвязное дополнение. Другое, самодополнительное определение состоит в том, что они являются графами без индуцированного подграфа в форме четырехвершинного пути. ^[5]
Другой самодополнительный класс графов — это класс расщепленных графов , графов, в которых вершины могут быть разделены на клику и независимое множество. Такое же разбиение дает независимое множество и клику в дополнительном графе. ^[6]
Пороговые графы — это графы, образованные путем многократного добавления либо независимой вершины (не имеющей соседей), либо универсальной вершины (смежной со всеми ранее добавленными вершинами). Эти две операции являются дополнительными и порождают самодополнительный класс графов. ^[7]

Алгоритмические аспекты

При анализе алгоритмов на графах различие между графом и его дополнением является важным, поскольку разреженный граф (граф с небольшим числом ребер по сравнению с числом пар вершин) в общем случае не будет иметь разреженного дополнения, и поэтому алгоритм, который занимает время, пропорциональное числу ребер на данном графе, может занять гораздо больше времени, если тот же алгоритм запущен на явном представлении дополняющего графа. Поэтому исследователи изучили алгоритмы, которые выполняют стандартные вычисления графа на дополнении входного графа, используя неявное представление графа , которое не требует явного построения дополняющего графа. В частности, можно смоделировать либо поиск в глубину , либо поиск в ширину на дополняющем графе за время, линейно зависящее от размера данного графа, даже если дополняющий граф может иметь гораздо больший размер. ^[8] Также можно использовать эти симуляции для вычисления других свойств, касающихся связности дополняющего графа. ^[8]^[9]

Ссылки

^ ab Bondy, John Adrian ; Murty, USR (1976), Теория графов с приложениями, North-Holland, стр. 6, ISBN 0-444-19451-7.
^ Дистель, Рейнхард (2005), Теория графов (3-е изд.), Springer , ISBN 3-540-26182-6. Электронное издание, стр. 4.
^ Чудновская, Мария ; Сеймур, Пол (2005), «Структура графов без клешней» (PDF) , Обзоры по комбинаторике 2005 , London Math. Soc. Lecture Note Ser., т. 327, Кембридж: Cambridge Univ. Press, стр. 153–171, MR 2187738.
^ Ловас, Ласло (1972a), «Нормальные гиперграфы и гипотеза о совершенном графе», Дискретная математика , 2 (3): 253–267, doi : 10.1016/0012-365X(72)90006-4.
^ Корнейл, Д.Г .; Лерчс, Х.; Стюарт Берлингем, Л. (1981), «Дополнительные сводимые графы», Дискретная прикладная математика , 3 (3): 163–174, doi : 10.1016/0166-218X(81)90013-5 , MR 0619603.
^ Golumbic, Martin Charles (1980), Алгоритмическая теория графов и совершенные графы , Academic Press, Теорема 6.1, стр. 150, ISBN 0-12-289260-7, МР 0562306.
^ Golumbic, Martin Charles; Jamison, Robert E. (2006), «Классы графов ранговой толерантности», Журнал теории графов , 52 (4): 317–340, doi :10.1002/jgt.20163, MR 2242832.
^ ab Ito, Hiro; Yokoyama, Mitsuo (1998), «Линейные алгоритмы времени для поиска графов и определения связности на дополнительных графах», Information Processing Letters , 66 (4): 209–213, doi :10.1016/S0020-0190(98)00071-4, MR 1629714.
^ Као, Мин-Ян; Оккиогроссо, Нил; Тенг, Шан-Хуа (1999), «Простые и эффективные схемы сжатия графов для плотных и дополнительных графов», Журнал комбинаторной оптимизации , 2 (4): 351–359, doi :10.1023/A:1009720402326, MR 1669307.