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

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

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

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

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

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

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

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

• в
• т
• е