Раскраска радуга

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

В теории графов путь в графе с краской ребра называется радужным, если на нем не повторяется ни один цвет. Граф называется радужно-связным (или окрашенным в радугу ), если между каждой парой его вершин есть радужный путь . Если между каждой парой вершин существует кратчайший путь радуги , то граф называется сильно радужно-связным (или сильно окрашенным в радугу ). ^[1]

Определения и границы [ править ]

Номер соединения радуги на графике - это минимальное количество цветов, необходимое для соединения радуги , и обозначается значком . Точно так же число сильной радужной связи графа - это минимальное количество цветов, необходимое для сильной радужной связи , и обозначается . Ясно, что каждая яркая радужная окраска также является радужной окраской, в то время как обратное в целом неверно.${\ displaystyle G}$${\ displaystyle G}$${\ displaystyle {\ text {rc}} (G)}$${\ displaystyle G}$${\ displaystyle G}$${\ displaystyle {\ text {src}} (G)}$

Легко заметить , что радужные подключить любой связный граф , мы должны по крайней мере , цвета, где есть диаметр от (т.е. длина самого длинного кратчайшего пути). С другой стороны, мы никогда не можем использовать больше цветов, где обозначает количество ребер в . Наконец, поскольку каждый граф с сильной радугой связан с радугой, мы это имеем .${\ displaystyle G}$${\ displaystyle {\ text {diam}} (G)}$${\ displaystyle {\ text {diam}} (G)}$${\ displaystyle G}$${\ displaystyle m}$${\ displaystyle m}$${\ displaystyle G}$${\ displaystyle {\ text {diam}} (G) \ leq {\ text {rc}} (G) \ leq {\ text {src}} (G) \ leq m}$

Следующие экстремальные случаи: ^[1]

• ${\ displaystyle {\ text {rc}} (G) = {\ text {src}} (G) = 1}$тогда и только тогда, когда это полный граф .${\ displaystyle G}$
• ${\ displaystyle {\ text {rc}} (G) = {\ text {src}} (G) = m}$тогда и только тогда, когда это дерево .${\ displaystyle G}$

Вышеизложенное показывает, что с точки зрения количества вершин верхняя оценка в целом является наилучшей из возможных. Фактически, раскраска радуги с использованием цветов может быть построена путем окраски краев остовного дерева в различные цвета. Оставшиеся неокрашенные края окрашиваются произвольно, без введения новых цветов. Когда это 2-связное, у нас это есть . ^[2] Более того, это сложно, о чем свидетельствуют, например, нечетные циклы.${\displaystyle {\text{rc}}(G)\leq n-1}$${\displaystyle n-1}$${\displaystyle G}$${\displaystyle G}$${\displaystyle {\text{rc}}(G)\leq \lceil n/2\rceil }$

Точные числа соединений радуги или сильной радуги [ править ]

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

• ${\displaystyle {\text{rc}}(C_{n})={\text{src}}(C_{n})=\lceil n/2\rceil }$, для каждого целого числа , где - график цикла . ^[1]${\displaystyle n\geq 4}$${\displaystyle C_{n}}$
• ${\displaystyle {\text{rc}}(W_{n})=3}$, для каждого целого числа , и , для , где - граф колеса . ^[1]${\displaystyle n\geq 7}$${\displaystyle {\text{src}}(W_{n})=\lceil n/3\rceil }$${\displaystyle n\geq 3}$${\displaystyle W_{n}}$

Сложность [ править ]

Проблема принятия решения о том для данного графа является NP-полной . ^[3] Потому что тогда и только тогда , ^[1] следует, что решение, является ли NP-полным для данного графа .${\displaystyle {\text{rc}}(G)=2}$${\displaystyle G}$${\displaystyle {\text{rc}}(G)=2}$${\displaystyle {\text{src}}(G)=2}$${\displaystyle {\text{src}}(G)=2}$${\displaystyle G}$

Варианты и обобщения [ править ]

Чартран, Окамото и Чжан ^[4] обобщили число радужной связи следующим образом. Пусть - нетривиальный связный граф порядка с раскрашенным ребрами . Дерево - это радужное дерево, если никаким двум краям не назначен один и тот же цвет. Позвольте быть фиксированным целым числом с . Ребро окраски называется -rainbow окраской , если для любого набора из вершин , есть радуга дерево , содержащая вершину . -Rainbow индекс в минимальное число цветов , необходимых в -rainbow окраски . -Rainbow окраска с использованием${\displaystyle G}$${\displaystyle n}$${\displaystyle T}$${\displaystyle T}$${\displaystyle k}$${\displaystyle 2\leq k\leq n}$${\displaystyle G}$${\displaystyle k}$${\displaystyle S}$${\displaystyle k}$${\displaystyle G}$${\displaystyle G}$${\displaystyle S}$${\displaystyle k}$ ${\displaystyle {\text{rx}}_{k}(G)}$${\displaystyle G}$${\displaystyle k}$${\displaystyle G}$${\displaystyle k}$${\displaystyle {\text{rx}}_{k}(G)}$цвета называется минимально- радужной раскраской${\displaystyle k}$ . Таким образом , число радуги соединения .${\displaystyle {\text{rx}}_{2}(G)}$${\displaystyle G}$

Радужная связность также изучалась в графах с цветными вершинами. Это понятие было введено Кривелевичем и Юстером. ^[5] Здесь номер соединения радужных вершин графа , обозначенный как , - это минимальное количество цветов, необходимых для раскраски , так что для каждой пары вершин существует путь, соединяющий их, внутренним вершинам которого назначены разные цвета.${\displaystyle G}$${\displaystyle {\text{rvc}}(G)}$${\displaystyle G}$

См. Также [ править ]

• Соответствие радуги

Заметки [ править ]

Ссылки [ править ]

• Чартран, Гэри ; Джонс, Гарри Л .; McKeon, Kathleen A .; Чжан, Пинг (2008), «Радужная связь в графах», Mathematica Bohemica , 133 (1).
• Чартран, Гэри ; Окамото, Футаба; Чжан Пин (2010), "Радуга деревья в графах и обобщенные подключения", сети , 55 (4), DOI : 10.1002 / net.20339.
• Чакраборти, Сурав; Фишер, Эльдар; Матслия, Арье; Юстер, Рафаэль (2011), «Твердость и алгоритмы для радужной связи», Журнал комбинаторной оптимизации , 21 (3): 330–347, arXiv : 0809.2493 , doi : 10.1007 / s10878-009-9250-9.
• Кривелевич Михаил ; Юстер, Рафаэль (2010), "Радуга Подключение графа (по большей части ) Взаимного до минимума степень", Журнал теории графов , 63 (3): 185-191, DOI : 10.1002 / jgt.20418.
• Ли, Сюэлянь; Ши, Юнтан; Сунь, Юэфан (2013), «Радужные соединения графов: обзор», Графы и комбинаторика , 29 (1): 1–38, arXiv : 1101.5747 , doi : 10.1007 / s00373-012-1243-2.
• Ли, Сюэлянь; Sun, Yuefang (2012), Радужные связности графов , Springer, стр. 103, ISBN 978-1-4614-3119-0.
• Экштейн, Ян; Голуб, Пршемысл; Кайзер, Томаш; Кох, Мария; Камачо, Стефан Матос; Рячек, Зденек; Ширмейер, Инго (2013), «Число радужной связи двухсвязных графов», Дискретная математика , 313 (19): 1884–1892, arXiv : 1110.5736 , doi : 10.1016 / j.disc.2012.04.022.