График дополнения - Complement graph

В Граф Петерсена (слева) и его дополнительный граф (справа).

В теория графов, то дополнять или же обратный графа грамм это график ЧАС на одних и тех же вершинах такие, что две различные вершины ЧАС смежные если и только если они не соседствуют в грамм. То есть, чтобы создать дополнение к графу, нужно заполнить все недостающие ребра, необходимые для формирования графа. полный график, и удаляет все края, которые были ранее.[1] Однако это не набор дополнений графа; дополняются только края.

Определение

Позволять грамм = (V, E) быть простой график и разреши K состоят из всех 2-элементных подмножеств V. потом ЧАС = (V, K \ E) является дополнением грамм,[2] куда K \ E это относительное дополнение из E в K. За ориентированные графы, дополнение может быть определено таким же образом, как ориентированный граф на том же множестве вершин, используя множество всех 2-элементных заказанные пары из V вместо набора K в формуле выше. Что касается матрица смежности А графа, если Q матрица смежности полный график одинакового числа вершин (т.е.все элементы равны единице, кроме диагональных элементов, равных нулю), то матрица смежности дополнения А является Q-A.

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

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

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

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

Путь с четырьмя вершинами самодостаточен.
Основная статья: Само-дополнительный граф

А самодополняющий граф это граф, который изоморфный к собственному дополнению.[1] Примеры включают четыре вершины граф путей и пятивершинник график цикла.

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

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

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

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

Рекомендации

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