Независимый от радуги набор - Rainbow-independent set

В теория графов, а радужно-независимый набор (ISR) является независимый набор в графе, в котором каждая вершина имеет свой цвет.

Формально пусть грамм = (V, E) - граф, и пусть V разделен на м подмножества, V₁,...,V_м, называемые «цветами». Набор U вершин называется не зависящим от радуги множеством, если оно удовлетворяет обоим следующим условиям:^[1]

Это независимый набор - каждые две вершины в U не смежные (между ними нет ребра);
Это радуга – U содержит не более одной вершины каждого цвета V_я.

Другие термины, используемые в литературе: независимая группа представителей,^[2] независимый поперечный,^[3] и независимая система представителей.^[4]

В качестве примера приложения рассмотрим факультет с м кафедры, на которых некоторые преподаватели не любят друг друга. Декан хочет создать комитет с м члены, по одному на отдел, но без пары членов, которые не любят друг друга. Эту проблему можно представить как нахождение ISR в графе, в котором узлами являются преподаватели, ребра описывают отношения «неприязни», а подмножества V₁,...,V_м есть отделы.^[3]

Варианты

Для удобства предполагается, что множества V₁,...,V_м попарно не пересекаются. В общем случае множества могут пересекаться, но этот случай легко сводится к случаю непересекающихся множеств: для каждой вершины x формируйте копию x для каждой я такой, что V_я содержит x. В получившемся графе соедините все копии x друг с другом. На новом графике V_я не пересекаются, и каждая ISR соответствует ISR в исходном графе.^[4]

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

Существование радужно-независимых множеств

Существуют различные достаточные условия существования ISR.

Условие на основе степени вершины

Интуитивно, когда отделы V_я больше, и между преподавателями меньше конфликтов, вероятность существования ISR должна быть выше. Состояние «меньше конфликтов» представлено степень вершины графа. Это формализуется следующей теоремой:^[5]^:Thm.2

Если степень каждой вершины в G не больше d, а размер каждого набора цветов не меньше 2d, то G имеет ISR.

2d наилучшим образом: есть граф со степенью вершины k и цвета размера 2d-1 без ISR.^[6] Но есть более точная версия, в которой оценка зависит как от d и дальше м.^[7]

Состояние на основе доминирующих наборов

Ниже, учитывая подмножество S цветов (подмножество {V₁,...,V_м}) обозначим через U_S объединение всех подмножеств в S (все вершины одного из цветов в S), и по грамм_S подграф G, индуцированный U_S.^[8] Следующая теорема описывает структуру графов, которые не имеют ISR, но являются край минимальныйв том смысле, что всякий раз, когда из них удаляется какое-либо ребро, оставшийся граф имеет ISR.

Если G не имеет ISR, но для каждого ребра e в E, G-e имеет ISR, то для каждого ребра e = (x, y) в E существует подмножество S цветов {V₁, ..., V_м}, и множество Z ребер графа G_S, такое, что:
Вершины Икс и у оба в U_S;
Край е = (Икс,у) в Z;
Множество вершин, смежных с Z доминирует грамм_S;
|Z| ≤ |S| − 1;
Z это соответствие - никакие два его ребра не смежны с одной и той же вершиной.

Состояние холла

Ниже, учитывая подмножество S цветов (подмножество {V₁,...,V_м}), независимый набор я_S из грамм_S называется специально для S если для каждого независимого подмножества J вершин грамм_S размера не более |S| - 1 существует несколько v в я_S такой, что J ∪ {v} также является независимым. Образно говоря, я_S это команда «нейтральных участников» для набора S отделов, которые могут увеличить любой достаточно небольшой набор неконфликтующих членов, чтобы создать такой больший набор. Следующая теорема аналогична Теорема холла о браке:^[9]

Если для любого подмножества цветов S граф G_S содержит независимое множество I_S это является специальным для S, то G имеет ISR.
Доказательство идеи. Теорема доказывается с использованием Лемма Спернера.^[3]^:Thm.4.2 Стандартный симплекс с м конечным точкам назначается триангуляция с некоторыми особыми свойствами. Каждая конечная точка я симплекса связан с цветовым набором V_я, each face {я₁,..,я_k} симплекса связан с множеством S = {V_i1, ..., V_ik} цветов. Каждая точка Икс триангуляции помечена вершиной грамм(Икс) из грамм такое, что: (а) Для каждой точки Икс на лице S, грамм(Икс) является элементом я_S - специальный независимый набор S. (б) Если точки Икс и у соседствуют в 1-скелет триангуляции, то грамм(Икс) и грамм(y) не смежны в грамм. По лемме Спернера существует под-симплекс, в котором для каждой точки Икс, грамм(Икс) принадлежит к другому набору цветов; набор этих грамм(Икс) является ISR.

Из приведенной выше теоремы следует условие брака Холла. Чтобы убедиться в этом, полезно сформулировать теорему для частного случая, когда грамм это линейный график какого-то другого графа ЧАС; это означает, что каждая вершина грамм край ЧАС, и каждый независимый набор грамм соответствует в ЧАС. Раскраска вершин грамм соответствует окраске ребер ЧАС, и независимый от радуги набор в грамм соответствует совпадению радуги в ЧАС. Соответствие я_S в ЧАС_S специально для S, если для каждого совпадения J в ЧАС_S размера не более |S| - 1, есть край е в я_S такой, что J ∪ {е} все еще соответствует в ЧАС_S.

Пусть H - граф с раскраской ребер. Если для каждого подмножества цветов S граф H_S содержит соответствие M_S это особенное для S, то H имеет радужное соответствие.

Позволять ЧАС = (Икс + Y, E) - двудольный граф, удовлетворяющий условию Холла. Для каждой вершины я из Иксназначить уникальный цвет V_я ко всем краям ЧАС рядом с я. Для каждого подмножества S цветов, условие Холла означает, что S имеет не менее |S| соседи в Y, а значит есть как минимум |S| края ЧАС смежные с различными вершинами Y. Позволять я_S быть набором |S| такие края. Для любого соответствия J размера не более |S| - 1 дюйм ЧАС, какой-то элемент е из я_S имеет другую конечную точку в Y чем все элементы J, и поэтому J ∪ {е} также является соответствием, поэтому я_S специально для S. Из приведенной выше теоремы следует, что ЧАС есть совпадение радуги M_р. По определению цветов, M_р идеальное сочетание в ЧАС.

Другим следствием приведенной выше теоремы является следующее условие, которое включает как степень вершины, так и длину цикла:^[3]^:Thm.4.3

Если степень каждой вершины в G не более 2, и длина каждого цикла G делится на 3, и размер каждого набора цветов равен не менее 3, тогда G имеет ISR.
Доказательство. Для каждого подмножества S цветов, график грамм_S содержит не менее 3 |S| вершин, и представляет собой объединение циклов длины, кратной 3, и путей. Позволять я_S быть независимым множеством в грамм_S содержащий каждую третью вершину в каждом цикле и каждом пути. Итак |я_S| содержит не менее 3 |S|/3 = |S| вершины. Позволять J быть независимым множеством в грамм_S размера не более |S| -1. Поскольку расстояние между каждыми двумя вершинами я_S не меньше 3, каждая вершина J смежна не более чем с одной вершиной из я_S. Следовательно, есть хотя бы одна вершина я_S которая не смежна ни с одной вершиной из J. Следовательно я_S специально для S. По предыдущей теореме грамм имеет ISR.

Состояние, основанное на гомологической связности

Одно семейство условий основано на гомологическая связность из комплекс независимости подграфов. Для формулировки условий используются следующие обозначения:

Ind (грамм) обозначает комплекс независимости графа грамм (это абстрактный симплициальный комплекс чьи грани являются независимыми множествами в грамм).
${ displaystyle eta _ {H} (X)}$ обозначает гомологическая связность симплициального комплекса Икс (т.е. наибольшее целое число k таких, что первые k групп гомологий Икс тривиальны), плюс 2.
[м] - набор индексов цветов, {1, ..., м}. Для любого подмножества J из [м], V_J это союз цветов V_j за j в J.
грамм[V_J] - подграф графа G, индуцированный вершинами из V_J.

Следующее условие подразумевается в ^[9] и явно доказано в.^[10]

Если для всех подмножеств J из [м]:
${ displaystyle eta _ {H} ({ text {Ind}} (G [V_ {J}])) geq | J |}$
тогда раздел V₁,...,V_м допускает ISR.

В качестве примера,^[4] предполагать грамм это двудольный граф, а его части точно V₁ и V₂. В этом случае [м] = {1,2}, поэтому есть четыре варианта для J:

J = {}: тогда грамм[J] = {} и Ind (грамм[J]) = {} и связность бесконечна, поэтому условие выполняется тривиально.
J = {1}: тогда грамм[J] - граф с вершинами V₁ и без краев. Здесь все множества вершин независимы, поэтому Ind (грамм[J]) - набор степеней V₁, т. е. имеет единственный м-симплекс (и все его подмножества). Известно, что одиночный симплекс k-связано для всех целых чисел k, поскольку все его редуцированные группы гомологий тривиальны (см. симплициальные гомологии ). Следовательно, условие выполнено.
J = {2}: этот случай аналогичен предыдущему.
J = {1,2}: тогда грамм[J] = грамм, а Ind (грамм) содержит два симплекса V₁ и V₂ (и все их подмножества). Условие ${ displaystyle eta _ {H} ({ text {Ind}} (G)) geq 2}$ эквивалентно условию гомологической связности Ind (грамм) не меньше 0, что равносильно условию ${ Displaystyle { тильда {H_ {0}}} ({ text {Ind}} (G))}$ - тривиальная группа. Это верно тогда и только тогда, когда комплекс Ind (грамм) содержит связь между двумя своими симплексами V₁ и V₂. Такое соединение эквивалентно независимому множеству, в котором одна вершина принадлежит V₁ и один из V_2. Таким образом, в данном случае условие теоремы не только достаточное, но и необходимое.

Другие условия

Каждый правильно окрашенный граф без треугольников из хроматическое число Икс содержит не зависящий от радуги набор размером не менее Икс/2.^[11]

Несколько авторов изучали условия существования больших радужно-независимых множеств в различных классах графов.^[1]^[12]

Вычисление

В Проблема решения ISR проблема определения того, является ли данный граф грамм = (V, E) и заданное разбиение V на м цвета допускают независимый от радуги набор. Эта проблема НП-полный. Доказательство проводится редукцией из 3-мерное соответствие проблема (3DM).^[4] Входом в 3DM является трехчастный гиперграф (Икс+Y+Z, F), куда Икс, Y, Z наборы вершин размера м, и F представляет собой набор троек, каждая из которых содержит по одной вершине каждого из Икс, Y, Z. Вход в 3DM можно преобразовать во вход в ISR следующим образом:

Для каждого ребра (Икс,у,z) в F, есть вершина v_{х, у, г} в V;
Для каждой вершины z в Z, позволять V_z = {v_{х, у, г} | Икс в X, у в Y}.
Для каждого x, y₁, y₂, z₁, z₂, есть край (v_{х, у1, z1}, v_{х, у2, z2}) в E;
Для каждого x₁, Икс₂, у, z₁, z₂, есть край (v_{х1, у, z1}, v_{х2, у, z2}) в E;

В получившемся графике грамм = (V, E) ISR соответствует набору троек (x, y, z), таких что:

Каждый триплет имеет разное значение z (поскольку каждый триплет принадлежит разному набору цветов V_z);
Каждый триплет имеет различное значение x и другое значение y (поскольку вершины независимы).

Следовательно, результирующий граф допускает ISR тогда и только тогда, когда исходный гиперграф допускает 3DM.

Альтернативное доказательство - редукция от СИДЕЛ.^[3]

Связанные понятия

Если грамм это линейный график какого-то другого графа ЧАС, то независимые множества в грамм являются совпадения в ЧАС. Следовательно, не зависящее от радуги множество в грамм это соответствие радуги в H. См. также сопоставление в гиперграфах.

Еще одна связанная концепция - это радужный цикл, что является цикл в котором каждая вершина имеет разный цвет.^[13]

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

Используя метафору факультета:^[3]

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

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