Set independent (teoria graficelor)

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare
Cele nouă vârfuri albastre formează un set maxim independent pentru graficul generalizat Petersen GP (12,4).

În teoria graficelor , o mulțime independentă sau stabilă este un set de vârfuri într-un grafic , care nu este adiacent cu două. Adică, este un set I de vârfuri astfel încât pentru fiecare două vârfuri din I , nu există o margine care să le lege. În mod echivalent, fiecare margine a graficului are cel mult o extremă în I. Dimensiunea unui set independent este numărul de vârfuri pe care le conține. Seturile independente au fost, de asemenea, numite seturi stabile intern. [1]

Un set maxim independent este un set independent astfel încât adăugarea oricărui vârf la set forțează setul să conțină o margine.

Un set independent maxim este un set independent de cea mai mare dimensiune posibilă pentru un grafic dat G. Această dimensiune se numește numărul de independență al lui G și se notează α ( G ). [2] Problema găsirii unui astfel de set se numește cea mai mare problemă de set independent și este o problemă de optimizare dificilă pentru NP . Ca atare, este puțin probabil să existe un algoritm eficient pentru găsirea unui set maxim independent de grafic.

Fiecare set maxim independent este, de asemenea, maxim, dar implicația inversă nu este neapărat validă.

Proprietate

Relația cu alți parametri ai graficului

Un set este independent dacă și numai dacă este o clică în complementul graficului, deci cele două concepte sunt complementare. Într-adevăr, graficele suficient de mari, fără fisuri mari, au seturi independente mari, o temă care este explorată în teoria lui Ramsey .

Un set este independent dacă și numai dacă complementul său este un capac de vârf . [3] Prin urmare, suma mărimii celui mai mare set independent α ( G ) și a dimensiunii celui mai mic capac de vârf β ( G ) este egală cu numărul de vârfuri din grafic.

Colorarea vârfurilor unui grafic G corespunde unei partiții a mulțimii vârfurilor sale în subseturi independente. Prin urmare, numărul minim de culori necesar pentru o colorare a vârfurilor, numărul cromatic χ ( G ), este cel puțin coeficientul dintre numărul de vârfuri din G și numărul independent α ( G ).

Într-un grafic bipartit fără vârfuri izolate, numărul vârfurilor dintr-un set maxim independent este egal cu numărul de muchii într-o acoperire minimă a muchiilor ; aceasta este teorema lui König .

Ansamblu maxim independent

Pictogramă lupă mgx2.svg Același subiect în detaliu: set independent maxim .

Un set independent care nu este un subset al unui alt set independent se numește maxim . Astfel de seturi sunt seturi dominante . Fiecare grafic conține cel mult 3 n / 3 seturi independente maxime, [4] dar multe grafice au mult mai puține. Numărul seturilor maxime independente din graficele ciclului n- vârf este dat de numerele Perrin , iar numărul seturilor maxime independente din graficele traseului n- vârf este dat de secvența Padovan . [5] Prin urmare, ambele numere sunt proporționale cu puterile de 1.324718, numărul plastic .

Găsiți seturi independente

Pictogramă lupă mgx2.svg Același subiect în detaliu: Problema clică .

În informatică , au fost studiate mai multe probleme de calcul legate de seturi independente.

  • În problema setului maxim independent , intrarea este un grafic indirect, iar ieșirea este un set maxim independent al graficului. Dacă există seturi independente de maxime multiple, doar unul trebuie să fie ieșirea. Această problemă este uneori denumită „ împachetarea vertexului ”.
  • În problema setului independent cu greutatea maximă , intrarea este un grafic indirect cu greutățile pe vârfurile sale, iar ieșirea este un set independent cu greutatea totală maximă. Problema celui mai mare set independent este cazul special în care greutățile sunt una.
  • În problema listării seturilor independente maxime , intrarea este un grafic indirect, iar ieșirea este o listă a tuturor seturilor independente maxime. Problema celui mai mare set independent poate fi rezolvată folosind ca subrutină un algoritm pentru problema listării seturilor maxime independente, deoarece setul maxim independent trebuie inclus în toate seturile maxime independente.
  • În problema de decizie a setului independent , intrarea este un grafic indirect și un număr k , iar ieșirea este o valoare booleană : adevărat dacă graficul conține un set independent de mărime k și fals în caz contrar.

Primele trei dintre aceste probleme sunt importante în aplicațiile practice; problema deciziei setului independent nu este, dar este necesar să se aplice teoria completitudinii NP problemelor legate de seturi independente.

Seturi maxime independente și fisuri maxime

Problema setului independent și problema clici sunt complementare: o clică în G este un set independent în graficul complement al lui G și invers. Prin urmare, multe rezultate de calcul pot fi aplicate la fel de bine ambelor probleme. De exemplu, rezultatele legate de problema fisurilor au următorii corolari:

  • Problema decizională a setului independent este NP-completă și, prin urmare, nu se crede că există un algoritm eficient pentru a o rezolva.
  • Problema celui mai mare set independent este NP-dificil și este, de asemenea, dificil de aproximat .

În ciuda relației strânse dintre clici maxime și seturi maxime independente în grafice arbitrare, problemele seturilor independente și clice pot fi foarte diferite atunci când sunt limitate la clase speciale de grafice. De exemplu, pentru graficele rare (grafice în care numărul muchiilor este cel mult o dată constantă a numărului de vârfuri în orice subgraf), fisura maximă este limitată ca dimensiune și poate fi găsită în timp exact liniar; [6] cu toate acestea, pentru aceleași clase de grafice, sau chiar pentru clasa mai restrânsă de grafice de grad limitat, găsiți că cel mai mare set independent este MAXSNP-complet , ceea ce înseamnă că, pentru o constantă c (în funcție de grad), este NP-dificil de găsit o soluție aproximativă care se încadrează într-un factor de c al optimului. [7]

Găsiți seturile maxime independente

Pictogramă lupă mgx2.svg Același subiect în detaliu: Problema fisurilor § Găsirea fisurilor maxime în grafice arbitrare .

Algoritmi exacți

Problema celui mai mare set independent este NP-dificilă. Cu toate acestea, poate fi rezolvat mai eficient decât în ​​timpul O ( n 2 2 n ) care ar fi dat de un algoritm naiv de forță brută care examinează fiecare subset al vârfurilor și verifică dacă este un set independent.

Un algoritm Robson (1986) rezolvă problema în timp O (1.2108 n ) folosind spațiul exponențial. Când se reduce la spațiul polinomial, există un algoritm în timpul O (1.2127 n ). [8] care îmbunătățește un algoritm O mai simplu (1.2209 n ). [9]

În unele clase de grafice, inclusiv grafice fără stele și grafice perfecte , cel mai mare set independent poate fi găsit în timp polinomial. [10]

Într-un grafic bipartit , toate nodurile care nu se află în acoperirea minimă a vârfurilor pot fi incluse în setul maxim independent; vezi teorema lui König . Prin urmare, acoperirea minimă a vârfurilor poate fi găsită folosind un algoritm de cuplare.

Algoritmi de aproximare

Problema generală a celui mai mare set independent nu poate fi aproximată la un factor constant în timpul polinomial (cu excepția cazului în care P = NP). Cu toate acestea, există algoritmi de aproximare eficienți pentru clase restrânse de grafice.

În graficele plane , setul maxim independent poate fi aproximat în orice raport de aproximare c <1 în timp polinomial; scheme similare de aproximare timp-polinom există în orice familie de grafice închise în timp ce identifică minorii . [11]

În graficele de grad limitat, algoritmii de aproximare efectivi sunt cunoscuți cu rapoarte de aproximare mai slabe decât cele constante; de exemplu, un algoritm lacom (lacom) care formează un set maxim independent prin selectarea, la fiecare pas, a vârfului de grad minim din grafic și eliminarea vecinilor acestuia, urmează un (raport de aproximare Δ + 2) / 3 pe grafice cu grad maxim Δ. [12]

Seturi independente în graficele de intersecție ale intervalelor

Pictogramă lupă mgx2.svg Același subiect în detaliu: Planificarea intervalelor .

Un grafic de intervale este un grafic în care nodurile sunt intervale unidimensionale (de exemplu, intervale de timp) și există o margine între două intervale dacă și numai dacă se intersectează. Un set independent într-un grafic de intervale este tocmai un set de intervale care nu se suprapun. Problema găsirii seturilor maxime independente în graficele de intervale a fost studiată, de exemplu, în contextul programării lucrărilor: dat fiind un set de joburi care trebuie rulate pe un computer, găsiți un set maxim de joburi care pot fi rulate fără a deduce din unul pe altul. Această problemă poate fi rezolvată în timp exact polinomial folosind cel mai devreme termen limită primul program.

Seturi independente în grafice de intersecție geometrice

Pictogramă lupă mgx2.svg Același subiect în detaliu: set disjunct maxim .

Un grafic de intersecție geometrică este un grafic în care nodurile sunt forme geometrice și există o margine între două forme dacă și numai dacă se intersectează. Un set independent într-un grafic de intersecție geometrică este tocmai un set de forme disjuncte (care nu se suprapun). Problema găsirii seturilor maxime independente în graficele geometrice de intersecție a fost studiată, de exemplu, în contextul plasării automate a etichetelor : dat un set de locații pe o hartă, găsiți un set maxim de etichete dreptunghiulare disjuncte lângă aceste locații.

Găsirea unui set maxim independent în graficele de intersecție este încă NP-completă, dar este mai ușor de aproximat decât problema generală a celui mai mare set independent. O recenzie recentă poate fi găsită în introducerea Chan & Har-Peled (2012) .

Găsiți seturi maxime independente

Pictogramă lupă mgx2.svg Același subiect în detaliu: set independent maxim .

Problema găsirii unui set independent maxim poate fi rezolvată în timp polinomial printr-un trivial algoritm lacom . [13] Toate seturile maxime independente pot fi găsite în timpul O (3 n / 3 ) = O (1,4423 n ).

Programe gratuite pentru cercetarea ansamblului maxim independent

Nume Licență Limbajul API Informații scurte
igraph GPL C, Python, R, Ruby soluție exactă. „Implementarea actuală a fost convertită în igraph de Very Nauty Graph Library de Keith Briggs și folosește algoritmul din eseul S. Tsukiyama, M. Ide, H. Ariyoshi și I. Shirawaka,„ Un nou algoritm pentru generarea tuturor independențelor maxime seturi ", SIAM J Computing , 6, pp. 505-517, 1977.
NetworkX BSD Piton soluție aproximativă, consultați rutina maximum_independent_set
OpenOpt BSD Piton soluție exactă și aproximativă, posibilitatea de a trimite nodurile care trebuie să fie
inclus / exclus; consultați clasa STAB pentru mai multe detalii și exemple

Notă

  1. ^ Korshunov (1974)
  2. ^ Godsil & Royle (2001) , p. 3.
  3. ^ Dovadă: un set V de vârfuri este un set independent dacă și numai dacă fiecare margine din grafic este adiacentă cel mult unui membru al lui V ; dacă și numai dacă fiecare margine din grafic este adiacentă la cel puțin un membru care nu este în V ; dacă și numai dacă complementul lui V este un capac de vârf.
  4. ^ Moon & Moser (1965) .
  5. ^ Füredi (1987) .
  6. ^ Nishizeki (1985) .
  7. ^ Berman199 , Berman și Fujito (1995) .
  8. ^ Bourgeois, Escoffier, Paschos și van Rooij (2010)
  9. ^ Fomin, Grandoni și Kratsch (2009)
  10. ^ Pentru grafice fără stele, vezi Sbihi (1980) . Pentru grafice perfecte, vezi Grötschel, Lovász & Schrijver (1988) .
  11. ^ Baker (1994) ; Grohe (2003) .
  12. ^ Halldórsson și Radhakrishnan (1997) .
  13. ^ Luby (1986) .

Bibliografie

Elemente conexe

  • Un set independent de margini este un set de margini care nu are niciun vârf în comun două câte două. De obicei se numește împerechere .
  • O colorare a vârfurilor este o partiție a setului de vârfuri în seturi independente.

Alte proiecte

linkuri externe

Adus de la „ https://it.wikipedia.org/w/index.php?title=Insieme_indipendente_(teoria_dei_grafi)&oldid=106587877 ”