Trapezformet graf

I grafteori er trapezformede grafer trapezformede skæringsgrafer , hvis parallelle sider ligger på to linjer. Denne klasse af grafer er indeholdt i klassen af grafer for samsammenlignelighed og indeholder intervalgrafer og permutationsgrafer som underklasser. En graf er trapezformet , hvis og kun hvis der er et sæt trapezoider svarende til grafens toppunkter, og to toppunkter på grafen er forbundet med en kant, hvis og kun hvis trapezerne svarende til toppunkterne skærer hinanden. Trapezformede grafer blev introduceret i 1988 af Ido Dagan, Martin Charles Golumbic og Ron Pinter. For disse grafer er der algoritmer med køretid til farvelægning af grafen, til at finde vægtede uafhængige sæt , klikdækninger og maksimalt vægtede kliker. ${O}(n\log n)$

Definition og karakteristika

Lad to parallelle linjer være givet. På disse linjer er der defineret trapezoider, hvor to hjørner ligger på den ene linje, og de to andre ligger på den anden linje. En graf er trapezformet , hvis og kun hvis der er et sæt trapezoider svarende til grafens toppunkter, og to toppunkter på grafen er forbundet med en kant, hvis og kun hvis trapezerne svarende til toppunkterne skærer hinanden. Dimensionen af et delvist ordnet sæt er det mindste antal d af komplette ordrer, således at . En poset-inkompatibilitetsgraf er en urettet graf , hvor et toppunkt x støder op til et toppunkt y i G, hvis og kun hvis x og y er uforlignelige i P. En urettet graf er en trapezformet graf, hvis og kun hvis det er uforligneligsgrafen for et delvist bestilt sæt med dimension højst 2. [1] $P=(X,<)$ ${\displaystyle P_{1}...P_{d))$ ${\displaystyle P=P_{1}\cap ...\cap P_{d))$ $P=(X,<)$ $G=(X,E)$

Ansøgninger

Problemerne med at finde maksimale kliker og farvelægge trapezformede grafer er relateret til problemet med at lægge ledende kanaler i designet af integrerede kredsløb . Hvis nogle mærkede punkter er sat på toppen og bunden af brættet, vil punkterne med de samme etiketter blive forbundet til et fælles netværk. Dette netværk kan repræsenteres af en trapez, der indeholder ekstreme (venstre og højre) punkter med samme etiket. Net kan udlægges uden krydsning, hvis og kun hvis trapezerne ikke krydser hinanden. Således er antallet af nødvendige lag nødvendige for at lægge ledere uden skæringspunkter lig med grafens kromatiske tal.

Tilsvarende repræsentationer

Repræsentation ved trapez

Trapezer kan bruges til at repræsentere en graf baseret på definitionen.

Repræsentation ved rektangler

Dominant boksrepræsentation viser punkter på én linje som punkter på x -aksen og punkter på den anden linje som punkter på y -aksen af det euklidiske plan. Så svarer enhver trapezoid til et rektangel i planet. I R K siges x at være domineret af y , som skrives som x < y hvis x i er mindre end y i for i = 1, …, k . Vi siger, at rektangel b dominerer b', hvis det nederste hjørne af b dominerer det øverste hjørne af b' . Vi siger, at to rektangler er sammenlignelige, hvis den ene dominerer den anden. Således skærer to trapezoider ikke nøjagtigt, når deres tilsvarende rektangler er sammenlignelige. Boksrepræsentationen er nyttig, fordi dominansrelationen gør det muligt at anvende udpakningsalgoritmen [2] Repræsentationen af grafen fra figur 1 i form af rektangler er vist i figur 3.

Bitolerante grafer

Bitolerante grafer er uforlignelige grafer af bitolerant orden. En rækkefølge siges at være bittolerant, hvis og kun hvis der er intervaller I x og reelle tal t 1 ( x ) og t r ( x ) tildelt hvert punkt x på en sådan måde, at x < y hvis og kun hvis når overlapningen af I x og I y er mindre end t r ( x ) og t 1 ( y ) og midten af I x er mindre end midten af I y . [3] I 1993 viste Langley, at afgrænsede bitolerante grafer svarer til klassen af trapezformede grafer. [fire]

Forholdet til andre familier af grafer

Klassen af trapezformede grafer indeholder intervalgrafer og permutationsgrafer og er ækvivalent med uforlignelige grafer for delvist ordnede rækkefølgedimensioner på højst to. Permutationsgrafer kan ses som et særligt tilfælde af trapezformede grafer, hvis trapezoider reduceres til linjer (det vil sige trapezoider med nul længder af parallelle sider).

Som alle uforlignelige grafer er trapezformede grafer perfekte .

Cirkulære trapezformede grafer

Cirkulære trapezformede grafer er en klasse af grafer foreslået af Felsner et al. i 1993. Disse grafer er en superklasse af trapezformede grafer og indeholder cirkulerende grafer og cirkelbuegrafer. Et cirkulært trapez er området af en cirkel mellem to ikke-skærende akkorder, og en cirkulær trapezgraf er skæringsgrafen for familien af cirkulære trapezoider. En cirkulær fremstilling af grafen er vist i figur 4. Der er en algoritme med køretid til løsning af problemet med at finde et uafhængigt sæt af maksimal vægt og en algoritme med køretid til problemet med at finde en klike med maksimal vægt. $O(n^{2})$ ${O}(n^{2}\log n)$

k -trapezformede grafer

k - trapezformede grafer er en generalisering af trapezformede grafer til højere dimensioner af rummet. De blev foreslået af Felsner og er baseret på definitionen af dominerende multidimensionelle rektangler. I disse grafer svarer toppunktet x til vektoren . Ved at bruge ( k − 1)-dimensionelle sorteringstræer til at gemme og hente koordinater løser Felsners algoritmer problemerne med at finde det kromatiske tal, maksimale klike og maksimale uafhængige sæt i tid . $(x_{1},\ldots,x_{k})$ ${O}(n\log ^{k-1}n)$

Algoritmer

Algoritmer for trapezformede grafer bør sammenlignes med algoritmer for mere generelle grafer for samsammenlignelighed. Til dette kan en bredere klasse af grafer, problemerne med at finde det maksimale uafhængige sæt og den minimale klikdækning løses i tide . [5] Dagan et al foreslog først en algoritme til farvning af trapezformede grafer i tid , hvor n er antallet af hjørner og k er det kromatiske tal på grafen. Senere, ved hjælp af rektangelrepræsentationen af trapezformede grafer, publicerede Felsner algoritmer til at finde det kromatiske tal, vægtede uafhængige sæt, klikdækning og maksimalt vægtet klik i tid . Alle disse algoritmer kræver en hukommelsesstørrelse på . Disse algoritmer er baseret på dominansen af repræsentationen ved hjælp af rektangler, hvilket tillader brugen af udpakningsalgoritmer. Algoritmerne foreslået af Felsner bruger balancerede træer, som gør det muligt at udføre indsættelse, sletning og forespørgselsoperationer i tide , hvilket giver den resulterende tid . ${O}(n^{2}\log n)$ ${O}(nk)$ ${O}(n\log n)$ ${O}(n)$ ${O}(\log n)$ ${O}(n\log n)$

Anerkendelse

For at afgøre, om en graf er trapezformet, leder man efter en transitiv orientering på grafens komplement . Da trapezformede grafer er en delmængde af grafer, der kan sammenlignes, skal dens komplement være en sammenlignelighedsgraf, hvis den er trapezformet. Hvis en transitiv orientering på komplementet ikke eksisterer, er grafen ikke trapezformet. Hvis den findes, kontrolleres det, om rækkefølgen angivet af den trapezformede rækkefølge vil være. Den hurtigste keystone-genkendelsesalgoritme blev foreslået af McConnell og Spinrad i 1994 med køretid . Processen reducerer spørgsmålet om dimensionen af en delordre (om den overstiger 2) til problemet med at dække den tilsvarende todelte graf med kæder (grafer uden genererede 2K 2 - undergrafer). [6] Som vist af Mertzios og Corneil kan problemet med at genkende trapezformede grafer løses i tid , hvor der angives antallet af kanter, hvis der anvendes toppunktsadskillelse. Denne proces bruger at udvide en given graf og derefter transformere den udvidede graf ved at erstatte alle de oprindelige hjørner i grafen med et par nye hjørner. Denne "delte graf" er en permutationsgraf med specielle egenskaber, hvis og kun hvis den er trapezformet. [7] ${G}$ ${F}$ ${G}$ ${G}$ ${\displaystyle {G'))$ ${F}$ ${\displaystyle {G'))$ ${G}$ ${F}$ ${F}$ $O(n^{2})$ $O(n(n+m))$ $m$ ${G}$ ${G}$

Noter

↑ Ido Dagan, Martin Charles Golumbic og Ron Yair Pinter. Trapezgrafer og deres farvning. Diskret Apple. Math., 35-46, 1988.
↑ Stefan Felsner, Rudolf Muller og Lorenz Wernisch. Trapezgrafer og generaliseringer, geometri og algoritmer. I Algorithm theory—SWAT '94 (Aarhus, 1994), bind 824 af Lecture Notes in Comput. Sci., side 143-154. Springer, Berlin, 1994.
↑ Kenneth P. Bogart, Garth Isaak. Korrekte og enhedsbitoleranceordrer og grafer. Diskret matematik 181(1-3): 37-51 (1998).
↑ Martin Charles Golumbic og Irith B.-A. Hartman, red., Graph Theory, Combinatorics and Algorithms: Interdisciplinary Applications, Springer-Verlag, New York, 2005
↑ R. McConnel og J. Spinrad, Lineær-tids modulær dekomponering og effektiv transitiv orientering af urettede grafer, Proc. 5. Ann. Symp. på Discr. Alg. (1994).
↑ Golumbic, Martin Charles., og Ann N. Trenk. Tolerance grafer. Cambridge [ua: Cambridge Univ., 2004.
↑ G. B. Mertzios og D. G. Corneil. Vertex-opdeling og genkendelse af trapezformede grafer. Discrete Applied Mathematics, 159(11), side 1131-1147, 2011.