Sada ovládající hrany - Edge dominating set - Wikipedia
v teorie grafů, an hrana dominující sada pro graf G = (PROTI, E) je podmnožina D ⊆ E tak, že každá hrana není v D sousedí s alespoň jedním okrajem v D. Sada ovládající hrany je také známá jako a sada dominující linii. Obrázky (a) - (d) jsou příklady sad ovládajících hrany (silné červené čáry).
A minimální hrana dominující sada je sada s nejmenší hranou. Obrázky (a) a (b) jsou příklady minimálních sad ovládajících okraje (lze zkontrolovat, že pro tento graf neexistuje sada ovládající okraje velikosti 2).
Vlastnosti
Sada s dominující hranou G je dominující sada pro jeho hranový graf L(G) a naopak.
Žádný maximální shoda je vždy hrana dominující sada. Obrázky (b) a (d) jsou příklady maximálních shod.
Velikost sady ovládající minimální hranu se navíc rovná velikosti a minimální maximální shoda. Minimální maximální shoda je minimální dominující množina hran; Obrázek (b) je příkladem minimální maximální shody. Sada ovládající minimální hranu nemusí nutně znamenat minimální maximální shodu, jak je znázorněno na obrázku (a); vzhledem k minimální dominující sadě hran D, je snadné najít minimální maximální shodu s |D| hrany (viz např. Yannakakis & Gavril 1980 ).
Algoritmy a výpočetní složitost
Určení, zda pro daný graf existuje množina dominující hraně dané velikosti, je NP-kompletní problém (a proto nalezení minimální sady ovládající hranu je NP-tvrdé problém). Yannakakis & Gavril (1980) ukázat, že problém je NP-úplný i v případě a bipartitní graf s maximálním stupněm 3, a také v případě a rovinný graf s maximálním stupněm 3.
Existuje jednoduchý polynomiální čas aproximační algoritmus s aproximačním faktorem 2: najděte maximální shodu. Maximální shoda je sada ovládající hrany; dále maximální shoda M může být v nejhorším případě dvakrát větší než nejmenší maximální shoda a nejmenší maximální shoda má stejnou velikost jako nejmenší hrana dominující množina.
Rovněž okrajově váženou verzi problému lze přiblížit v rámci faktoru 2, ale algoritmus je podstatně složitější (Fujito & Nagamochi 2002; Parekh 2002 ).
Chlebík & Chlebíková (2006) ukázat, že najít lepší než (7/6) přiblížení je NP-těžké.
Reference
- Ausiello, Giorgio; Crescenzi, Pierluigi; Gambosi, Giorgio; Kann, Viggo; Marchetti-Spaccamela, Alberto; Protasi, Marco (2003), Složitost a aproximace: Problémy kombinatorické optimalizace a vlastnosti jejich přibližnostiSpringer.
- Minimální sada ovládající hranu (optimalizační verze) je problém GT3 v příloze B (strana 370).
- Minimální maximální shoda (optimalizační verze) je problém GT10 v příloze B (strana 374).
- Chlebík, Miroslav; Chlebíková, Janka (2006), "Aproximační tvrdost hran dominujících nastavených problémů", Journal of Combinatorial Optimization, 11 (3): 279–290, doi:10.1007 / s10878-006-7908-0.
- Garey, Michael R.; Johnson, David S. (1979), Počítače a neodolatelnost: Průvodce po teorii NP-úplnosti, W.H. Freemane, ISBN 978-0-7167-1045-5.
- O sadě dominujících hran (rozhodovací verze) se pojednává pod problémem dominující sady, kterým je problém GT2 v příloze A1.1.
- Minimální maximální shoda (rozhodovací verze) je problém GT10 v příloze A1.1.
- Yannakakis, Mihalis; Gavril, Fanica (1980), „Okrajové sady v grafech“, SIAM Journal on Applied Mathematics, 38 (3): 364–372, CiteSeerX 10.1.1.477.4278, doi:10.1137/0138030, JSTOR 2100648.
- Fujito, Toshihiro; Nagamochi, Hiroshi (2002), „Algoritmus 2-aproximace pro problém minimální hrany dominující množině“, Diskrétní aplikovaná matematika, 118 (3): 199–207, doi:10.1016 / S0166-218X (00) 00383-8.
- Parekh, Ojas (2002), „Okrajové a hypomatchovatelné sady“, Sborník z třináctého ročníku sympozia ACM-SIAM o diskrétních algoritmech, str. 287–291.
externí odkazy
- Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, Gerhard Woeginger (2000), „Kompendium problémů s optimalizací NP“: