Доминантни скуп — разлика између измена
Садржај обрисан Садржај додат
Нема описа измене |
Нема описа измене |
||
Ред 45:
Следећи пар редукција ( Кан 1992, стр 108-109) показује да су проблем минимума доминантног скупа и проблем скупа покривача еквивалентни у Л-редукцији: уколико дамо инстанцу једног проблема, можемо изградити еквивалентну инстанцу другог проблема.
'''Од доминантог скупа до скупа покривања.''' Дат је граф ''G = (V, Е)'' са ''V'' = {1, 2, ..., ''n''}, који гради инстанцу скупа покривања (''S, U'') на следећи начин: универзум ''U'' је ''V'', и породица подскупа је ‘’S'' = {''S''<sub>1</sub>, ''S''<sub>2</sub>, ..., ''S''<sub>''n''</sub>} тако да се ''S''<sub>v</sub> састоји од чвора ''v'' и свих чворова придруженим ''v'' у ''G''.
Сада, ако је ''D'' доминантан скуп за ''G'', онда ''C'' = { ''S''<sub>''v''</sub>: ''v'' ∈ ''D''} је изводљиво решење проблема скупа покривача, са |’’C’’| = |''D''|. С друге стране, ако је ''C'' = {''S''<sub>''v''</sub>: ''v'' ∈ ''D''} изводљиво решење проблема скупа покривача, онда је ''D'' доминантан скуп за ''G'', са |''D''| = |''C''|.
Отуда je величинa минимума доминантог скупа за ‘’G’’ једнакa величини минимума скупа покривача за (‘’S, U''). Осим тога, постоји једноставан алгоритам који води од доминантаног скупа до скупа прекривача исте величине и обрнуто. Конкретно, ефикасан α-апроксимиран алгоритам за покривање обезбеђује ефикасна алгоритам α-апроксимације за минимуме доминантних скупова
[[File:Dominating-set-2.svg|right]]
::На пример, дат је граф ''G'' приказан на десној страни, ми конструишемо инстанцу скупа покривача са универзумом ''U'' = {1, 2, ..., 6} и подгрупе ''S''<sub>1</sub> = {1, 2, 5}, ''S''<sub>2</sub> = { 1, 2, 3, 5}, ''S''<sub>3</sub> = {2, 3, 4, 6}, ''S''<sub>4</sub> = {3, 4}, ''S''<sub>5</sub> = {1, 2, 5, 6}, и ''S''<sub>6</sub> = {3, 5, 6 }. У овом примеру, ''D'' = {3, 5} је доминантан скуп за ''G'' - то одговара скупу прекривача ''C'' = { ''S''<sub>3</sub>, ''S''<sub>5</sub> }. На пример, чвор 3 ∈ ''D'' доминира чвором 4 ∈ ''V'', и елемент 4 ∈ ''U'' је садржан у скупу ''S''<sub>3</sub> ∈ ''C''.
| |||