Suurin itsenäinen sarja

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 9. marraskuuta 2021 tarkistetusta versiosta . tarkastukset vaativat 2 muokkausta .

Graafiteoriassa suurin riippumaton joukko , suurin stabiili joukko tai suurin stabiili joukko on riippumaton joukko , joka ei ole toisen riippumattoman joukon osajoukko. Toisin sanoen se on joukko pisteitä S siten, että jollakin graafin reunalla on vähintään yksi päätepiste, joka ei ole S :ssä , ja jokaisella kärjellä, joka ei ole S :ssä, on vähintään yksi naapuri S :ssä . Suurin riippumaton joukko on myös hallitsevakaaviossa, ja minkä tahansa hallitsevan joukon, joka on riippumaton, on oltava maksimaalinen riippumaton, joten maksimaalisia riippumattomia joukkoja kutsutaan myös itsenäisiksi hallitseviksi joukoiksi . Graafilla voi olla useita maksimaalisia riippumattomia joukkoja laajalla kokoalueella. [yksi]

Suurinta riippumatonta joukkoa kutsutaan suurimmaksi itsenäiseksi joukoksi .

Esimerkiksi graafissa P 3 polut, joissa on kolme kärkeä a , b ja c ja kaksi reunaa ab ja bc , joukot { ​​b } ja { a , c } ovat molemmat maksimiriippumattomia, joista vain { a , c } on suurin riippumaton. Joukko { a } on riippumaton, mutta ei maksimaalinen, koska se on { a , c }:n osajoukko. Samassa kaaviossa joukot { ​​a , b } ja { b , c } ovat maksimiklikejä.

Ilmaisua "maksimiriippumaton joukko" käytetään myös kuvaamaan riippumattomien elementtien enimmäisosajoukkoja muissa matemaattisissa rakenteissa kuin kaavioissa, erityisesti vektoriavaruuksissa ja matroideissa .

Suhde muihin kärkijoukkoon

Jos S  on maksimaalinen riippumaton joukko jossain graafissa, niin se on maksimiklikki graafin komplementissa . Maksimiklikki on joukko pisteitä, jotka luovat täydellisen aligraafin ja joita ei sisälly suurempaan täydelliseen osagraafiin. Tämä on siis S :n kärkijoukko siten, että mikä tahansa S :n kärkipari on yhdistetty reunalla, ja millekään S :n ulkopuoliselle kärjelle ei ole reunaa, joka yhdistäisi sen vähintään yhteen S :n kärkeen . Kaaviossa voi olla useita erikokoisia maksimiklikkejä. Maksimikokoisen maksimiklikin löytäminen on maksimiklikin ongelma .

Jotkut kirjoittajat vaativat, että klikki on maksimaalinen määritelmässä ja käyttävät termiä klikki maksimiklikin sijaan.

Maksimiriippumattoman joukon komplementti eli ne pisteet, jotka eivät kuulu riippumattomaan joukkoon, muodostavat minimipisteen peitteen . Toisin sanoen komplementti on vertex cover , kärkijoukko, joka sisältää vähintään yhden minkä tahansa reunan päätypisteen, ja on minimaalinen siinä mielessä, että yhtäkään kärkeä ei voida poistaa rikkomatta kantta. Vähimmäispistekattavuutta tutkitaan tilastollisessa mekaniikassa kaasuhilamallissa jäykillä palloilla , matemaattisella abstraktiolla siirtymisestä nesteestä kiinteään tilaan. [2]

Mikä tahansa maksimaalinen riippumaton joukko on hallitseva , eli joukko pisteitä siten, että mikä tahansa graafin kärki joko kuuluu joukkoon tai on sen vieressä. Vertex-joukko on maksimaalinen riippumaton joukko silloin ja vain, jos se on riippumaton hallitseva joukko.

Käyttö kaavioperheiden ominaisuuksissa

Joitakin graafiperheitä voidaan kuvata niiden maksimaalisten klikkien tai riippumattomien enimmäisjoukkojen avulla. Esimerkkejä ovat graafit, joissa on pelkistymättömiä maksimaalisia klikkeja ja kaavioita, joissa on perinnöllisesti pelkistymättömiä maksimaalisia klikkeja. Graafilla sanotaan olevan redusoitumattomia maksimiklikkejä , jos mikä tahansa maksimiklikki sisältää reunan, joka ei kuulu mihinkään muuhun maksimiklikkiin, ja perinnöllisesti redusoitumattomia maksimiklikkejä , jos tämä ominaisuus on totta mille tahansa aligraafille. [3] Graafeihin, joissa on perinnöllisesti redusoitumattomia maksimiklikejä, kuuluvat kolmiotottomat kaaviot , kaksiosaiset graafit ja intervallikaaviot .

Kuvaajat voidaan kuvata graafisiksi, joissa mikä tahansa maksimaalinen klikki leikkaa minkä tahansa suurimman riippumattoman joukon ja joissa tämä ominaisuus on totta kaikille generoiduille aligraafille.

Arviot sarjojen määrästä

Moon ja Moser ( Moon, Moser 1965 ) osoittivat, että millä tahansa graafilla, jossa on n kärkeä, on korkeintaan 3n /3 maksimiklikkiä. Lisäksi graafissa, jossa on n kärkeä, on enintään 3 n /3 maksimiriippumatonta joukkoa. Graafi, jossa on täsmälleen 3n /3 maksimaalista riippumatonta joukkoa, on helppo rakentaa yksinkertaisesti ottamalla irrallinen joukko n /3 kolmiomaista kuvaajaa . Mikä tahansa suurin riippumaton joukko tässä kaaviossa muodostetaan valitsemalla yksi kärki jokaisesta kolmiosta. Lisägraafi, jossa on 3 n /3 maksimiklikkiä , on Turan-graafien erityinen muoto . Koska tämä kuvaaja on yhteydessä Kuu-Moser-rajaan, näitä kaavioita kutsutaan joskus Kuu-Moser-kaavioiksi. Vahvemmat rajat ovat mahdollisia, jos maksimaalisten riippumattomien joukkojen koko on rajoitettu — k -koon riippumattomien joukkojen enimmäismäärä missään graafissa, jossa on n kärkeä, ei ylitä

Tämän rajan saavuttavat kuvaajat ovat jälleen Turan-kaavioita. [neljä]

Joillakin graafiperheillä voi kuitenkin olla huomattavasti vahvemmat rajat riippumattomien joukkojen tai maksimiklikkien lukumäärälle. Esimerkiksi jos perheen graafit sisältävät O(n) reunaa ja perhe on suljettu alagraafien alle, niin kaikki maksimiklikit ovat vakiokokoisia ja maksimiklikkien lukumäärä on lähes lineaarinen. [5]

On selvää, että millä tahansa graafilla, jolla on redusoitumattomia maksimiklikkejä, on korkeintaan maksimiklikkejä kuin reunoja. Voimakkaampi rajoitus on mahdollista intervallikaavioille ja sointukaavioille – näissä kaavioissa  ei voi olla enempää kuin n maksimiklikkiä.

Riippumattomien joukkojen enimmäismäärä syklissä , jossa on n pistettä , saadaan Perrin-luvuilla , ja riippumattomien joukkojen enimmäismäärä polussa , jossa on n pistettä , saadaan Padovan-sekvenssistä . [6] Siten nämä molemmat sekvenssit ovat verrannollisia 1,324718:n potenssiin (eli plastiseen numeroon ).

Aseta luettelointialgoritmit

Algoritmi, jolla luetellaan kaikki maksimaaliset riippumattomat joukot tai maksimaaliset klikkit graafissa, voidaan käyttää rutiinina monien NP-täydellisten graafisen teorian ongelmien ratkaisemiseen. Ilmeisimpiä ongelmia ovat suurin riippumaton joukko-ongelma, maksimiklikki-ongelma ja pienin riippumaton hallitseva joukko-ongelma.

Niiden kaikkien on oltava maksimaalisia riippumattomia joukkoja tai maksimiklikkejä, ja ne voidaan löytää käyttämällä algoritmia, joka luettelee kaikki tällaiset joukot ja valitsee suurimman tai pienimmän koon joukon. Samalla tavalla minimipistepeite löytyy yhden suurimman riippumattoman joukon komplementtina. Lawler ( Lawler 1976 ) totesi, että maksimaalisten riippumattomien joukkojen laskemista voidaan käyttää myös graafin kolmivärisen värityksen löytämiseen - graafi voi olla kolmivärinen, jos ja vain jos yhden suurimman riippumattoman joukon komplementti on kaksiosainen . Hän käytti tätä lähestymistapaa ei vain värjäykseen kolmella värillä, vaan myös osana yleisempää graafin värjäysalgoritmia, ja muut kirjoittajat ovat käyttäneet samanlaista lähestymistapaa kuvaajien värjäämiseen. [7]

Muut monimutkaisemmat ongelmat voidaan supistaa klikin tai erillisen erikoisjoukon löytämiseen. Tämä tarjoaa motivaatiota löytää algoritmeja, jotka laskevat tehokkaasti kaikki suurimmat riippumattomat joukot (tai vastaavasti maksimaaliset klikkit).

On mahdollista muuttaa suoraan Moonin ja Moserin todistus 3 n /3 : n rajasta riippumattomien enimmäisjoukkojen lukumäärään algoritmiksi, joka luettelee kaikki tällaiset joukot O(3 n /3 ) -ajassa. [8] Graafeille, joissa on suurin mahdollinen enimmäismäärä riippumattomia joukkoja, tämä algoritmi antaa vakioajan per löydetty joukko. Algoritmi tällä aikarajalla voi kuitenkin olla erittäin tehoton kaavioille, joissa on rajoitetumpi määrä riippumattomia joukkoja. Tästä syystä monet tutkijat etsivät algoritmeja, joilla luetellaan kaikki suurimmat riippumattomat joukot polynomiajassa per löydetty joukko. [9] Aika yhden maksimaalisen riippumattoman joukon löytämiseen on verrannollinen matriisin kertolaskuaikaan tiheissä kaavioissa tai nopeammin erilaisissa harvalukuisten graafien luokissa. [kymmenen]

Muistiinpanot

  1. ↑ Erdős ( Erdős 1966 ) osoitti, että erikokoisten maksimiriippumattomien joukkojen lukumäärä graafissa, jossa on n kärkeä, voi saavuttaa eikä koskaan ylittää .
  2. ↑ Weigt, Hartmann, 2001 .
  3. ↑ Tietojärjestelmä kaavioluokkien sisällyttämisestä: Kuvaajat, joissa on redusoitumattomia maksimiklikkejä Arkistoitu 2007-07-09 . ja perinnöllisesti vähentymättömillä maksimiklikeillä Arkistoitu alkuperäisestä 8. heinäkuuta 2007. .
  4. ↑ ( Byskov 2003 ). Katso aikaisemmat työt ( Croitoru 1979 ) ja ( Eppstein 2003 ).
  5. ↑ ( Chiba, Nishizeki 1985 ). Harvaisuusehto vastaa ehtoa, että graafiperheellä on rajattu puuisuus .
  6. ↑ ( Bisdorff, Marichal 2007 ); ( Euler 2005 ); ( Füredi 1987 ).
  7. ↑ ( Eppstein 2003 ); ( Byskov 2003 ).
  8. ↑ ( Eppstein 2003 ). Katso laajasti käytetyn Bron-Kerbosh-algoritmin rajat ( 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 ).

Linkit