В теории графов , то дополнение или обратный граф G является граф H на один и те же вершины, что две различных вершин H смежны тогда и только тогда , когда они не смежны в G . То есть, чтобы сгенерировать дополнение графа, нужно заполнить все недостающие ребра, необходимые для формирования полного графа , и удалить все ребра, которые были там ранее. [1] Однако это не набор дополнений к графу; дополняются только края.
Определение [ править ]
Пусть G = ( V , E ) быть простой граф , и пусть К состоит из всех 2-элементных подмножеств V . Тогда Н = ( V , К \ Е ) является дополнением G , [2] , где К \ Е является относительно дополнения из Е в К . Для ориентированных графов дополнение может быть определено таким же образом, как ориентированный граф на том же наборе вершин, используя набор всех 2-элементных упорядоченных париз V вместо множества K в приведенной выше формуле. В терминах матрицы смежности A графа, если Q является матрицей смежности полного графа с одинаковым числом вершин (т.е. все элементы равны единице, кроме диагональных элементов, которые равны нулю), то матрица смежности дополнения А - это QA .
Для мультиграфов дополнение не определено . В графах, которые допускают самостоятельные петли (но не множественные смежности), дополнение к G может быть определено путем добавления петли к каждой вершине, у которой нет такой петли в G , или с использованием той же формулы, что и выше. Эта операция, однако, отличается от операции для простых графов, поскольку ее применение к графу без петель приведет к получению графа с петлями на всех вершинах.
Приложения и примеры [ править ]
Несколько концепций теории графов связаны друг с другом через дополнительные графы:
- Дополнение к безреберному графу - это полный граф, и наоборот.
- Любой подграф комплемента графа графа G является дополнением соответствующего индуцированного подграфа в G .
- Независимое множество в графе есть клика в дополнении графа и наоборот. Это частный случай двух предыдущих свойств, поскольку независимое множество является индуцированным подграфом без ребер, а клика - полным индуцированным подграфом.
- Группа автоморфизмов графа - это группа автоморфизмов его дополнения.
- Дополнением каждого треугольника свободной графа является граф без клешней , [3] , хотя обратное неверно.
Самодополняемые графы и классы графов [ править ]
Самодополнительный граф является граф, изоморфный своему собственному комплемента. [1] Примеры включают в себя четыре вершины графа пути и пять вершин графа цикла .
Несколько классов графов являются самодополняющими, в том смысле, что дополнение любого графа в одном из этих классов является другим графом того же класса.
- Совершенные графы - это графы, в которых для каждого индуцированного подграфа хроматическое число равно размеру максимальной клики. Дело в том , что дополнение совершенного графа также идеально является идеальной теоремой графа из Ловас . [4]
- Кографы определяются как графы, которые могут быть построены из отдельных вершин с помощью операций несвязного объединения и дополнения. Они образуют самодополняемое семейство графов: дополнение к любому кографу - это еще один другой кограф. Для кографов из более чем одной вершины связным является ровно один граф в каждой дополнительной паре, и одно эквивалентное определение кографов состоит в том, что каждый из их связных индуцированных подграфов имеет несвязное дополнение. Другое, самодополняющее определение состоит в том, что это графы без индуцированного подграфа в форме пути с четырьмя вершинами. [5]
- Другой самодополняемый класс графов - это класс расщепленных графов , в которых вершины могут быть разбиты на клику и независимое множество. Одно и то же разбиение дает независимый набор и клику в графе дополнения. [6]
- В пороговых графиках являются графиками , образованными путем многократного добавления либо независимая вершины (один без соседей) или универсальной вершины (прилегающей ко всем ранее добавленным вершинам). Эти две операции дополняют друг друга и порождают самодополняемый класс графов. [7]
Алгоритмические аспекты [ править ]
При анализе алгоритмов на графах различие между графом и его дополнением является важным, потому что разреженный граф (один с небольшим количеством ребер по сравнению с количеством пар вершин), как правило, не будет иметь разреженного дополнения. , и поэтому алгоритм, который требует времени, пропорционального количеству ребер на данном графе, может занять гораздо большее количество времени, если тот же алгоритм выполняется на явном представлении дополнительного графа. Поэтому исследователи изучили алгоритмы, которые выполняют стандартные вычисления графа на дополнении входного графа, используя неявное представление графа, которое не требует явного построения графа дополнения. В частности, можно смоделировать либопоиск в глубину или поиск в ширину на дополнительном графе за время, линейное по размеру данного графа, даже если дополнительный граф может иметь гораздо больший размер. [8] Также можно использовать эти симуляции для вычисления других свойств, касающихся связности дополнительного графа. [8] [9]
Ссылки [ править ]
- ^ Б Бонди, Джон Адриан ; Мурти, USR (1976), Теория графов с приложениями , Северная Голландия, стр. 6 , ISBN 0-444-19451-7.
- ^ Diestel Рейнхард (2005), теории графов (3 - е изд.), Springer , ISBN 3-540-26182-6. Электронное издание , стр. 4.
- ↑ Чудновский, Мария ; Сеймур, Пол (2005), "Структура графов без клешней" (PDF) , Обзоры по комбинаторике 2005 , London Math. Soc. Lecture Note Ser., 327 , Cambridge: Cambridge Univ. Press, стр. 153–171, MR 2187738 ..
- ^ Ловас, Ласло (1972a), «Нормальные гиперграфы и гипотеза идеального графа», Дискретная математика , 2 (3): 253–267, DOI : 10.1016 / 0012-365X (72) 90006-4.
- ^ Корнейл, Д.Г .; Lerchs, H .; Стюарт Burlingham, Л. (1981), "комплемент приводимых граф", Дискретная прикладная математика , 3 (3): 163-174, DOI : 10.1016 / 0166-218X (81) 90013-5 , МР 0619603 .
- ^ Голумбик, Мартин Чарльз (1980), Алгоритмическая теория графов и совершенные графы , Academic Press, теорема 6.1, с. 150, ISBN 0-12-289260-7, Руководство по ремонту 0562306.
- ^ Голумбик, Мартин Чарльз; Джемисон, Роберт Е. (2006), "Уровень толерантности графа классов", Журнал теории графов , 52 (4): 317-340, DOI : 10.1002 / jgt.20163 , MR 2242832 .
- ^ а б Ито, Хиро; Ёкояма, Мицуо (1998), «Алгоритмы линейного времени для поиска графов и определения связности на дополнительных графах», Письма об обработке информации , 66 (4): 209–213, DOI : 10.1016 / S0020-0190 (98) 00071-4 , MR 1629714 .
- ^ Као, Мин-Ян; Очкиогроссо, Нил; Тен, Шан-Хуа (1999), "Простые и эффективные схемы сжатия график для плотных и комплемента графов", журнал комбинаторной оптимизации , 2 (4): 351-359, DOI : 10,1023 / A: 1009720402326 , МР 1669307 .
