WikiDer > Хорошо покрытый граф

Well-covered graph
Хорошо покрытый граф, граф пересечений девяти диагоналей шестиугольник. Три красные вершины образуют одно из его 14 максимальных независимых множеств одинакового размера, а шесть синих вершин образуют дополнительное минимальное покрытие вершин.

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

Хорошо покрытые графики включают в себя все полные графикисбалансированный полные двудольные графы, а графики ладьи вершины которого представляют собой квадраты шахматной доски, а ребра - ходы шахматной ладьи. Известные характеристики хорошо укрытых кубические графы, хорошо покрытый графы без когтей, и хорошо покрытые графики высоких обхват позволяют распознать эти графики в полиномиальное время, но проверить, хорошо ли покрыты другие виды графиков, является coNP-Complete проблема.

Определения

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

An независимый набор в графе - это набор вершин, никакие две из которых не смежны друг с другом. Если C это вершинное покрытие в графе грамм, то дополнять из C должен быть независимым набором, и наоборот. C является минимальным вершинным покрытием тогда и только тогда, когда его дополнение я - максимальное независимое множество, а C является минимальным вершинным покрытием тогда и только тогда, когда его дополнение является максимальным независимым множеством. Следовательно, хорошо покрытый граф эквивалентно графу, в котором каждое максимальное независимое множество имеет одинаковый размер, или графу, в котором каждое максимальное независимое множество является максимальным.[1]

В исходной статье, определяющей хорошо покрытые графы, эти определения были ограничены связанные графы,[2] хотя они имеют значение и для несвязных графов. Некоторые более поздние авторы заменили требование связности более слабым требованием, согласно которому хорошо покрытый граф не должен иметь изолированных вершин.[3] Как для связных хорошо покрытых графов, так и для хорошо покрытых графов без изолированных вершин не может быть существенные вершины, вершины, принадлежащие каждому минимальному покрытию вершин.[2] Кроме того, каждый хорошо покрытый граф является критический граф для вершинного покрытия в том смысле, что для каждой вершины v, удаление v из графа производит граф с меньшим минимальным покрытием вершин.[2]

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

Примеры

абcdежграммчас
8
Chessboard480.svg
d8 белая ладья
g7 белая ладья
c6 белая ладья
а5 белая ладья
b4 белая ладья
h3 белая ладья
e2 белая ладья
f1 белая ладья
8
77
66
55
44
33
22
11
абcdежграммчас
Не атакующее размещение восьми ладей на шахматной доске. Если на шахматной доске не атакующим образом размещено менее восьми ладей, их всегда можно расширить до восьми ладей, которые останутся не атакующими.

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

Если п является либо многоугольником, либо набором точек, S это набор открыто отрезки с вершинами п как конечные точки и иначе не пересекаются с п, и грамм это граф пересечений из S (граф, у которого есть вершина для каждого отрезка прямой в S и ребро для каждых двух отрезков, которые пересекают друг друга), тогда грамм хорошо покрыт. Ведь в этом случае каждое максимальное независимое множество в грамм соответствует набору ребер в триангуляция из п, и расчет с участием Эйлерова характеристика показывает, что каждые две триангуляции имеют одинаковое количество ребер.[5]

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

Двудольность, хорошо покрытые графы и обхват

Фаварон (1982) определяет очень хорошо покрытый граф быть хорошо покрытым графом (возможно, несвязным, но без изолированных вершин), в котором каждое максимальное независимое множество (и, следовательно, также каждое минимальное покрытие вершин) содержит ровно половину вершин. Это определение включает корневые продукты графа грамм и однореберный граф. Он также включает, например, двудольные хорошо покрытые графы, изученные Равиндра (1977) и Берже (1981): в двудольном графе без изолированных вершин обе стороны любого двудольного графа образуют максимальные независимые множества (и минимальные покрытия вершин), поэтому, если граф хорошо покрыт, обе стороны должны иметь одинаковое количество вершин. На хорошо покрытом графике с п вершин размер максимального независимого множества не превосходит п/2, поэтому очень хорошо покрытые графы - это хорошо покрытые графы, в которых максимальный размер независимого множества максимально велик.[8]

Двудольный граф грамм хорошо покрывается тогда и только тогда, когда у него есть идеальное соответствие M со свойством, что для каждого ребра УФ в M, то индуцированный подграф соседей ты и v образует полный двудольный граф.[9] Характеристика в терминах паросочетаний может быть расширена от двудольных графов до очень хорошо покрытых графов: графа грамм очень хорошо покрыт, если и только если он имеет идеальное соответствие M со следующими двумя свойствами:

  1. Нет края M принадлежит треугольнику в грамм, и
  2. Если край M центральное ребро трехреберного пути в грамм, то две конечные точки пути должны быть смежными.

Более того, если грамм очень хорошо покрыты, то каждое идеальное совпадение в грамм удовлетворяет этим свойствам.[10]

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

Регулярность и плоскостность

Семь кубических 3-связных хорошо покрытых графов
Кубический односвязный хорошо покрытый граф, образованный заменой каждого узла шестиузлового пути одним из трех фрагментов.
В курносый дисфеноид, один из четырех хорошо покрытых 4-связных 3-х мерных симплициальных многогранников.

В кубический (3-регулярный) хорошо покрытые графы классифицированы: они состоят из семи 3-связный примеры вместе с тремя бесконечными семействами кубических графов с меньшей связностью.[13]

Семь 3-связных кубических хорошо покрытых графов являются полный график K4, графики треугольная призма и пятиугольная призма, то Граф Дюрера, то график полезности K3,3, восьмивершинный граф, полученный из графа полезности Y-Δ преобразование, а 14-вершина обобщенный граф Петерсена грамм(7,2).[14] Из этих графиков первые четыре планарные графы. Они всего четыре кубических многогранные графы (графики просто выпуклые многогранники), которые хорошо покрыты. Четыре графа (две призмы, граф Дюрера и грамм(7,2)) являются обобщенными графами Петерсена.

Все одно- и двухсвязные кубические хорошо покрытые графы образуются заменой узлов пути или цикла тремя фрагментами графов, которые Пламмер (1993) этикетки А, B, и C. Фрагменты А или же B может использоваться для замены узлов цикла или внутренних узлов пути, в то время как фрагмент C используется для замены двух конечных узлов пути. Фрагмент А содержит мост, поэтому результат выполнения этого процесса замены на пути и использования фрагмента А для замены некоторых узлов пути (и двух других фрагментов для оставшихся узлов) является кубический хорошо покрытый граф с 1-вершинной связью. Все 1-вершинно-связанные кубические хорошо покрытые графы имеют этот вид, и все такие графы плоские.[13]

Есть два типа двухвершинно-связных кубических хорошо покрытых графов. Одно из этих двух семейств образуется заменой узлов цикла фрагментами А и B, причем по крайней мере два из фрагментов относятся к типу А; граф этого типа является плоским тогда и только тогда, когда он не содержит фрагментов типа B. Другое семейство образовано заменой узлов пути фрагментами типа B и C; все такие графы плоские.[13]

В дополнение к описанию хорошо покрытых простых многогранников в трех измерениях исследователи также рассмотрели хорошо покрытые симплициальные многогранники, или, что то же самое, максимальные планарные графы с хорошим покрытием. Каждый максимальный планарный граф с пятью или более вершинами имеет связность вершин 3, 4 или 5.[15] Нет хорошо покрытых 5-связных максимальных планарных графов, и есть только четыре 4-связных хорошо покрытых максимальных планарных графа: графы правильный октаэдр, то пятиугольная дипирамида, то курносый дисфеноид, и неправильный многогранник (невыпуклый дельтаэдр) с 12 вершинами, 30 ребрами и 20 треугольными гранями. Однако существует бесконечно много 3-связных хорошо покрытых максимальных плоских графов.[16] Например, хорошо покрываемый 3-связный максимальный планарный граф может быть получен с помощью конструкции кликового покрытия[7] из любого 3т-вершинный максимальный планарный граф, в котором есть т непересекающиеся треугольные грани путем добавления т новые вершины, по одной в каждой из этих граней.

Сложность

Проверка того, содержит ли граф два максимальных независимых набора разных размеров, является НП-полный; то есть, дополнительно, проверка того, хорошо ли покрыт граф, является coNP-полным.[17] Хотя легко найти максимальные независимые множества в графах, которые, как известно, хорошо покрыты, для алгоритма также NP-сложно создать в качестве выходных данных на всех графах либо максимальное независимое множество, либо гарантию того, что вход не покрыты хорошо.[18]

Напротив, можно проверить, действительно ли данный график грамм очень хорошо покрыт полиномиальное время. Для этого найдите подграф ЧАС из грамм состоящий из ребер, которые удовлетворяют двум свойствам совпадающего ребра в очень хорошо покрытом графе, а затем использовать алгоритм сопоставления, чтобы проверить, ЧАС имеет идеальное соответствие.[10] Некоторые проблемы, NP-полные для произвольных графов, например, проблема нахождения Гамильтонов цикл, также может быть решена за полиномиальное время для очень хорошо покрытых графов.[19]

Граф называется равноценный если каждый максимальное соответствие максимум; то есть, оно равнозначно, если его линейный график хорошо покрыт. Можно проверить, является ли линейный график или, в более общем смысле, граф без когтей, хорошо покрывается за полиномиальное время.[20]

Характеристики хорошо покрытых графов с обхватом пять или более и хорошо покрытых графов, которые являются 3-регулярными, также приводят к эффективным алгоритмам полиномиального времени для распознавания этих графов.[21]

Примечания

  1. ^ Пламмер (1993).
  2. ^ а б c Пламмер (1970).
  3. ^ Фаварон (1982).
  4. ^ Примеры статей, использующих эту терминологию, см. Дохтерманн и Энгстрём (2009) и Кук и Нагель (2010).
  5. ^ Гринберг (1993).
  6. ^ Этот класс примеров изучался Fink et al. (1985); они также (вместе с четырехреберным циклом, который также хорошо покрыт) в точности являются графами, число доминирования которых равно п/2. Его свойство хорошо покрываемости также сформулировано в другой терминологии (имеющей комплекс чистой независимости) как теорема 4.4 из Дохтерманн и Энгстрём (2009).
  7. ^ а б Кук и Нагель (2010).
  8. ^ Берже (1981).
  9. ^ а б Равиндра (1977); Пламмер (1993).
  10. ^ а б Скобы (1975); Фаварон (1982); Пламмер (1993).
  11. ^ Финбоу и Хартнелл (1983); Пламмер (1993), Теорема 4.1.
  12. ^ Финбоу и Хартнелл (1983); Пламмер (1993), Теорема 4.2.
  13. ^ а б c Кэмпбелл (1987); Кэмпбелл и Пламмер (1988); Пламмер (1993).
  14. ^ Кэмпбелл (1987); Финбоу, Хартнелл и Новаковски (1988); Кэмпбелл, Эллингем и Ройл (1993); Пламмер (1993).
  15. ^ Полные графы с 1, 2, 3 и 4 вершинами все максимально плоские и хорошо покрыты; их связность вершин либо неограничена, либо не более трех, в зависимости от деталей определения связности вершин, которые не имеют отношения к большим максимальным планарным графам.
  16. ^ Финбоу, Хартнелл, Новаковски и др. (2003, 2009, 2010).
  17. ^ Шанкаранараяна и Стюарт (1992); Chvátal & Slater (1993); Каро, Себо и Тарси (1996).
  18. ^ Рагхаван и Спинрад (2003).
  19. ^ Шанкаранараяна и Стюарт (1992).
  20. ^ Леск, Plummer и Pulleyblank (1984); Танкус и Тарси (1996); Танкус и Тарси (1997).
  21. ^ Кэмпбелл, Эллингем и Ройл (1993); Пламмер (1993).

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