Utfyllingsdiagram - Complement graph
I grafteori , den komplement eller inverse av en graf G er en graf H på samme toppunkter, slik at to adskilte punkt av H er tilstøtende hvis og bare hvis de ikke er tilstøtende i G . For å generere komplementet til en graf, fyller man ut alle manglende kanter som kreves for å danne en komplett graf , og fjerner alle kantene som tidligere var der.
Komplementet er ikke det komplette komplementet til grafen; bare kantene utfylles.
Definisjon
La G = ( V , E ) være en enkel graf, og la K bestå av alle delelementene av V med 2 elementer . Deretter H = ( V , K \ E ) er komplementet til G , hvor K \ E er den relative komplementet av E i K . For rettede grafer kan komplement defineres på samme måte, som en rettet graf på samme toppunktet sett, ved hjelp av settet med alle to-element ordnede par av V i stedet for settet K i formelen ovenfor. Når det gjelder adjacency-matrisen A i grafen, hvis Q er adjacency-matrisen til den komplette grafen av det samme antall hjørner (dvs. alle oppføringene er enhet bortsett fra de diagonale oppføringene som er null), så er adjacency-matrisen til komplementet til A er QA .
Komplementet er ikke definert for multigrafier . I grafer som tillater selvløkker (men ikke flere adjacenser), kan komplementet til G defineres ved å legge til en selvløkke til hvert toppunkt som ikke har en i G , og ellers bruke samme formel som ovenfor. Denne operasjonen er imidlertid forskjellig fra den for enkle grafer, siden bruk av den på en graf uten selvløkker ville resultere i en graf med selvløkker på alle hjørner.
Søknader og eksempler
Flere grafteoretiske begreper er relatert til hverandre via komplementering:
- Komplementet til en kantløs graf er en komplett graf og omvendt.
- Enhver induserte sub-graf av komplement graf av en graf G er komplementet av den tilsvarende induserte sub-graf i G .
- Et uavhengig sett i en graf er en klikk i komplementgrafen og omvendt. Dette er et spesielt tilfelle av de to foregående egenskapene, da et uavhengig sett er en kantløs indusert subgraf og en klikk er en komplett indusert subgraf.
- Den automorphism gruppen av en graf er automorphism gruppen av sin komplement.
- Komplementet til hver trekantfrie graf er en klofri graf , selv om det motsatte ikke er sant.
Selvkomplementære grafer og grafklasser
En selvkomplementær graf er en graf som er isomorf til sitt eget komplement. Eksempler omfatter fire verteks bane graf og fem-toppunktet syklus graf . Det er ingen kjent karakterisering av selvkomplementære grafer.
Flere grafklasser er selvkomplementære, i den forstand at komplementet til en hvilken som helst graf i en av disse klassene er en annen graf i samme klasse.
- Perfekte grafer er grafene der det kromatiske tallet for hver indusert subgraf er lik størrelsen på den maksimale klikken. Det faktum at komplementet til en perfekt graf også er perfekt, er den perfekte grafsetningen til László Lovász .
- Cographs er definert som grafene som kan bygges opp fra enkelt hjørner ved usammenhengende forenings- og komplementeringsoperasjoner. De danner en selvkomplementær familie av grafer: komplementet til en hvilken som helst graf er en annen annerledes graf. For graver med mer enn ett toppunkt, er nøyaktig en graf i hvert komplementære par koblet sammen, og en ekvivalent definisjon av graver er at hver av deres tilkoblede induserte underbilder har et frakoblet komplement. En annen, selvkomplementær definisjon er at de er grafene uten indusert subgraf i form av en fire-spissbane.
- En annen selvkomplementær klasse av grafer er klassen av delte grafer , grafene der hjørnene kan deles inn i en klikk og et uavhengig sett. Den samme partisjonen gir et uavhengig sett og en klikk i komplementgrafen.
- Den terskel kurver er kurvene som er dannet ved gjentatte ganger å tilsette enten en selvstendig toppunkt (ett med ingen naboer) eller en universell toppunkt (ved siden av alle tidligere økende hjørner). Disse to operasjonene er komplementære, og de genererer en selvkomplementær klasse av grafer.
Algoritmiske aspekter
I analysen av algoritmer på grafer er skillet mellom en graf og dens komplement viktig, fordi en sparsom graf (en med et lite antall kanter sammenlignet med antall par i toppunktene) generelt ikke vil ha et sparsomt komplement. , og slik at en algoritme som tar tid proporsjonal med antall kanter på en gitt graf kan ta mye større tid hvis den samme algoritmen kjøres på en eksplisitt representasjon av komplementgrafen. Derfor har forskere studert algoritmer som utfører standard grafberegninger på komplementet til en inngangsgraf, ved å bruke en implisitt grafrepresentasjon som ikke krever eksplisitt konstruksjon av komplementgrafen. Spesielt er det mulig å simulere enten dybde-første søk eller bredde-første søk på komplementgrafen, i en tid som er lineær i størrelsen på den gitte grafen, selv når komplementgrafen kan ha en mye større størrelse . Det er også mulig å bruke disse simuleringene til å beregne andre egenskaper angående tilkoblingen til komplementgrafen.
