Ansluten dominerande set

En ansluten dominerande uppsättning och ett maximalt bladat spännträd är två närbesläktade strukturer definierade på en oriktad graf .

Definitioner

En sammankopplad dominerande uppsättning av en graf G är en uppsättning D av hörn med två egenskaper:

  1. Från vilken nod som helst i D kan du gå till vilken annan nod som helst i D längs en väg som är helt inuti D . Det vill säga, D genererar en ansluten subgraf till grafen G.
  2. Varje hörn i G tillhör antingen D eller ligger intill en hörn i D. Det vill säga, D är den dominerande uppsättningen av grafen G.

Den minst anslutna dominerande mängden [1] i grafen G är den anslutna dominerande mängden med den minsta kardinaliteten bland alla anslutna dominerande uppsättningar av grafen G . Det sammankopplade dominanstalet för en graf G är antalet hörn i den minsta sammankopplade dominerande uppsättningen [2] .

Varje spännträd T i en graf G har minst två blad. Ett maximalt lövspännande träd är ett spännträd som har det maximala antalet löv bland alla spännträd i G . Det maximala antalet löv i graf G är antalet löv i det spännande trädet med maximalt lövverk [3] .

Kompletterande

Om d är det sammankopplade dominanstalet för en graf G med n hörn, där n > 2 och l är dess maximala antal blad, så är de tre storheterna d , l och n relaterade till den enkla likheten

[4] .

Om D är en sammankopplad dominerande mängd, så finns det ett spännträd i G vars blad inkluderar alla hörn som inte är i D - vi bildar ett spännande träd av subgrafen som genereras av mängden D tillsammans med kanter som förbinder varje återstående vertex v som inte ligger i D med sin granne v en hörn tillhörande D . Detta visar att l ≥ n − d .

I motsatt riktning, om T är något spännande träd i G , så bildar de icke-bladiga hörnen i trädet T en sammankopplad dominerande uppsättning av grafen G . Detta visar att n − l ≥ d . dessa två erhållna olikheter innebär likheten n = d + l .

Sålunda, i vilken graf som helst, är summan av det anslutna dominanstalet och det maximala antalet blad lika med antalet grafens hörn. Ur beräkningssynpunkt innebär detta att beräkningen av det kopplade dominanstalet har samma svårighet som att beräkna det maximala antalet löv.

Algoritmer

Problemet med att kontrollera om det finns en ansluten dominerande uppsättning med en storlek som är mindre än en given tröskel är NP-komplett , och ett sådant problem är likvärdigt med att kontrollera om det finns ett spännträd med åtminstone ett givet antal löv. Således kan vi anta att problemet med att hitta den minsta anslutna dominerande mängden och problemet med att hitta ett spännträd med maximalt antal löv inte kan lösas i polynomtid.

När man överväger problem i termer av approximationsalgoritmer, är ansluten dominans och maximalt spännande trädblad inte samma sak - att approximera ett problem med en given approximationskoefficient är inte detsamma som att approximera ett annat problem med samma koefficient. Det finns en approximation för problemet att hitta den minsta anslutna dominerande mängden med koefficienten 2 ln Δ + O(1) , där Δ betyder den maximala graden av hörn i grafen G [5] . Uppgiften att hitta ett spännträd med maximalt lövverk MAX-SNP är svårt, vilket antyder att det tydligen inte finns något ungefärligt polynomtidsschema [6] . Problemet kan dock approximeras med en faktor 2 i polynomtid [7] .

Båda problemen kan lösas på grafer med n hörn i tiden O (1,9 n ) [8] . Det maximala lövverksproblemet är fast-parametriskt lösbart , vilket innebär att det kan lösas i tid som beror exponentiellt på antalet löv, men bara polynomiskt på grafens storlek. Muslingvärdet för dessa algoritmer (intuitivt sett är detta antalet blad för vilka algoritmen körs på en acceptabel tid) har gradvis ökat i takt med att algoritmerna har förbättrats till cirka 37 [9] och det finns förslag på att ett värde på 50 kan uppnås [10] .

Applikationer

Anslutna dominerande uppsättningar är användbara för ruttberäkning för trådlösa decentraliserade självorganiserande nätverk . I dessa applikationer används en liten ansluten dominerande uppsättning som en dataöverföringsstam, och noder som inte tillhör denna uppsättning sänder meddelanden genom grannar som finns på stamnätet [11] .

Det maximala antalet blad används för att utveckla fast-parametriskt lösbara -algoritmer - vissa NP-hårda optimeringsproblem kan lösas i polynomtid på grafer med ett begränsat maximalt antal blad [3] .

Se även

Anteckningar

  1. ↑ Den minimala anslutna dominerande uppsättningen förekommer ofta . I ryskspråkig litteratur råder en stor förvirring av orden maximal och störst (respektive minimum och minst ). Vanligtvis förstås maximum som ett element som inte kan utökas, och maximum förstås som ett element med maximal numerisk karaktäristik (jämför till exempel maximal matchning och största matchning )
  2. ↑ Sampathkumar, Walikar, 1979 , sid. 607–613.
  3. ↑ 1 2 Fellows, Lokshtanov, Misra et al., 2009 , sid. 822–848.
  4. ↑ Douglas, 1992 , sid. 41–47.
  5. ↑ Guha, Khuller, 1998 , sid. 374–387.
  6. ↑ Galbiati, Maffioli, Morzenti 1994 , sid. 45–49.
  7. ↑ Solis-Oba, 1998 , sid. 441–452.
  8. ↑ Fernau, Kneis, Kratsch et al., 2011 , sid. 6290–6302.
  9. ↑ Binkele-Raible, Fernau, 2014 , sid. 179–200.
  10. ↑ Fellows, McCartin, Rosamond, Stege, 2000 , sid. 240–251.
  11. ↑ Wu, Li, 1999 , sid. 7–14.

Litteratur