Maximalt oberoende set

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 9 november 2021; kontroller kräver 2 redigeringar .

I grafteorin är en maximal oberoende uppsättning , en maximal stabil uppsättning eller en maximal stabil uppsättning en oberoende uppsättning som inte är en delmängd av en annan oberoende uppsättning. Det vill säga, det är en uppsättning av hörn S så att vilken kant av grafen som helst har minst en ändpunkt som inte är i S , och vilken som helst hörn som inte är i S har minst en granne i S . En maximal oberoende mängd är också en dominant mängd i en graf, och varje dominant mängd som är oberoende måste vara en maximal oberoende mängd, vilket är anledningen till att maximala oberoende mängder också kallas oberoende dominerande mängder . En graf kan ha många maximala oberoende uppsättningar över ett brett spektrum av storlekar. [ett]

Den största oberoende uppsättningen i storlek kallas den största oberoende uppsättningen .

Till exempel, i en graf P 3 , banor med tre hörn a , b och c och två kanter ab och bc , är mängderna { b } och { a , c } båda maximalt oberoende, av vilka endast { a , c } är den största oberoende. Mängden { a } är oberoende, men inte maximal, eftersom den är en delmängd av { a , c }. I samma graf är uppsättningarna { a , b } och { b , c } de maximala klicken.

Frasen "maximal oberoende uppsättning" används också för att beskriva de maximala delmängderna av oberoende element i matematiska strukturer andra än grafer, i synnerhet i vektorrum och matroider .

Relation med andra vertexuppsättningar

Om S  är en maximal oberoende mängd i någon graf, så är det en maximal klick i grafens komplement . En maximal klick är uppsättningen av hörn som genererar en komplett subgraf och som inte ingår i en större komplett subgraf. Detta är alltså uppsättningen av hörn av S så att vilket par av hörn som helst i S är sammankopplade med en kant, och för alla hörn som inte är i S finns det ingen kant som förbinder den med åtminstone en hörn i S . En graf kan ha flera maximala klicker av olika storlekar. Att hitta den maximala klicken av maximal storlek är problemet med maximal klick .

Vissa författare kräver att klicken är maximal i definitionen och använder termen klick istället för maximal klick.

Komplementet av den maximala oberoende uppsättningen, det vill säga de hörn som inte tillhör den oberoende uppsättningen, bildar det minsta vertextäcket . Det vill säga, komplementet är ett vertextäcke , uppsättningen av hörn som innehåller minst en ändspets av vilken kant som helst, och är minimal i den meningen att ingen av topparna kan tas bort utan att bryta höljet. Minsta vertextäckning studeras i statistisk mekanik i gasgittermodellen på stela sfärer , en matematisk abstraktion av övergången från ett flytande till ett fast tillstånd. [2]

Varje maximalt oberoende uppsättning dominerar , det vill säga en uppsättning av hörn så att varje hörn i grafen antingen hör till mängden eller ligger intill den. En vertexmängd är en maximal oberoende mängd om och endast om den är en oberoende dominerande mängd.

Använd i egenskaper för familjer av grafer

Vissa familjer av grafer kan beskrivas i termer av deras maximala klick eller maximala oberoende uppsättningar. Exempel inkluderar grafer med irreducerbara maximala klicker och grafer med ärftligt irreducerbara maximala klicker. En graf sägs ha irreducerbara maximala klicker om någon maximal klick innehåller en kant som inte tillhör någon annan maximal klick, och ärftligt irreducerbara maximala klicker om denna egenskap är sann för någon subgraf. [3] Grafer med ärftligt irreducerbara maximala klicker inkluderar triangelfria grafer , tvådelade grafer och intervallgrafer .

Kografer kan beskrivas som grafer där vilken maximal klick som helst skär en maximal oberoende uppsättning, och där denna egenskap är sann för alla genererade subgrafer.

Uppskattningar för antalet uppsättningar

Moon och Moser ( Moon, Moser 1965 ) visade att varje graf med n hörn har högst 3n /3 maximala klick. Dessutom har en graf med n hörn högst 3 n /3 maximala oberoende uppsättningar. En graf som har exakt 3n /3 maximala oberoende uppsättningar är lätt att konstruera genom att helt enkelt ta en frånkopplad uppsättning av n /3 triangulära grafer . Varje maximal oberoende uppsättning i denna graf bildas genom att välja en vertex från varje triangel. Den extra grafen med 3 n /3 maximala klick är en speciell form av Turan-grafer . På grund av kopplingen mellan denna graf och gränsen mellan Månen och Moser, kallas dessa grafer ibland för Mån-Moser-grafer. Starkare gränser är möjliga om storleken på maximala oberoende uppsättningar är begränsade — antalet maximala oberoende uppsättningar av storlek k i någon graf med n hörn överstiger inte

Graferna som når denna gräns är återigen Turan-grafer. [fyra]

Vissa graffamiljer kan dock ha betydligt starkare gränser för antalet maximala oberoende uppsättningar eller maximala klick. Till exempel, om graferna i en familj har O(n) kanter och familjen är stängd under subgrafer, då är alla maximala klick av konstant storlek och antalet maximala klick är nästan linjärt. [5]

Det är tydligt att varje graf med irreducerbara maximala klick har som mest maximala klicker än kanter. En starkare gräns är möjlig för intervallgrafer och ackordsgrafer  — det kan inte finnas fler än n maximala klick i dessa grafer.

Antalet maximala oberoende uppsättningar i en cykel med n hörn ges av Perrin-talen , och antalet maximala oberoende uppsättningar i en bana med n hörn ges av Padovan-sekvensen . [6] Sålunda är båda dessa sekvenser proportionella mot potensen 1,324718 (det vill säga plasttalet ).

Ställ in uppräkningsalgoritmer

En algoritm för att lista alla maximala oberoende uppsättningar eller maximala klick i en graf kan användas som en rutin för att lösa många NP-kompletta problem inom grafteorin. De mest uppenbara problemen är problemet med maximal oberoende uppsättning, maximal klickproblem och minsta oberoende dominerande uppsättningsproblem.

De måste alla vara maximala oberoende uppsättningar eller maximala klicker och kan hittas med en algoritm som räknar upp alla sådana uppsättningar och väljer en uppsättning av högsta eller minsta storlek. På samma sätt kan det minsta vertextäcket hittas som komplement till en av de maximala oberoende uppsättningarna. Lawler ( Lawler 1976 ) noterade att uppräkning av maximala oberoende uppsättningar också kan användas för att hitta en 3- färgsfärgning av en graf - en graf kan vara 3-färgad om och endast om komplementet av en av de maximalt oberoende uppsättningarna är tvådelat . Han använde detta tillvägagångssätt inte bara för att färga med 3 färger, utan också som en del av en mer allmän graffärgningsalgoritm, och en liknande metod för graffärgning har använts av andra författare. [7]

Andra mer komplexa problem kan reduceras till att hitta en klick eller en oberoende uppsättning av ett speciellt slag. Detta ger motivation för att hitta algoritmer som effektivt räknar upp alla maximala oberoende uppsättningar (eller motsvarande maximala klick).

Det är möjligt att direkt omvandla Moon och Mosers bevis på 3 n /3 gränsen på antalet maximala oberoende mängder till en algoritm som räknar upp alla sådana mängder i O(3 n /3 ) tid. [8] För grafer som har maximalt möjliga antal maximalt oberoende uppsättningar, ger denna algoritm konstant tid per hittad uppsättning. En algoritm med denna tidsgräns kan dock vara extremt ineffektiv för grafer med mer begränsat antal oberoende uppsättningar. Av denna anledning letar många forskare efter algoritmer för att räkna upp alla maximala oberoende uppsättningar i polynomtid per hittad uppsättning. [9] Tiden för att hitta en maximal oberoende uppsättning är proportionell mot tiden för matrismultiplikation i täta grafer eller snabbare i olika klasser av glesa grafer. [tio]

Anteckningar

  1. ↑ Erdős ( Erdős 1966 ) visade att antalet olika storlekar av maximala oberoende uppsättningar i en graf med n hörn kan nå och aldrig överstiga .
  2. ↑ Weigt, Hartmann, 2001 .
  3. ↑ Informationssystem om grafklassinneslutningar: Grafer med irreducerbara maximala klicker Arkiverad 2007-07-09 . och med ärftligt irreducerbara maximala klicker Arkiverad från originalet den 8 juli 2007. .
  4. ↑ ( Byskov 2003 ). För tidigare arbete se ( Croitoru 1979 ) och ( Eppstein 2003 ).
  5. ↑ ( Chiba, Nishizeki 1985 ). Sparsitetsvillkoret är ekvivalent med villkoret att en familj av grafer har avgränsad trädighet .
  6. ↑ ( Bisdorff, Marichal 2007 ); ( Euler 2005 ); ( Füredi 1987 ).
  7. ↑ ( Eppstein 2003 ); ( Byskov 2003 ).
  8. ↑ ( Eppstein 2003 ). För gränserna för den allmänt använda Bron-Kerbosh-algoritmen, se ( 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 ).

Länkar