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