Maksimalt uafhængigt sæt

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 9. november 2021; checks kræver 2 redigeringer .

I grafteori er et maksimalt uafhængigt sæt , et maksimalt stabilt sæt eller et maksimalt stabilt sæt et uafhængigt sæt , der ikke er en delmængde af et andet uafhængigt sæt. Det vil sige, at det er et sæt toppunkter S , således at enhver kant på grafen har mindst ét endepunkt ikke i S , og ethvert toppunkt, der ikke er i S , har mindst én nabo i S. Et maksimalt uafhængigt sæt er også et dominant sæt i en graf, og ethvert dominant sæt, der er uafhængigt, skal være et maksimalt uafhængigt sæt, hvorfor maksimale uafhængige mængder også kaldes uafhængige dominerende mængder . En graf kan have mange maksimale uafhængige sæt over en lang række størrelser. [en]

Det største uafhængige sæt i størrelse kaldes det største uafhængige sæt .

For eksempel, i en graf P 3 , stier med tre spidser a , b og c og to kanter ab og bc , er mængderne { b } og { a , c } begge maksimalt uafhængige, hvoraf kun { a , c } er den største uafhængige. Mængden { a } er uafhængig, men ikke maksimal, da den er en delmængde af { a , c }. I samme graf er mængderne { a , b } og { b , c } de maksimale kliker.

Udtrykket "maksimalt uafhængigt sæt" bruges også til at beskrive de maksimale delmængder af uafhængige elementer i andre matematiske strukturer end grafer, især i vektorrum og matroider .

Forholdet til andre toppunkter

Hvis S er et maksimalt uafhængigt sæt i en graf, så er det en maksimal klike i grafens komplement . En maksimal klike er det sæt af hjørner, der genererer en komplet undergraf og ikke er indeholdt i en større komplet undergraf. Dette er således mængden af toppunkter af S , således at ethvert par af toppunkter i S er forbundet med en kant, og for ethvert toppunkt, der ikke er i S , er der ingen kant, der forbinder det med mindst ét toppunkt i S . En graf kan have flere maksimale kliker af forskellige størrelser. At finde den maksimale klike af maksimal størrelse er problemet med den maksimale klike .

Nogle forfattere kræver, at kliken er maksimal i definitionen og bruger udtrykket klike i stedet for maksimal klike.

Komplementet af det maksimale uafhængige sæt, det vil sige de hjørner, der ikke hører til det uafhængige sæt, danner det mindste toppunktsdæksel . Det vil sige, at komplementet er et toppunktsdæksel , det sæt af toppunkter, der indeholder mindst et endepunkt af enhver kant, og er minimalt i den forstand, at ingen af toppunkterne kan fjernes uden at bryde låget. Den minimale topdækning studeres i statistisk mekanik i gasgittermodellen på stive kugler , en matematisk abstraktion af overgangen fra en flydende til en fast tilstand. [2]

Ethvert maksimalt uafhængigt sæt er dominerende , det vil sige et sæt af hjørner, således at ethvert knudepunkt i grafen enten hører til sættet eller støder op til det. Et toppunktssæt er et maksimalt uafhængigt sæt, hvis og kun hvis det er et uafhængigt dominerende sæt.

Brug i karakteristika for familier af grafer

Nogle familier af grafer kan beskrives i form af deres maksimale kliker eller maksimale uafhængige sæt. Eksempler omfatter grafer med irreducerbare maksimale kliker og grafer med arveligt irreducerbare maksimale kliker. En graf siges at have irreducerbare maksimale kliker , hvis en maksimal klike indeholder en kant, der ikke hører til nogen anden maksimal klike, og arveligt irreducerbare maksimale kliker , hvis denne egenskab er sand for enhver undergraf. [3] Grafer med arveligt irreducerbare maksimale kliker inkluderer trekantfrie grafer , todelte grafer og intervalgrafer .

Kografer kan beskrives som grafer, hvor enhver maksimal klik skærer ethvert maksimalt uafhængigt sæt, og hvor denne egenskab er sand for alle genererede undergrafer.

Estimater for antallet af sæt

Moon og Moser ( Moon, Moser 1965 ) viste, at enhver graf med n toppunkter højst har 3n /3 maksimale kliker. Desuden har en graf med n toppunkter højst 3 n /3 maksimale uafhængige sæt. En graf med nøjagtigt 3n /3 maksimale uafhængige sæt er let at konstruere ved blot at tage et afbrudt sæt af n /3 trekantede grafer . Ethvert maksimalt uafhængigt sæt i denne graf dannes ved at vælge et toppunkt fra hver trekant. Den ekstra graf med 3 n /3 maksimale kliker er en speciel form for Turan-grafer . På grund af denne grafs forbindelse med Måne-Moser-grænsen, kaldes disse grafer nogle gange Måne-Moser-grafer. Stærkere grænser er mulige, hvis størrelsen af maksimale uafhængige sæt er begrænset - antallet af maksimale uafhængige sæt af størrelse k i enhver graf med n toppunkter overstiger ikke

\lgulv n/k\rgulv ^{{k-(n{\bmod k})}}\lgulv n/k+1\rgulv ^{{n{\bmod k}}}.

Graferne, der når denne grænse, er igen Turan-grafer. [fire]

Nogle graffamilier kan dog have væsentligt stærkere grænser for antallet af maksimale uafhængige sæt eller maksimale kliker. For eksempel, hvis graferne i en familie har O(n) kanter, og familien er lukket under undergrafer, så er alle maksimale kliker af konstant størrelse, og antallet af maksimale kliker er næsten lineært. [5]

Det er klart, at enhver graf med irreducerbare maksimale kliker højst har maksimale kliker end kanter. En stærkere grænse er mulig for intervalgrafer og akkordgrafer - der kan ikke være mere end n maksimale klik i disse grafer.

Antallet af maksimale uafhængige sæt i en cyklus med n toppunkter er givet af Perrin-tallene , og antallet af maksimale uafhængige sæt i en sti med n toppunkter er givet af Padovan-sekvensen . [6] Således er begge disse sekvenser proportionale med potensen 1,324718 (det vil sige det plastiske tal ).

Indstil optællingsalgoritmer

En algoritme til at liste alle maksimale uafhængige sæt eller maksimale kliker i en graf kan bruges som en rutine til at løse mange NP-komplette problemer i grafteori. De mest åbenlyse problemer er problemet med det maksimale uafhængige sæt, det maksimale klikproblem og det mindste uafhængige dominerende sæt-problem.

De skal alle være maksimale uafhængige sæt eller maksimale kliker og kan findes ved hjælp af en algoritme, der opregner alle sådanne sæt og vælger et sæt med maksimum eller minimum størrelse. På samme måde kan minimum toppunktsdækning findes som komplementet til et af de maksimale uafhængige sæt. Lawler ( Lawler 1976 ) bemærkede, at opregning af maksimale uafhængige mængder også kan bruges til at finde en 3- farvefarvning af en graf - en graf kan være 3-farvet, hvis og kun hvis komplementet af et af de maksimale uafhængige sæt er todelt . Han brugte denne tilgang ikke kun til farvning med 3 farver, men også som en del af en mere generel graffarvealgoritme, og en lignende tilgang til graffarvning er blevet brugt af andre forfattere. [7]

Andre mere komplekse problemer kan reduceres til at finde en klike eller et selvstændigt sæt af en særlig art. Dette giver motivation til at finde algoritmer, der effektivt opregner alle maksimale uafhængige sæt (eller tilsvarende maksimale kliker).

Det er muligt direkte at omdanne Moon og Mosers bevis for 3 n /3 bundet på antallet af maksimale uafhængige mængder til en algoritme, der opregner alle sådanne mængder i O(3 n /3 ) tid. [8] For grafer, der har det maksimalt mulige antal maksimalt uafhængige sæt, giver denne algoritme konstant tid pr. fundet sæt. En algoritme med denne tidsgrænse kan dog være ekstremt ineffektiv for grafer med et mere begrænset antal uafhængige sæt. Af denne grund leder mange forskere efter algoritmer til at opregne alle maksimale uafhængige sæt i polynomiel tid pr. fundet sæt. [9] Tiden til at finde et maksimalt uafhængigt sæt er proportional med tiden for matrixmultiplikation i tætte grafer eller hurtigere i forskellige klasser af sparsomme grafer. [ti]

Noter