L (h, k) -ракраска - L(h, k)-coloring
В теория графов, а L (час, k) -маркировка, L (час, k) -раскрашивание или иногда L (п, q) -раскрашивание это (собственная) раскраска вершин в котором каждая пара соседних вершин имеет цветовые номера, различающиеся не менее чем на час, и любые узлы, соединенные путём длиной 2, их цвета отличаются как минимум на k.[1] Параметры, час и k понимаются как неотрицательные целые числа.
Проблема возникла из-за проблемы с назначением каналов в радиосетях. В охватывать L (час, k) -маркировка, ρh, k(G) - разница между наибольшей и наименьшей присвоенной частотой. Цель L (час, k) Проблема маркировки обычно заключается в том, чтобы найти маркировку с минимальным интервалом.[2] Для данного графа минимальным промежутком среди всех возможных функций разметки является λh, k-количество грамм, обозначаемый λh, k(ГРАММ).
Когда час= 1 и k= 0, это обычный (собственная) раскраска вершин.
По L (час, k) -маркировка, с разными час и k параметры и различные классы графиков.
В некоторых вариантах цель - минимизировать количество используемых цветов ( порядок).
Смотрите также
Рекомендации
- ^ Чартран, Гэри; Чжан, Пин (2009). «14. Раскраски, расстояние и доминирование». Теория хроматических графов. CRC Press. С. 397–438.
- ^ Тициана, Каламонери (2006), «Проблема маркировки L (h, k): обзор и аннотированная библиография», Comput. Дж., 49 (5): 585–608, Дои:10.1093 / comjnl / bxl018