Доминантни скуп — разлика између измена
Садржај обрисан Садржај додат
Нема описа измене |
Нема описа измене |
||
Ред 52:
[[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''.
'''Од скупа покривања до доминантог скупа''' .Нека (''S, U'') буде инстанца проблема скупа покривача са универзумом ''U'' и породицом подскупа ''S'' = { ''S''<sub>''i''</sub>: ''i'' ∈ ''I''}; претпостављамо да су ''U'' и индекс ‘’I’’ раздвојени. Изградити граф ''G = (V, Е)'' на следећи начин: скуп чворова је ''V'' = ''I ∪ U'', ту је грана {''i, ј''} ∈ ''E'' између сваког чвора ''i, j'' ∈ ''I'', а ту је грана {''i, u''} за свако ''i'' ∈ ''I'' и ''u'' ∈ ''S''<sub>''i''</sub>. То је, ''G'' је [[подељен граф]]: ‘’I’’ је [[клика]], а ''U'' је [[независан скуп]].
Сада, ако је ''C'' = {''S''<sub>''i''</sub>:''i'' ∈ ''D''} изводљиво решење проблема скупа чворова за неки подскуп ''D'' ⊆ ''I'', онда је ''D'' доминанатан скуп за ''G'', са |''D''| = |''C''|: Прво, за сваку ''u'' ∈ ''U'' постоји ''i'' ∈ ''D'', тако да ''u'' ∈ ''S''<sub>''i''</sub> и изградњом , ''u'' и ''i'' су повезани у ''G'' ; стога и доминира у ‘’i’’. Друго, будући да ''D'' мора бити непразан, свако ''i'' ∈ ''I'' је суседан чвору у ‘’D’’.
| |||