Радужно-независимый набор

Независимое множество в графе

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

Формально, пусть $G = (V, E)$ — граф, и предположим, что множество вершин V разделено $на$ m подмножеств $V$ 1 $,$ $\dots$ $,$ $V$ $m$ , называемых «цветами». Множество вершин $U$ называется радужно-независимым множеством, если оно удовлетворяет обоим следующим условиям: ^[1]

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

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

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

Варианты

Для удобства предполагается, что множества $V 1, \dots, 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$ , а размер каждого цветового множества не менее $2 d$ , то $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, \dots, V m}$ и множество $Z$ ребер $G S$ , такие что:
Вершины $x$ и $y$ находятся в $США;$
Ребро $e = (x, y)$ находится в $Z$ ;
Множество вершин, смежных с $Z,$ доминирует над $G S$ ;
$| Z | \leq | S | - 1$ ;
$Z$ — паросочетание : никакие два его ребра не смежны с одной и той же вершиной.

Состояние типа Холла

Ниже, учитывая подмножество $S$ цветов (подмножество ${V 1, \dots, V m}$ ), независимое множество $I S$ из $G S$ называется специальным для $S,$ если для каждого независимого подмножества $J$ вершин $G S$ размера не более $| S | - 1$ , существует некоторое $v$ из $I S$ такое, что $J \cup {v}$ также независимо. Образно говоря, $I S$ является командой «нейтральных членов» для множества $S$ отделов, которая может увеличить любой достаточно малый набор неконфликтующих членов, чтобы создать больший такой набор. Следующая теорема аналогична теореме Холла о браке : ^[9]

Если для каждого подмножества цветов S граф $G S$ содержит независимое множество $I S$ , которое является специальным для $S$ , то $G$ имеет ISR.

Идея доказательства . Теорема доказывается с помощью леммы Шпернера . ^[3]^{: Теор.4.2} Стандартному симплексу с $m$ конечными точками назначается триангуляция с некоторыми специальными свойствами. Каждая конечная точка $i$ симплекса связана с набором цветов $V i$ , каждая грань ${i 1, \dots, i k}$ симплекса связана с набором цветов $S = {V i 1, \dots, V ik} . Каждая точка$ $x$ триангуляции помечена вершиной $g (x)$ графа $G$ таким образом, что: (a) Для каждой точки $x$ на грани $S$ , $g (x)$ является элементом $I S$ – специального независимого множества графа $S$ . (b) Если точки $x$ и $y$ являются смежными в 1-скелете триангуляции, то $g (x)$ и $g (y)$ не являются смежными в $G$ . По лемме Шпернера существует подсимплекс, в котором для каждой точки $x$ , $g (x)$ принадлежит другому цветовому множеству; множество этих $g (x)$ является ISR.

Из вышеприведенной теоремы следует условие брака Холла. Чтобы увидеть это, полезно сформулировать теорему для особого случая, в котором $G$ является линейным графом некоторого другого графа $H$ ; это означает, что каждая вершина $G$ является ребром $H$ , и каждое независимое множество $G$ является паросочетанием в $H$ . Раскраска вершин $G$ соответствует раскраске ребер $H$ , а радужно-независимое множество в $G$ соответствует радужному паросочетанию в $H$ . Сопоставление $I S$ в $H S$ является особым для $S$ , если для каждого паросочетания $J$ в $H S$ размера не более $| S | - 1$ , существует ребро $e$ в $I S$ такое, что $J \cup {e}$ все еще является паросочетанием в $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 |$ ребер $H$ , смежных с различными вершинами $Y$ . Пусть $I S$ — множество из $| S |$ таких ребер. Для любого паросочетания $J$ размера не более $| S | - 1$ в $H$ некоторый элемент $e$ из $I S$ имеет другую конечную точку в $Y ,$ чем все элементы $J$ , и, таким образом, $J \cup {e}$ также является паросочетанием, поэтому $I S$ является специальным для $S$ . Из вышеприведенной теоремы следует, что $H$ имеет радужное паросочетание $M R$ . По определению цветов $M 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$ . Следовательно, $I S$ является особым для $S$ . По предыдущей теореме $G$ имеет ISR.

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

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

$Ind(G)$ обозначает комплекс независимости графа $G$ (то есть абстрактный симплициальный комплекс , грани которого являются независимыми множествами в $G$ ).
$η H (X)$ обозначает гомологическую связность симплициального комплекса $X$ (т. е. наибольшее целое число $k$ такое, что первые $k$ групп гомологий $X$ тривиальны), плюс 2.
$[m]$ — это набор индексов цветов, ${1, \dots, n}.$ Для любого подмножества $J$ из $[m]$ , $V J$ — это объединение цветов $V J$ для $J$ в $J$ .
$G [V J]$ — подграф $G,$ индуцированный вершинами из $V J$ .

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

Если для всех подмножеств $J$ из $[m]$ :
$\eta _{H}({\text{Ind}}(G[V_{J}]))\geq |J|$
тогда раздел $V 1, \dots, 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$ , т. е. оно имеет один $n$ -симплекс (и все его подмножества). Известно, что один симплекс является $k$ -связным для всех целых чисел $k$ , поскольку все его редуцированные группы гомологий тривиальны (см. симплициальная гомология ). Следовательно, условие выполняется.
$J = {2}:$ этот случай аналогичен предыдущему.
$J = {1,2}:$ тогда $G [J] = G$ , и $Ind(G)$ содержит два симплекса $V 1$ и $V 2$ (и все их подмножества). Условие $η H (Ind(G)) \geq 2$ эквивалентно условию, что гомологическая связность $Ind(G)$ не меньше 0, что эквивалентно условию, чтоявляется тривиальной группой. Это выполняется тогда и только тогда, когда комплекс $Ind($ $G$ $)$ содержит связь между своими двумя симплексами $V$ $1$ и $V$ $2$ . Такая связь эквивалентна независимому множеству, в котором одна вершина принадлежит $V$ $1$ , а другая — $V$ $2$ . Таким образом, в этом случае условие теоремы является не только достаточным, но и необходимым. ${\tilde {H_{0}}}({\text{Ind}}(G))$

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

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

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

Вычисление

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

Для каждого ребра $(x, y, z)$ в $F$ существует вершина $v x,y,z$ в $V$ ;
Для каждой вершины $z$ в $Z$ пусть $V z = {v x,y,z | x \in X, y \in Y}.$
$Для$ каждого $x$ , $y1$ , $y2$ , $z1$ , $z2$ существует ребро $($ $vx$ $,$ $y1$ $,$ $z1$ $,$ $vx$ $,$ $y2$ $,$ $z2$ $)$ $в$ $E$ ; $$ $$ $$ $$ $$ $$ $$ $$
Для каждого $x 1$ , $x 2$ , $y$ , $z 1$ , $z 2$ существует ребро $(v x 1, y, z 1, v x 2, y, z 2)$ в $E$ ;

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

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

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

Альтернативное доказательство — сокращение от SAT . ^[3]

Связанные концепции

Если $G$ — линейный граф некоторого другого графа $H$ , то независимые множества в $G$ являются паросочетаниями в $H.$ Следовательно, радужно-независимое множество в $G$ является радужным паросочетанием в $H.$ См. также паросочетания в гиперграфах .

Другая связанная концепция — радужный цикл , представляющий собой цикл , в котором каждая вершина имеет свой цвет. ^[13]

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

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

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

Радужная клика или цветная клика — это клика , в которой каждая вершина имеет свой цвет. ^[10] Каждая клика в графе соответствует независимому множеству в ее дополнительном графе . Таким образом, каждая радужная клика в графе соответствует независимому от радуги множеству в ее дополнительном графе.

Смотрите также

Ссылки

^ ab Ахарони, Рон; Бриггс, Джозеф; Ким, Джинха; Ким, Минки (2019-09-28). «Радужные независимые множества в некоторых классах графов». arXiv : 1909.13143 [math.CO].
^ Ахарони, Рон; Бергер, Эли; Котлар, Дэни; Зив, Ран (01 октября 2017 г.). «О догадке Штейна». 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.
^ abcdef Хакселл, П. (2011-11-01). «О формировании комитетов». The American Mathematical Monthly . 118 (9): 777– 788. doi :10.4169/amer.math.monthly.118.09.777. ISSN 0002-9890. S2CID 27202372.
^ abcd Ахарони, Рон; Бергер, Эли; Зив, Ран (1 мая 2007 г.). «Независимые системы представителей во взвешенных графах». Комбинаторика . 27 (3): 253–267 . doi :10.1007/s00493-007-2086-y. ISSN 1439-6912. S2CID 43510417.
^ E, HaxellP (2001-07-01). "Заметка о раскраске списка вершин". Комбинаторика, вероятность и вычисления . 10 (4): 345– 347. doi :10.1017/s0963548301004758. S2CID 123033316.
^ Сабо*, Тибор; Тардос†, Габор (2006-06-01). «Экстремальные задачи для трансверсалей в графах с ограниченной степенью». Combinatorica . 26 (3): 333– 351. doi :10.1007/s00493-006-0019-9. hdl : 20.500.11850/24692 . ISSN 1439-6912. S2CID 15413015.
^ Хакселл, Пенни; Сабо, Тибор (2006-01-01). «Нечетные независимые трансверсали нечетны». Комбинаторика, вероятность и вычисления . 15 ( 1– 2): 193– 211. doi :10.1017/S0963548305007157 (неактивен 1 ноября 2024 г.). ISSN 1469-2163. S2CID 6067931.{{cite journal}}: CS1 maint: DOI неактивен по состоянию на ноябрь 2024 г. ( ссылка )
^ Берке, Роберт; Хакселл, Пенни; Сабо, Тибор (2012). «Ограниченные трансверсали в многодольных графах». Журнал теории графов . 70 (3): 318– 331. doi :10.1002/jgt.20618. ISSN 1097-0118. S2CID 17608344.
^ ab Ахарони, Рон; Хакселл, Пенни (2000). «Теорема Холла для гиперграфов». Журнал теории графов . 35 (2): 83– 88. doi :10.1002/1097-0118(200010)35:2<83::AID-JGT2>3.0.CO;2-V. ISSN 1097-0118.
^ ab Мешулам, Рой (2001-01-01). «Комплекс клик и сопоставление гиперграфов». Combinatorica . 21 (1): 89– 94. doi :10.1007/s004930170006. ISSN 1439-6912. S2CID 207006642.
^ Аравинд, Северная Каролина; Камби, Стейн; ван Батенбург, Воутер Камес; де Веркло, Реми де Жоаннис; Канг, Росс Дж.; Патель, Виреш (15 марта 2020 г.). «Структура и цвет в графах без треугольников». arXiv : 1912.13328 [math.CO].
^ Ким, Джинха; Ким, Минки; Квон, О.-джунг (2020-02-05). «Радужные независимые множества на плотных графовых классах». arXiv : 2001.10566 [math.CO].
^ Ахарони, Рон; Бриггс, Джозеф; Хольцман, Рон; Цзян, Цзилинь (2021). «Радужные нечетные циклы». SIAM Journal по дискретной математике . 35 (4): 2293–2303 . arXiv : 2007.09719 . дои : 10.1137/20M1380557. S2CID 220647170.

[:0-1] Ахарони, Рон; Бриггс, Джозеф; Ким, Джинха; Ким, Минки (2019-09-28). «Радужные независимые множества в некоторых классах графов». arXiv : 1909.13143 [math.CO].

[2] Ахарони, Рон; Бергер, Эли; Котлар, Дэни; Зив, Ран (01 октября 2017 г.). «О догадке Штейна». 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.

[:2-3] Хакселл, П. (2011-11-01). «О формировании комитетов». The American Mathematical Monthly . 118 (9): 777– 788. doi :10.4169/amer.math.monthly.118.09.777. ISSN 0002-9890. S2CID 27202372.

[:1-4] Ахарони, Рон; Бергер, Эли; Зив, Ран (1 мая 2007 г.). «Независимые системы представителей во взвешенных графах». Комбинаторика . 27 (3): 253–267 . doi :10.1007/s00493-007-2086-y. ISSN 1439-6912. S2CID 43510417.

[5] E, HaxellP (2001-07-01). "Заметка о раскраске списка вершин". Комбинаторика, вероятность и вычисления . 10 (4): 345– 347. doi :10.1017/s0963548301004758. S2CID 123033316.

[6] Сабо*, Тибор; Тардос†, Габор (2006-06-01). «Экстремальные задачи для трансверсалей в графах с ограниченной степенью». Combinatorica . 26 (3): 333– 351. doi :10.1007/s00493-006-0019-9. hdl : 20.500.11850/24692 . ISSN 1439-6912. S2CID 15413015.

[7] Хакселл, Пенни; Сабо, Тибор (2006-01-01). «Нечетные независимые трансверсали нечетны». Комбинаторика, вероятность и вычисления . 15 ( 1– 2): 193– 211. doi :10.1017/S0963548305007157 (неактивен 1 ноября 2024 г.). ISSN 1469-2163. S2CID 6067931.{{cite journal}}: CS1 maint: DOI неактивен по состоянию на ноябрь 2024 г. ( ссылка )

[8] Берке, Роберт; Хакселл, Пенни; Сабо, Тибор (2012). «Ограниченные трансверсали в многодольных графах». Журнал теории графов . 70 (3): 318– 331. doi :10.1002/jgt.20618. ISSN 1097-0118. S2CID 17608344.

[:4-9] Ахарони, Рон; Хакселл, Пенни (2000). «Теорема Холла для гиперграфов». Журнал теории графов . 35 (2): 83– 88. doi :10.1002/1097-0118(200010)35:2<83::AID-JGT2>3.0.CO;2-V. ISSN 1097-0118.

[:3-10] Мешулам, Рой (2001-01-01). «Комплекс клик и сопоставление гиперграфов». Combinatorica . 21 (1): 89– 94. doi :10.1007/s004930170006. ISSN 1439-6912. S2CID 207006642.

[11] Аравинд, Северная Каролина; Камби, Стейн; ван Батенбург, Воутер Камес; де Веркло, Реми де Жоаннис; Канг, Росс Дж.; Патель, Виреш (15 марта 2020 г.). «Структура и цвет в графах без треугольников». arXiv : 1912.13328 [math.CO].

[12] Ким, Джинха; Ким, Минки; Квон, О.-джунг (2020-02-05). «Радужные независимые множества на плотных графовых классах». arXiv : 2001.10566 [math.CO].

[13] Ахарони, Рон; Бриггс, Джозеф; Хольцман, Рон; Цзян, Цзилинь (2021). «Радужные нечетные циклы». SIAM Journal по дискретной математике . 35 (4): 2293–2303 . arXiv : 2007.09719 . дои : 10.1137/20M1380557. S2CID 220647170.