Разметка графа в математике — это назначение меток, которые традиционно представляются целыми числами , рёбрами , вершинами , или рёбрам, и вершинам графа .

Формально, если дан граф G = ( V , E ) , вершинная разметка является функцией из множества вершин V в множество меток . Граф с такой функцией называется графом с разметкой вершин . Аналогично, разметка рёбер является функцией из множества рёбер E в множество меток. В этом случае граф называется графом с разметкой рёбер .

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

Если не указано явно, термин разметка графа обычно означает вершинную разметку, при которой все метки различны. Такой граф эквивалентно можно разметить последовательными целыми числами {1, …, | V |}, где | V | — число вершин графа . Для многих приложений рёбрам или вершинам даются метки, имеющие смысл в соответствующей области. Например, рёбрам могут быть назначены веса , представляющие собой «цену» проезда между двумя смежными вершинами .

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

История

Большинство разметок графов имеют истоком разметки, представленные Алексом Роза в его статье 1967 года . Роза выделил три типа разметки, которые он назвал α-, β- и ρ-разметками . β-разметку позднее С. В. Голомб переименовал в грациозную и это имя стало популярным.

Специальные случаи

Грациозная разметка

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

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

Рёберная грациозная разметка

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

Рёберную грациозную разметку первым ввёл С. Ло в 1985 .

Необходимым условием существования для графа рёберной грациозной разметки является условие Ло :

${\displaystyle q(q+1)=p/(p-1)2\mod p.}$

Гармоничная разметка

Гармоничная разметка графа G — это вложение множества вершин графа G в группу целых чисел сравнения по модулю k , где k — число рёбер графа G , которое порождает биекцию между рёбрами графа G и числами по модулю k путём выбора в качестве метки ребра ( x , y ) суммы меток двух вершин x , y (mod k ). Гармоничный граф — это граф, имеющий гармоничную разметку. Нечётные циклы являются гармоничными графами, как и граф Петерсена . Есть гипотеза, что все деревья являются гармоничными графами, если позволить одну вершину использовать повторно . Книга с семью страницами K _1,7 × K ₂ даёт пример негармоничного графа .

Раскраска графов

Раскраска графа является подклассом разметки графа. Вершинная раскраска назначает различные метки смежным вершинам, рёберная раскраска назначает различные метки смежным рёбрам.

Счастливая разметка

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

Примечания

Литература