Войти
В математике дисциплины теории графов маркировка графиков - это присвоение меток, традиционно представленных целыми числами, ребрам и / или вершинам графа .
Формально, учитывая график 
, когда метки ребер являются членами упорядоченного набора (например, действительные числа ), его можно назвать взвешенным графом .
При использовании без уточнения термин помеченный граф обычно относится к помеченному вершиной графу, у которого все метки различны. Такой граф может быть эквивалентно помечен последовательными целыми числами 
В приведенном выше определении граф понимается как конечный неориентированный простой граф. Однако понятие разметки можно применять ко всем расширениям и обобщениям графов. Например, в теории автоматов и теории формального языка удобно рассматривать помеченные мультиграфы, т. Е. Пара вершин может быть соединена несколькими помеченными ребрами.
Большинство надписей на графиках ведут свое происхождение от надписей, представленных Александром Розой в его статье 1967 года. Роза выделил три типа меток, которые он назвал α, β- и ρ-метками. β-метки были позже переименованы Соломоном Голомбом в «изящные», и с тех пор это имя стало популярным.
Изящная маркировка; метки вершин отмечены черным цветом, а метки ребер - красным. Граф называется изящным, когда его вершины помечены от 0 до | E |, размер графа, и эта разметка индуцирует разметку ребер от 1 до | E |. Для любого ребра e метка e - это положительная разность между двумя вершинами, инцидентными e. Другими словами, если e инцидентен вершинам, помеченным i и j, e будет помечен | i - j |. Таким образом, граф G = (V, E) является изящным тогда и только тогда, когда существует инъекция, которая индуцирует биекцию от E к положительным целым числам до | E |.
В своей оригинальной статье Роза доказал, что все графы Эйлера с размером , эквивалентным 1 или 2 (mod 4), не изящны. Являются ли определенные семейства графов изящными или нет - это область теории графов, которая активно изучается. Возможно, самая крупная недоказанная гипотеза о разметке графов - это гипотеза Рингеля – Котцига, которая предполагает, что все деревья изящны. Это было доказано для всех троп, гусениц и многих других бесконечных семейств деревьев. Антон Коциг сам назвал попытку доказать эту гипотезу «болезнью».
Изящное ребро разметки на простом графе без петель или несколько ребер на p вершинах и q ребрах - это разметка ребер различными целыми числами в {1,…, q}, такая, что разметка на вершинах, индуцированная пометкой вершины суммой инцидентных ребер, взятой по модулю p, присваивает все значения от 0 до p - 1 до вершин. Граф G называется «грациозным по ребрам», если он допускает разметку, грациозную по ребрам.
Градиентные разметки по краям были впервые введены Шенг-Пингом Ло в 1985 году.
Необходимым условием для градации граничных границ является «условие Ло»:
«Гармоничная разметка» на графе G представляет собой инъекцию из вершин G в группу целых чисел по модулю k, где k - количество ребер G, которая индуцирует биекцию между ребер графа G и числа по модулю k, взяв за метку края для ребра (x, y) сумму меток двух вершин x, y (mod k). «Гармоничный график» - это тот, который имеет гармоничную маркировку. Нечетные циклы гармоничны, как и графики Петерсена. Предполагается, что все деревья гармоничны, если разрешено повторно использовать одну метку вершины. Семистраничный книжный график K 1,7 × K 2 представляет собой пример графика, который не является гармоничным.
Раскраска графа - это подкласс разметки графа. Раскраски вершин присваивают разные метки соседним вершинам, а раскраски ребер присваивают разные метки смежным ребрам.
Удачная маркировка графа G - это присвоение положительных целых чисел вершинам графа G такая, что если S (v) обозначает сумму меток на соседях v, то S является раскраской вершин G. "Счастливое число" G - это наименьшее k такое, что G имеет удачную маркировку с целыми числами {1,…, k}.
