Set independent maxim

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 9 noiembrie 2021; verificările necesită 2 modificări .

În teoria grafurilor, o mulțime independentă maximă , o mulțime maximă stabilă sau o mulțime maximă stabilă este o mulțime independentă care nu este o submulțime a unei alte mulțimi independente. Adică, este un set de vârfuri S astfel încât orice muchie a graficului are cel puțin un vârf de capăt care nu este în S și orice vârf care nu este în S are cel puțin un vecin în S . Setul maxim independent este, de asemenea, dominantîntr-un grafic, și orice mulțime dominantă care este independentă trebuie să fie independentă maximă, deci mulțimile independente maxime sunt numite și mulțimi dominante independente . Un grafic poate avea multe seturi independente maxime pe o gamă largă de dimensiuni. [unu]

Cea mai mare multime independenta ca dimensiune se numeste cea mai mare multime independenta .

De exemplu, într-un grafic P 3 , căi cu trei vârfuri a , b și c și două muchii ab și bc , mulțimile { b } și { a , c } sunt ambele maxim independente, dintre care numai { a , c } este cel mai mare independent. Mulțimea { a } este independentă, dar nu maximă, deoarece este o submulțime a lui { a , c }. În același grafic, mulțimile { a , b } și { b , c } sunt clicurile maxime.

Expresia „mulțime independentă maximă” este, de asemenea, folosită pentru a descrie subseturile maxime de elemente independente în structuri matematice, altele decât grafice, în special în spații vectoriale și matroide .

Relația cu alte mulțimi de vârfuri

Dacă S  este o mulțime independentă maximă într-un grafic, atunci este o clică maximă în complementul graficului . O clică maximă este setul de vârfuri care generează un subgraf complet și nu este conținut într-un subgraf complet mai mare. Astfel, aceasta este mulțimea de vârfuri a lui S astfel încât orice pereche de vârfuri din S este conectată printr-o muchie, iar pentru orice vârf care nu este în S nu există nicio muchie care să o conecteze la cel puțin un vârf din S . Un grafic poate avea mai multe clicuri maxime de diferite dimensiuni. Găsirea clicei maxime de dimensiune maximă este problema clicei maxime .

Unii autori cer clică să fie maximă în definiție și folosesc termenul clică în loc de clică maximă.

Complementul mulțimii independente maxime, adică vârfurile care nu aparțin mulțimii independente, formează acoperirea minimă a vârfurilor . Adică, complementul este un înveliș de vârfuri , mulțimea de vârfuri care conțin cel puțin un vârf de capăt al oricărei muchii și este minim în sensul că niciunul dintre vârfuri nu poate fi îndepărtat fără a rupe capacul. Acoperirea minimă a vârfurilor este studiată în mecanica statistică în modelul rețelei de gaze pe sfere rigide , o abstractizare matematică a tranziției de la o stare lichidă la o stare solidă. [2]

Orice mulțime independentă maximă este dominantă , adică o mulțime de vârfuri astfel încât orice vârf din grafic fie aparține mulțimii, fie este adiacent acesteia. O mulțime de vârfuri este o mulțime independentă maximă dacă și numai dacă este o mulțime dominantă independentă.

Utilizare în caracteristicile familiilor de grafice

Unele familii de grafuri pot fi descrise în termeni de clicuri maxime sau de mulțimi independente maxime. Exemplele includ grafice cu clicuri maxime ireductibile și grafice cu clicuri maxime ireductibile ereditar. Se spune că un grafic are clicuri maxime ireductibile dacă orice clică maximă conține o margine care nu aparține niciunei alte clicuri maxime și clicuri maxime ireductibile ereditar dacă această proprietate este adevărată pentru orice subgraf. [3] Graficele cu clicuri maxime ereditar ireductibile includ grafice fără triunghi , grafice bipartite și grafice cu intervale .

Cografele pot fi descrise ca grafice în care orice clică maximă intersectează orice mulțime independentă maximă și în care această proprietate este adevărată pentru toate subgrafele generate.

Estimări pentru numărul de seturi

Moon și Moser ( Moon, Moser 1965 ) au arătat că orice grafic cu n vârfuri are cel mult 3n /3 clicuri maxime. De asemenea, un grafic cu n vârfuri are cel mult 3 n /3 mulțimi independente maxime. Un grafic având exact 3n /3 seturi independente maxime este ușor de construit prin simpla luare a unui set deconectat de n /3 grafice triunghiulare . Orice mulțime independentă maximă din acest grafic se formează prin alegerea unui vârf din fiecare triunghi. Graficul suplimentar cu 3 n /3 clicuri maxime este o formă specială de grafice Turan . Datorită conexiunii acestui grafic cu granița Moon-Moser, aceste grafice sunt uneori numite grafice Moon-Moser. Limite mai puternice sunt posibile dacă dimensiunea mulțimilor independente maxime este limitată - numărul de mulțimi independente maxime de dimensiunea k în orice grafic cu n vârfuri nu depășește

Graficele care ajung la această limită sunt din nou grafice Turan. [patru]

Unele familii de grafice pot avea totuși limite substanțial mai puternice ale numărului de mulțimi independente maxime sau clicuri maxime. De exemplu, dacă graficele dintr-o familie au muchii O(n) și familia este închisă sub subgrafe, atunci toate clicurile maxime sunt de dimensiune constantă și numărul de clicuri maxime este aproape liniar. [5]

Este clar că orice grafic cu clicuri maxime ireductibile are cel mult clicuri maxime decât muchii. O limită mai puternică este posibilă pentru graficele de intervale și graficele de acorduri  - nu pot exista mai mult de n clicuri maxime în aceste grafice.

Numărul de mulţimi maxime independente dintr-un ciclu cu n vârfuri este dat de numerele Perrin , iar numărul de mulţimi maxime independente dintr-o cale cu n vârfuri este dat de succesiunea Padovan . [6] Astfel, ambele aceste secvențe sunt proporționale cu puterea lui 1,324718 (adică numărul plastic ).

Setați algoritmi de enumerare

Un algoritm pentru listarea tuturor mulțimilor independente maxime sau clicurilor maxime într-un grafic poate fi folosit ca o rutină pentru rezolvarea multor probleme NP-complete în teoria grafurilor. Cele mai evidente probleme sunt problema setului independent maxim, problema clicei maxime și problema setului dominant minim independent.

Ele trebuie să fie toate seturi independente maxime sau clicuri maxime și pot fi găsite folosind un algoritm care enumeră toate astfel de seturi și selectează un set de dimensiune maximă sau minimă. În același mod, acoperirea minimă a vârfurilor poate fi găsită ca complement al uneia dintre mulțimile maxime independente. Lawler ( Lawler 1976 ) a observat că enumerarea mulțimilor independente maxime poate fi folosită și pentru a găsi o colorare în trei culori a unui grafic - un grafic poate fi tricolorat dacă și numai dacă complementul uneia dintre mulțimile independente maxime este bipartit . El a folosit această abordare nu numai pentru colorarea cu 3 culori, ci și ca parte a unui algoritm mai general de colorare a graficelor, iar o abordare similară pentru colorarea graficelor a fost folosită de alți autori. [7]

Alte probleme mai complexe pot fi reduse la găsirea unei clicuri sau a unui set independent de un tip special. Acest lucru oferă motivație pentru găsirea de algoritmi care enumeră eficient toate seturile independente maxime (sau, echivalent, clicurile maxime).

Este posibil să se transforme direct demonstrația lui Moon și Moser a limitei 3 n /3 a numărului de mulțimi independente maxime într-un algoritm care enumeră toate astfel de mulțimi în timp O(3 n /3 ). [8] Pentru graficele care au numărul maxim posibil de mulțimi independente maxime, acest algoritm oferă un timp constant per set găsit. Cu toate acestea, un algoritm cu această limită de timp poate fi extrem de ineficient pentru grafice cu un număr mai limitat de mulțimi independente. Din acest motiv, mulți cercetători caută algoritmi pentru a enumera toate mulțimile independente maxime în timp polinomial per set găsit. [9] Timpul pentru a găsi o mulțime independentă maximă este proporțional cu timpul de înmulțire a matricei în grafice dense sau mai rapid în diferite clase de grafice rare. [zece]

Note

  1. ↑ Erdős ( Erdős 1966 ) a arătat că numărul de mărimi diferite de mulțimi independente maxime dintr-un grafic cu n vârfuri poate atinge și nu depășește niciodată .
  2. ↑ Weigt, Hartmann, 2001 .
  3. ↑ Information System on Graph Class Inclusions: Graphs with Irreductible Maximal Cliques Arhivat 09-07-2007 . și cu clicuri maxime ereditar ireductibile Arhivat din original la 8 iulie 2007. .
  4. ↑ ( Byskov 2003 ). Pentru lucrările anterioare vezi ( Croitoru 1979 ) și ( Eppstein 2003 ).
  5. ↑ ( Chiba, Nishizeki 1985 ). Condiția de sparsitate este echivalentă cu condiția ca o familie de grafice să aibă treeness mărginit .
  6. ↑ ( Bisdorff, Marichal 2007 ); ( Euler 2005 ); ( Füredi 1987 ).
  7. ↑ ( Eppstein 2003 ); ( Byskov 2003 ).
  8. ↑ ( Eppstein 2003 ). Pentru limitele algoritmului larg utilizat Bron-Kerbosh, vezi ( Tomita, Tanaka, Takahashi 2006 ).
  9. ↑ ( Bomze, Budinich, Pardalos, Pelillo 1999 ); ( Eppstein 2005 ); ( Jennings, Motycková 1992 ); ( Johnson, Yannakakis, Papadimitriou 1988 ); ( Lawler, Lenstra, Rinnooy Kan 1980 ); ( Liang, Dhall, Lakshmivarahan 1991 ); ( Makino, Uno 2004 ); ( Mishra, Pitt 1997 ); ( Stix 2004 ); ( Tsukiyama, Ide, Ariyoshi, Shirakawa 1977 ); ( Yu, Chen 1993 ).
  10. ↑ ( Makino, Uno 2004 ); ( Eppstein 2005 ).

Link -uri