4430
правок
Радиораскраска в планарных графах: различия между версиями
Материал из WEGA
Радиораскраска в планарных графах (посмотреть исходный код)
Версия от 14:32, 1 октября 2023
, 1 октября 2023нет описания правки
Irina (обсуждение | вклад) мНет описания правки |
Irina (обсуждение | вклад) мНет описания правки |
||
| (не показана 1 промежуточная версия этого же участника) | |||
| Строка 54: | Строка 54: | ||
• Вначале было показано, что количество цветов, используемое при нахождении ''минимального порядка диапазона'' для радиораскраски графа G, отличается от хроматического числа квадрата этого графа – <math>\chi (G^2) \;</math>. В частности, оно может быть больше <math>\chi (G^2) \;</math>. | • Вначале было показано, что количество цветов, используемое при нахождении ''минимального порядка диапазона'' для радиораскраски графа G, отличается от хроматического числа квадрата этого графа – <math>\chi (G^2) \;</math>. В частности, оно может быть больше <math>\chi (G^2) \;</math>. | ||
• Затем было доказано, что задача радиораскраски для графов общего вида с трудом поддается аппроксимации (за исключением случая NP = ZPP – класса задач с рандомизированными алгоритмами с нулевой ошибкой и полиномиальным временем | • Затем было доказано, что задача радиораскраски для графов общего вида с трудом поддается аппроксимации (за исключением случая NP = ZPP – класса задач с рандомизированными алгоритмами с нулевой ошибкой и полиномиальным временем выполнения) с коэффициентом <math>n^{1/2 - \epsilon} \;</math> (для любого <math>\epsilon > 0 \;</math>), где n – количество вершин графа. Однако при рассмотрении некоторых специальных разновидностей графов задача становится проще. | ||
Было показано, что задачи нахождения минимального диапазона и минимального порядка диапазона для радиораскраски являются NP-полными для планарных графов. Заметим, что некоторые комбинаторные задачи остаются сложными и для планарных графов, притом доказать их сложность также непросто, поскольку при этом необходимо использовать «планарные приспособления», сложные для нахождения и понимания. | Было показано, что задачи нахождения минимального диапазона и минимального порядка диапазона для радиораскраски являются NP-полными для планарных графов. Заметим, что некоторые комбинаторные задачи остаются сложными и для планарных графов, притом доказать их сложность также непросто, поскольку при этом необходимо использовать «планарные приспособления», сложные для нахождения и понимания. | ||
• Был представлен алгоритм с временем | • Был представлен алгоритм с временем выполнения <math>O(n \Delta (G)) \;</math>, ''аппроксимирующий'' минимальный порядок радиораскраски, <math>X_{order} \;</math>, в планарном графе G ''с константным коэффициентом, который стремится к 2'' по мере возрастания максимальной степени <math>\Delta(G) \;</math> графа G. | ||
Представленный алгоритм вдохновлен теоремой Хёвела и Макгиннеса о конструктивной раскраске [9]. Построение из [9], как показано, может привести к получению алгоритма с временем <math>O(n^2) \;</math>, предполагая, что планарное вложение графа G задано. В [5, 6] временная сложность аппроксимационного алгоритма была улучшена, также был представлен намного более простой алгоритм для проверки и внедрения, не требующий на входе планарного вложения. | Представленный алгоритм вдохновлен теоремой Хёвела и Макгиннеса о конструктивной раскраске [9]. Построение из [9], как показано, может привести к получению алгоритма с временем <math>O(n^2) \;</math>, предполагая, что планарное вложение графа G задано. В [5, 6] временная сложность аппроксимационного алгоритма была улучшена, также был представлен намного более простой алгоритм для проверки и внедрения, не требующий на входе планарного вложения. | ||
• Наконец, была рассмотрена задача ''оценки количества различных радиораскрасок'' планарного графа G. Это NP-полная задача (что можно легко заметить в связи с представленным в данных работах способом редукции полноты, которая может быть выполнена консервативным образом). Авторы применяют здесь стандартную технику, сочетая цепи Маркова и новый способ формирования пар, чтобы получить доказательство ''быстрой сходимости'' (см., например, [10]) и представляют ''полностью полиномиальную рандомизированную схему | • Наконец, была рассмотрена задача ''оценки количества различных радиораскрасок'' планарного графа G. Это NP-полная задача (что можно легко заметить в связи с представленным в данных работах способом редукции полноты, которая может быть выполнена консервативным образом). Авторы применяют здесь стандартную технику, сочетая цепи Маркова и новый способ формирования пар, чтобы получить доказательство ''быстрой сходимости'' (см., например, [10]) и представляют ''полностью полиномиальную рандомизированную аппроксимационную схему'' для оценки количества радиораскрасок с <math>\lambda \;</math> цветами для планарного графа G, когда <math>\lambda \ge 4 \Delta (G) + 50 \;</math>. | ||
