4501
правка
Деревья с ограниченной степенью: различия между версиями
Перейти к навигации
Перейти к поиску
м
Деревья с ограниченной степенью (посмотреть исходный код)
Версия от 13:16, 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-полной. | ||
| Строка 16: | Строка 16: | ||
== Основные результаты == | == Основные результаты == | ||
Легко показать, что задачи вычисления остовного дерева с минимальной степенью и дерева Штейнера являются NP-полными, поскольку они содержат задачу нахождения гамильтонова пути. Следовательно, не следует ожидать, что алгоритм с полиномиальным временем исполнения сможет найти минимальную возможную степень A*. Из того же рассуждения следует, что аппроксимацию с множителем, меньшим 3/2, невозможно провести за полиномиальное время, если только не верно соотношение P = NP. | Легко показать, что задачи вычисления остовного дерева с минимальной степенью и дерева Штейнера являются NP-полными, поскольку они содержат задачу нахождения гамильтонова пути. Следовательно, не следует ожидать, что алгоритм с полиномиальным временем исполнения сможет найти минимальную возможную степень A*. Из того же рассуждения следует, что аппроксимацию с множителем, меньшим 3/2, невозможно провести за полиномиальное время, если только не верно соотношение P = NP. | ||
Ранние алгоритмы | Ранние аппроксимационные алгоритмы получали решение степени 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 – обратная функция Аккермана. | ||
| Строка 29: | Строка 29: | ||
Прямое применение эти алгоритмы находят в сетях для некритической широковещательной передачи, где может возникнуть необходимость ограничить величину нагрузки на каждый узел, а также в проектировании единых энергосистем, в которых стоимость разделения растет вместе со степенью. Еще одним серьезным преимуществом сети с малыми степенями является ограничение эффекта отказа узла. | Прямое применение эти алгоритмы находят в сетях для некритической широковещательной передачи, где может возникнуть необходимость ограничить величину нагрузки на каждый узел, а также в проектировании единых энергосистем, в которых стоимость разделения растет вместе со степенью. Еще одним серьезным преимуществом сети с малыми степенями является ограничение эффекта отказа узла. | ||
Кроме того, основные результаты аппроксимации вычисления остовного дерева с минимальной степенью и дерева Штейнера легли в основу алгоритмов | Кроме того, основные результаты аппроксимации вычисления остовного дерева с минимальной степенью и дерева Штейнера легли в основу аппроксимационных алгоритмов различных задач проектирования сетей, в том числе включающих дополнительные параметры. | ||
Клейн, Кришнан, Рагавачари и Рави [11] сумели найти двусвязные подграфы с приближенной минимальной степенью в двусвязных графах, а также остовные деревья с приближенной минимальной степенью (ветвления) в ориентированных графах. Эти алгоритмы выполняются за квазиполиномиальное время и аппроксимируют степень A* с приближением (1 + e)A* + O(log1+e n). | Клейн, Кришнан, Рагавачари и Рави [11] сумели найти двусвязные подграфы с приближенной минимальной степенью в двусвязных графах, а также остовные деревья с приближенной минимальной степенью (ветвления) в ориентированных графах. Эти алгоритмы выполняются за квазиполиномиальное время и аппроксимируют степень A* с приближением (1 + e)A* + O(log1+e n). | ||
| Строка 38: | Строка 38: | ||
В последнее время некоторые результаты были значительно улучшены. Пусть w – минимальная стоимость некоторого остовного дерева с заданной степенью B*. Алгоритм Геманса [9] дает остовное дерево со стоимостью w и степенью B* + 2. Сингху и Лау [16] удалось понизить степень до B* + 1, сохранив индивидуальные границы степени A * для каждой вершины v таким же образом. | В последнее время некоторые результаты были значительно улучшены. Пусть w – минимальная стоимость некоторого остовного дерева с заданной степенью B*. Алгоритм Геманса [9] дает остовное дерево со стоимостью w и степенью B* + 2. Сингху и Лау [16] удалось понизить степень до B* + 1, сохранив индивидуальные границы степени A * для каждой вершины v таким же образом. | ||
Известны также любопытные алгоритмы | Известны также любопытные аппроксимационные алгоритмы для задачи вычисления двумерного Евклидова остовного дерева с минимальным весом и ограниченной степенью, в котором вершины представляют собой точки на плоскости, а веса дуг – евклидовы расстояния между ними. Хуллер, Рагавачари и Янг [10] предложили аппроксимации с коэффициентами 1,5 и 1,25 для границ степени 3 и 4, соответственно. Эти границы впоследствии были слегка улучшены Чаном [1]. Чуть более слабые результаты получили Фекете и коллеги [4], используя потоковые методы для более общего случая, в котором весовая функция всего лишь удовлетворяет неравенству треугольника. | ||
== Открытые вопросы == | == Открытые вопросы == | ||