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