Гамильтонова раскраска - Hamiltonian coloring

Гамильтонова раскраска, названный в честь Уильям Роуэн Гамильтон, это тип раскраска графика. Гамильтонова раскраска использует понятие объездного расстояния между двумя вершины графа.[1] Он имеет множество приложений в различных областях науки и техники.

Терминологии

Раскраска радио

Граф G диаметра D с n узлами, раскрашенный (т.е. имеющий положительное целое число, присвоенное каждой вершине) в k цветов, называется радио k-раскраской G, если для каждой пары вершин a и b сумма расстояний между их, а разница между их метками («цветами») больше k. Например, два узла с метками 3 и 7 на расстоянии 5 приемлемы для окраски радиостанции 8, но не для окраски радиостанции 9, поскольку , что не больше 9.

Антиподальная окраска

Радио (d-1) -раскраска, то есть где k на единицу меньше диаметра графа, известна как антиподальная раскраска, потому что противоположные вершины могут быть окрашены одинаково, но все узлы между ними должны быть разными.

Расстояние объезда

Объездное расстояние между u и v в C5 это 4

Расстояние между двумя вершинами в графе определяется как минимум длины пути соединяя эти вершины. В объездное расстояние между двумя вершинами, скажем, u и v определяется как длина самого длинного пути u-v в графе.[1] В случае дерева обходное расстояние между любыми двумя вершинами такое же, как расстояние между двумя вершинами.

Гамильтонова раскраска

Гамильтоновы раскраски - это разновидность антиподальных раскрасок, где вместо учета регулярного расстояния между узлами рассматривается обходное расстояние. В частности, узлы гамильтоновой раскраски обладают тем свойством, что обходное расстояние плюс разница в цветах больше или равно на единицу меньше n, количества узлов в графе. Если граф G является путем, то любая гамильтонова раскраска также является антиподальной раскраской, что послужило вдохновением для определения гамильтоновой раскраски.

Рекомендации

  1. ^ а б Чартран, Гэри; Чжан, Пин (2009). «14. Раскраски, расстояние и доминирование». Теория хроматических графов. CRC Press. С. 397–438.
  • Chartrand, Gary et al. «Гамильтонова раскраска графов». Дискретная прикладная математика, т. 146, нет. 3, 15 марта 2005 г., Дои:10.1016 / j.dam.2004.08.007.