Маркировка графиков
В математической дисциплине теории графов — маркировка графа присвоение меток, традиционно представленных целыми числами , ребрам и/или вершинам графа это . [1]
для данного графа G = ( V , E ) маркировка вершин является функцией V Формально , для набора меток; Граф с такой определенной функцией называется графом, помеченным вершинами . Аналогично, маркировка ребер является функцией E для набора меток. В этом случае граф называется графом с метками ребер .
Когда метки ребер являются членами упорядоченного набора (например, вещественных чисел ), его можно назвать взвешенным графом .
При использовании без уточнений термин « меченый граф» обычно относится к графу, помеченному вершинами, у которого все метки различны. Такой граф можно эквивалентно пометить последовательными целыми числами { 1, …, | В | } , где | В | — количество вершин в графе. [1] Во многих приложениях ребрам или вершинам присваиваются метки, значимые в связанной области. Например, ребрам могут быть присвоены веса, представляющие «стоимость» прохождения между инцидентными вершинами. [2]
В приведенном выше определении под графом понимается конечный неориентированный простой граф. Однако понятие разметки можно применить ко всем расширениям и обобщениям графов. Например, в теории автоматов и теории формального языка удобно рассматривать помеченные мультиграфы , т. е. пару вершин можно соединить несколькими помеченными ребрами. [3]
История
[ редактировать ]Большинство графических разметок берут свое начало от разметок, представленных Александром Розой в его статье 1967 года. [4] Роза выделил три типа мечений, которые он назвал α- , β- и ρ -мечениями. [5] β переименовал Позднее Соломон Голомб -мечения в «изящные» , и с тех пор это имя стало популярным.
Особые случаи
[ редактировать ]Изящная маркировка
[ редактировать ]
Граф называется изящным, если его вершины помечены от 0 до | Е | , размер графа, и если эта маркировка вершин вызывает маркировку ребер от 1 до | Е | . Для любого ребра e метка e — это положительная разность меток двух вершин, инцидентных e . Другими словами, если e инцидентно вершинам, помеченным i и j , то e будет помечено | я - j | . Таким образом, граф G = ( V , E ) изящный тогда и только тогда, когда существует инъекция из V в {0, ..., | E |} , индуцирующий биекцию из E в {1, ..., | Е |} .
В своей оригинальной статье Роза доказал, что все эйлеровы графы размера, эквивалентного 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] Семистраничный книжный график К 1,7 × К 2 представляет собой пример негармоничного графика. [9]
Раскраска графа
[ редактировать ]Раскраска графа — это подкласс разметки графа. Раскраска вершин присваивает разные метки соседним вершинам, а раскраска ребер присваивает разные метки соседним ребрам. [10]
Удачная маркировка
[ редактировать ]Счастливая разметка графа G — это присвоение целых положительных чисел вершинам графа G такое, что если S ( v ) обозначает сумму меток на соседях графа v , то S — раскраска вершин G. графа «Счастливое число» G — это наименьшее k такое, что G имеет счастливую маркировку целыми числами {1, …, k }. [11]
Ссылки
[ редактировать ]- ^ Jump up to: а б Вайсштейн, Эрик В. «Размеченный граф» . Математический мир .
- ^ Роберт Калдербанк, Различные аспекты теории кодирования , (1995) ISBN 0-8218-0379-4 , с. 53 "
- ^ « Развитие теории языка », Proc. 9-е. Интернат.Конф., 2005, ISBN 3-540-26546-5 , с. 313
- ^ Галлиан, Дж. «Динамический обзор разметки графов, 1996–2023 гг.» . Электронный журнал комбинаторики . дои : 10.37236/27 .
- ^ Роза, Александр (1967). О некоторых оценках вершин графа . Теория графов, Межд. Симп. Рим, июль 1966 года. Гордон и Брич. стр. 349–355. Збл 0193.53204 .
- ^ Виетри, Андреа (2008). «Плывем к гипотезе изящного дерева, а затем против нее: некоторые неоднозначные результаты». Вестник Института комбинаторики и ее приложений . 53 . Институт комбинаторики и ее приложений : 31–46. ISSN 1183-1278 . S2CID 16184248 .
- ^ Ло, Шэн-Пин (1985). «О изящной маркировке графов». Конгресс Нумерантиум . Конференция Сандэнс, Юта. Том. 50. С. 231–241. Збл 0597.05054 .
- ^ Гай, Ричард К. (2004). Нерешенные проблемы теории чисел (3-е изд.). Спрингер-Верлаг . Задача C13, стр. 190–191. ISBN 0-387-20860-7 . Збл 1058.11001 .
- ^ Галлиан, Джозеф А. (1998). «Динамический обзор разметки графов» . Электронный журнал комбинаторики . 5 : Динамическое обследование 6. MR 1668059 . .
- ^ Шартран, Гэри ; Иган, Куру; Чжан, Пин (2019). Как маркировать график . SpringerBriefs по математике. Спрингер. стр. 3–4. ISBN 9783030168636 .
- ^ Червинский, Себастьян; Гричук, Ярослав; Желязны, Виктор (2009). «Удачные разметки графиков». Инф. Процесс. Летт . 109 (18): 1078–1081. дои : 10.1016/j.ipl.2009.05.011 . Збл 1197.05125 .