4501
правка
Деревья с ограниченной степенью: различия между версиями
Перейти к навигации
Перейти к поиску
м
Деревья с ограниченной степенью (посмотреть исходный код)
Версия от 14:22, 1 октября 2023
, 1 октября 2023нет описания правки
Irina (обсуждение | вклад) мНет описания правки |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 5: | Строка 5: | ||
Необходимо построить остовное дерево с малой степенью для связного неориентированного графа G = (V, E). В формулировке Штейнера, помимо входного графа G, задано также множество выделенных вершин D С V. Дерево Штейнера – это дерево в G, охватывающей, по меньшей мере, множество D. | Необходимо построить остовное дерево с малой степенью для связного неориентированного графа G = (V, E). В формулировке Штейнера, помимо входного графа G, задано также множество выделенных вершин D С V. Дерево Штейнера – это дерево в G, охватывающей, по меньшей мере, множество D. | ||
Поскольку задача нахождения остова или дерева Штейнера с минимальной возможной степенью A * является NP-полной, любопытны подходы в аппроксимации этой задачи минимизации степени. Для многих подобных комбинаторных задач цель состоит в нахождении аппроксимации за полиномиальное время (с константой или бОльшим множителем). Для задач нахождения остова и дерева Штейнера итеративные аппроксимационные алгоритмы с полиномиальным временем | Поскольку задача нахождения остова или дерева Штейнера с минимальной возможной степенью A * является NP-полной, любопытны подходы в аппроксимации этой задачи минимизации степени. Для многих подобных комбинаторных задач цель состоит в нахождении аппроксимации за полиномиальное время (с константой или бОльшим множителем). Для задач нахождения остова и дерева Штейнера итеративные аппроксимационные алгоритмы с полиномиальным временем выполнения авторства Фюрера и Рагавачари [8] (см. также [14]) находят намного лучшее решение. Степень A дерева решения не превышает A* + 1. | ||
Имеется всего несколько естественных NP-полных задач оптимизации, для которых оптимум может быть найден с точностью до дополнительного члена величины 1. Одной такой задачей является раскраска планарного графа; раскраска в четыре цвета может быть проведена за полиномиальное время. С другой стороны, задача раскраски в три цвета является NP-полной даже для планарных графов. Другой подобной задачей является раскраска дуг графа степени Д. Если раскраска в Д + 1 цветов всегда может быть выполнена за полиномиальное время, задача раскраски в Д цветов является NP-полной. | Имеется всего несколько естественных NP-полных задач оптимизации, для которых оптимум может быть найден с точностью до дополнительного члена величины 1. Одной такой задачей является раскраска планарного графа; раскраска в четыре цвета может быть проведена за полиномиальное время. С другой стороны, задача раскраски в три цвета является NP-полной даже для планарных графов. Другой подобной задачей является раскраска дуг графа степени Д. Если раскраска в Д + 1 цветов всегда может быть выполнена за полиномиальное время, задача раскраски в Д цветов является NP-полной. | ||
| Строка 15: | Строка 15: | ||
== Основные результаты == | == Основные результаты == | ||
Легко показать, что задачи вычисления остовного дерева с минимальной степенью и дерева Штейнера являются NP-полными, поскольку они содержат задачу нахождения гамильтонова пути. Следовательно, не следует ожидать, что алгоритм с полиномиальным временем | Легко показать, что задачи вычисления остовного дерева с минимальной степенью и дерева Штейнера являются NP-полными, поскольку они содержат задачу нахождения гамильтонова пути. Следовательно, не следует ожидать, что алгоритм с полиномиальным временем выполнения сможет найти минимальную возможную степень A*. Из того же рассуждения следует, что аппроксимацию с множителем, меньшим 3/2, невозможно провести за полиномиальное время, если только не верно соотношение P = NP. | ||
Ранние аппроксимационные алгоритмы получали решение степени O(A* log n) [6], где n = j Vj – количество вершин. Оптимальный результат для случая остовного дерева был получен Фюрером и Рагавачари [7, 8]. | Ранние аппроксимационные алгоритмы получали решение степени O(A* log n) [6], где n = j Vj – количество вершин. Оптимальный результат для случая остовного дерева был получен Фюрером и Рагавачари [7, 8]. | ||
Теорема 1. Пусть A* – степень остовного дерева с неизвестной минимальной степенью для входного графа G = (V, E). Существует аппроксимационный алгоритм с полиномиальным временем | Теорема 1. Пусть A* – степень остовного дерева с неизвестной минимальной степенью для входного графа G = (V, E). Существует аппроксимационный алгоритм с полиномиальным временем выполнения для решения задачи вычисления остовного дерева с минимальной степенью, который находит остовное дерево, степень которого не превышает A* + 1. | ||
Впоследствии этот результат был расширен на случай дерева Штейнера [8]. | Впоследствии этот результат был расширен на случай дерева Штейнера [8]. | ||
Теорема 2. Предположим, что в задаче нахождения дерева Штейнера заданы граф G = (V, E) и произвольное подмножество D множества вершин V. Пусть A* – степень остовного дерева с неизвестной минимальной степенью для входного графа G, охватывающего по меньшей мере множество D. Тогда существует аппроксимационный алгоритм с полиномиальным временем | Теорема 2. Предположим, что в задаче нахождения дерева Штейнера заданы граф G = (V, E) и произвольное подмножество D множества вершин V. Пусть A* – степень остовного дерева с неизвестной минимальной степенью для входного графа G, охватывающего по меньшей мере множество D. Тогда существует аппроксимационный алгоритм с полиномиальным временем выполнения для нахождения дерева Штейнера с минимальной степенью, который находит дерево Штейнера, степень которого не превышает A* + 1. | ||
Оба алгоритма выполняются за время O(mn ■ log na(m, n)), где m – число дуг, а a – обратная функция Аккермана. | Оба алгоритма выполняются за время O(mn ■ log na(m, n)), где m – число дуг, а a – обратная функция Аккермана. | ||