Book investering

En bogindlejring i grafteori  er en generalisering af en plan indlejring af en graf til en indlejring i en bog  - et sæt halvplaner , der har den samme rette linje som en grænse. Det kræves normalt, at grafens toppunkter ligger på denne grænse, og kanterne skal være inden for samme side. Bogtykkelsen (eller antallet af sider ) af en graf er det mindste antal halvplaner for alle bogindlejringer af grafen. [1] Bogindlejring bruges til flere andre grafinvarianter , herunder sidebredde [2] og bogantal af krydser [3] .

Enhver graf med n toppunkter har højst en bogbredde . Denne grænse er tæt for komplette grafer [1] . Dog kan underinddeling af hver kant reducere bogens tykkelse til en mængde, der er proportional med kvadratroden af ​​n . [4] Grafer med bogtykkelse en er udvendige grafer , [1] og grafer med bogtykkelse højst to er sub-Hamiltonske , som altid er plane [2] . Enhver plan graf har en bogtykkelse, der ikke overstiger fire [5] . Alle mindre lukkede familier af grafer , og især grafer med afgrænset træbredde eller afgrænset slægt , har også afgrænset bogtykkelse [6] . At bestemme den nøjagtige bogtykkelse af en given graf er et NP-hårdt problem , uanset om rækkefølgen af ​​hjørnerne på rygsøjlen er kendt eller ej [7] [8] .

En af de første grunde til at studere bognesting var dens anvendelse i VLSI-design , hvor bognesting-hjørner repræsenterer komponenter og kanter repræsenterer forbindelser mellem komponenter [7] [9] . Når du visualiserer grafer, kan to standardstile af grafrepræsentation, buediagrammer [10] og cirkulære arrangementer [11] bygges ved hjælp af bogindlejring. De forskellige start- og slutpunkter for trafikken for fodgængere og køretøjer, der er reguleret af et lyskryds, kan modelleres matematisk som grafhjørnepunkter, med kanter, der repræsenterer start-ende-par, og bogens indlejring af denne graf kan bruges til at skabe et trafiklys adfærd for at give trafikregulering med minimalt antal lyskrydstilstande [12] . I bioinformatikproblemer , der beskæftiger sig med RNA- strukturer , repræsenterer en en-sides bogindlejring den klassiske form af en nukleinsyresekundær struktur , og en to-siders indlejring repræsenterer pseudoknoter [13] . Bogindlejring bruges også i generel algebra [14] og knudeteori [15] [16] .

De åbne spørgsmål vedrørende boginvestering er

Historie

Navnet "bog" blev introduceret af Persinger og Atneosen (CA Persinger, Gail Atneosen) i 1960'erne [21] [22] [23] . Atneosen havde allerede brugt indlejring af grafer i bøger, men det formelle koncept med bogindlejring blev formuleret af C. Kainen og L. Taylor Ollman i begyndelsen af ​​1970'erne, og der blev tilføjet nogle yderligere begrænsninger for indlejringsmetoden - i deres formulering, grafens hjørner skal ligge på rygraden af ​​en bog, hver kant skal ligge på én side (skær ikke rygraden) og to kanter krydser kun ved fælles endespidser [24] [25] .

Vigtige milepæle i den videre udvikling af bogindlejring er Michalis Giannakakis ' bevis i slutningen af ​​1980'erne på, at bogens tykkelse af plane grafer ikke overstiger fire [26] [5] , og opdagelsen i slutningen af ​​1990'erne af et tæt forhold mellem bog indlejring og bioinformatik . [13]

Definitioner

En bog er en særlig form for topologisk rum (også kaldet en fan halvplaner) [21] [27] . Den består af en enkelt lige linje ℓ kaldet bogens rygrad [28] sammen med et sæt af et eller flere halvplaner kaldet bogens sider eller blade . Hvert halvplan skal have den samme linje ℓ som sin grænse. Bøger med et endeligt antal ( k ) sider kan indlejres i tredimensionelt rum, for eksempel ved at vælge et rektangulært koordinatsystem som linjen ℓ på z - aksen og som den i - de side (af k ) en kan tage et sæt punkter p , således at det korteste segment , der forbinder p med z -aksen , har en vinkel på 2π i / k i forhold til xz -planet [1] .

Visualiseringen af ​​en bog med endelig graf G i bog B er en tegning af graf G i B , således at ethvert toppunkt af G tegnes på rygrad B , og enhver kant af G tegnes som en kurve, der ligger inden for en side af B. Det k -sides bognummer af skæringspunkter i en graf G  er det mindste antal skæringspunkter i en tegning på en k -sidet bog [3] .

En bogindlejring af en graf G i B  er en indlejring af en graf G i et mellemrum B. Det vil sige, at det er en tegning af en graf G i B , hvor kanterne ikke skærer hinanden. Enhver finit graf har en bog indlejret i en bog med et tilstrækkeligt stort antal sider. For eksempel er det altid muligt at indlejre hver kant på sin egen side. Bogens tykkelse , antallet af sider eller stakantallet af graf G er  det mindste antal sider, der kræves for en bogindlejring af graf G. En anden parameter, der måler kvaliteten af ​​en vedhæftet bog, udover antallet af sider, er sidebredde . Dette er det maksimale antal kanter, der krydser strålen vinkelret på rygsøjlen inde på en enkelt side. Tilsvarende (for bogindlejringer, hvor hver kant er tegnet som en monoton kurve), er dette den maksimale størrelse af en undergruppe af kanter, således at intervallerne defineret på rygraden af ​​kanternes endepunkter alle skærer [2] [29] [30] .

Det er væsentligt for disse definitioner, at kanterne kun kan ligge på én side. Som Ameosen allerede har bemærket, hvis kanterne kan gå fra side til side (gennem ryggen), så kan enhver graf indlejres i en tre-siders bog [22] [31] [20] . Men for en tre-siders topologisk bogindlejring , hvor rygskæring er tilladt, er det fortsat et interessant problem at bestemme det mindste rygskæringsnummer, der tillader grafen at blive indlejret i en bog [20] [32] .

Specifikke grafer

Som vist i den første figur er bogtykkelsen af ​​den komplette graf tre. Fordi den er ikke-plan, er dens bogtykkelse større end to, men der er en bogindlejring med tre sider. Bogtykkelsen af ​​enhver komplet vertexgraf er nøjagtig . Dette resultat giver en øvre grænse for den maksimale bogtykkelse af enhver graf med hjørner [1] . Det to-siders skæringsnummer for den komplette graf er

hvilket er i overensstemmelse med Anthony Hills ubeviste formodning . Det vil sige, at hvis Hills formodning er sand, så er tegningen af ​​denne graf, der minimerer antallet af skæringspunkter, en to-siders tegning [33] .

Tykkelsen af ​​bogen af ​​en komplet todelt graf er næsten ens  - for hvert hjørne af en mindre del kan du arrangere kanterne, der falder ind på disse hjørner på deres egen side. Denne grænse er ikke altid streng. For eksempel har den en bogtykkelse på tre, ikke fire. Men når de to sider af grafen er meget ubalancerede, c , er bogens tykkelse nøjagtig . [1] [34] Tykkelsen af ​​bøgerne med binære de Bruijn -grafer, blandede udvekslingsgrafer og kubiske netværk med cyklusser (når disse grafer er store nok til ikke at være plane) er nøjagtig tre. [35]

Egenskaber

Underinddelingsadfærd

Uløste problemer i matematik : Kan en grafs bogtykkelse begrænses af en funktion af bogtykkelsen af ​​underinddelinger?

At opdele hver kant af en graf i to-kantede baner ved at tilføje nye hjørner for hver kant kan nogle gange øge tykkelsen af ​​bogen (for eksempel har en diamant en bogtykkelse på én, men dens underinddeling har en bogtykkelse på to). En sådan underpartition kan dog også reducere grafens bogtykkelse betydeligt efter partitionen. For eksempel er bogtykkelsen af ​​en komplet graf K n er Θ( n ) proportional med antallet af dens hjørner, men opdeling af hver kant i to giver en underinddeling med en meget mindre bogtykkelse, kun O(√ n ). [4] . På trods af eksistensen af ​​eksempler som det ovenfor, formodede Blankenship og Oporowski [31] , at bogtykkelsen af ​​underinddelinger ikke kan være væsentligt mindre end den oprindelige graf. Især antog de, at der er en funktion f , som for enhver graf G og graf H opnået ved at erstatte hver kant af G med en bane med to kanter, hvis bogtykkelsen af ​​graf H er t , så bogtykkelsen af ​​grafen G overstiger ikke f ( t ). [31] I 2013 forblev Blankenship-Oporowski-formodningen ubevist. [17]

Planaritet og ydre planaritet

Bogtykkelsen af ​​en given graf G overstiger ikke 1, hvis og kun hvis G er udvendig plan . En ydreplanær graf er en graf, der har en plan indlejring, hvor alle hjørner hører til den ydre flade af indlejringen. For sådanne grafer giver placering af hjørnerne i samme rækkefølge langs rygsøjlen, som de vises på den ydre flade (når et knudepunkt dukker op på den ydre flade, kun én kopi af spidsen), en grafindlejring på én side. Omvendt er en bogindlejring på én side automatisk outerplanar - hvis grafen er indlejret på én side, giver tilføjelse af et andet halvplan et fuldt plan, og den ydre flade vil indeholde hele det tilføjede halvplan, med alle hjørner liggende på denne ydre flade [1] [2] .

Enhver bogindlejring med to sider er et specialtilfælde af en plan indlejring, da foreningen af ​​to bogsider er et rum, der topologisk svarer til et plan. Enhver graf med bogtykkelse to er således automatisk plan . Mere præcist er bogtykkelsen af ​​en graf G højst to, hvis og kun hvis G er en undergraf til en plan graf, der har en Hamiltonsk cyklus [1] . Givet en graf med en bogindlejring på to sider, kan grafen udvides til en plan Hamiltonsk graf ved at tilføje (på en hvilken som helst side) yderligere kanter mellem to på hinanden følgende hjørner langs rygsøjlen, hvis de ikke allerede er forbundet med en kant, og mellem rygsøjlens første og sidste toppunkt. Goldner-Harari grafen giver et eksempel på en plan graf, der ikke har bogtykkelse to - det er en maksimal plan graf , så det er umuligt at tilføje nogen kant, mens planheden bevares, og grafen har ikke en Hamiltonian cyklus [1] . På grund af kravet om at have Hamiltonske cyklusser er grafer, der tillader to-siders indlejring, kendt som sub-Hamiltonske grafer [2] .

Alle plane grafer med maksimal grad på højst fire har en bogindlejringsdybde på højst to. [36] . Plane 3-trees har en maksimal bogbredde på tre [37] . Alle plane grafer har en bogtykkelse, der ikke overstiger fire [26] [5] . Som Michalis Yannakakis udtalte i 1986 [26] , er der plane grafer med en bogindlejringstykkelse nøjagtigt lig med fire, men et detaljeret bevis for denne påstand, annonceret i [5] , er aldrig blevet offentliggjort. Af denne grund markerede Duimovich [19] problemet med at bestemme den maksimale tykkelse af en bogindlejring af plane grafer som uløst [19] .

Forholdet til andre grafinvarianter

Bogens tykkelse er relateret til tykkelsen af ​​grafen , antallet af plane grafer, der er nødvendige for at dække kanterne på en given graf. En graf G har tykkelsen θ, hvis den kan indlejres i et plan, og kanterne kan farves i θ-farver på en sådan måde, at kanter af samme farve ikke skærer hinanden. Tilsvarende har en graf G bogbredde θ, hvis den kan tegnes i et halvplan med spidser på grænsen af ​​halvplanet og kantfarvet i θ farver uden at krydse kanter af samme farve. Med denne formulering svarer kanterne af samme farve til siderne i bogens bilag. Tykkelsen af ​​grafen og tykkelsen af ​​bogen kan dog variere betydeligt - der er opdelinger af komplette grafer , der har en ubegrænset bogtykkelse [31] [20] [4] , på trods af at tykkelsen af ​​grafen er ens til to [4] .

Grafer med træbredde k har højst en bogbredde k + 1 [19] [38] og denne grænse nås for k > 2. [19] . Grafer med m kanter har bogbredde O(√ m ) [39] , og grafer med slægt g har  bogbredde O(√ g ) [40] . Mere generelt har enhver mindre lukket familie af grafer en afgrænset bogtykkelse [6] [41] .

Enhver kontraherende mol af en graf med afgrænset bogtykkelse er en sparsom graf, hvis kant-til-spids-forhold er afgrænset af en konstant, der kun afhænger af dybden af ​​molen og bogtykkelsen. Det vil sige, i Nexetrils terminologi [6] har grafer med afgrænset bogtykkelse afgrænset vækst [6] . Selv grafer med en afgrænset grafgrad , et væsentligt stærkere vækstbegrænsningskrav, kan dog have en ubegrænset bogtykkelse [42] .

Fordi bogtykkelse to grafer er plane grafer, opfylder de planar partitioneringssætning  - de har separatorer, delmængder af toppunkter, hvis fjernelse deler grafen i stykker med højst 2 n /3 hjørner i hvert stykke, med kun O(√ n ) hjørner i separator. Her betyder n antallet af grafens toppunkter. Der er dog grafer med bogtykkelse tre, der ikke har sublineære størrelsesseparatorer [43] .

Kanterne på den ene side af en vedhæftet bog opfører sig som en stak . Dette kan formaliseres ved at overveje en vilkårlig sekvens af push- og pop-operationer (skubbe og poppe) på stakken og danne en graf, hvor stak-operationerne svarer til hjørnerne af grafen placeret på rygraden af ​​bogindlægget i rækkefølgen af ​​operationerne. Hvis vi nu tegner en kant fra hver pop-operation, der springer et objekt x fra stakken til push-operationen, der skubber det element ind på stakken, vil den resulterende graf automatisk have en én-sides nesting. Af denne grund kaldes antallet af sider i en graf også for dens staknummer . Analogt definerer forskere en næste grafindlejring som en tegning af en graf i en bog, hvor to kanter på siden enten skærer eller spænder over ikke-skærende intervaller på rygsøjlen. Sådanne indlejringer svarer på en eller anden måde til køer , og det mindste antal sider, der kræves for hver grafindlejring, kaldes dets antal køer [6] [44] [45] .

Beregningsmæssig kompleksitet

At bestemme tykkelsen af ​​en bogindlejring er et NP-hårdt problem . Dette følger af det faktum, at det er et NP-komplet problem at finde en Hamilton-cyklus i maksimale plane grafer . Tykkelsen af ​​bogens indlejring af en maksimal plan graf er to, hvis og kun hvis der findes en Hamilton-sti. Derfor er det også et NP-komplet problem at bestemme, at tykkelsen af ​​bogindlejringen af ​​en given maksimal plan graf er to. [7]

Hvis rækkefølgen af ​​hjørnerne langs rygsøjlen i bogindlejring er forudbestemt, kan en to-siders indlejring (hvis en findes) findes i lineær tid som en planaritetstest mulighed for en graf opnået ved at udvide en given graf ved at skabe en løkke, der forbinder spidser langs rygsøjlen [13] . Unger hævdede, at finde en tre-siders indlejring med en forudbestemt toppunkt rækkefølge kunne gøres i polynomium tid , selvom hans beskrivelse af dette resultat mangler en række væsentlige detaljer [18] . Men for grafer, der kræver fire eller flere sider , forbliver problemet med at finde en indlejring med det mindst mulige antal sider NP-hårdt på grund af ækvivalensen til det NP-hårde problem med at farve cirkelgrafer , skæringsgrafer for cirkelakkorder . Givet en graf G med en fast rækkefølge af hjørner på rygsøjlen, placerer disse hjørner i samme rækkefølge på cirklen og repræsenterer kanterne af G som segmenter, giver det et sæt akkorder, der repræsenterer grafen G . Man kan nu danne en cirkulær graf med akkorderne i dette diagram som hjørner og krydsende par af akkorder som kanter. Farvelægning af en cirkelgraf giver en opdeling af grafens kanter G i delmængder, der kan tegnes uden skæringspunkter på én side. En optimal farvelægning svarer således til en optimal bogindlejring. Da det er NP-hårdt at farve en cirkelgraf med fire eller flere farver, og da enhver cirkelgraf kan genereres på denne måde ud fra et eller andet problem med at finde en bogindlejring, er det også et NP-hårdt problem at finde den optimale bogindlejring [8] [46] [47] . For en fast rækkefølge af hjørner på rygsøjlen under en to-siders nesting, er det et NP-hårdt problem at minimere antallet af skæringspunkter, hvis dette tal ikke er nul [46] .

Hvis rækkefølgen af ​​hjørnerne på rygsøjlen er ukendt, men paging af kanter er givet, er det muligt at finde en 2-siders nesting (hvis den findes) i lineær tid ved at anvende en algoritme baseret på SPQR-træer [48] [ 49] . Men at finde en 2-siders nesting er NP-komplet, hvis hverken rækkefølgen af ​​toppunkterne på rygsøjlen eller pagingen af ​​kanter er kendt. At finde bognummeret af skæringspunkter i en graf er også NP-svært på grund af NP-fuldstændigheden af ​​problemet med at kontrollere, om det to-siders bognummer af skæringspunkter er nul.

[ subgraph isomorphism problem , som er at bestemme, om en størrelsesbegrænset graf af en art findes som en subgraf af en større graf, kan løses i lineær tid, hvis den større graf har en afgrænset bogindlejringstykkelse. Det samme gælder for at bestemme, om en graf af en eller anden art er en genereret undergraf af en større graf, eller om den har en homeomorfisme med den større graf [50] [51] . Af samme grund kan problemet med at kontrollere, om en graf med afgrænset bogtykkelse opfylder en given førsteordens logikformel , løses med hensyn til en fast parameter [52] .

Ansøgninger

Fejltolerant multiprocessor computing

En af hovedårsagerne til at studere bogindlejring (ifølge Chang, Leighton og Rosenberg [7] ) er dens brug i udviklingen af ​​VLSI til at skabe fejltolerante multiprocessorsystemer . I DIOGENES-systemet udviklet af disse forfattere er processorerne i et multiprocessorsystem organiseret i en logisk kæde svarende til bogens rygrad (selvom de ikke behøver at være placeret i en lige linje fysisk på diagrammet ). Disse processorers kommunikationslinks er grupperet i "bundter", der svarer til siderne i en bog og fungerer som stakke  - at forbinde en af ​​processorerne til begyndelsen af ​​kommunikationslinjen skubber alle tidligere forbindelser i bundtet op og forbinder en anden processor til enden af ​​kommunikationslinjen forbinder den til en af ​​de nederste processorer i strålen og skubber alle resterende ned. På grund af denne stablingsadfærd kan et enkelt bundt tjene et sæt kommunikationslinjer, der danner kanterne på en enkelt side i en bogvedhæftning. Ved at arrangere links på denne måde kan en lang række topologier implementeres, hvor det er lige meget, hvilken processor der fejler, så længe der er nok processorer på netværket. De netværkstopologier, der kan organiseres af et sådant system, er præcis dem, der er bogtykke og ikke overstiger antallet af bundter, der skal gøres tilgængelige [7] .

Stak sortering

En anden applikation, påpeget af Chang, Leighton og Rosenberg [7] , vedrører sortering af permutationer ved hjælp af stakke . Knuth viste, at et system, der behandler en strøm af data ved at skubbe input-elementer ind på stakken og derefter poppe dem på output-strømmen på det rigtige tidspunkt, kan sortere dataene, hvis og kun hvis der ikke er nogen mønsterpermutationer i den originale elementrækkefølge [ 53 ] . Siden da har der været arbejdet meget med dette og lignende problemer med at sortere en strøm af data med mere generelle stack- og køsystemer. I systemet betragtet af Chang, Leighton og Rosenberg skal hvert element fra inputstrømmen skubbes ind på en af ​​stakkene. Efter at alle data er blevet skubbet ind på stakkene, skubbes elementerne af disse stakke (i den passende rækkefølge) til outputstrømmen. Som Chang et al. bemærkede, kan en given permutation sorteres efter et sådant system, hvis og kun hvis en graf opnået fra permutationen har en bogindlejring med en fast rækkefølge af hjørner langs rygraden og antallet af sider, der ikke overstiger antallet af stakke [7] .

Bevægelseskontrol

Som Kainen [12] beskriver , kan bogindlejring bruges til at beskrive faserne af trafiklys i et kontrolleret kryds. I et kryds kan indgående og udgående trafikbaner (inklusive enderne af fodgængerfelter og cykelbaner) repræsenteres som grafspidser placeret på rygraden af ​​en bogvedhæftning i den rækkefølge, der svarer til rækkefølgen for ind-/udgang af trafikken langs med kryds (med uret). Stierne gennem krydset, hvor trafikken bevæger sig, og fodgængere fra indgangspunktet til udgangspunktet, kan repræsenteres som kanterne af en urettet graf. For eksempel kan denne graf have en kant fra en indgangsbane til en udgangsbane, der hører til det samme vejsegment, og dermed repræsentere en U-vending, hvis U-sving er tilladt i krydset. En given delmængde af sådanne kanter repræsenterer et sæt stier, der kan følges uden skæringspunkter, hvis og kun hvis delmængden ikke indeholder et par skærende kanter, der er på samme side af en bogindlejring. Bogindlejringen af ​​grafen beskriver således opdelingen af ​​stier i delmængder, hvor bevægelsen ikke krydser hinanden, og bogtykkelsen af ​​denne graf (med en fast indlejring på rygraden) giver det minimumsantal af forskellige trafiklysfaser, der kræves for en trafiklysplan, der omfatter alle mulige stier gennem krydset [12] . Denne model er dog ikke anvendelig til mere komplekse trafikstyringssystemer, der ikke har en fast tidsplan.

Grafvisualisering

Bogindlejring bruges også ofte til at visualisere netværksdataflow. De to standardgrafvisualiseringsskemaer , buediagrammer [ 10] og cirkeldiagrammer [11] , kan betragtes som boginvesteringer. Bogindlejring kan også bruges til at bygge klyngeskemaer [48] , samtidige indlejringer [54] og 3D-graftegninger [55] .

Et buediagram [10] eller en linjeindlejring [46] placerer grafens hjørner på en linje, og grafens kanter tegnes som halvcirkler over og under den linje, hvilket nogle gange tillader kanterne at være linjestykker. Denne tegnestil svarer til en bog med én side (hvis alle halvcirkler er over linjen) eller to sider (hvis begge sider af linjen er brugt) og blev oprindeligt introduceret som en måde at studere skæringsantallet af grafer. [56] [57] Plane grafer, der ikke har en to-siders bogindlejring, kan tegnes på en lignende måde ved at lade kanter repræsenteres af to halvcirkler over og under en lige linje. Sådanne tegninger er ikke bogindlejringer i forhold til den sædvanlige definition og kaldes topologiske bogindlejringer [58] . For enhver plan graf er det altid muligt at finde en indlejring, der højst krydser rygsøjlen én gang. [59] .

I en anden tegnestil, det cirkulære arrangement , placeres grafens hjørner på en cirkel, og kanterne er tegnet inden for eller uden for cirklen [11] . Igen svarer opstillingen af ​​kanter inden for cirklen (f.eks. som linjestykker) til en bogtegning på én side, mens opstillingen af ​​kanter på hver side af cirklen svarer til en to-siders bogtegning [60] .

For en-sides tegninger af enhver stil er det vigtigt at holde antallet af krydsninger lavt for at reducere det visuelle kaos i tegningen. At minimere antallet af skæringspunkter er et NP-komplet problem [46] , men problemet kan tilnærmes med relationen O (log 2 n ), hvor n er antallet af toppunkter [61] . Minimering af en-sides eller to-siders skæringsnummer kan bestemmes med hensyn til en fast parameter , når den parametreres af det cyklomatiske nummer på den givne graf [62] . Heuristiske metoder er også blevet udviklet til at reducere kompleksiteten af ​​skæringspunkter, baseret for eksempel på nøjagtig toppunktindsættelsesrækkefølge og på lokal optimering [11] .

En to-siders bogindlejring med en fast fordeling af kanter på tværs af sider kan repræsenteres som en slags klyngeplanaritet , hvor en given graf skal tegnes, så dele af grafen (to delmængder af kanter) er arrangeret i figuren for at afspejle deres klyngedannelse [48] . En to-siders bogindlejring bruges også til at finde en samtidig grafindlejring, hvor to grafer er givet på det samme sæt af hjørner, og du skal finde placeringen af ​​hjørnerne, hvor begge grafer er tegnet plant ved hjælp af lige linje segmenter [54] .

Bogvedhæftede filer, der har mere end to sider, bruges til at bygge tredimensionelle tegninger af grafer. Wood brugte især konstruktionen af ​​bogindlejringer, som bevarer den lave grad af hvert toppunkt inden for hver side, som en metode til at indlejre grafer i et tredimensionelt gitter med lille volumen [55] .

Folding RNA

Når man studerer, hvordan RNA- molekyler foldes for at danne en RNA-struktur, kan standardbilledet af den sekundære struktur af en nukleinsyre beskrives ved hjælp af et diagram som en kæde af baser (RNA-sekvens) tegnet langs en lige linje sammen med et sæt af buer over linjen, der beskriver de parrede baser af strukturen. . Det vil sige, at selvom denne struktur har et komplekst tredimensionelt udseende, kan dens forbindelser (hvis der eksisterer en sekundær struktur) beskrives ved en mere abstrakt struktur, en en-sides bogindlæg. Det er dog ikke alle RNA'er, der opfører sig så simpelt. Haslinger og Stadler foreslog en såkaldt "bisekundær struktur" for visse RNA- pseudoknots , som har form af en to-siders bogindlejring - RNA-sekvensen er igen tegnet langs en lige linje, men de parrede baser er tegnet som buer over og under denne linje. For at danne en bisekundær struktur skal grafen have en grad, der ikke overstiger tre - hver base kan kun være i den ene kant af diagrammet, såvel som i to forbindelser med nabobaser i sekvensen. Fordelen ved denne formulering omfatter det faktum, at den udelukker strukturer, der faktisk er knyttet i rummet, og at den dækker de fleste af de kendte RNA-pseudoknoter [13] .

Da rækkefølgen på rygsøjlen er kendt til at begynde med, kontrolleres eksistensen af ​​en bisekundær struktur for givne parrede baser direkte. Opgaven med at fordele kanter over to sider kan formuleres som et specialtilfælde af problemet med tilfredsstillelse af booleske formler i 2-konjunktiv normalform eller som et problem med at kontrollere todeltheden af ​​en cirkulær graf, hvis toppunkter er parrede baser, og kanterne beskriver krydsningen mellem parrede baser [13] . En anden og mere effektiv måde, som vist af Haslinger og Stadler [13] , til at bestemme, at der eksisterer en bisekundær struktur, er ved det faktum, at det sker, hvis og kun hvis inputgrafen (grafen dannet ved at sløjfe baserne i rækkefølgen efter og tilføjelse af parrede baser som kanter) er plan [13] . Dette faktum gør det muligt at genkende en bisekundær struktur i lineær tid som et særligt tilfælde af planaritetstesten .

Blin, Fertin, Rusu og Sinokvet brugte forholdet mellem sekundære strukturer og bogvedhæftninger som en del af beviset på , at nogle problemer med at sammenligne sekundære RNA-strukturer er NP-hårde [63] . Og hvis strukturen af ​​RNA'et er tertiær snarere end bisekundær (det vil sige, hvis der kræves mere end to sider i dets diagram), så er det igen et NP-hårdt problem at bestemme antallet af sider [64] .

Computational complexity theory

Paian, Tewari og Vinodsoandran brugte bogindlejring til at studere den beregningsmæssige kompleksitet af tilgængelighedsproblemet i rettede grafer . Som de bemærkede, kan tilgængelighedsproblemet for to-siders rettede grafer løses i et logaritmisk rum med en enkelt værdi (analogt med den deterministiske logaritmiske hukommelseskompleksitet af problemer i klasse UP ). Imidlertid giver tilgængelighedsproblemet for tre-siders rettede grafer ikke- deterministisk logaritmisk hukommelseskompleksitet . Bogindlejring ser således ud til at være tæt forbundet med forskellene mellem disse to kompleksitetsklasser [65] .

Eksistensen af ​​ekspandere med et konstant antal sider [43] er et nøgletrin i at bevise, at der ikke er nogen tidssubquadratisk simulering af to-bånds ikke- deterministiske Turing-maskiner med enkeltbånds ikke-deterministiske maskiner [66] .

Andre områder af matematik

Mackenzie og Overbey [14] studerede bogtykkelsesapplikationer i generel algebra ved hjælp af grafer afledt af nuldivisorerne i en endelig lokal ring ved at skabe et toppunkt for hver nuldivisor og en kant for hvert par værdier, hvis produkt er nul [14] .

I en række artikler studerede Dynnikov topologiske bogindlejringer af knuder og links , og viste, at disse indlejringer kan beskrives ved en kombinatorisk sekvens af symboler, og at den topologiske ækvivalens af to led kan vises ved en sekvens af lokale ændringer i indlejringer [15 ] [16] .

Noter

  1. ↑ 1 2 3 4 5 6 7 8 9 Bernhart og Kainen, 1979 , s. 320-331.
  2. ↑ 1 2 3 4 5 Heath, 1987 , s. 198-218.
  3. ↑ 12 Shahrokhi et al., 1996 , s. 413-424.
  4. ↑ 1 2 3 4 Eppstein, 2001 .
  5. ↑ 1 2 3 4 Yannakakis, 1989 , s. 36-67.
  6. ↑ 1 2 3 4 5 Nešetřil, Ossona de Mendez, 2012 , s. 321-328.
  7. ↑ 1 2 3 4 5 6 7 Chung et al., 1987 , s. 33-58.
  8. ↑ 12 Unger , 1988 , s. 61-72.
  9. ↑ Arnold L. Rosenberg. Proceedings fra den syttende sydøstlige internationale konference om kombinatorik, grafteori og computing (Boca Raton, Fla., 1986). - 1986. - T. 54. - S. 217-224. — (Congressus Numerantium). .
  10. ↑ 1 2 3 Wattenberg, 2002 , s. 111-116.
  11. ↑ 1 2 3 4 Baur, Brandes, 2005 , pp. 332-343.
  12. ↑ 1 2 3 Kainen, 1990 , s. 127-132.
  13. ↑ 1 2 3 4 5 6 7 Haslinger et al., 1999 , s. 437-467.
  14. ↑ 1 2 3 McKenzie, Overbay, 2010 , s. 55-63.
  15. ↑ 1 2 Dynnikov, 1999 , s. 25-37, 96.
  16. ↑ 1 2 Dynnikov, 2001 , pp. 243-283.
  17. ↑ 12 Blankenship , Oporowski, 2009 .
  18. ↑ 1 2 Walter Unger. STACS 92: 9th Annual Symposium on Theoretical Aspects of Computer Science, Cachan, Frankrig, 13.-15. februar 1992, Proceedings. - Berlin: Springer, 1992. - T. 577. - S. 389-400. — (Forelæsningsnotater i datalogi). - doi : 10.1007/3-540-55210-3_199 . .
  19. ↑ 1 2 3 4 5 Dujmović, Wood, 2007 , s. 641-670.
  20. ↑ 1 2 3 4 Enomoto, Miyauchi, 1999 , s. 337-341.
  21. ↑ 12 Persinger , 1966 , s. 169-173.
  22. ↑ 1 2 Atneosen, 1968 , s. 79.
  23. ↑ Gail H. Atneosen. Endimensionel n - bladet kontinua // Fundamenta Mathematicae . - 1972. - T. 74 , no. 1 . — s. 43–45 . .
  24. ↑ Paul C. Kainen. Grafer og kombinatorik (Proceedings of the Capital Conference on Graph Theory and Combinatorics på George Washington University 18.-22. juni 1973) / Ruth A. Bari, Frank Harary. - 1974. - T. 406. - S. 76-108. — (Forelæsningsnotater i matematik). .
  25. ↑ L. Taylor Ollmann. Proc. 4th Southeastern Conference on Combinatorics, Graph Theory and Computing / Frederick Hoffman, Roy B. Levow, Robert SD Thomas. - 1973. - T. VIII. - S. 459. - (Congressus Numerantium). .
  26. ↑ 1 2 3 Yannakakis, 1986 , s. 104-108.
  27. ↑ T. C. Hales. Kuglepakninger. II // Diskret & beregningsgeometri. - 1997. - T. 18 , no. 2 . — S. 135–149 . - doi : 10.1007/PL00009312 . .
  28. ↑ Oprindeligt ryg eller ryg
  29. ↑ Elena Stohr. En afvejning mellem sidetal og sidebredde af bogindlejringer af grafer // Information and Computation. - 1988. - T. 79 , no. 2 . — S. 155–162 . - doi : 10.1016/0890-5401(88)90036-3 . .
  30. ↑ Elena Stohr. Sidebredden af ​​trivalente plane grafer // Diskret matematik . - 1991. - T. 89 , no. 1 . — s. 43–49 . - doi : 10.1016/0012-365X(91)90398-L . .
  31. ↑ 1 2 3 4 Blankenship, Oporowski, 1999 .
  32. ↑ Hikoe Enomoto, Miki Shimabara Miyauchi, Katsuhiro Ota. Nedre grænser for antallet af kantkrydsninger over rygsøjlen i en topologisk bog indlejring af en graf // Diskret anvendt matematik. - 1999. - T. 92 , no. 2-3 . — S. 149–155 . - doi : 10.1016/S0166-218X(99)00044-X . .
  33. ↑ Bernardo M. Ábrego, Oswin Aichholzer, Silvia Fernández-Merchant, Pedro Ramos, Gelasio Salazar. Proceedings of the 28th Annual Symposium on Computational Geometry (SCG'12). - ACM, New York, 2012. - S. 397-403. - doi : 10.1145/2261250.2261310 . .
  34. ↑ For yderligere resultater om bogtykkelsen af ​​Complete Bipartite Graphs, se Etienne de Klerk, Dmitrii V. Pasechnik, Gelasio Salazar. Bogtegninger af komplette todelte grafer // Diskret anvendt matematik. - 2014. - T. 167 . — S. 80–93 . - doi : 10.1016/j.dam.2013.11.001 . .
  35. ↑ Toru Hasunuma, Yukio Shibata. Indlejring af de Bruijn, Kautz og shuffle-exchange netværk i bøger // Diskret anvendt matematik. - 1997. - T. 78 , no. 1-3 . — S. 103–116 . - doi : 10.1016/S0166-218X(97)00009-7 . Yuuki Tanaka, Yukio Shibata På sidenummeret for de terningforbundne cykler // Mathematics in Computer Science. - 2010. - Vol. 3 , udgave. 1 . — S. 109–117 . - doi : 10.1007/s11786-009-0012-y . Se også Bojana Obrenic. Indlejring af de Bruijn og shuffle-exchange-grafer på fem sider // SIAM Journal on Discrete Mathematics. - 1993. - T. 6 , no. 4 . — S. 642–654 . - doi : 10.1137/0406049 . .
  36. ↑ Bekos et al, 2014 , s. 137-148.
  37. ↑ Lenny Heath. Proceedings of the 25th Annual Symposium on Foundations of Computer Science. - 1984. - S. 74-83. - doi : 10.1109/SFCS.1984.715903 .
  38. ↑ Joseph L. Ganley, Lenwood S. Heath. Sidetallet for k - træer er O ( k ) // Diskret anvendt matematik. - 2001. - T. 109 , udg. 3 . — S. 215–221 . - doi : 10.1016/S0166-218X(00)00178-5 . .
  39. ↑ Seth M. Malitz. Grafer med E - kanter har sidenummer O (√ E ) // Journal of Algorithms : journal. - 1994. - Juli ( bind 17 , hæfte 1 ). — s. 71–84 . - doi : 10.1006/jagm.1994.1027 .
  40. ↑ Seth M. Malitz. Genus g - grafer har sidenummer O (√ g ) // Journal of Algorithms. - 1994. - T. 17 , no. 1 . — S. 85–109 . - doi : 10.1006/jagm.1994.1028 . .
  41. ↑ R. Blankenship. Bogindlejringer af grafer. — Institut for Matematik, Louisiana State University, 2003. . Som citeret af Neshetri.
  42. ↑ János Barát, Jiří Matoušek, David R. Wood. Afgrænsede graders grafer har vilkårlig stor geometrisk tykkelse // Electronic Journal of Combinatorics. - 2006. - T. 13 , no. 1 . — C.R3 . .
  43. ↑ 1 2 Vida Dujmovic, Anastasios Sidiropoulos, David R. Wood. 3-monotone ekspandere. - arXiv : 1501.05020 . , en forbedring i forhold til et tidligere resultat af Jean Bourgain. Ekspanderer og dimensionsudvidelse // Comptes Rendus Mathematique. - 2009. - T. 347 , no. 7-8 . — S. 357–362 . - doi : 10.1016/j.crma.2009.02.009 . ; Jean Bourgain, Amir Yehudayoff. Udvidelse i og monotone ekspandere // Geometrisk og funktionel analyse. - 2013. - T. 23 , no. 1 . — S. 1–41 . - doi : 10.1007/s00039-012-0200-9 . . Se også Zvi Gali, Ravi Kannan, Endre Szemerédi. På 3-pushdown grafer med store separatorer  // Combinatorica. - 1989. - T. 9 , no. 1 . — S. 9–19 . - doi : 10.1007/BF02122679 . ; Zeev Dvir, Avi Wigderson. Monotone ekspandere: konstruktioner og applikationer // Theory of Computing. - 2010. - T. 6 . — S. 291–308 . - doi : 10.4086/toc.2010.v006a012 . .
  44. ↑ Lenwood S. Heath, Arnold L. Rosenberg. Udlægning af grafer ved hjælp af køer // SIAM Journal on Computing. - 1992. - T. 21 , no. 5 . — S. 927–958 . - doi : 10.1137/0221055 . .
  45. ↑ Vida Dujmovic, David R. Wood. Om lineære layout af grafer // Diskret matematik og teoretisk datalogi. - 2004. - T. 6 , no. 2 . — S. 339–357 . .
  46. ↑ 1 2 3 4 Masuda et al., 1990 , s. 124-127.
  47. ↑ MR Garey, DS Johnson, GL Miller, CH Papadimitriou. Kompleksiteten i at farve cirkulære buer og akkorder // SIAM Journal om algebraiske og diskrete metoder. - 1980. - Bind 1 , udgave. 2 . — S. 216–227 . - doi : 10.1137/0601025 . .
  48. ↑ 1 2 3 Hong, Nagamochi, 2009 .
  49. ↑ Patrizio Angelini, Marco Di Bartolomeo, Giuseppe Di Battista. Graftegning: 20th International Symposium, GD 2012, Redmond, WA, USA, 19.-21. september 2012, Revised Selected Papers. - Springer, 2013. - T. 7704. - S. 79–89. — (Forelæsningsnotater i datalogi). - doi : 10.1007/978-3-642-36763-2_8 . .
  50. ↑ Nešetřil, Ossona de Mendez, 2008 , s. 777-791.
  51. ↑ Nešetřil, Ossona de Mendez, 2012 , Corollary 18.1, s. 401.
  52. ↑ Nešetřil, Ossona de Mendez, 2012 , Teorem 18.7, s. 405.
  53. ↑ Donald E. Knuth. The Art Of Computer Programming Vol. 1 . - Boston: Addison-Wesley, 1968. - ISBN 0-201-89683-4 . .
  54. ↑ 12 Angelini et al, 2012 , s. 150-172.
  55. ↑ 12 Wood , 2002 , s. 312-327.
  56. ↑ Thomas L. Saaty. Minimumsantallet af kryds i komplette grafer // Proceedings of the National Academy of Sciences of the United States of America . - 1964. - T. 52 . — S. 688–690 . - doi : 10.1073/pnas.52.3.688 . .
  57. ↑ TAJ Nicholson. Permutationsprocedure for at minimere antallet af krydsninger i et netværk // Proceedings of the Institution of Electrical Engineers. - 1968. - T. 115 . — S. 21–26 . - doi : 10.1049/piee.1968.0004 . .
  58. ↑ Miki Miyauchi. Topologisk bogindlejring af todelte grafer  (engelsk)  // IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences. - 2006. - Bd. E89-A , iss. 5 . — S. 1223–1226 . - doi : 10.1093/ietfec/e89-a.5.1223 .
  59. ↑ Francesco Giordano, Giuseppe Liotta, Tamara Mchedlidze, Antonios Symvonis. Algoritmer og beregninger: 18. internationale symposium, ISAAC 2007, Sendai, Japan, 17.-19. december 2007, Proceedings. - Springer, 2007. - T. 4835. - S. 172-183. — (Forelæsningsnotater i datalogi). - doi : 10.1007/978-3-540-77120-3_17 . .
  60. ↑ Hongmei He, Ondrej Sykora. Proceedings of the Workshop on Information Technologies – Applications and Theory (ITAT), Slovakiet, 15.-19. september 2004. - 2004. .
  61. ↑ Farhad Shahrokhi, Ondrej Sýkora, László A. Székely, Imrich Vrt'o. Graph-Theoretic Concepts in Computer Science: 20th International Workshop, WG '94, Herrsching, Tyskland, 16.-18. juni 1994, Proceedings. - Springer, 1995. - T. 903. - S. 256-268. — (Forelæsningsnotater i datalogi). - doi : 10.1007/3-540-59071-4_53 . .
  62. ↑ Michael J. Bannister, David Eppstein, Joseph A. Simons. Graftegning: 21st International Symposium, GD 2013, Bordeaux, Frankrig, 23.-25. september 2013, Revised Selected Papers. - 2013. - T. 8242. - S. 340-351. — (Forelæsningsnotater i datalogi). - doi : 10.1007/978-3-319-03841-4_30 . .
  63. ↑ Guillaume Blin, Guillaume Fertin, Irena Rusu, Christine Sinoquet. Kombinatorik, algoritmer, probabilistiske og eksperimentelle metoder: Første internationale symposium, ESCAPE 2007, Hangzhou, Kina, 7.-9. april 2007, Revised Selected Papers. - 2007. - T. 4614. - S. 140-151. — (Forelæsningsnotater i datalogi). - doi : 10.1007/978-3-540-74450-4_13 . .
  64. ↑ Peter Clote, Stefan Dobrev, Ivan Dotu, Evangelos Kranakis, Danny Krizanc, Jorge Urrutia. På sidenummeret af RNA sekundære strukturer med pseudoknoter // Journal of Mathematical Biology. - 2012. - T. 65 , no. 6-7 . - S. 1337-1357 . - doi : 10.1007/s00285-011-0493-6 . .
  65. ↑ A. Pavan, Raghunath Tewari, NV Vinodchandran. Om entydighedens magt i log-rum // Computational Complexity. - 2012. - T. 21 , no. 4 . — S. 643–670 . - doi : 10.1007/s00037-012-0047-3 . .
  66. ↑ Zvi Galil, Ravi Kannan, Endre Szemerédi. Om ikke-trivielle separatorer til k-sides grafer og simuleringer af ikke-deterministiske Turing-maskiner med ét bånd // Journal of Computer and System Sciences. - 1989. - T. 38 , no. 1 . — S. 134–149 . - doi : 10.1016/0022-0000(89)90036-6 . .

Litteratur