Trapetsformad graf

I grafteorin är trapetsformade grafer trapetsformade skärningsdiagram , vars alla parallella sidor ligger på två linjer. Denna klass av grafer ingår i klassen med grafer för samjämförbarhet och innehåller intervallgrafer och permutationsgrafer som underklasser. En graf är trapetsformad om och endast om det finns en uppsättning trapetser som motsvarar grafens hörn, och två hörn i grafen är sammankopplade med en kant om och endast om trapetserna som motsvarar hörnen skär varandra. Trapetsformade grafer introducerades 1988 av Ido Dagan, Martin Charles Golumbic och Ron Pinter. För dessa grafer finns det algoritmer med körtid för färgläggning av grafen, för att hitta viktade oberoende uppsättningar , klicktäckningar och maximalt viktade klick. ${O}(n\log n)$

Definition och egenskaper

Låt två parallella linjer ges. På dessa linjer definieras trapetser, där två hörn ligger på en linje, och de andra två ligger på den andra linjen. En graf är trapetsformad om och endast om det finns en uppsättning trapetser som motsvarar grafens hörn, och två hörn i grafen är sammankopplade med en kant om och endast om trapetserna som motsvarar hörnen skär varandra. Dimensionen för en partiellt beställd uppsättning är det minsta antalet d av kompletta beställningar så att . En poset-inkompatibilitetsgraf är en oriktad graf där en vertex x ligger intill en vertex y i G om och endast om x och y är oförlikbara i P. En oriktad graf är en trapetsformad graf om och endast om det är injämförbarhetsgrafen för ett delvis beställt set med dimension högst 2. [1] $P=(X,<)$ ${\displaystyle P_{1}...P_{d))$ ${\displaystyle P=P_{1}\cap ...\cap P_{d))$ $P=(X,<)$ $G=(X,E)$

Applikationer

Problemen med att hitta maximala klicker och färga trapetsformade grafer är relaterade till problemet med att lägga ledande kanaler i designen av integrerade kretsar . Om några märkta punkter är inställda på kortets övre och nedre sidor kommer punkterna med samma etiketter att kopplas till ett gemensamt nätverk. Detta nätverk kan representeras av en trapets som innehåller extrema (vänster och höger) punkter med samma etikett. Nät kan läggas utan korsning om och endast om trapetserna inte skär varandra. Således är antalet nödvändiga lager som behövs för att lägga ledare utan skärningspunkter lika med grafens kromatiska nummer.

Motsvarande representationer

Representation av trapetser

Trapetser kan användas för att representera en graf, baserat på definitionen.

Representation av rektanglar

Dominant boxrepresentation visar punkter på en linje som punkter på x -axeln och punkter på den andra linjen som punkter på y -axeln i det euklidiska planet. Då motsvarar vilken trapets som helst en rektangel i planet. I R K sägs x domineras av y , vilket skrivs som x < y om x i är mindre än y i för i = 1, …, k . Vi säger att rektangeln b dominerar b' om det nedre hörnet av b dominerar det övre hörnet av b' . Vi säger att två rektanglar är jämförbara om den ena dominerar den andra. Två trapetser skär sig alltså inte exakt när deras motsvarande rektanglar är jämförbara. Lådrepresentationen är användbar eftersom dominansrelationen tillåter att uppackningsalgoritmen tillämpas [2] Representationen av grafen från figur 1 i form av rektanglar visas i figur 3.

Bitoleranta grafer

Bitoleranta grafer är ojämförbarhetsgrafer av bitolerant ordning. En ordning sägs vara bittolerant om och endast om det finns intervall I x och reella tal t 1 ( x ) och t r ( x ) tilldelade varje punkt x på ett sådant sätt att x < y om och endast om när överlappningen av I x och I y är mindre än t r ( x ) och t 1 ( y ) och mitten av I x är mindre än mitten av I y . [3] 1993 visade Langley att gränsade bitoleranta grafer är ekvivalenta med klassen av trapetsformade grafer. [fyra]

Släktskap med andra graffamiljer

Klassen av trapetsformade grafer innehåller intervallgrafer och permutationsgrafer och är ekvivalent med ojämförbarhetsgraferna för partiellt ordnade uppsättningar av ordningsdimension som högst två. Permutationsgrafer kan ses som ett specialfall av trapetsformade grafer om trapetser reduceras till linjer (det vill säga trapetser med noll längder på parallella sidor).

Som alla ojämförlighetsgrafer är trapetsformade grafer perfekta .

Cirkulära trapetsformade grafer

Cirkulära trapetsformade grafer är en klass av grafer som föreslagits av Felsner et al 1993. Dessa grafer är en superklass av trapetsformade grafer och innehåller cirkulerande grafer och cirkelbågsgrafer. En cirkulär trapets är området av en cirkel mellan två icke-korsande ackord, och en cirkulär trapetsform är skärningsdiagrammet för familjen av cirkulära trapetser. En cirkulär representation av grafen visas i figur 4. Det finns en algoritm med gångtid för att lösa problemet med att hitta en oberoende uppsättning av maximal vikt och en algoritm med löptid för problemet att hitta en klick med maximal vikt. $O(n^{2})$ ${O}(n^{2}\log n)$

k -trapesformade grafer

k - trapetsformade grafer är en generalisering av trapetsformade grafer till högre dimensioner av rymden. De föreslogs av Felsner och är baserade på definitionen av dominerande flerdimensionella rektanglar. I dessa grafer motsvarar vertex x vektorn . Genom att använda ( k − 1)-dimensionella sorteringsträd för att lagra och hämta koordinater, löser Felsners algoritmer problemen med att hitta det kromatiska talet, maximal klick och maximal oberoende uppsättning i tid . $(x_{1},\ldots,x_{k})$ ${O}(n\log ^{k-1}n)$

Algoritmer

Algoritmer för trapetsformade grafer bör jämföras med algoritmer för mer generella grafer för samjämförbarhet. För detta kan en bredare klass av grafer, problemen med att hitta den maximala oberoende uppsättningen och den minsta klicktäckningen lösas i tid . [5] Dagan et al föreslog först en algoritm för att färga trapetsformade grafer i tid , där n är antalet hörn och k är det kromatiska numret på grafen. Senare, med hjälp av rektangelrepresentationen av trapetsformade grafer, publicerade Felsner algoritmer för att hitta det kromatiska numret, viktad oberoende uppsättning, klicktäckning och maximal viktad klick i tid . Alla dessa algoritmer kräver en minnesstorlek på . Dessa algoritmer är baserade på dominansen av representationen av rektanglar, vilket gör det möjligt att använda avvecklingsalgoritmer. Algoritmerna som föreslagits av Felsner använder balanserade träd, som gör att insättning, radering och frågeoperationer kan utföras i tid , vilket ger den resulterande tiden . ${O}(n^{2}\log n)$ ${O}(nk)$ ${O}(n\log n)$ ${O}(n)$ ${O}(\log n)$ ${O}(n\log n)$

Erkännande

För att avgöra om en graf är trapetsformad, letar man efter en transitiv orientering på grafens komplement . Eftersom trapetsformade grafer är en delmängd av medjämförbara grafer, om den är trapetsformad, måste dess komplement vara en jämförbarhetsgraf. Om en transitiv orientering på komplementet inte existerar är grafen inte trapetsformad. Om det hittas kontrolleras det om den ordning som anges av den trapetsformade ordningen kommer att vara. Den snabbaste keystone-igenkänningsalgoritmen föreslogs av McConnell och Spinrad 1994 med körtid . Processen reducerar frågan om dimensionen av en delorder (om den överstiger 2) till problemet med att täcka motsvarande tvådelade graf med kedjor (grafer utan genererade 2K 2 subgrafer). [6] Som visat av Mertzios och Corneil, om vertexseparation används, kan problemet med att känna igen trapetsformade grafer lösas i tiden , där anger antalet kanter. Denna process använder sig av att expandera en given graf och sedan transformera den expanderade grafen genom att ersätta alla de ursprungliga hörnen i grafen med ett par nya hörn. Denna "delade graf" är en permutationsgraf med speciella egenskaper om och endast om den är trapetsformad. [7] ${G}$ ${F}$ ${G}$ ${G}$ ${\displaystyle {G'))$ ${F}$ ${\displaystyle {G'))$ ${G}$ ${F}$ ${F}$ $O(n^{2})$ $O(n(n+m))$ $m$ ${G}$ ${G}$

Anteckningar

↑ Ido Dagan, Martin Charles Golumbic och Ron Yair Pinter. Trapetsdiagram och deras färg. Diskret Apple. Math., 35–46, 1988.
↑ Stefan Felsner, Rudolf Muller och Lorenz Wernisch. Trapetsgrafer och generaliseringar, geometri och algoritmer. In Algorithm theory—SWAT '94 (Aarhus, 1994), volym 824 av Lecture Notes in Comput. Sci., sidorna 143–154. Springer, Berlin, 1994.
↑ Kenneth P. Bogart, Garth Isaak. Korrekt och enhetlig bitoleransordningar och grafer. Diskret matematik 181(1–3): 37–51 (1998).
↑ Martin Charles Golumbic och Irith B.-A. Hartman, red., Graph Theory, Combinatorics and Algorithms: Interdisciplinary Applications, Springer-Verlag, New York, 2005
↑ R. McConnel och J. Spinrad, Linear-time modular decomposition and efficient transitive orientation of undirected graphs, Proc. 5. Ann. Symp. på Discr. Alg. (1994).
↑ Golumbic, Martin Charles. och Ann N. Trenk. Toleransgrafer. Cambridge [ua: Cambridge Univ., 2004.
↑ G. B. Mertzios och D. G. Corneil. Vertexdelning och igenkänning av trapetsformade grafer. Discrete Applied Mathematics, 159(11), sidorna 1131-1147, 2011.

Länkar

Martin Charles Golumbic. Algoritmisk grafteori och perfekta grafer. — Academic Press, 1980. Andra upplagan, Annals of Discrete Mathematics 57, Elsevier, 2004.