Delad graf - Split graph
I grafteori , en gren av matematik, är en delad graf en graf i vilken topparna kan delas upp i en klick och en oberoende uppsättning . Delade grafer studerades först av Földes och Hammer ( 1977a , 1977b ) och introducerades oberoende av Tyshkevich och Chernyak ( 1979 ).
En delad graf kan ha mer än en partition i en klick och en oberoende uppsättning; till exempel är banan a - b - c en delad graf, vars hörn kan delas upp på tre olika sätt:
- klicket { a , b } och den oberoende uppsättningen { c }
- klicket { b , c } och den oberoende uppsättningen { a }
- klicken { b } och den oberoende uppsättningen { a , c }
Delade grafer kan karakteriseras i termer av deras förbjudna inducerade underbilder : ett diagram delas om och endast om inget inducerat subgraf är en cykel på fyra eller fem hörn, eller ett par ojämna kanter (komplementet till en 4-cykel).
Förhållande till andra diagramfamiljer
Från definitionen är delade grafer tydligt stängda under komplement . En annan karakterisering av delade grafer involverar komplemente: de är ackord grafer de komplementen av som också ackord. Precis som ackorddiagram är korsningsdiagrammen för trädens träd, så är delade grafer korsningsdiagrammen för distinkta substjärnor till stjärndiagram . Nästan alla ackorddiagram är delade grafer; det vill säga, i gränsen när n går till oändligheten, närmar sig fraktionen av n- vertexkorddiagram som delas upp en.
Eftersom ackorddiagram är perfekta , så är delade grafer också. De dubbla delade graferna , en familj av grafer som härrör från delade grafer genom att fördubbla varje toppunkt (så klicket kommer att framkalla en antimatchning och den oberoende uppsättningen kommer att inducera en matchning), framträdande framträdande som en av fem grundläggande klasser av perfekta grafer från vilka alla andra kan bildas i beviset av Chudnovsky et al. (2006) av Strong Perfect Graph Theorem .
Om ett diagram både är ett delat diagram och ett intervalldiagram , är dess komplement både ett delat diagram och ett jämförelsediagram , och vice versa. Diagrammen för delad jämförbarhet, och därför också delningsintervalldiagrammen, kan karakteriseras i termer av en uppsättning av tre förbjudna inducerade underbilder. De delade graferna är exakt tröskeldiagrammen . Delad permutationsdiagram är exakt intervalldiagrammen som har komplement för intervalldiagram; dessa är permutationsdiagrammen för skev sammanslagna permutationer . Delade grafer har kochromatiskt nummer 2.
Algoritmiska problem
Låt G vara en delad graf, fördelades in i en klick C och en oberoende uppsättning jag . Då varje maximal klick i en delad diagram antingen C själv, eller närheten av ett hörn i jag . Således är det enkelt att identifiera den maximala klicken och komplettera den maximala oberoende uppsättningen i en delad graf. I alla delade diagram måste en av följande tre möjligheter vara sant:
- Det finns ett vertex x i I så att C ∪ { x } är komplett. I detta fall är C ∪ { x } en maximal klick och jag är en maximal oberoende uppsättning.
- Det finns ett vertex x i C så att I ∪ { x } är oberoende. I det här fallet är I ∪ { x } en maximal oberoende uppsättning och C är en maximal klick.
- C är en maximal klick och jag är en maximal oberoende uppsättning. I det här fallet har G en unik partition ( C , I ) till en klick och en oberoende uppsättning, C är den maximala klicken och jag är den maximala oberoende uppsättningen.
Några andra optimeringsproblem som är NP-kompletta i mer generella graffamiljer, inklusive graffärgning , är lika enkla för delade grafer. Att hitta en Hamilton-cykel förblir NP-komplett även för delade grafer som är starkt ackorddiagram . Det är också känt att problemet med minsta dominerande uppsättning förblir NP-komplett för delade grafer.
Gradsekvenser
En anmärkningsvärd egenskap hos delade grafer är att de endast kan kännas igen från deras gradssekvenser . Låt gradsekvensen för ett diagram G vara d 1 ≥ d 2 ≥ ... ≥ d n , och låt m vara det största värdet av i så att d i ≥ i - 1. Då är G en delad graf om och bara om
Om så är fallet bildar m- hörn med de största graderna en maximal klick i G , och de återstående hörnpunkterna utgör en oberoende uppsättning.
Räknar delade grafer
Royle (2000) visade att n- vertikala delade grafer med n är i en-till-en-korrespondens med vissa Sperner-familjer . Med hjälp av detta faktum bestämde han en formel för antalet icke-isomorfa delade grafer på n hörn. För små värden på n , med början från n = 1, är dessa siffror
Detta uppräkningsresultat bevisades också tidigare av Tyshkevich & Chernyak (1990) .
Anteckningar
Referenser
- Bender, EA; Richmond, LB; Wormald, NC (1985), "Nästan alla ackorddiagram delas", J. Austral. Matematik. Soc. , A, 38 (2): 214-221, doi : 10.1017 / S1446788700023077 , MR 0770128.
- Bertossi, Alan A. (1984), "Dominerande uppsättningar för delade och bipartitdiagram", Information Processing Letters , 19 : 37–40, doi : 10.1016 / 0020-0190 (84) 90126-1.
- Brandstädt, Andreas ; Le, Van Bang; Spinrad, Jeremy (1999), Grafklasser: A Survey , SIAM Monographs on Discrete Mathematics and Applications, ISBN 0-89871-432-X.
- Chudnovsky, Maria ; Robertson, Neil ; Seymour, Paul ; Thomas, Robin (2006), "The strong perfect graph theorem", Annals of Mathematics , 164 (1): 51–229, arXiv : math / 0212070 , doi : 10.4007 / annals.2006.164.51 , MR 2233847.
- Földes, Stéphane; Hammer, Peter Ladislaw (1977a), "Delade grafer", Proceedings of the Eight Southeastern Conference on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, La., 1977) , Congressus Numerantium, XIX , Winnipeg: Utilitas Math ., s. 311–315, MR 0505860.
- Földes, Stéphane; Hammer, Peter Ladislaw (1977b), "Delade grafer med Dilworth nummer två", Canadian Journal of Mathematics , 29 (3): 666–672, doi : 10.4153 / CJM-1977-069-1 , MR 0463041.
- Golumbic, Martin Charles (1980), algoritmisk grafteori och perfekta grafer , Academic Press, ISBN 0-12-289260-7, MR 0562306.
- Hammer, Peter Ladislaw ; Simeone, Bruno (1981), "The splittance of a graph", Combinatorica , 1 (3): 275–284, doi : 10.1007 / BF02579333 , MR 0637832.
- Kézdy, André E .; Snevily, Hunter S .; Wang, Chi (1996), "Partitionering av permutationer till ökande och minskande sekvenser", Journal of Combinatorial Theory , serie A , 73 (2): 353–359, doi : 10.1016 / S0097-3165 (96) 80012-4 , MR 1370138.
- McMorris, FR; Shier, DR (1983), "Representerar ackorddiagram på K 1, n ", Kommentarer Mathematicae Universitatis Carolinae , 24 : 489–494, MR 0730144.
- Merris, Russell (2003), "Split grafer", European Journal of Combinatorics , 24 (4): 413–430, doi : 10.1016 / S0195-6698 (03) 00030-1 , MR 1975945.
- Müller, Haiko (1996), "Hamiltonian Circuits in Chordal Bipartite Graphs", Discrete Mathematics , 156 : 291–298, doi : 10.1016 / 0012-365x (95) 00057-4.
- Royle, Gordon F. (2000), "Counting set covers and split charts" (PDF) , Journal of Integer Sequences , 3 (2): 00.2.6, MR 1778996.
- Tyshkevich, Regina I. (1980), "[Den kanoniska nedbrytningen av en graf]", Doklady Akademii Nauk SSSR (på ryska), 24 : 677–679, MR 0587712
- Tyshkevich, Regina I .; Chernyak, AA (1979), "Kanonisk partition av en graf definierad av graderna på dess hörn", Isv. Akad. Nauk BSSR, Ser. Fiz.-matta. Nauk (på ryska), 5 : 14–26, MR 0554162.
- Tyshkevich, Regina I .; Chernyak, AA (1990),Еще один метод перечисления непомеченных комбинаторных объеstances, Mat. Zametki (på ryska), 48 (6): 98–105, MR 1102626. Översatt som "Ytterligare en annan metod för att räkna upp omärkta kombinatoriska föremål" (1990), Matematisk tonerna i Academy of Sciences i Sovjetunionen 48 (6): 1239-1245, doi : 10,1007 / BF01240267 .
- Tyshkevich, Regina I .; Melnikow, OI; Kotov, VM (1981), "Om grafer och gradssekvenser: den kanoniska nedbrytningen", Kibernetika (på ryska), 6 : 5–8, MR 0689420.
- Voss, H.-J. (1985), "Note on a paper of McMorris and Shier", Kommentarer Mathematicae Universitatis Carolinae , 26 : 319–322, MR 0803929.
Vidare läsning
- Ett kapitel om delade grafer visas i boken av Martin Charles Golumbic , " Algorithmic Graph Theory and Perfect Graphs".