Отличительная окраска
В теории графов отличительная раскраска или отличительная маркировка графа — это присвоение цветов или меток вершинам графа , которое разрушает все нетривиальные симметрии графа . Раскраска не обязательно должна быть правильной : соседним вершинам разрешено придавать один и тот же цвет. Для цветного графа не должно существовать однозначного отображения вершин в себя, сохраняющего как смежность, так и раскраску. Минимальное количество цветов в различающей раскраске называется различающим числом графа.
Отличительные цвета и числа были введены Альбертсоном и Коллинзом (1996) , которые привели следующий мотивирующий пример, основанный на головоломке, ранее сформулированной Фрэнком Рубином: «Предположим, у вас есть связка ключей от разных дверей; каждый ключ открывает только одну дверь. , но все они кажутся вам неразличимыми. Сколько цветов вам нужно, чтобы раскрасить ручки клавиш так, чтобы можно было однозначно идентифицировать каждую клавишу?» [1] Этот пример решается с помощью отличительной раскраски графа цикла . При такой раскраске каждая клавиша будет однозначно идентифицироваться по своему цвету и последовательности окружающих ее цветов. [2]
Примеры
[ редактировать ]
Граф имеет отличительный номер один тогда и только тогда, когда он асимметричен . [3] Например, граф Фрухта имеет отличительную раскраску только в один цвет.
В полном графе единственные различающиеся раскраски присваивают каждой вершине свой цвет. Ведь если бы двум вершинам был присвоен один и тот же цвет, существовала бы симметрия, которая поменяла бы эти две вершины местами, оставив остальные на месте. отличительное число полного графа Kn n равно . Следовательно , Однако граф, полученный из K n присоединением вершины первой степени к каждой вершине K n, имеет значительно меньшее отличительное число, несмотря на ту же группу симметрии: он имеет отличительную раскраску с цвета, полученные путем использования разных упорядоченных пар цветов для каждой пары вершины K n и ее присоединенного соседа. [2]
Для графа циклов из трех, четырех или пяти вершин необходимо три цвета для построения различающей раскраски. Например, каждая двухраскраска пятицикла обладает отражательной симметрией. В каждом из этих циклов присвоение уникального цвета каждой из двух соседних вершин и использование третьего цвета для всех оставшихся вершин приводит к трехцветной отличительной раскраске. Однако циклы из шести и более вершин имеют отличительную раскраску только в два цвета. То есть головоломка с брелоками Фрэнка Рубина требует трех цветов для колец из трех, четырех или пяти ключей, но только двух цветов для шести и более ключей или для двух ключей. [2] Например, в показанном кольце из шести ключей каждый ключ можно отличить по цвету и длине или длине соседних блоков ключей противоположного цвета: существует только один ключ для каждой комбинации цвета ключа и длин соседних блоков. .
Графы гиперкубов демонстрируют то же явление, что и графы циклов. Двумерный и трехмерный графы гиперкуба (4-цикл и граф куба соответственно) имеют отличительное число три. Однако каждый граф гиперкуба более высокой размерности имеет отличительное число только два. [4]
Граф Петерсена имеет отличительное число 3. Однако, кроме этого графа и полных графов, все графы Кнезера имеют отличительное число 2. [5] Аналогично среди обобщенных графов Петерсена только сам граф Петерсена и граф куба имеют отличительное число 3; остальные имеют отличительный номер 2. [6]
Вычислительная сложность
[ редактировать ]Отличительные числа деревьев , плоских графов и интервальных графов могут быть вычислены за полиномиальное время . [7] [8] [9]
Точная сложность вычисления различающих чисел неясна, поскольку она тесно связана с до сих пор неизвестной сложностью изоморфизма графов . Однако было показано, что он принадлежит к классу сложности AM . [10] Кроме того, проверка того, не превышает ли три различающее хроматическое число, является NP-сложной . [9] и проверить, не превышает ли их два, «по крайней мере так же сложно, как автоморфизм графа, но не сложнее, чем изоморфизм графа». [11]
Дополнительные свойства
[ редактировать ]Раскраска данного графа является различительной для этого графа тогда и только тогда, когда она является различительной для графа-дополнения . Следовательно, каждый граф имеет то же отличительное число, что и его дополнение. [2]
Для каждого графа G отличительное число не более чем пропорционально логарифму числа автоморфизмов G G . Если автоморфизмы образуют нетривиальную абелеву группу , то различающее число равно двум, а если она образует группу диэдра , то отличительное число не превосходит трех. [2]
Для каждой конечной группы существует граф, в котором эта группа является группой автоморфизмов с отличительным номером два. [2] Этот результат расширяет теорему Фрухта о том, что каждую конечную группу можно реализовать как группу симметрий графа.
Вариации
[ редактировать ]Правильная различающая раскраска — это различающая раскраска, которая также является правильной раскраской: каждые две соседние вершины имеют разные цвета. Минимальное количество цветов в правильной различающей раскраске графа называется различающим хроматическим числом графа. [12]
Ссылки
[ редактировать ]- ^ Рубин, Франк (1979), «Задача 729: ключи слепого», Журнал развлекательной математики , 11 : 128 . Решение в т. 12, 1980. Цитируется Albertson & Collins (1996) . Вместо использования цветов Рубин сформулировал проблему с помощью рукояток клавиш, которые можно было отличить друг от друга на ощупь. Точнее, эта задача предполагает, что каждый ключ симметричен, так что ключи нельзя отличить друг от друга по их ориентации на связке ключей.
- ^ Jump up to: а б с д и ж Альбертсон, Майкл О.; Коллинз, Карен Л. (1996), «Нарушение симметрии в графах» , Электронный журнал комбинаторики , 3 (1): R18, doi : 10.37236/1242 , MR 1394549 .
- ^ См., например, Имрих, Вильфрид; Klavžar, Sandi (2006), «Различающие декартовые способности графиков», Journal of Graph Theory , 53 (3): 250–260, Citeseerx 10.1.1.59.9242 , doi : 10.1002/jgt.20190 , MR 2262268 , S2CID 6808067 ,
Если граф не имеет нетривиальных автоморфизмов, его отличительное число равно 1. Другими словами, D ( G ) = 1 для асимметричных графов.
- ^ Богстад, Билл; Коуэн, Ленор Дж. (2004), «Отличительное число гиперкуба», Discrete Mathematics , 283 (1–3): 29–35, doi : 10.1016/j.disc.2003.11.018 , MR 2061481 .
- ^ Альбертсон, Майкл О.; Бутин, Дебра Л. (2007), «Использование определяющих наборов для различения графов Кнезера» , Электронный журнал комбинаторики , 14 (1): R20, doi : 10.37236/938 , MR 2285824 .
- ^ Лал, АК; Бхаттачарджья, Б. (2009), «Нарушение симметрии книжного графа и обобщенного графа Петерсена», SIAM Journal on Discrete Mathematics , 23 (3): 1200–1216, doi : 10.1137/080728640 , MR 2538646 . Лал и Бхаттачарья (теорема 4.3) приписывают этот результат неопубликованной магистерской диссертации К.С. Потанки (Политехнический университет Вирджинии, 1998).
- ^ Ченг, Кристин Т. (2006), «О вычислении отличительных чисел деревьев и лесов» , Электронный журнал комбинаторики , 13 (1): R11, doi : 10.37236/1037 , MR 2200539 .
- ^ Арвинд, В.; Ченг, Кристин Т.; Деванур, Нихил Р. (2008), «О вычислении отличительных чисел плоских графов и не только: подход к подсчету», SIAM Journal on Discrete Mathematics , 22 (4): 1297–1324, arXiv : math/0703927 , doi : 10.1137 /07068686X , MR 2443115 , S2CID 2402306 .
- ^ Jump up to: а б Ченг, Кристин Т. (2009), «О вычислении различения и различения хроматических чисел интервальных графиков и других результатах», Discrete Mathematics , 309 (16): 5169–5182, doi : 10.1016/j.disc.2009.04.004 , МР 2548918 .
- ^ Рассел, Александр; Сундарам, Рави (1998), «Заметки об асимптотике и вычислительной сложности различимости графов» , Electronic Journal of Combinatorics , 5 : R23, doi : 10.37236/1361 , MR 1617449 .
- ^ Эшен, Элейн М.; Хоанг, Чинь Т.; Шритаран, Р.; Стюарт, Лорна (2011), «О сложности определения того, не превышает ли отличительное хроматическое число графа два», Discrete Mathematics , 311 (6): 431–434, arXiv : 0907.0691 , doi : 10.1016/j.disc .2010.12.013 , МР 2799894 , S2CID 7679211 .
- ^ Коллинз, Карен Л .; Тренк, Энн Н. (2006), «Различающее хроматическое число» , Электронный журнал комбинаторики , 13 (1): R16, doi : 10.37236/1042 , MR 2200544 .