В теории графов независимый от радуги набор (ISR) - это независимый набор в графе, в котором каждая вершина имеет свой цвет.
Формально, пусть G = ( V , E ) - граф, и пусть V разбивается на m подмножеств V 1 , ..., V m , называемых «цветами». Множество вершин U называется независимым от радуги, если оно удовлетворяет обоим следующим условиям: [1]
- Это независимое множество - каждые две вершины в U не смежны (между ними нет ребра);
- Это радужное множество - U содержит не более одной вершины каждого цвета V i .
Другие термины , используемые в литературе, независимый набор представителей , [2] независимый трансверсалъ , [3] и независимую систему представителей . [4]
В качестве примера приложения рассмотрим факультет с m отделами, где некоторые преподаватели не любят друг друга. Декан хочет создать комитет из m членов, по одному на факультет, но без пары членов, которые не любят друг друга. Эту задачу можно представить как поиск ISR в графе, в котором узлами являются преподаватели, ребра описывают отношения «неприязни», а подмножества V 1 , ..., V m являются отделами. [3]
Варианты
Для удобства предполагается, что множества V 1 , ..., V m попарно не пересекаются. В общем, множества могут пересекаться, но этот случай легко сводится к случаю непересекающихся множеств: для каждой вершины x сформируйте копию x для каждого i , так что V i содержит x. В получившемся графе соедините все копии x друг с другом. В новом графе V i не пересекаются, и каждая ISR соответствует ISR в исходном графе. [4]
ISR обобщает концепцию системы различных представителей (SDR, также известный как трансверсальный ). Каждая трансверсаль - это ISR, где в нижележащем графе связаны все и только копии одной и той же вершины из разных наборов.
Существование не зависящих от радуги множеств
Существуют различные достаточные условия существования ISR.
Условие на основе степени вершины
Интуитивно понятно, что когда отделы V i больше, и между преподавателями меньше конфликтов, вероятность существования ISR должна быть выше. Условие «меньше конфликтов» представлено степенью вершины графа. Это формализуется следующей теоремой: [5] : Теорема.2
Если степень каждой вершины в G не больше d, а размер каждого набора цветов не меньше 2d, то G имеет ISR.
2 d является наилучшим возможным: есть граф со степенью вершины k и цветами размера 2 d -1 без ISR. [6] Но есть более точный вариант, в котором оценка зависит как от d, так и от m . [7]
Состояние на основе доминирующих наборов
Ниже, учитывая подмножество цветов S (подмножество { V 1 , ..., V m }), мы обозначаем через U S объединение всех подмножеств в S (всех вершин, цвет которых является одним из цветов в S ) , и G S подграф G , индуцированный U S . [8] Следующая теорема описывает структуру графов, которые не имеют ISR, но являются реберно-минимальными в том смысле, что всякий раз, когда из них удаляется какое-либо ребро, оставшийся граф имеет ISR.
Если G не имеет ISR, но для каждого ребра e в E, Ge имеет ISR, то для каждого ребра e = (x, y) в E существует подмножество S цветов {V 1 , ..., V m } и множество Z ребер графа G S такие, что:
- Обе вершины x и y принадлежат U S ;
- Ребро e = ( x , y ) лежит в Z ;
- Множество вершин, смежных с Z, доминирует над G S ;
- | Z | ≤ | S | - 1;
- Z - паросочетание - никакие два его ребра не смежны с одной и той же вершиной.
Состояние холла
Ниже для данного подмножества S цветов (подмножества { V 1 , ..., V m }) независимое множество I S из G S называется специальным для S, если для каждого независимого подмножества J вершин G S из размер не более | S | - 1, существует v в I S такое, что J ∪ { v } также независима. Образно говоря, I S - это команда «нейтральных членов» для множества S отделов, которая может дополнять любой достаточно небольшой набор неконфликтующих членов, чтобы создать такой больший набор. Следующая теорема аналогична теореме Холла о браке : [9]
Если для каждого подмножества S цветов граф G S содержит независимое множество I S, которое является специальным для S, то G имеет ISR.
Доказательство идеи . Теорема доказывается с использованием леммы Спернера . [3] : Thm.4.2 Стандартному симплексу с m конечными точками назначается триангуляция с некоторыми особыми свойствами. Каждая конечная точка i симплекса связана с цветовым набором V i , каждая грань { i 1 , .., i k } симплекса связана с набором S = {V i1 , ..., V ik } из цвета. Каждая точка х триангуляции метят с вершиной г ( х ) из G таким образом, что: (а) для каждой точки х на поверхность S , г ( х ) является элементом I S - специальный независимый набор S . (б) Если точки х и у являются смежными в 1-остова триангуляции, то г ( х ) и г (у) не являются смежными в G . В силу леммы Шпернера, существует суб-симплекс , в котором для каждой точки х , г ( х ) принадлежит к другой цветовой набор; набор этих g ( x ) является ISR.
Из приведенной выше теоремы следует условие брака Холла. Чтобы убедиться в этом, полезно сформулировать теорему для частного случая, когда G является линейным графом некоторого другого графа H ; Это означает , что каждая вершина G является ребром H , и каждый независимый набор G является соответствие в H . Вершинный окраска G соответствует ребру-окрашиванию H , и радуги независимых-множество в G соответствует радужному сопоставлению в H . Соответствие I S в H S является специальным для S , если для каждого соответствия J в H S размера не более | S | - 1, существует ребро е в я S таким образом, что J ∪ { е } еще в соответствие H S .
Пусть H - граф с раскраской ребер. Если для каждого подмножества S цветов граф H S содержит соответствие M S, которое является специальным для S, то H имеет соответствие радуги.
Пусть H = ( X + Y , E ) двудольный граф, удовлетворяющий условию Холла. Для каждой вершины i из X присвойте уникальный цвет V i всем ребрам H, смежным с i . Для любого подмножества цветов S из условия Холла следует, что S имеет не менее | S | соседей по Y , а значит, есть не менее | S | Края Н смежных с различными вершинами Y . Пусть I S - набор | S | такие края. Для любого соответствия J размера не более | S | - 1 в H , некоторый элемент е из I S имеют другую конечную точку в Y , чем все элементы J , и , следовательно , J ∪ { е } также соответствие, поэтому я S специально для S . Выше теоремы следует , что Н имеет радугу , соответствующий M R . По определению цветов, М R представляет собой идеальное соответствие в H .
Другим следствием приведенной выше теоремы является следующее условие, которое включает как степень вершины, так и длину цикла: [3] : Теорема.4.3
Если степень каждой вершины в G не больше 2, а длина каждого цикла G делится на 3, и размер каждого набора цветов не меньше 3, то G имеет ISR.
Доказательство . Для любого подмножества цветов S граф G S содержит не менее 3 | S | вершин, и это объединение циклов длины, кратной 3, и путей. Пусть I S - независимое множество в G S, содержащее каждую третью вершину в каждом цикле и каждом пути. Итак | I S | содержит не менее 3 | S | / 3 = | S | вершины. Пусть J - независимое множество в G S размера не более | S | -1. Так как расстояние между каждыми двумя вершинами I S составляет , по меньшей мере , 3, каждая вершина J смежна не более одной вершины из I S . Таким образом, существует по крайней мере одна вершина I S , которая не примыкает к любой вершине J . Поэтому я S специально для S . По предыдущей теореме G имеет ISR.
Состояние, основанное на гомологической связности
Одна семья условий базируется на гомологической связи в независимости комплекса подграфов. Для формулировки условий используются следующие обозначения:
- Ind ( G ) обозначает комплекс независимости графа G (т. Е. Абстрактный симплициальный комплекс , грани которого являются независимыми множествами в G ).
- обозначает гомологическую связность симплициального комплекса X (т. е. наибольшее целое число k такое, что первые k групп гомологий X тривиальны) плюс 2.
- [ m ] - это набор индексов цветов, {1, ..., m }. Для любого подмножества J из [ м ], V J является объединением цветов V J для J в J .
- G [ V J ] является подграф , индуцированный вершинами в V J .
Следующее условие неявно указано в [9] и явно доказано в [10].
Если для всех подмножеств J из [ m ]:
то разбиение V 1 , ..., V m допускает ISR.
В качестве примера [4] предположим, что G - двудольный граф , и его части - это в точности V 1 и V 2 . В этом случае [ m ] = {1,2}, поэтому есть четыре варианта для J :
- J = {}: тогда G [ J ] = {} и Ind ( G [ J ]) = {} и связность бесконечна, поэтому условие тривиально выполняется.
- J = {1}: тогда G [ J ] - граф с вершинами V 1 и без ребер. Здесь все множества вершин независимы, поэтому Ind ( G [ J ]) - это множество степеней V 1 , т. Е. Он имеет единственный m -симплекс (и все его подмножества). Известно, что один симплекс является k -связным для всех целых k , поскольку все его редуцированные группы гомологий тривиальны (см. Симплициальные гомологии ). Следовательно, условие выполнено.
- J = {2}: этот случай аналогичен предыдущему.
- J = {1,2}: тогда G [ J ] = G , и Ind ( G ) содержит два симплекса V 1 и V 2 (и все их подмножества). Условиеэквивалентно условию, что гомологическая связность Ind ( G ) не меньше 0, что эквивалентно условию, что- тривиальная группа. Это верно тогда и только тогда, когда комплекс Ind ( G ) содержит связь между двумя своими симплексами V 1 и V 2 . Такая связь эквивалентна независимому множеству, в котором одна вершина принадлежит V 1, а другая - V 2. Таким образом, в этом случае условие теоремы не только достаточное, но и необходимое.
Другие условия
Каждый правильно раскрашенный граф без треугольников с хроматическим числом x содержит не зависящее от радуги множество размером не менее x / 2. [11]
Несколько авторов изучали условия существования больших радужно-независимых множеств в различных классах графов. [1] [12]
Вычисление
Проблема решения ISR - это проблема определения того, допускает ли данный граф G = ( V , E ) и данное разбиение V на m цветов набор, не зависящий от радуги. Эта проблема является NP-полной . Доказательство сводится к 3-мерной задаче согласования (3DM). [4] Входными данными в 3DM является трехчастный гиперграф ( X + Y + Z , F ), где X , Y , Z - наборы вершин размера m , а F - набор троек, каждый из которых содержит одну вершину. каждый из Х , Y , Z . Входные данные в 3DM можно преобразовать во входные данные в ISR следующим образом:
- Для каждого ребра ( x , y , z ) в F существует вершина v x, y, z в V ;
- Для каждой вершины z в Z положим V z = { v x, y, z | x в X, y в Y}.
- Для каждого x, y 1 , y 2 , z 1 , z 2 существует ребро ( v x, y1, z1 , v x, y2, z2 ) в E ;
- Для каждого x 1 , x 2 , y, z 1 , z 2 существует ребро ( v x1, y, z1 , v x2, y, z2 ) в E ;
В результирующем графе G = ( V , E ) ISR соответствует набору троек (x, y, z) таких, что:
- Каждый триплет имеет различное значение z (поскольку каждый триплет принадлежит разному набору цветов V z );
- Каждый триплет имеет различное значение x и другое значение y (поскольку вершины независимы).
Следовательно, результирующий граф допускает ISR тогда и только тогда, когда исходный гиперграф допускает 3DM.
Связанные понятия
Если G является линейным графиком некоторого другого графа Н , то независимые множества в G являются паросочетанием в H . Следовательно, не зависящее от радуги множество в G является радужным соответствием в H. См. Также сопоставление в гиперграфах .
Другая связанная концепция - это цикл радуги , который представляет собой цикл, в котором каждая вершина имеет свой цвет. [13]
Когда существует ISR, возникает естественный вопрос, существуют ли другие ISR, такие, что весь набор вершин разбивается на непересекающиеся ISR (при условии, что количество вершин в каждом цвете одинаково). Такое разбиение называется сильной раскраской .
Используя метафору факультета: [3]
- Система различных представителей является комитетом отдельных членов, с или без конфликтов.
- Независимое множество является комитетом, без конфликтов.
- Независимый трансверсально является комитетом, без конфликта, ровно один члена от каждого отдела.
- Раскраски графа является разделение членов профессорско - преподавательского состава в комитетах, не имеющих конфликта.
- Сильное окрашивание является разделение членов профессорско - преподавательского состава в комитетах, не имеющих конфликта и с точно один член от каждого отдела. Поэтому эту проблему иногда называют проблемой счастливого декана .
Радуги клика или красочная клика является кликой , в котором каждая вершина имеет другой цвет. [10] Каждая клика в графе соответствует независимому множеству в его дополнительном графе . Следовательно, каждой радужной клике в графе соответствует не зависящее от радуги множество в его дополнительном графе.
Смотрите также
- Раскраска графика
- Раскраска списка
- Раскраска радуга
- Раскрашиваемый радугой гиперграф
- Комплекс Независимости
Рекомендации
- ^ a b Ахарони, Рон; Бриггс, Джозеф; Ким, Джинха; Ким, Минки (2019-09-28). «Радужные независимые множества в некоторых классах графов». arXiv : 1909.13143 [ math.CO ].
- ^ Ахарони, Рон; Бергер, Эли; Котлар, Дани; Зив, Ран (2017-10-01). «По догадке Штейна». Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg . 87 (2): 203–211. DOI : 10.1007 / s12188-016-0160-3 . ISSN 1865-8784 . S2CID 119139740 .
- ^ а б в г д е Хакселл, П. (2011-11-01). «Об образовании комитетов». Американский математический ежемесячник . 118 (9): 777–788. DOI : 10,4169 / amer.math.monthly.118.09.777 . ISSN 0002-9890 . S2CID 27202372 .
- ^ а б в г Ахарони, Рон; Бергер, Эли; Зив, Ран (2007-05-01). «Независимые системы представителей в взвешенных графах». Combinatorica . 27 (3): 253–267. DOI : 10.1007 / s00493-007-2086-у . ISSN 1439-6912 . S2CID 43510417 .
- ^ E, HaxellP (01.07.2001). «Замечание о раскраске списка вершин». Комбинаторика, теория вероятностей и вычисления . 10 (4): 345–347. DOI : 10,1017 / s0963548301004758 .
- ^ Сабо *, Тибор; Тардос †, Габор (01.06.2006). «Экстремальные задачи для трансверсалей в графах с ограниченной степенью». Combinatorica . 26 (3): 333–351. DOI : 10.1007 / s00493-006-0019-9 . ЛВП : 20.500.11850 / 24692 . ISSN 1439-6912 . S2CID 15413015 .
- ^ Хакселл, Пенни; Сабо, Тибор (01.01.2006). «Нечетные независимые трансверсали - нечетные» . Комбинаторика, теория вероятностей и вычисления . 15 (1-2): 193-211. DOI : 10.1017 / S0963548305007157 . ISSN 1469-2163 .
- ^ Берке, Роберт; Хакселл, Пенни; Сабо, Тибор (2012). «Ограниченные трансверсали в многодольных графах». Журнал теории графов . 70 (3): 318–331. DOI : 10.1002 / jgt.20618 . ISSN 1097-0118 .
- ^ а б Ахарони, Рон; Хакселл, Пенни (2000). «Теорема Холла для гиперграфов» . Журнал теории графов . 35 (2): 83–88. DOI : 10.1002 / 1097-0118 (200010) 35: 2 <83 :: AID-JGT2> 3.0.CO; 2-V . ISSN 1097-0118 .
- ^ а б Мешулам, Рой (01.01.2001). «Кликовый комплекс и соответствие гиперграфа». Combinatorica . 21 (1): 89–94. DOI : 10.1007 / s004930170006 . ISSN 1439-6912 . S2CID 207006642 .
- ^ Aravind, NR; Камби, Стейн; ван Батенбург, Воутер Камес; де Веркло, Реми де Жоаннис; Канг, Росс Дж .; Патель, Виреш (15 марта 2020 г.). «Структура и цвет в графах без треугольников». arXiv : 1912.13328 [ math.CO ].
- ^ Ким, Джинха; Ким, Минки; Квон, О. Чжон (05.02.2020). «Радужно-независимые множества на плотных классах графов». arXiv : 2001.10566 [ math.CO ].
- ^ Ахарони, Рон; Бриггс, Джозеф; Хольцман, Рон; Цзян, Зилинь (19.07.2020). «Радужные нечетные циклы». arXiv : 2007.09719 [ math.CO ].