Разметка графа

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

Формально, если дан граф 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.

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

$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}.