В математической дисциплине теории графов , маркировка графа является присвоение меток, традиционно представлены целыми числами , по краям и / или вершин одного графа . [1]
Формально, учитывая график , А маркировки вершины является функцией к набору меток; граф с такой определенной функцией называется графом с помеченными вершинами . Точно так же маркировка кромок является функцией набора меток. В этом случае граф называется графом с помеченными ребрами .
Когда метки ребер являются членами упорядоченного набора (например, действительные числа ), его можно назвать взвешенным графом .
При использовании без квалификации, термин помеченный граф обычно относится к вершинной-меченого графа со всеми этикетками различных. Такой граф может быть эквивалентно помечен последовательными целыми числами , где - количество вершин в графе. [1] Для многих приложений ребрам или вершинам присваиваются метки, значимые в соответствующей области. Например, ребрам могут быть присвоены веса, представляющие «стоимость» перехода между инцидентными вершинами. [2]
В приведенном выше определении граф понимается как конечный неориентированный простой граф. Однако понятие разметки можно применять ко всем расширениям и обобщениям графов. Например, в теории автоматов и формальных языках теории удобно рассматривать меченых мультиграфы , т.е. пару вершин может быть соединена несколько помеченных ребрами. [3]
История [ править ]
Большинство надписей на графиках берет свое начало от надписей, представленных Александром Розой в его статье 1967 года. [4] Роза выделил три типа меток, которые он назвал α , β - и ρ -метками. [5] Соломон Голомб позже переименовал β- метки в «изящные» , и с тех пор это имя стало популярным.
Особые случаи [ править ]
Изящная маркировка [ править ]
Граф называется изящным, если его вершины помечены от 0 до | E |, размер графа, и эта разметка индуцирует разметку ребер от 1 до | E |, Для любого ребра e метка e - это положительная разность между двумя вершинами, инцидентными e . Другими словами, если e инцидентно вершинам, помеченным i и j , то e будет помечен | я - j |. Таким образом, граф G = ( V , E ) изящен тогда и только тогда, когда существует инъекция, индуцирующая биекцию из Eс целыми положительными числами до | E |,
В своей оригинальной статье Роза доказал, что все графы Эйлера с размером, эквивалентным 1 или 2 ( mod 4), не являются изящными. Являются ли определенные семейства графов изящными или нет - это область теории графов, которая активно изучается. Возможно, самая крупная недоказанная гипотеза о разметке графов - это гипотеза Рингеля – Котцига, которая предполагает, что все деревья изящны. Это было доказано для всех дорожек , гусениц и многих других бесконечных семейств деревьев. Сам Антон Коциг назвал попытку доказать гипотезу «болезнью». [6]
Градиентная маркировка [ править ]
Разметка ребер на простом графе без петель или кратных ребер на p вершинах и q ребрах - это разметка ребер различными целыми числами в {1, ..., q }, такая, что разметка вершин, индуцированная пометкой вершины с помощью сумма инцидентных ребер, взятая по модулю p, присваивает вершинам все значения от 0 до p - 1 . Граф G называется «грациозным по ребрам», если он допускает разметку, грациозную по ребрам.
Маркировка с изящными краями была впервые введена Шэн-Пинг Ло в 1985 году. [7]
Необходимым условием для градации ребер является «условие Ло»:
Гармоничная маркировка [ править ]
А «гармоничная маркировка» на графе G является инъекцией из вершин G к группе целых чисел по модулю к , где к есть число ребер 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]
Ссылки [ править ]
- ^ a b Вайсштейн, Эрик В. «Размеченный граф» . MathWorld .
- ^ Роберт Калдербанк, Различные аспекты теории кодирования , (1995) ISBN 0-8218-0379-4 , стр. 53 "
- ^ " Развитие теории языка ", Proc. 9-е. Междунар. Конф ., 2005, ISBN 3-540-26546-5 , стр. 313
- ^ Галлиан, Дж. "Динамический обзор разметки графиков, 1996-2005". Электронный журнал комбинаторики. Цитировать журнал требует
|journal=( помощь ) - ^ Роза, Александр (1967). О некоторых оценках вершин графа . Теория графов, Междунар. Symp. Рим, июль 1966 года. Гордон и Брич. С. 349–355. Zbl 0193.53204 .
- ^ Виетри, Андреа (2008). «Плыть к, а затем и против гипотезы изящного дерева: некоторые беспорядочные результаты». Вестник Института комбинаторики и ее приложений . Институт комбинаторики и ее приложений . 53 : 31–46. ISSN 1183-1278 . S2CID 16184248 .
- Перейти ↑ Lo, Sheng-Ping (1985). «О граничных разметках графов». Congressus Numerantium . 50 : 231–241. Zbl 0597.05054 .
- ^ Гай, Ричард К. (2004). Нерешенные проблемы теории чисел (3-е изд.). Springer-Verlag . Задача C13, стр. 190–191. ISBN 0-387-20860-7. Zbl 1058.11001 .
- ^ Галлиан, Джозеф А. (1998). «Динамический обзор разметки графов» . Электронный журнал комбинаторики . 5 : Динамическое исследование 6. MR 1668059 . .
- ^ Chartrand, Гэри ; Иган, Куру; Чжан, Пин (2019). Как пометить график . SpringerBriefs по математике. Springer. С. 3–4. ISBN 9783030168636.
- ^ Czerwiński, Себастьян; Грычук, Ярослав; Желязны, Виктор (2009). «Удачные разметки графиков». Инф. Процесс. Lett . 109 (18): 1078–1081. DOI : 10.1016 / j.ipl.2009.05.011 . Zbl 1197.05125 .
