WikiSort.ru - Не сортированное

Цикловую раскраску можно рассматривать как уточнение обычной раскраски графов. Цикловое хроматичекое число графа ${\displaystyle G}$ с обозначением ${\displaystyle \chi _{c}(G)}$ можно определить следующими эквивалентными (для конечных графов) способами.

1. ${\displaystyle \chi _{c}(G)}$ равен инфимуму по всем вещественным числам ${\displaystyle r}$ , таким что существует отображение из ${\displaystyle V(G)}$ в окружность с длиной окружности 1, при этом две смежные вершины отображаются в точки на расстоянии, не превосходящем ${\displaystyle \geqslant {\tfrac {1}{r}}}$ вдоль окружности.
2. ${\displaystyle \chi _{c}(G)}$ равен инфимуму по рациональным числам ${\displaystyle {\tfrac {n}{k}}}$ , таким что существует отображение из ${\displaystyle V(G)}$ в циклическую группу ${\displaystyle {\mathbb {Z} }/n{\mathbb {Z} }}$ со свойством, что смежные вершины отображаются в элементы на расстоянии ${\displaystyle \geqslant k}$ друг от друга.
3. В ориентированном графе определим дисбаланс цикла ${\displaystyle C}$ как значение ${\displaystyle |E(C)|}$ , делённое на меньшее из числа рёбер, направленных по часовой стрелке и числа рёбер, направленных против часовой стрелки. Определим дисбаланс ориентированного графа как максимальный дисбаланс по всем циклам. Теперь, ${\displaystyle \chi _{c}(G)}$ равен минимальному дисбалансу по всем ориентациям графа ${\displaystyle G}$ .

Относительно несложно видеть, что ${\displaystyle \chi _{c}(G)\leqslant \chi (G)}$ (используя определение 1. или 2.), но, фактически, ${\displaystyle \lceil \chi _{c}(G)\rceil =\chi (G)}$ . В этом смысле мы говорим, что цикловое хроматичекое число уточняет обычное хроматичекое число.

Цикловую раскраску первоначально определил Винс^[1], который назвал её «звёздной раскраской».

Цикловая раскраска двойственна субъекту нигде не нулевого потока и более того, цикловая раскраска имеет естественное двойственное понятие «циркуляционный поток».

Цикловые полные графы

Циркулярный полный граф
Вершин	n
Рёбер	${\displaystyle {\tfrac {n(n-2k+1)}{2}},}$
Обхват	${\displaystyle \left\{{\begin{array}{ll}\infty &n=2k\\n&n=2k+1\\4&2k+2\leq n<3k\\3&{\text{otherwise}}\end{array}}\right.}$
Хроматическое число	⌈n/k⌉
Свойства	(n − 2k + 1)- регулярный Вершинно-транзитивный Циркулянтный Гамильтонов

Для целых ${\displaystyle n,k}$ , таких что ${\displaystyle n\geqslant 2k}$ , цикловой полный граф ${\displaystyle K_{\tfrac {n}{k}}}$ (известный также как цикловая клика) — это граф с множеством вершин ${\displaystyle {\mathbb {Z} }/n{\mathbb {Z} }}$ и рёбрами между элементами на расстоянии ${\displaystyle \geqslant k}$ друг от друга. То есть, вершинами являются числа {0, 1, ..., n-1} и вершина i смежна с:

${\displaystyle i+k,i+k+1,\dots ,i+n-k\mod n}$ .

Например, ${\displaystyle K_{\tfrac {n}{1}}}$ является просто полным графом K_n, в то время как граф ${\displaystyle K_{\tfrac {2n+1}{n}}}$ изоморфен графу-циклу ${\displaystyle C_{2n+1}}$ .

Цикловая раскраска тогда, согласно второму определению выше, является гомоморфизмом в цикловой полный граф. Критическое обстоятельство об этих графах, что ${\displaystyle K_{\tfrac {a}{b}}}$ допускает гомоморфизм в ${\displaystyle K_{\tfrac {c}{d}}}$ тогда и только тогда, когда ${\displaystyle {\tfrac {a}{b}}\leqslant {\tfrac {c}{d}}}$ . Это объясняет обозначение, поскольку если рациональные числа ${\displaystyle {\tfrac {a}{b}}}$ и ${\displaystyle {\tfrac {c}{d}}}$ равны, то ${\displaystyle K_{\tfrac {a}{b}}}$ и ${\displaystyle K_{\tfrac {c}{d}}}$ гомоморфно эквивалентны. Более того, порядок гомоморфизма уточняет порядок, задающийся полными графами в плотным порядком и соответствующий рациональным числам ${\displaystyle \geqslant 2}$ . Например

${\displaystyle K_{\tfrac {2}{1}}\to K_{\tfrac {5}{2}}\to K_{\tfrac {7}{3}}\to \dots \to K_{\tfrac {3}{1}}\to K_{\tfrac {4}{1}}\to \dots }$

Или, эквивалентно

${\displaystyle K_{2}\to C_{5}\to C_{7}\to \dots \to K_{3}\to K_{4}\to \dots }$

Пример на рисунке можно интерпретировать как гомоморфизм из снарка «Цветок» ${\displaystyle J_{5}}$ в ${\displaystyle K_{\tfrac {5}{2}}\approx C_{5}}$ , который идёт раньше ${\displaystyle K_{3}}$ , что соответствует факту, что ${\displaystyle \chi _{c}(J_{5})\leqslant 2,5<3}$ .

Примечания

Литература

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии. Проверить статью на грамматические и орфографические ошибки.