Komplementgraf
Inom det matematiska fältet för grafteorin är komplementet eller inversen av en graf G en graf H på samma hörn så att två distinkta hörn av H är intilliggande om och endast om de inte är intilliggande i G. Det vill säga, för att generera komplementet till en graf, fyller man i alla saknade kanter som krävs för att bilda en komplett graf och tar bort alla kanter som tidigare fanns där.
Komplementet är inte det fastställda komplementet till grafen; endast kanterna kompletteras.
Definition
Låt G = ( V , E ) vara en enkel graf och låt K bestå av alla 2-elements delmängder av V . Då H = ( V , K \ E ) komplementet till G , där K \ E är det relativa komplementet till E i K . För riktade grafer kan komplementet definieras på samma sätt, som en riktad graf på samma vertexuppsättning, genom att använda uppsättningen av alla 2-element ordnade par av V istället för mängden K i formeln ovan. När det gäller grafens närliggande matris A , om Q är närliggande matris för hela grafen med samma antal hörn (dvs alla poster är enhet utom de diagonala ingångarna som är noll), då närliggande matrisen för komplementet av A är QA .
Komplementet är inte definierat för multigrafer . I grafer som tillåter självslingor (men inte flera angränsningar) kan komplementet till G definieras genom att lägga till en självslinga till varje vertex som inte har en i G och i övrigt använda samma formel som ovan. Denna operation skiljer sig dock från den för enkla grafer, eftersom att tillämpa den på en graf utan självslingor skulle resultera i en graf med självslingor på alla hörn.
Tillämpningar och exempel
Flera grafteoretiska begrepp är relaterade till varandra via komplement:
- Komplementet till en kantlös graf är en komplett graf och vice versa.
- Varje inducerad subgraf av komplementgrafen i en graf G är komplementet till den motsvarande inducerade subgrafen i G .
- En oberoende uppsättning i en graf är en klick i komplementgrafen och vice versa. Detta är ett specialfall av de två föregående egenskaperna, eftersom en oberoende uppsättning är en kantlös inducerad subgraf och en klick är en komplett inducerad subgraf.
- Automorfismgruppen i en graf är automorfismgruppen av dess komplement .
- Komplementet av varje triangelfri graf är en klofri graf , även om det omvända inte är sant.
Självkompletterande grafer och grafklasser
En självkomplementär graf är en graf som är isomorf till sitt eget komplement. Exempel inkluderar kurvdiagrammet med fyra hörn och cykeldiagram med fem hörn . Det finns ingen känd karakterisering av självkomplementära grafer.
Flera klasser av grafer är självkomplementerande, i den meningen att komplementet till en graf i en av dessa klasser är en annan graf i samma klass.
- Perfekta grafer är de grafer där, för varje inducerad subgraf, det kromatiska talet är lika med storleken på den maximala klicken. Det faktum att komplementet till en perfekt graf också är perfekt är László Lovász ' perfekta grafsats .
- Kografer definieras som de grafer som kan byggas upp från enstaka hörn genom osammanhängande förenings- och komplementoperationer. De bildar en självkomplementär familj av grafer: komplementet till vilken kograf som helst är en annan annan kograf. För kografer av mer än en vertex är exakt en graf i varje komplementärt par kopplad, och en ekvivalent definition av kografer är att var och en av deras anslutna inducerade subgrafer har ett frånkopplat komplement. En annan, självkomplementär definition är att de är graferna utan inducerad subgraf i form av en väg med fyra vertex.
- En annan självkomplementär klass av grafer är klassen delade grafer , de grafer där hörnen kan delas upp i en klick och en oberoende uppsättning. Samma partition ger en oberoende uppsättning och en klick i komplementgrafen.
- Tröskelgraferna är de grafer som bildas genom att upprepade gånger lägga till antingen en oberoende vertex (en utan grannar) eller en universell vertex (intill alla tidigare tillagda hörn). Dessa två operationer är komplementära och de genererar en självkomplementär klass av grafer.
Algoritmiska aspekter
I analysen av algoritmer på grafer är skillnaden mellan en graf och dess komplement viktig, eftersom en gles graf (en med ett litet antal kanter jämfört med antalet hörnpar) i allmänhet inte kommer att ha ett gles komplement , och därför kan en algoritm som tar tid proportionell mot antalet kanter på en given graf ta mycket längre tid om samma algoritm körs på en explicit representation av komplementgrafen. Därför har forskare studerat algoritmer som utför standardgrafberäkningar på komplementet till en ingångsgraf, med hjälp av en implicit grafrepresentation som inte kräver den explicita konstruktionen av komplementgrafen. I synnerhet är det möjligt att simulera antingen djup-först-sökning eller bredd-första-sökning på komplementgrafen, under en tidsperiod som är linjär i storleken på den givna grafen, även när komplementgrafen kan ha en mycket större storlek . Det är också möjligt att använda dessa simuleringar för att beräkna andra egenskaper som rör komplementgrafens anslutningsbarhet.