Введение

Присвоение меток элементам графа

В математической дисциплине теории графов, маркировка графа — это присвоение меток, традиционно представленных целыми числами, рёбрам и/или вершинам графа. Формально, для графа G = (V, E), маркировка вершин является функцией из V в множество меток; граф, для которого определена такая функция, называется графом с маркировкой вершин. Аналогично, маркировка рёбер является функцией из E в множество меток. В этом случае граф называется графом с маркировкой рёбер. Если метки рёбер принадлежат упорядоченному множеству (например, действительным числам), он может называться взвешенным графом. При использовании без уточнения термин «маркированный граф» обычно относится к графу с маркировкой вершин, в котором все метки различны. Такой граф может быть эквивалентно помечен последовательными целыми числами, где — количество вершин в графе. В приведённом выше определении граф понимается как конечный неориентированный простой граф. Однако понятие маркировки может применяться ко всем расширениям и обобщениям графов. Например, в теории автоматов и теории формальных языков удобно рассматривать маркированные мультиграфы, то есть пара вершин может быть соединена несколькими маркированными рёбрами.

История

Большинство раскрасок графов восходят к раскраскам, представленным Александром Розой в его статье 1967 года. Роза выделил три типа раскрасок, которые он назвал α, β и ρ раскрасками. Позднее β-раскраски были переименованы Соломоном Голомбом в "изящные", и это название с тех пор стало широко используемым.

Красивая маркировка

Граф называется грациозным, если его вершины помечены числами от 0 до |V| - 1, где |V| – размер графа, и если такая маркировка вершин индуцирует маркировку ребер числами от 1 до |E|. Для любого ребра e, метка e равна положительной разности между метками двух вершин, инцидентных e. Иными словами, если ребро e инцидентно вершинам с метками i и j, то e будет помечено |i - j|. Таким образом, граф G = (V, E) является грациозным тогда и только тогда, когда существует инъекция из V в {0, 1, ..., |V|-1}, которая индуцирует биекцию из E в {1, 2, ..., |E|}.

В своей оригинальной работе Роза доказал, что все эйлеровы графы с размером, сравнимым с 1 или 2 по модулю 4, не являются грациозными. Вопрос о том, являются ли грациозными определенные семейства графов, является активно изучаемой областью теории графов. Вероятно, самая большая недоказанная гипотеза в теории маркировки графов – гипотеза Рингеля-Котцига, которая утверждает, что все деревья являются грациозными. Она была доказана для всех путей, гусениц и многих других бесконечных семейств деревьев. Сам Антон Котциг назвал усилия по доказательству этой гипотезы "болезнью".

Гармоничное маркирование

"Гармоническая раскраска" графа G — это инъективное отображение вершин G в группу целых чисел по модулю k, где k — число ребер G, которое индуцирует биекцию между ребрами G и числами по модулю k, определяя метку ребра (x, y) как сумму меток двух вершин x и y по модулю k. "Гармоничный граф" — это граф, для которого существует гармоническая раскраска. Нечетные циклы являются гармоничными, как и графы Петерсена. Предполагается, что деревья являются гармоничными, если допускается повторное использование метки одной вершины. Граф "семистраничная книга" является примером графа, который не является гармоничным.

Цвет графика

Раскраска графа — это подкласс графовых раскрасок. Раскраска вершин присваивает различные метки смежным вершинам, а раскраска рёбер — различные метки смежным рёбрам.

Удачная маркировка

Счастливая маркировка графа G — это присвоение положительных целых чисел вершинам G, такое что если S(v) обозначает сумму меток соседей вершины v, то S является раскраской вершин графа G. "Счастливое число" графа G — наименьшее k, для которого существует счастливая маркировка графа G с использованием целых чисел от 1 до k.