Drzewo rozpinające z ograniczeniami stopni

W teorii grafów drzewo rozpinające o ograniczonym stopniu jest drzewem rozpinającym , w którym maksymalny stopień wierzchołka jest ograniczony do pewnej stałej k . Problem drzewa rozpinającego z ograniczeniami stopni polega na określeniu, czy dany graf ma takie drzewo rozpinające dla określonego k .

Definicja formalna

Wejście: n -węzłowy graf nieskierowany G(V,E); dodatnia liczba całkowita k < n .

Pytanie: Czy G ma drzewo rozpinające, w którym żaden węzeł nie ma stopnia większego niż k ?

NP-zupełność

Ten problem jest NP-zupełny ( Garey i Johnson 1979 ). Można to wykazać przez redukcję z problemu ścieżki Hamiltona . Pozostaje NP-zupełne, nawet jeśli k jest ustalone na wartość ≥ 2. Jeśli problem jest zdefiniowany jako stopień musi być ≤ k , przypadek k = 2 drzewa rozpinającego o ograniczonym stopniu jest problemem ścieżki Hamiltona.

Minimalne drzewo rozpinające o ograniczonym stopniu

Na grafie ważonym minimalne drzewo rozpinające z ograniczeniami stopni (DCMST) to drzewo rozpinające z ograniczeniami stopni, w którym suma jego krawędzi ma minimalną możliwą sumę. Znalezienie DCMST jest problemem NP-trudnym.

Zaproponowano algorytmy heurystyczne, które mogą rozwiązać problem w czasie wielomianowym, w tym algorytmy genetyczne i oparte na mrówkach.

Algorytm aproksymacji

Fürer i Raghavachari (1994) podają iteracyjny algorytm czasu wielomianowego, który na podstawie wykresu $Δ$ drzewo rozpinające o maksymalnym stopniu nie większym niż $\ Displaystyle \ Delta ^ {*} + 1}$ , gdzie $jest$ minimalnym możliwym maksymalnym stopniem na wszystkich drzewach Tak więc, jeśli $k$ $+ 1}$ albo zwróci drzewo opinające o maksymalnym stopniu, $k$ .

Garey, Michael R .; Johnson, David S. (1979), Komputery i nieustępliwość: przewodnik po teorii NP-kompletności , WH Freeman, ISBN 978-0-7167-1045-5 . A2.1: ND1, s. 206. {{ cytat }} : CS1 maint: post scriptum ( link )
Furer, Martin; Raghavachari, Balaji (1994), „Zbliżanie drzewa Steinera o minimalnym stopniu do jednego z optymalnych”, Journal of Algorithms , 17 (3): 409–423, CiteSeerX 10.1.1.136.1089 , doi : 10.1006/jagm.1994.1042 .