Разметка графиков - Graph labeling

в математический дисциплина теория графов, а маркировка графиков присвоение ярлыков, традиционно представленных целые числа, чтобы края и / или вершины из график.[1]

Формально, учитывая график , а разметка вершин является функцией к набору этикеток; граф с такой определенной функцией называется помеченный вершинами граф. Точно так же маркировка краев является функцией к набору этикеток. В этом случае граф называется помеченный ребрами граф.

Когда метки кромок являются элементами заказал набор (например, действительные числа ), его можно назвать взвешенный график.

При использовании без уточнения термин помеченный график обычно относится к графу с метками вершин, все метки которого различны. Такой граф может быть эквивалентно помечен последовательными целыми числами , где - количество вершин в графе.[1] Для многих приложений ребрам или вершинам присваиваются метки, значимые в соответствующей области. Например, ребрам можно присвоить веса представляющая «стоимость» перехода между инцидентными вершинами.[2]

В приведенном выше определении граф понимается как конечный неориентированный простой граф. Однако понятие разметки можно применять ко всем расширениям и обобщениям графов. Например, в теория автоматов и формальный язык теорию удобно рассматривать помеченную мультиграфы, т.е. пара вершин может быть соединена несколькими помеченными ребрами.[3]

История

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

Особые случаи

Изящная маркировка

Основная статья: Изящная маркировка
Изящная маркировка; метки вершин - черные, а метки краев - красные

Граф называется изящным, если его вершины помечены от 0 до |E|, размер графа, и эта разметка индуцирует разметку ребер от 1 до |E|, Для любого края е, этикетка е положительная разница между двумя вершинами, инцидентными е. Другими словами, если е инцидентно вершинам, помеченным я и j, е будет помечен |я − j|, Таким образом, график г = (V, E) изящно тогда и только тогда, когда существует инъекция, которая индуцирует биекцию из E с целыми положительными числами до |E|.

В своей оригинальной статье Роза доказал, что все Эйлеровы графы с размером эквивалент до 1 или 2 (мод 4) не изящны. Являются ли определенные семейства графов изящными или нет - это область теории графов, которая активно изучается. Возможно, самая крупная недоказанная гипотеза о разметке графов - это гипотеза Рингеля – Котцига, которая предполагает, что все деревья изящны. Это доказано для всех пути, гусеницы, и многие другие бесконечные семейства деревьев. Антон Коциг сам назвал попытку доказать эту гипотезу «болезнью».[6]

Изящная маркировка

Основная статья: Изящная маркировка

Разметка с изящными ребрами на простом графе без петель или кратных ребер на п вершины и q ребра - это разметка ребер различными целыми числами в {1, …, q} такая, что разметка вершин, индуцированная разметкой вершины суммой инцидентных ребер, взятой по модулю п присваивает все значения от 0 до п − 1 к вершинам. График г называется "изящным по краям", если он допускает разметку по краям.

Этикетки с изящными краями были впервые представлены Sheng-Ping Lo в 1985 году.[7]

Необходимым условием для градации ребер является «условие Ло»:

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

«Гармоничная разметка» на графике г инъекция из вершин г к группа целых чисел по модулю k, где k количество ребер г, что индуцирует биекция между краями г и числа по модулю k взяв метку края за край (Икс, у) быть суммой меток двух вершин Икс, у (мод k). «Гармоничный график» - это тот, который имеет гармоничную маркировку. Нечетные циклы гармоничны, как и Графики Петерсена. Предполагается, что все деревья будут гармоничными, если разрешено повторно использовать одну метку вершины.[8]Семистраничный книжный график K1,7 × K2 представляет собой пример графика, который не является гармоничным.[9]

Раскраска графика

Основная статья: Раскраска графика

Раскраска графов - это подкласс пометок графов. Раскраски вершин присваивают разные метки смежным вершинам, а цвета ребер присваивают разные метки смежным ребрам.[нужна цитата ]

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

Удачная маркировка графа г является присвоением положительных целых чисел вершинам г так что если S(v) обозначает сумму меток на соседях v, тогда S раскраска вершин г. «Счастливое число» г наименее k такой, что г имеет удачную маркировку с целыми числами {1, …, k}.[10]

использованная литература

  1. ^ а б Вайсштейн, Эрик В. «Маркированный график». MathWorld.
  2. ^ Роберт Колдербанк, Различные аспекты теории кодирования, (1995) ISBN  0-8218-0379-4, п. 53 "
  3. ^ "Развитие теории языка ", Материалы 9-й Международной конф., 2005 г., ISBN  3-540-26546-5, п. 313
  4. ^ Галлиан Дж. "Динамический обзор разметки графиков, 1996-2005". Электронный журнал комбинаторики. Цитировать журнал требует | журнал = (Помогите)
  5. ^ Роза, Александр (1967). О некоторых оценках вершин графа. Теория графов, Междунар. Symp. Рим, июль 1966 года. Гордон и Брич. С. 349–355. Zbl  0193.53204.
  6. ^ Виетри, Андреа (2008). «Плыть к, а затем и против гипотезы изящного дерева: некоторые беспорядочные результаты». Вестник Института комбинаторики и ее приложений. Институт комбинаторики и ее приложений. 53: 31–46. ISSN  1183-1278. S2CID  16184248.
  7. ^ Ло, Шэн-Пин (1985). «О граничных разметках графов». Congressus Numerantium. 50: 231–241. Zbl  0597.05054.
  8. ^ Парень (2004), стр.190–191
  9. ^ Галлиан, Джозеф А. (1998), «Динамический обзор разметки графиков», Электронный журнал комбинаторики, 5: Динамический обзор 6, Г-Н  1668059.
  10. ^ Червиньски, Себастьян; Грычук, Ярослав; Желязны, Виктор (2009). «Удачные разметки графиков». Инф. Обработать. Латыш. 109 (18): 1078–1081. Дои:10.1016 / j.ipl.2009.05.011. Zbl  1197.05125.