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