Штајнерово дрво

Проблем Штајнеровог стабла, или најмањег Штајнеровог стабла, названог по Јакобу Штајнеру, је проблем из комбинаторике и оптимизације, који се може формулисати на више начина, којима је заједничко да се тражи најкраћа веза између датих објеката.

Проблем Штајнеровог дрвета сличан је проблему најмањег разапињућег стабла проблем: дати сет V тачака (чворова) треба повезати (направити Граф) најмање дужине, где је дужина збир дужина свих ивица. Разлика између Штајнеровог дрвета и најмањег разапињућег дрвета је у томе што се у Штајнерово дрво могу убацити додатни(помоћни) чворови и ивице како би се смањила дужина разапињуцег стабла. Овакви чворови, који се додају зарад смањивања укупне дужине стабла зову се Штајнерове тачке или Штајнерови чворови. Доказано је да се овим поступком долази до стабла, познатог као Штајнерово стабло. За задати сет тачака може постојати више Штајнерових стабала.

Већина верзија проблема Штајнеровог дрвета је НП комплетна.Чак се једна верзија налази медју Карпових 21 НП-комплетих проблема. Неке упрошћене верзије могу се решити у полиномијалном времену.

Еуклидско Штајнерово дрво[уреди | уреди извор]

Оригинални проблем је био формулисан онако како сада формулисемо Проблем Еуклидског Штајнеровог стабла или геометријског Штајнеровог стабла: за Н тачака равни, циљ је повезати их тако да су сваке две повезане или директно или преко других тачака.

Може се доказати да се тако добијене ивице не секу сем у чворовима, и да је резултат стабло.

За проблем еуклидског Штајнеровог стабла, чворови који се додају графу (Штајнерови чворови) морају имати степен 3, и суседне ивице које полазе из тог чвора морају медјусобно заклапати углове од 120 степени. Следи да је максималан број Штајнерових чворова Н − 2, где је Н број на почетку задатих чворова.

За Н = 3 постоје два могућа случаја:ако су углови троугла који формирају задате тачке мањи од 120 степени, Штајнерова тачка се поклапа са Торичелијевом тачком тог троугла; у супротном ивице графа су странице трогла које заклапају угао већи од 120 степени.

За опште Н, проблем Еуклидског Штајнеровог стабла је НП тежак проблем, и зато се не зна да ли се да ли се оптимално ресење може наци у полиномијалном времену. Додуше у полиномијалном времену се може наћи апроксимација оптималног ресења(приближно оптимално речење).^[1]

Праволинијско Штајнерово стабло[уреди | уреди извор]

Овај проблем је варијанта Еуклидског поблема само сто су еуклидске раздаљине замењене такозваним праволинијским растојањем(збир апсоутних разлика x и y координата тачака).

Уопштење најмањег Штајнеровог стабла[уреди | уреди извор]

Штајнерова стабла се такоже изучавају у области тежинских графова(драфова чије гране имају тежину ). У општем проблему Штајнеровог стабла yадат нам је тежински граф Г = (V, Е, w) и подскуп чворова С ⊆ V. Штајнерово стабло је стабло уГкоје садржи све чворове из С. Постоје две верзије прблема:у првој (проблему оптимизацје), циљ је пронаћи Штајнерово стабло са најмањом тежином; у другом (проблему одлучивања), за задату вредност ктреба да проверимо да ли постоји Штајнерово стабло са тежином не већом од к еxистс. Проблем одлучивања је био један од Карпових 21 НП-комплетих проблема.

Специјалан случај проблема је када је Г комплетан граф и тежине ивица задовољавају неједнакост троугла.Ова верзија је позната као метричка варијанта проблема Штајнеровог стабла. За задати пример (неметричког) Штајнеровог стабла можемо наћи еквивалентан пример метричког Штајнеровог стабла, у полиномијалном времену, трансформација чува фактор апрофсимације.^[2]

Проблем Штајнеровог стабла јр такоже изучаван у другим димензијама и на различитим поврчинама. Алгоритми за проналажење најмањег Штајнеровог стабла пронаћени су и за сферу, пројективну раван, конус и друге.^[3]

Друга уопштења проблема су она где се тражи граф који остаје повезан када се из њега уклони не више било којизан када се уклони не висе од к било којих чворова, за неко к.(к-едге-цоннецтед грапх и к-вертеx-цоннецтед грапх)

Апроксимација Штајнеровог стабла[уреди | уреди извор]

У општем графу Штајнеровог стабла, минимално разапињуће стабло индуковоно скупом граничних тачака $R$ затварања $G_{m}$ оф $G$ . Ово стабло је остварљиво али не обавезно оптимално решење проблема Штајнеровог стабла. Метричко затварање $G_{m}$ може бити замењено са $G$ без умањења општости, и описује се тако што се измедју свака два чвора у убацује ивица тежине једнаке тежини најкраћег пута измедју њих. Оваквих ивица има $|V|*(|V|-1)/2=O(|V|^{2})$ , па се њихове дужине могу наћи у полиномијалном времену применом Дјикстриног алгоритма. Тривијално се доказује да је оптимално решење на $Opt_{G}$ оптимално и на $G$ .

Минимално стабло је разапињуће стабло на потпуном подграфу метричког затварања које садржи само граничне тачке и ивице које их спајају. Овакво стабло је $2-2/|R|$ апроксимација где је $|R|$ број граничних тачака.

Штајнеров количник[уреди | уреди извор]

Штајнеров количник је супремум количника укупне дужине минималног Штајнеровог стабла и минималног разапињућег стабла за задат сет тачака у Еуклидској равни.^[4]

У Еуклидском проблему Штајнеровог стабла, за Штајнеров количник се само претпоставља да износи ${\frac {2}{\sqrt {3}}}$ . Упркос ранијим тврдњама о доказу, питање је још отворено,^[5]^[6] У праволинијском Штајнеровом стаблу , количник износи ${\frac {3}{2}}$ .

Референце[уреди | уреди извор]

^ Цресцензи, Пиерлуиги; Канн, Вигго; Халлдóрссон, Магнúс; Карпински, Марек; Wоегингер, Герхард (2000). „А Цомпендиум оф НП Оптимизатион Проблемс”
^ Вазирани 2003, стр. 27–28
^ Ду, Дингзху; Хwанг, Франк (1995). Цомпутинг ин Еуцлидеан геометрy. Лецтуре Нотес оф Цомпутинг. 4 (2нд изд.). Ривер Едге, Њ: Wорлд Сциентифиц Публисхинг Цо. стр. 361. ИСБН 978-981-02-1876-8.
^ Ганлеy, Јосепх L. (2004). „Стеинер ратио”. Ур.: Блацк, Паул Е. Дицтионарy оф Алгоритхмс анд Дата Струцтурес. У.С. Натионал Институте оф Стандардс анд Тецхнологy. Приступљено 24. 5. 2012
^ Тхе Неw Yорк Тимес, Оцт 30, 1990, репортед тхат а прооф хад беен фоунд, анд тхат Роналд Грахам, wхо хад офферед $500 фор а прооф, wас абоут то маил а цхецк то тхе аутхорс.
^ Иванов, А. О.; А. А. Тузхилин (2012). „Тхе Стеинер Ратио Гилберт–Поллак Цоњецтуре Ис Стилл Опен: Цларифицатион Статемент”. Алгоритхмица. 62 (1-2): 630—632. дои:10.1007/с00453-011-9508-3. Приступљено 1. 3. 2012. ^{[мртва веза]}

Референце[уреди | уреди извор]

Извори[уреди | уреди извор]

Гареy, Мицхаел Р.; Јохнсон, Давид С. (1979), Цомпутерс анд Интрацтабилитy: А Гуиде то тхе Тхеорy оф НП-Цомплетенесс, W. Х. Фрееман, ИСБН 0-7167-1045-5 . стр. 208–209, проблемс НД12 анд НД13.
Ф. К. Хwанг; D. С. Рицхардс; П. Wинтер (1992). Тхе Стеинер Трее Проблем. Анналс оф Дисцрете Матхематицс. 53. Нортх-Холланд: Елсевиер. ИСБН 978-0-444-89098-6.
А. О. Иванов; А. А. Тузхилин (1994). Минимал Нетwоркс: Тхе Стеинер Проблем анд Итс Генерализатионс. Н.W., Боца Ратон, Флорида: ЦРЦ Пресс. ИСБН 978-0-8493-8642-8.
А. О. Иванов; А. А. Тузхилин (2000). Бранцхинг солутионс то оне-дименсионал вариатионал проблемс. Сингапоре-Неw Јерсеy-Лондон-Хонг Конг: Wорлд Сциентифиц. ИСБН 978-981-02-4060-8.
А. О. Иванов; А. А. Тузхилин (2003). Еxтреме Нетwоркс Тхеорy (на језику: руски). Мосцоw-Изхевск: Институте оф Цомпутер Инвестигатионс. ИСБН 978-5-93972-292-6.
Корте, Бернхард; Вyген, Јенс (2006). „Сецтион 20.1”. Цомбинаториал Оптимизатион: Тхеорy анд Алгоритхмс (3рд изд.). Спрингер. ИСБН 978-3-540-25684-7.
Вазирани, Вијаy V. (2003). Аппроxиматион Алгоритхмс. Берлин: Спрингер. ИСБН 978-3-540-65367-7.
Берман, Пиотр; Карпински, Марек; Зеликовскy, Алеxандер (2009). „1.25-Аппроxиматион Алгоритхм фор Стеинер Трее Проблем wитх Дистанцес 1 анд 2”. Лецтуре Нотес ин Цомпутер Сциенце. 5664: 86—97. дои:10.1007/978-3-642-03367-4_8.
Wу, Банг Yе; Цхао, Кун-Мао (2004). „Цхаптер 7”. Спаннинг Треес анд Оптимизатион Проблемс. Цхапман & Халл/ЦРЦ. ИСБН 978-1-58488-436-1.
Берн, Марсхалл W.; Грахам, Роналд L. (1989). „Тхе Схортест-Нетwорк Проблем”. Сциентифиц Америцан. 260 (1): 84—89. дои:10.1038/сциентифицамерицан0189-84.
Циеслик, Диетмар (1998). Стеинер Минимал Треес. стр. 319. ИСБН 978-0-7923-4983-9.

Спољашње везе[уреди | уреди извор]

Хазеwинкел, M. (2001). „Стеинер трее проблем”. Ур.: Хазеwинкел Мицхиел. Енцyцлопаедиа оф Матхематицс. Спрингер. ISBN 978-1556080104.
M. Hauptmann, M. Karpinski (2013): A Compendium on Steiner Tree Problems
GeoSteiner (Steiner tree solver, Source available, for non commercial use)
http://www.archive.org/details/RonaldLG1988 (Мовие: Роналд L Грахам: Тхе Схортест Нетwорк Проблем (1988)
Фортран суброутине фор финдинг тхе Стеинер вертеx оф а триангле (и.е., Фермат поинт), итс дистанцес фром тхе триангле вертицес, анд тхе релативе вертеx wеигхтс.
Пхyломурка (Солвер фор тхе Стеинер трее проблем ин нетwоркс)

[1] Цресцензи, Пиерлуиги; Канн, Вигго; Халлдóрссон, Магнúс; Карпински, Марек; Wоегингер, Герхард (2000). „А Цомпендиум оф НП Оптимизатион Проблемс”

[2] Вазирани 2003, стр. 27–28

[3] Ду, Дингзху; Хwанг, Франк (1995). Цомпутинг ин Еуцлидеан геометрy. Лецтуре Нотес оф Цомпутинг. 4 (2нд изд.). Ривер Едге, Њ: Wорлд Сциентифиц Публисхинг Цо. стр. 361. ИСБН 978-981-02-1876-8.

[4] Ганлеy, Јосепх L. (2004). „Стеинер ратио”. Ур.: Блацк, Паул Е. Дицтионарy оф Алгоритхмс анд Дата Струцтурес. У.С. Натионал Институте оф Стандардс анд Тецхнологy. Приступљено 24. 5. 2012

[5] Тхе Неw Yорк Тимес, Оцт 30, 1990, репортед тхат а прооф хад беен фоунд, анд тхат Роналд Грахам, wхо хад офферед $500 фор а прооф, wас абоут то маил а цхецк то тхе аутхорс.

[6] Иванов, А. О.; А. А. Тузхилин (2012). „Тхе Стеинер Ратио Гилберт–Поллак Цоњецтуре Ис Стилл Опен: Цларифицатион Статемент”. Алгоритхмица. 62 (1-2): 630—632. дои:10.1007/с00453-011-9508-3. Приступљено 1. 3. 2012. ^{[мртва веза]}

[1]

[2]

[3]

[4]

[5]

[6]