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

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

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

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

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

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

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

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

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

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

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

Ссылки

^ Перейти обратно: ^а ^б Шартран, Гэри ; Чжан, Пин (2009). «14. Раскраски, дистанция и доминирование». Теория хроматических графов . ЦРК Пресс. стр. 397–438.

Чартран, Гэри и др. «Гамильтонова раскраска графов». Дискретная прикладная математика, вып. 146, нет. 3, 15 марта 2005 г., два : 10.1016/j.dam.2004.08.007 .

Эта теории графов статья, посвященная , незавершена . Вы можете помочь Википедии, расширив ее .

[e01-1] Перейти обратно: ^а ^б Шартран, Гэри ; Чжан, Пин (2009). «14. Раскраски, дистанция и доминирование». Теория хроматических графов . ЦРК Пресс. стр. 397–438.

[1]