Připojená dominantní sada

Souvislá dominující množina a maximálně olistěná kostra jsou dvě úzce související struktury definované na neorientovaném grafu .

Definice

Souvislá dominující množina grafu G je množina D vrcholů se dvěma vlastnostmi:

  1. Z kteréhokoli uzlu v D můžete přejít do kteréhokoli jiného uzlu v D po cestě, která je zcela uvnitř D. To znamená, že D generuje souvislý podgraf grafu G.
  2. Jakýkoli vrchol v G buď patří k D , nebo sousedí s vrcholem v D. To znamená, že D je dominující množina grafu G.

Nejméně souvislá dominující množina [1] grafu G je souvislá dominující množina s nejmenší mohutností ze všech spojených dominujících množin grafu G . Souvislé číslo dominance grafu G je počet vrcholů v nejmenší spojené dominující množině [2] .

Libovolná kostra T grafu G má alespoň dva listy. Strom s maximálním počtem listů je kostra, která má maximální možný počet listů mezi všemi kostrami v G . Maximální počet listů v grafu G je počet listů v kostrovém stromu s maximálním olistěním [3] .

Doplňkové

Jestliže d je souvislé číslo dominance grafu G s n vrcholy, kde n > 2 a l je jeho maximální počet listů, pak tři veličiny d , l a n souvisí jednoduchou rovností

[4] .

Je-li D spojená dominující množina, pak v G existuje kostra, jejíž listy zahrnují všechny vrcholy, které nejsou v D - tvoříme kostru podgrafu generovaného množinou D spolu s hranami spojujícími každý zbývající vrchol v neležící v D se svým sousedem v a vrcholem náležejícím k D . To ukazuje, že l ≥ n − d .

V opačném směru, je-li T libovolný kostra v G , pak nelistové vrcholy ve stromu T tvoří souvislou dominující množinu grafu G . To ukazuje, že n − l ≥ d . tyto dvě získané nerovnosti implikují rovnost n = d + l .

V libovolném grafu je tedy součet spojeného čísla dominance a maximálního počtu listů roven počtu vrcholů grafu. Z výpočtového hlediska to znamená, že výpočet připojeného čísla dominance je stejně náročný jako výpočet maximálního počtu listů.

Algoritmy

Problém kontroly, zda existuje připojená dominující množina o velikosti menší než daný práh, je NP-úplný a takový problém je ekvivalentní kontrole, zda existuje kostra s alespoň daným počtem listů. Můžeme tedy předpokládat, že problém nalezení minimální spojené dominující množiny a problém nalezení kostry s maximálním počtem listů nelze vyřešit v polynomiálním čase.

Při zvažování problémů z hlediska aproximačních algoritmů nejsou připojená dominance a olistění maximálního spanning tree totéž – aproximace jednoho problému s daným aproximačním koeficientem není totéž jako aproximace jiného problému se stejným koeficientem. Existuje aproximace pro problém nalezení nejmenší souvislé dominující množiny s koeficientem 2 ln Δ + O(1) , kde Δ znamená maximální stupeň vrcholů v grafu G [5] . Úkol najít kostru s maximálním olistěním MAX-SNP je obtížný, což znamená, že zjevně neexistuje žádné přibližné polynomiální časové schéma [6] . Problém však lze aproximovat faktorem 2 v polynomiálním čase [7] .

Oba problémy lze řešit na grafech s n vrcholy v čase O (1,9 n ) [8] . Problém maximálního olistění je pevně-parametricky řešitelný , což znamená, že jej lze vyřešit v čase, který závisí exponenciálně na počtu listů, ale pouze polynomiálně na velikosti grafu. Hodnota clam těchto algoritmů (intuitivně je to počet listů, pro které algoritmus běží v přijatelném čase) se postupně zvyšovala, jak se algoritmy zlepšily na přibližně 37 [9] a existují návrhy, že hodnota 50 lze dosáhnout [10] .

Aplikace

Propojené dominující sady jsou užitečné pro výpočet trasy pro bezdrátové decentralizované samoorganizující se sítě . V těchto aplikacích se jako páteř přenosu dat používá malá připojená dominující množina a uzly, které do této množiny nepatří, přenášejí zprávy přes sousedy umístěné na páteři [11] .

Maximální počet listů se používá k vývoji pevně-parametricky řešitelných algoritmů - některé NP-těžké optimalizační problémy lze řešit v polynomiálním čase na grafech s omezeným maximálním počtem listů [3] .

Viz také

Poznámky

  1. ↑ Minimální připojená dominantní sada se často vyskytuje . V ruskojazyčné literatuře dochází k velké záměně slov maximum a největší (respektive minimum a minimum ). Obvykle se maximem rozumí prvek, který nelze rozšířit, a maximem se rozumí prvek s maximální číselnou charakteristikou (srovnejte např. maximální shoda a největší shoda )
  2. ↑ Sampathkumar, Walikar, 1979 , str. 607–613.
  3. ↑ 1 2 Fellows, Lokshtanov, Misra et al., 2009 , s. 822–848.
  4. ↑ Douglas, 1992 , s. 41–47.
  5. ↑ Guha, Khuller, 1998 , s. 374–387.
  6. ↑ Galbiati, Maffioli, Morzenti 1994 , str. 45–49.
  7. ↑ Solis-Oba, 1998 , s. 441–452.
  8. ↑ Fernau, Kneis, Kratsch et al., 2011 , str. 6290–6302.
  9. ↑ Binkele-Raible, Fernau, 2014 , str. 179–200.
  10. ↑ Fellows, McCartin, Rosamond, Stege, 2000 , str. 240–251.
  11. ↑ Wu, Li, 1999 , str. 7–14.

Literatura