Könyvbefektetés

A gráfelméletben a könyvbeágyazás egy gráf síkbeli beágyazásának  általánosítása egy könyvbe való beágyazásra – olyan félsíkok  halmazára , amelyeknek ugyanaz az egyenes vonala , mint a határvonal. Általában megkövetelik, hogy a gráf csúcsai ezen a határon legyenek, és az éleknek ugyanazon az oldalon belül kell lenniük. A gráf könyvvastagsága (vagy oldalak száma ) a legkisebb félsíkok száma a gráf összes könyvbeágyazásánál. [1] A könyvbeágyazást számos más gráfinvariánshoz használják , beleértve az oldalszélességet [2] és a keresztek könyvszámát [3] .

Minden n csúcsú gráfnak legfeljebb könyvszélessége van . Ez a korlát közel van a teljes gráfokhoz [1] . Az egyes élek felosztása azonban csökkentheti a könyv vastagságát n négyzetgyökével arányos mértékre . [4] Az egy könyvvastagságú gráfok külső síkbeli gráfok , [1] a legfeljebb kettő vastagságú gráfok pedig szub-Hamilton-féleek , amelyek mindig síkbeliek [2] . Bármely síkgráf könyvvastagsága nem haladja meg a négyet [5] . Minden kismértékben zárt gráfcsalád , és különösen a korlátos faszélességű vagy korlátos nemzetség gráfok , szintén korlátos könyvvastagsággal rendelkeznek [6] . Egy adott gráf könyvvastagságának pontos meghatározása NP-nehéz probléma , függetlenül attól, hogy a gerinc csúcsainak sorrendje ismert vagy sem [7] [8] .

A könyvbeágyazás tanulmányozásának egyik kezdeti oka a VLSI tervezésben való alkalmazása volt , ahol a könyvbeágyazási csúcsok a komponenseket, az élek pedig a komponensek közötti kapcsolatokat képviselik [7] [9] . A gráfok megjelenítésénél a gráfábrázolás két szabványos stílusa, az ívdiagramok [10] és a körkörös elrendezések [11] építhetők fel könyvbeágyazással. A jelzőlámpával szabályozott gyalogosok és járművek forgalmának különböző kezdő- és végpontjai matematikailag modellezhetők gráfcsúcsként, ahol az élek kezdő-vég párokat reprezentálnak, és ennek a gráfnak a könyvbeágyazása használható közlekedési lámpa létrehozására. magatartás a forgalomszabályozás biztosítása érdekében minimális számú jelzőlámpa állapottal [12] . Az RNS -struktúrákkal foglalkozó bioinformatikai problémákban az egyoldalas könyvbeágyazás a nukleinsav másodlagos szerkezetének klasszikus formáját képviseli , a kétoldalas beágyazás pedig pszeudoknotokat [13] . A könyvbeágyazást az általános algebra [14] és a csomóelmélet [15] [16] is használják .

A könyvbefektetéssel kapcsolatos nyitott kérdések a következők

Történelem

A "könyv" nevet Persinger és Atneosen (CA Persinger, Gail Atneosen) vezette be az 1960-as években [21] [22] [23] . Atneosen már korábban is alkalmazta a gráfok beágyazását könyvekbe, de a könyvbeágyazás formális koncepcióját C. Kainen és L. Taylor Ollman fogalmazta meg az 1970-es évek elején, és a beágyazási módszert néhány további megszorítással illették - megfogalmazásukban a A gráf csúcsainak a könyv gerincén kell feküdniük, minden élnek egy oldalon kell feküdnie (nem metszi a gerincet), és bármely két él csak a közös végcsúcsokban metszi egymást [24] [25] .

A könyvbeágyazás további fejlődésének fontos mérföldkövei az 1980-as évek végén Michalis Giannakakis bizonyítéka, hogy a síkgráfok könyvvastagsága nem haladja meg a négyet [26] [5] , valamint az 1990-es évek végén a könyvek közötti szoros kapcsolat felfedezése. beágyazás és bioinformatika . [13]

Definíciók

A könyv a topológiai tér egy speciális fajtája (más néven félsíkok legyezőjének ) [21] [27] . Egyetlen egyenes vonalból ℓ áll, amelyet a könyv gerincének [28] neveznek , valamint egy vagy több félsíkot , amelyet a könyv oldalainak vagy lapjainak neveznek . Minden félsíknak meg kell egyeznie a határvonalával ℓ . A véges számú ( k ) oldalas könyvek beágyazhatók háromdimenziós térbe, például úgy, hogy a z tengely ℓ vonalaként egy téglalap alakú koordinátarendszert választunk , és a ( k ) i - edik oldalaként. felvehet egy p ponthalmazt úgy, hogy a p -t a z tengellyel összekötő legrövidebb szakasz 2π i / k szöget zár be az xz síkkal [1] .

Egy véges G gráf könyvének megjelenítése B könyvbe a G gráf rajza B - ben úgy , hogy G bármely csúcsa a B gerincre , G bármely éle pedig görbeként B -nek egy oldalán belül van . A G gráf metszéspontjainak k - oldalas könyvszáma a metszéspontok  minimális száma egy k oldalas könyv rajzában [3] .

Egy G gráf B - be való könyvbeágyazása egy G gráf B térbe  való beágyazása . Azaz egy B - beli G gráf rajza, amelyben az élek nem metszik egymást. Bármely véges gráfban van egy könyv, amely kellően nagy oldalszámú könyvbe ágyazódik. Például mindig lehetséges az egyes élek egymásba ágyazása a saját oldalon. A könyv vastagsága, az oldalak száma vagy a G gráf kötegszáma a G gráf  könyvbeágyazásához szükséges minimális oldalszám . Egy másik paraméter, amely a könyvmelléklet minőségét méri, az oldalak száma mellett, az oldalszélesség . Ez az élek maximális száma, amely egy oldalon belül a gerincre merőlegesen keresztezi a sugarat . Ezzel egyenértékűen (a könyvbeágyazásoknál, ahol minden él monoton görbeként van megrajzolva) ez az élek egy részhalmazának a maximális mérete úgy, hogy a gerincen az élek végpontjai által meghatározott intervallumok mindegyike metszi egymást [2] [29] [30] .

Ezekhez a meghatározásokhoz elengedhetetlen, hogy a szélek csak egy oldalon feküdjenek. Ahogy Ameosen már megjegyezte, ha az élek oldalról oldalra haladhatnak (a gerincen keresztül), akkor bármelyik gráf beágyazható egy háromoldalas könyvbe [22] [31] [20] . Azonban egy háromoldalas topológiai könyvbeágyazásnál , amelyben megengedett a gerinc metszéspontja, továbbra is érdekes probléma marad a legkisebb gerincmetszésszám meghatározása, amely lehetővé teszi a gráf könyvbe ágyazását [20] [32] .

Konkrét grafikonok

Amint az első ábrán látható, a teljes grafikon könyvvastagsága három. Mivel nem sík, a könyvvastagsága kettőnél nagyobb, de van egy háromoldalas könyvfészek. Bármely teljes csúcsgráf könyvvastagsága pontosan . Ez az eredmény egy felső korlátot ad bármely [1] csúcsú gráf maximális könyvvastagságára . A teljes grafikon kétoldalas metszéspontszáma a

ami összhangban van Anthony Hill nem bizonyított sejtésével . Vagyis ha Hill sejtése igaz, akkor ennek a metszéspontok számát minimalizáló gráfnak a rajza egy kétoldalas rajz [33] .

Egy teljes kétrészes gráf könyvének vastagsága majdnem egyenlő  - egy kisebb rész minden csúcsához elrendezheti az ezekre a csúcsokra eső éleket a saját oldalukon. Ez a határ nem mindig szigorú. Például a könyv vastagsága három, nem négy. Ha azonban a grafikon két oldala erősen kiegyensúlyozatlan, c , akkor a könyv vastagsága pontosan . [1] [34] A bináris de Bruijn -gráfok, a kevert cseregráfok és a ciklusú köbös hálózatok könyveinek vastagsága pontosan három. [35]

Tulajdonságok

Alosztály viselkedése

Megoldatlan problémák a matematikában : Korlátozható-e egy gráf könyvvastagsága a felosztások könyvvastagságának függvényével?

A gráf minden élének felosztása kétéles útvonalakra úgy, hogy minden élhez új csúcsokat ad hozzá, néha megnövelheti a könyv vastagságát (például egy gyémánt könyvvastagsága egy, de a felosztása kettős). Egy ilyen alpartíció azonban jelentősen csökkentheti a gráf könyvvastagságát is a partíció után. Például egy K n teljes gráf könyvvastagsága Θ( n ) arányos a csúcsainak számával, de az egyes éleket kettéosztva sokkal kisebb könyvvastagságú felosztást kapunk, csak O(√ n ). [4] . A fentihez hasonló példák megléte ellenére Blankenship és Oporowski [31] úgy sejtették , hogy a felosztások könyvvastagsága nem lehet lényegesen kisebb, mint az eredeti gráfé. Konkrétan azt feltételezték, hogy létezik valamilyen f függvény , amely bármely G gráf és H gráf esetén, amelyet úgy kapunk, hogy G minden élét két élből álló útvonalra cseréljük, ha a H gráf könyvvastagsága t , akkor a gráf könyvvastagsága G nem haladja meg az f ( t )-t. [31] 2013 -ra a Blankenship-Oporowski sejtés bizonyítatlan maradt. [17]

Síkság és külső síkosság

Egy adott G gráf könyvvastagsága akkor és csak akkor nem haladja meg az 1- et, ha G külső síkbeli . A külső sík gráf egy olyan gráf, amelynek síkbeli beágyazása van, és amelyben minden csúcs a beágyazás külső felületéhez tartozik. Az ilyen gráfok esetében, ha a csúcsokat ugyanabban a sorrendben helyezzük el a gerinc mentén, ahogy a külső felületen jelennek meg (amikor egy csúcs ismét megjelenik a külső felületen, a csúcsnak csak egy másolata készül), egyoldalas gráfbeágyazást eredményez. Ezzel szemben az egyoldalas könyvek egymásba ágyazása automatikusan a síkon kívül van – ha a gráf egy oldalba van beágyazva, egy második félsík hozzáadásával teljes síkot kapunk, a külső oldal pedig a teljes hozzáadott félsíkot fogja tartalmazni, minden csúcsával ez a külső felület [1] [2] .

Bármilyen kétoldalas könyvbeágyazás a síkbeli beágyazás speciális esete, mivel két könyvoldal egyesítése olyan tér, amely topológiailag egy síkkal ekvivalens. Így minden gráf kettős könyvvastagsággal automatikusan síkbeli . Pontosabban, egy G gráf könyvvastagsága legfeljebb kettő akkor és csak akkor, ha G egy Hamilton-ciklussal rendelkező síkgráf részgráfja [1] . Egy kétoldalas könyvbeágyazású gráf esetén a gráf kiterjeszthető egy síkbeli Hamilton-gráfra úgy, hogy (bármely oldalon) további éleket adunk a gerinc mentén tetszőleges két egymást követő csúcs közé, ha még nincsenek összekötve éllel, és a gerinc első és utolsó csúcsa között . A Goldner–Harari gráf egy olyan síkgráfra ad példát, amelynek nincs kettős könyvvastagsága – ez egy maximális síkgráf , így a síkság megtartása mellett lehetetlen éleket hozzáadni, és a gráfnak nincs Hamilton-gráfja. ciklus [1] . A Hamilton-ciklusokra vonatkozó követelmény miatt a kétoldalas egymásba ágyazást lehetővé tevő gráfokat szub-Hamilton-gráfoknak nevezzük [2] .

Minden legfeljebb négyes fokozatú síkgráf könyvbeágyazási mélysége legfeljebb kettő. [36] . A sík 3 fák maximális könyvszélessége három [37] . Minden síkgráf könyvvastagsága nem haladja meg a négyet [26] [5] . Ahogy Michalis Yannaakis 1986-ban [26] kijelentette , léteznek olyan síkgráfok, amelyekben egy könyv beágyazási vastagsága pontosan négy, de ennek az állításnak a [5] -ben bejelentett részletes bizonyítéka soha nem jelent meg. Emiatt Duimovich [19] megoldatlannak jelölte a síkgráfok könyvbeágyazásának maximális vastagságának meghatározását [19] .

Kapcsolat más gráfinvariánsokkal

A könyv vastagsága összefügg a gráf vastagságával, az adott gráf éleinek lefedéséhez szükséges síkgráfok számával. Egy G gráf vastagsága θ, ha síkba ágyazható, és az élek θ színűre színezhetők úgy, hogy az azonos színű élek ne metsszék egymást. Hasonlóképpen, egy G gráf könyvszélessége θ, ha megrajzolható egy félsíkban, amelynek csúcsai a félsík határán vannak, és θ színű élekkel színezhető anélkül, hogy azonos színű éleket keresztezne. Ennél a megfogalmazásnál az azonos színű élek a könyvmelléklet lapjainak felelnek meg. A grafikon vastagsága és a könyv vastagsága azonban jelentősen eltérhet - a teljes gráfoknak vannak olyan felosztásai, amelyek korlátlan vastagságúak [31] [20] [4] , annak ellenére, hogy a grafikon vastagsága egyenlő kettőre [4] .

A k faszélességű grafikonok könyvszélessége legfeljebb k + 1 [19] [38] , és ez a korlát k > 2 esetén érhető el . [19] . Az m élű gráfok könyvszélessége O(√ m ) [39] , a g nemzetségbe tartozó gráfok pedig  O(√ g ) [40] . Általánosságban elmondható, hogy minden kisebb-nagyobb zárt gráfcsalád korlátos könyvvastagsággal rendelkezik [6] [41] .

A korlátos könyvvastagságú gráf bármely összehúzódó mollja egy ritka gráf , amelynek él-csúcs arányát egy olyan állandó határolja, amely csak a moll mélységétől és a könyv vastagságától függ. Vagyis a Nexetril [6] terminológiájában a korlátos könyvvastagságú gráfok korlátos növekedést mutatnak [6] . Azonban még a korlátos gráffokozatú gráfok is , amelyek lényegesen erősebb növekedési korlátozási követelményt jelentenek, rendelkezhetnek korlátlan könyvvastagsággal [42] .

Mivel a könyvvastagság két gráf sík gráf, eleget tesz a síkbeli particionálási tételnek  – vannak elválasztóik, csúcsok részhalmazai, amelyek eltávolítása a gráfot olyan darabokra osztja, amelyek mindegyikében legfeljebb 2 n /3 csúcs található, és csak O(√ n ) csúcsok vannak. elválasztóban. Itt n a gráf csúcsainak számát jelenti. Vannak azonban három könyvvastagságú gráfok, amelyek nem rendelkeznek szublineáris méretelválasztókkal [43] .

Egy könyvmelléklet oldalának szélei kötegként viselkednek . Ez formalizálható úgy, hogy figyelembe veszünk egy tetszőleges push és pop műveletsort (push és pop) a veremen, és készítünk egy gráfot, amelyben a veremműveletek megfelelnek a gráf csúcsainak, amelyek a könyvbetét gerincén találhatók. a műveletek sorrendjét. Ha most minden olyan pop-műveletből rajzolunk egy élt, amely egy x objektumot a veremből az elemet a verembe helyező push művelethez, akkor az eredményül kapott gráf automatikusan egyoldalas beágyazást fog tartalmazni. Emiatt a grafikon oldalainak számát veremszámnak is nevezik . Analógia útján a kutatók a következő gráfbeágyazást úgy határozzák meg, mint egy gráf rajzát egy könyvben, amelyben az oldal bármely két éle vagy metszi egymást, vagy a gerincen nem metsző intervallumokat ível át. Az ilyen beágyazások valamilyen módon a várólistáknak felelnek meg , és az egyes gráfbeágyazáshoz szükséges minimális oldalszámot a sorok számának nevezik [6] [44] [45] .

Számítási összetettség

A könyvbeágyazás vastagságának meghatározása NP-nehéz probléma . Ez abból a tényből következik, hogy a Hamilton-ciklus megtalálása maximális síkgráfokban NP-teljes probléma . Egy maximális síkgráf könyvbeágyazásának vastagsága akkor és csak akkor kettő, ha létezik Hamilton-útvonal. Ezért annak meghatározása, hogy egy adott maximális síkgráf könyvbeágyazásának vastagsága kettő, szintén NP-teljes probléma. [7]

Ha a gerinc mentén a csúcsok sorrendje a könyvbeágyazásban előre meghatározott, akkor lineáris időben egy kétoldalas egymásba ágyazás (ha van ilyen) megtalálható egy adott gráf kibővítésével kapott gráf síkossági tesztjeként egy hurokösszekötő létrehozásával. csúcsok a gerinc mentén [13] . Unger azt állította, hogy egy háromoldalas beágyazást előre meghatározott csúcsrenddel meg lehet találni polinomiális idő alatt is , bár ennek az eredménynek a leírásában számos lényeges részlet hiányzik [18] . A négy vagy több oldalt igénylő grafikonok esetében azonban a lehető legkisebb oldalszámú beágyazás megtalálásának problémája továbbra is NP-nehéz, mivel egyenértékű a körgráfok színezésének NP-nehéz problémájával , a körhúrok metszésgráfjaival . Adott egy G gráf a gerincen rögzített csúcsok sorrendjével, ha ezeket a csúcsokat ugyanabban a sorrendben helyezzük el a körön, és G éleit szegmensként ábrázoljuk, akkor a G gráfot reprezentáló akkordhalmazt kapjuk . Most létrehozhatunk egy körgráfot , amelyben ennek a diagramnak az akkordjai csúcsok, és egymást metsző akkordpárok élek. A körgráf kiszínezése a G gráf éleit részhalmazokra osztja, amelyek metszéspontok nélkül rajzolhatók meg egy oldalon. Így az optimális színezés egyenértékű a könyv optimális beágyazásával. Mivel egy körgráf négy vagy több színnel színezése NP-nehéz, és mivel a könyvbeágyazás megtalálásának valamilyen problémájából bármilyen körgráf előállítható, az optimális könyvbeágyazás megtalálása is NP-nehéz probléma [8]. [46] [47] . Egy kétoldalas egymásba ágyazás alatt álló gerincen a csúcsok rögzített sorrendje esetén NP-nehéz probléma a metszéspontok számának minimalizálása, ha ez a szám nem nulla [46] .

Ha a gerincen a csúcsok sorrendje nem ismert, de az élek lapozása adott, akkor egy SPQR fákon alapuló algoritmus segítségével lineáris időben találhatunk 2 oldalas egymásba ágyazást (ha van ilyen) [48] [ 49] . A 2 oldalas egymásba ágyazás megtalálása azonban NP-teljes, ha sem a gerincen lévő csúcsok sorrendje, sem az élek lapozása nem ismert. Egy gráf metszéspontjainak könyvszámának megtalálása szintén NP-nehéz annak a feladatnak az NP-teljessége miatt, hogy a metszéspontok kétoldalas könyvszáma nulla-e.

Az részgráf izomorfizmus problémája , amelynek célja annak meghatározása, hogy egy méretkorlátos gráf megtalálható-e egy nagyobb gráf részgráfjaként, lineáris időben megoldható, ha a nagyobb gráf korlátos könyvbeágyazási vastagságú. Ugyanez igaz annak meghatározására is, hogy egy bizonyos gráf egy nagyobb gráf generált részgráfja , vagy van-e homeomorfizmusa a nagyobb gráfgal [50] [51] . Ugyanezen okból megoldható egy fix paraméterre [52] az a probléma, hogy egy korlátos könyvvastagságú gráf megfelel-e egy adott elsőrendű logikai képletnek .

Alkalmazások

Hibatűrő többprocesszoros számítástechnika

A könyvbeágyazás tanulmányozásának egyik fő oka (Chang, Leighton és Rosenberg [7] szerint) az, hogy a VLSI fejlesztésében hibatűrő többprocesszoros rendszerek létrehozására használják . Az e szerzők által kidolgozott DIOGENES rendszerben egy többprocesszoros rendszer processzorai a könyv gerincének megfelelő logikai láncba szerveződnek (bár fizikailag nem kell egyenes vonalban elhelyezkedniük a diagramon ). Ezeknek a processzoroknak a kommunikációs kapcsolatai „kötegekbe” vannak csoportosítva, amelyek egy könyv lapjainak felelnek meg, és úgy működnek, mint a verem  – ha az egyik processzort a kommunikációs vonal elejére csatlakoztatjuk, az összes korábbi kapcsolat feljebb kerül a kötegben, és egy másik processzort csatlakoztatunk. a kommunikációs vonal végére csatlakoztatja a sugár egyik alsó processzorához, és lenyomja az összes maradékot. Ennek a halmozási viselkedésnek köszönhetően egyetlen köteg olyan kommunikációs vonalakat tud kiszolgálni, amelyek egy könyvmelléklet egyetlen oldalának széleit alkotják. A hivatkozások ilyen módon történő elrendezésével a topológiák széles skálája valósítható meg, amelyekben mindegy, hogy melyik processzor hibásodik meg, amíg elegendő processzor marad a hálózaton. Egy ilyen rendszerrel pontosan azok a hálózati topológiák szervezhetők, amelyek könyvvastagságúak, nem haladják meg a rendelkezésre bocsátandó kötegek számát [7] .

Stack rendezés

Egy másik alkalmazás, amelyre Chang, Leighton és Rosenberg [7] mutatott rá, a permutációk veremekkel történő rendezésére vonatkozik . Knuth megmutatta, hogy egy olyan rendszer, amely egy adatfolyamot úgy dolgoz fel , hogy a bemeneti elemeket a verembe tolja, majd a megfelelő időben a kimeneti folyamra helyezi őket, akkor és csak akkor tudja rendezni az adatokat, ha nincsenek mintapermutációk az eredeti elemsorrendben 53 ] . Azóta sokat dolgoztak ezen és hasonló problémákon, amelyek az adatfolyamok általánosabb verem- és sorrendszerekkel történő rendezésével kapcsolatosak. A Chang, Leighton és Rosenberg által vizsgált rendszerben a bemeneti adatfolyam minden elemét az egyik verembe kell tolni. Miután az összes adat a verembe került, az elemek (a megfelelő sorrendben) kikerülnek a veremekből a kimeneti adatfolyamba. Ahogy Chang és munkatársai megjegyezték, egy adott permutációt akkor és csak akkor lehet rendezni egy ilyen rendszerrel, ha a permutációból nyert gráfban van egy könyvbeágyazás a gerinc mentén rögzített csúcsok sorrendjével, és az oldalak száma nem haladja meg a permutáció számát. verem [7] .

Mozgásvezérlés

Ahogy Kainen [12] leírja, a könyvbeágyazással leírhatók a közlekedési lámpák fázisai egy szabályozott kereszteződésben. Egy kereszteződésben a bejövő és kimenő forgalmi sávok (beleértve a gyalogátkelőhelyek és kerékpárutak végeit is) egy könyvmelléklet gerincén elhelyezkedő gráfcsúcsokként ábrázolhatók a forgalom be-/kilépési sorrendjének megfelelő sorrendben. kereszteződés (az óramutató járásával megegyezően). A kereszteződésen áthaladó utak, ahol a forgalom mozog, és a gyalogosok a belépési ponttól a kilépési pontig, egy irányítatlan gráf éleiként ábrázolhatók. Például ennek a grafikonnak lehet egy éle egy bemeneti sávtól egy ugyanahhoz az útszakaszhoz tartozó kimeneti sávhoz, így visszakanyarodást jelent, ha a kereszteződésben megengedett a visszafordulás. Az ilyen élek adott részhalmaza olyan utak halmazát képviseli, amelyek akkor és csak akkor követhetők metszéspontok nélkül, ha az alhalmaz nem tartalmaz olyan metsző élpárt, amely egy könyvbeágyazás ugyanazon az oldalán található. Így a gráf könyves beágyazása leírja az utak olyan részhalmazokra való felosztását, amelyekben a mozgás nem metszi egymást, és ennek a grafikonnak a könyvvastagsága (fix beágyazással a gerincen) megadja a különböző közlekedési lámpák fázisainak minimális számát, amelyek szükségesek jelzőlámpás menetrend, amely tartalmazza az összes lehetséges utat a kereszteződésen [12] . Ez a modell azonban nem alkalmazható bonyolultabb, rögzített menetrenddel nem rendelkező forgalomirányítási rendszerekre.

Grafikonábrázolás

A könyvbeágyazást gyakran használják a hálózati adatáramlás megjelenítésére is. A két szabványos gráfvizualizációs séma , az ívdiagramok [10] és a kördiagramok [11] könyvbefektetésnek tekinthetők. A könyvbeágyazás használható klasztersémák [48] , szimultán beágyazások [54] és 3D gráfrajzok [55] készítésére is .

Egy ívdiagram [10] vagy egy vonalbeágyazás [46] a gráf csúcsait egy egyenesre helyezi, és a gráf élei félkörként rajzolódnak meg a vonal felett és alatt, néha lehetővé téve, hogy az élek vonalszakaszok legyenek. Ez a rajzstílus egy oldalas (ha minden félkör a vonal felett van) vagy két oldalas (ha a vonal mindkét oldalát használjuk) egymásba ágyazott könyvnek felel meg, és eredetileg a grafikonok metszéspontszámának tanulmányozására vezették be. [56] [57] A kétoldalas könyvbeágyazást nem tartalmazó síkgráfok hasonló módon rajzolhatók meg, ha az éleket egy egyenes felett és alatt két félkörrel ábrázolhatjuk. Az ilyen rajzok a szokásos definíció szerint nem könyvbeágyazások, és topológiai könyvbeágyazásoknak nevezik őket [58] . Bármely síkgráfnál mindig lehet találni olyan beágyazást, amely legfeljebb egyszer keresztezi a gerincet. [59] .

Egy másik rajzstílusban, a kör alakú elrendezésben a gráf csúcsait egy körre helyezzük, az éleket pedig a körön belül vagy kívül [11] . A körön belüli élek elrendezése (pl. vonalszakaszként) itt is egyoldalas könyvrajznak felel meg, míg az élek elrendezése a kör két oldalán egy kétoldalas könyvrajznak [60] .

Bármilyen stílusú egyoldalas rajzoknál fontos, hogy a metszéspontok száma alacsony legyen, hogy csökkentsük a rajz vizuális káoszát. A metszéspontok számának minimalizálása NP-teljes feladat [46] , de a probléma közelíthető az O relációval (log 2 n ), ahol n a csúcsok száma [61] . Az egyoldalas vagy kétoldalas metszésszám minimalizálása egy fix paraméter vonatkozásában eldönthető, ha az adott gráf ciklomatikus számával paraméterezzük [62] . A metszéspontok bonyolultságának csökkentésére heurisztikus módszereket is kidolgoztak, amelyek például a csúcspontok pontos beillesztési sorrendjén és a lokális optimalizáláson alapulnak [11] .

Egy kétoldalas könyvbeágyazás az élek oldalak közötti fix eloszlásával egyfajta klasztersíkságként ábrázolható , amelyben egy adott gráfot úgy kell megrajzolni, hogy a gráf részei (az élek két részhalmaza) legyenek elrendezve. a klaszterezésüket tükröző ábra [48] . Egy kétoldalas könyvbeágyazás is használható egyidejű gráfbeágyazás megtalálásához, amelyben két gráf van megadva ugyanazon a csúcshalmazon, és meg kell találni a csúcsok helyét, amelyekben mindkét gráf síkban, egyenes vonallal van megrajzolva. szegmensek [54] .

A kettőnél több oldalas könyvmellékleteket háromdimenziós grafikonok készítésére használják. Wood különösen a könyvbeágyazások felépítését használta, amelyek megőrzik az egyes csúcsok alacsony fokát az egyes oldalakon belül, a gráfok kis térfogatú háromdimenziós rácsba való beágyazásának módszereként [55] .

Összecsukható RNS

Amikor azt vizsgáljuk, hogy az RNS -molekulák hogyan hajtogatnak össze RNS-szerkezetet, a nukleinsav másodlagos szerkezetének standard nézete egy diagram segítségével leírható, mint egy bázislánc (RNS-szekvencia), amelyet egyenes vonal mentén rajzolnak egy halmazzal együtt. a szerkezet páros alapjait leíró vonal feletti ívek . Vagyis bár ennek a szerkezetnek összetett háromdimenziós megjelenése van, kapcsolatai (ha létezik másodlagos szerkezet) egy elvontabb szerkezettel, egy oldalas könyvbetéttel írhatók le. Azonban nem minden RNS viselkedik ilyen egyszerű módon. Haslinger és Stadler úgynevezett "kétszekunder struktúrát" javasolt bizonyos RNS pszeudoknotokhoz , amelyek egy kétoldalas könyvbeágyazás formáját öltik – az RNS-szekvencia ismét egyenes vonal mentén van megrajzolva, de a páros bázisok ívekként rajzolódnak felül, és e vonal alatt. Biszekunder struktúra kialakításához a gráf fokszáma nem haladhatja meg a hármat - minden bázis csak a diagram egyik élén, valamint két linkben lehet a szekvenciában szomszédos bázisokkal. Ennek a készítménynek az az előnye, hogy kizárja azokat a struktúrákat, amelyek valójában a térben csomósodnak, és lefedi a legtöbb ismert RNS-álcsomót [13] .

Mivel a gerincen a sorrend kezdetben ismert, a biszekunder struktúra meglétét az adott páros bázisoknál közvetlenül ellenőrzik. Az élek két oldalon való elosztásának feladata megfogalmazható a Boole-képletek 2-konjunktív normálalakú kielégíthetőségi problémájának speciális eseteként, vagy egy olyan körgráf bipartititásának ellenőrzési problémájaként, amelynek csúcsai páros bázisok, az élek pedig a páros alapok közötti kereszteződést írják le [13] . Egy másik és hatékonyabb módszer, amint azt Haslinger és Stadler [13] kimutatta , az a tény, hogy ez akkor és csak akkor történik meg, ha a bemeneti gráf (az alapok hurkolásával kialakított gráf a következő sorrendben: páros alapok élként való hozzáadása) síkbeli [13] . Ez a tény lehetővé teszi egy biszekunder struktúra felismerését lineáris időben , mint a síksági vizsgálat speciális esetét .

Blin, Fertin, Rusu és Sinokvet a másodlagos struktúrák és a könyvcsatolások közötti összefüggést használta annak bizonyítására , hogy az RNS másodlagos struktúráinak összehasonlításával kapcsolatos egyes problémák NP-nehézek [63] . És ha az RNS szerkezete harmadlagos, nem pedig biszekunder (vagyis ha kettőnél több oldalra van szükség a diagramban), akkor az oldalak számának meghatározása ismét NP-nehéz probléma [64] .

Számítási komplexitás elmélet

Paian, Tewari és Vinodsoandran könyvbeágyazást használt az elérhetőségi probléma számítási bonyolultságának tanulmányozására irányított gráfokban . Mint megjegyezték, a kétoldalas irányított gráfok elérhetőségi problémája megoldható egy egyértékű logaritmikus térben (hasonlóan az UP osztályú feladatok determinisztikus logaritmikus memória komplexitásához ). A háromoldalas irányított gráfok elérhetőségi problémája azonban nemdeterminisztikus logaritmikus memóriabonyolultságot ad . Így úgy tűnik, hogy a könyvbeágyazás szorosan összefügg a két komplexitási osztály közötti különbségekkel [65] .

Az állandó oldalszámú bővítők [43] megléte kulcsfontosságú lépés annak bizonyítására, hogy nem létezik kétszalagos, nem determinisztikus Turing-gépek idő-szubquadratikus szimulációja egyszalagos nemdeterminisztikus gépekkel [66] .

A matematika egyéb területei

Mackenzie és Overbey [14] a könyvvastagság -alkalmazásokat tanulmányozta az általános algebrában egy véges lokális gyűrű nullaosztóiból származtatott gráfok segítségével úgy, hogy minden nulla osztóhoz csúcsot és élt hoztak létre minden olyan értékpárhoz, amelynek szorzata nulla [14] .

Cikkeinek sorozatában Dynnikov a csomók és linkek topológiai könyvbeágyazásait tanulmányozta , bemutatva, hogy ezek a beágyazások leírhatók a szimbólumok kombinatorikus sorozatával, és hogy két link topológiai ekvivalenciája kimutatható a beágyazások lokális változásainak sorozatával [15] ] [16] .

Jegyzetek

  1. ↑ 1 2 3 4 5 6 7 8 9 Bernhart és Kainen, 1979 , pp. 320–331.
  2. ↑ 1 2 3 4 5 Heath, 1987 , pp. 198–218.
  3. ↑ 12 Shahrokhi et al, 1996 , pp. 413–424.
  4. ↑ 1 2 3 4 Eppstein, 2001 .
  5. ↑ 1 2 3 4 Yannakakis, 1989 , pp. 36–67.
  6. ↑ 1 2 3 4 5 Nešetřil, Ossona de Mendez, 2012 , pp. 321–328.
  7. ↑ 1 2 3 4 5 6 7 Chung et al, 1987 , pp. 33–58.
  8. ↑ 12 Unger , 1988 , pp. 61–72.
  9. ↑ Arnold L. Rosenberg. A tizenhetedik délkeleti nemzetközi kombinatorika, gráfelmélet és számítástechnika konferencia anyaga (Boca Raton, Fla., 1986). - 1986. - T. 54. - S. 217-224. — (Congressus Numerantium). .
  10. ↑ 1 2 3 Wattenberg, 2002 , pp. 111–116.
  11. ↑ 1 2 3 4 Baur, Brandes, 2005 , pp. 332–343.
  12. ↑ 1 2 3 Kainen, 1990 , pp. 127–132.
  13. ↑ 1 2 3 4 5 6 7 Haslinger et al, 1999 , pp. 437–467.
  14. ↑ 1 2 3 McKenzie, Overbay, 2010 , pp. 55–63.
  15. ↑ 1 2 Dynnikov, 1999 , pp. 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, Franciaország, 1992. február 13–15., Proceedings. - Berlin: Springer, 1992. - T. 577. - S. 389-400. — (Számítástechnikai előadásjegyzetek). - doi : 10.1007/3-540-55210-3_199 . .
  19. ↑ 1 2 3 4 5 Dujmović, Wood, 2007 , pp. 641–670.
  20. ↑ 1 2 3 4 Enomoto, Miyauchi, 1999 , pp. 337–341.
  21. ↑ 12 Persinger , 1966 , pp. 169–173.
  22. ↑ 1 2 Atneosen, 1968 , p. 79.
  23. ↑ Gail H. Atneosen. Egydimenziós n - levelű kontinua // Fundamenta Mathematicae . - 1972. - T. 74 , sz. 1 . – 43–45 . .
  24. ↑ Paul C. Kainen. Graphs and Combinatorics (Proceedings of the Capital Conference on Graph Theory and Combinatorics at the George Washington University, 1973. június 18–22.) / Ruth A. Bari, Frank Harary. - 1974. - T. 406. - S. 76-108. — (Matematikai előadásjegyzetek). .
  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 , pp. 104–108.
  27. ↑ T. C. Hales. Gömbös csomagolások. II // Diszkrét és számítási geometria. - 1997. - T. 18 , sz. 2 . – S. 135–149 . - doi : 10.1007/PL00009312 . .
  28. ↑ Eredetileg gerinc vagy hát
  29. ↑ Elena Stohr. Kompromisszum az oldalszám és a grafikonok könyvbeágyazásának oldalszélessége között // Információ és számítás. - 1988. - T. 79 , sz. 2 . – S. 155–162 . - doi : 10.1016/0890-5401(88)90036-3 . .
  30. ↑ Elena Stohr. A háromértékű síkgráfok oldalszélessége // Discrete Mathematics . - 1991. - T. 89 , sz. 1 . – 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. Alsó korlátok a gerincen átívelő élkeresztezések számához egy gráf topológiai könyvbeágyazásában // Discrete Applied Mathematics. - 1999. - T. 92 , sz. 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. ↑ A Complete Bipartite Graphs könyvvastagságára vonatkozó további eredményekért lásd: Etienne de Klerk, Dmitrii V. Pasechnik, Gelasio Salazar. Teljes kétoldalú gráfok könyvrajzai // Discrete Applied Mathematics. - 2014. - T. 167 . – S. 80–93 . - doi : 10.1016/j.dam.2013.11.001 . .
  35. ↑ Toru Hasunuma, Yukio Shibata. De Bruijn, Kautz és shuffle-exchange hálózatok beágyazása könyvekbe // Discrete Applied Mathematics. - 1997. - T. 78 , sz. 1-3 . – S. 103–116 . - doi : 10.1016/S0166-218X(97)00009-7 . Yuuki Tanaka, Yukio Shibata A kockakapcsolt ciklusok oldalszámán // Matematika a számítástechnikában. - 2010. - 3. évf. , szám. 1 . – S. 109–117 . - doi : 10.1007/s11786-009-0012-y . Lásd még Bojana Obrenic. De Bruijn és shuffle-exchange grafikonok beágyazása öt oldalba // SIAM Journal on Discrete Mathematics. - 1993. - T. 6 , sz. 4 . — S. 642–654 . - doi : 10.1137/0406049 . .
  36. ↑ Bekos et al, 2014 , pp. 137–148.
  37. ↑ Lenny Heath. A számítástechnika alapjairól szóló 25. éves szimpózium anyaga. - 1984. - S. 74-83. - doi : 10.1109/SFCS.1984.715903 .
  38. ↑ Joseph L. Ganley, Lenwood S. Heath. A k -fák oldalszáma O ( k ) // Discrete Applied Mathematics. - 2001. - T. 109 , szám. 3 . – S. 215–221 . - doi : 10.1016/S0166-218X(00)00178-5 . .
  39. ↑ Seth M. Malitz. Az E élű grafikonok oldalszáma O (√ E ) // Journal of Algorithms : Journal. - 1994. - július ( 17. évf. , 1. szám ). – 71–84 . - doi : 10.1006/jagm.1994.1027 .
  40. ↑ Seth M. Malitz. A g nemzetség grafikonjainak oldalszáma O (√ g ) // Journal of Algorithms. - 1994. - T. 17 , sz. 1 . – S. 85–109 . - doi : 10.1006/jagm.1994.1028 . .
  41. ↑ R. Blankenship. Könyv Grafikonok beágyazása. — Matematika Tanszék, Louisiana Állami Egyetem, 2003 . Neshetri idézete szerint.
  42. ↑ Barát János, Jiří Matoušek, David R. Wood. A korlátos fokú gráfok tetszőlegesen nagy geometriai vastagsággal rendelkeznek // Electronic Journal of Combinatorics. - 2006. - T. 13 , sz. 1 . — C. R3 . .
  43. ↑ 1 2 Vida Dujmovic, Anastasios Sidiropoulos, David R. Wood. 3 monoton bővítők. - arXiv : 1501.05020 . , Jean Bourgain korábbi eredményének javítása . Tágítók és méretbővítés // Comptes Rendus Mathematique. - 2009. - T. 347 , sz. 7-8 . – S. 357–362 . - doi : 10.1016/j.crma.2009.02.009 . ; Jean Bourgain, Amir Yehudayoff. Expansion in és monoton expander // Geometric and Functional Analysis. - 2013. - T. 23 , sz. 1 . – S. 1–41 . - doi : 10.1007/s00039-012-0200-9 . . Lásd még Gali Zvi, Ravi Kannan, Szemerédi Endre. 3-lenyomható grafikonokon nagy elválasztókkal  // Combinatorica. - 1989. - T. 9 , sz. 1 . — P. 9–19 . - doi : 10.1007/BF02122679 . ; Zeev Dvir, Avi Wigderson. Monoton bővítők: konstrukciók és alkalmazások // Számítástechnika elmélete. - 2010. - T. 6 . – S. 291–308 . - doi : 10.4086/toc.2010.v006a012 . .
  44. ↑ Lenwood S. Heath, Arnold L. Rosenberg. Grafikonok elrendezése sorok segítségével // SIAM Journal on Computing. - 1992. - T. 21 , sz. 5 . – S. 927–958 . - doi : 10.1137/0221055 . .
  45. ↑ Vida Dujmovic, David R. Wood. Grafikonok lineáris elrendezéséről // Discrete Mathematics & Theoretical Computer Science. - 2004. - T. 6 , sz. 2 . – S. 339–357 . .
  46. ↑ 1 2 3 4 Masuda et al, 1990 , pp. 124–127.
  47. ↑ MR Garey, DS Johnson, GL Miller, CH Papadimitriou. A körívek és akkordok színezésének összetettsége // SIAM Journal on Algebraic and Discrete Methods. - 1980. - 1. évf. , szám. 2 . – S. 216–227 . - doi : 10.1137/0601025 . .
  48. ↑ 1 2 3 Hong, Nagamochi, 2009 .
  49. ↑ Patrizio Angelini, Marco Di Bartolomeo, Giuseppe Di Battista. Grafikonrajz: 20th International Symposium, GD 2012, Redmond, WA, USA, 2012. szeptember 19–21., Revised Selected Papers. - Springer, 2013. - T. 7704. - S. 79–89. — (Számítástechnikai előadásjegyzetek). - doi : 10.1007/978-3-642-36763-2_8 . .
  50. ↑ Nešetřil, Ossona de Mendez, 2008 , pp. 777–791.
  51. ↑ Nešetřil, Ossona de Mendez, 2012 , Következmény 18.1, p. 401.
  52. ↑ Nešetřil, Ossona de Mendez, 2012 , 18.7. Tétel, p. 405.
  53. ↑ Donald E. Knuth. A Számítógép-programozás Művészete Vol. 1 . - Boston: Addison-Wesley, 1968. - ISBN 0-201-89683-4 . .
  54. ↑ 12 Angelini et al, 2012 , pp. 150–172.
  55. ↑ 12 Wood , 2002 , pp. 312–327.
  56. ↑ Thomas L. Saaty. A metszéspontok minimális száma teljes grafikonokban // 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. Permutációs eljárás a keresztezések számának minimalizálására egy hálózatban // Villamosmérnökök Intézetének közleménye. - 1968. - T. 115 . – S. 21–26 . - doi : 10.1049/piee.1968.0004 . .
  58. ↑ Miki Miyauchi. Bipartite graphs topological book embedding of bipartite graphs  (angol)  // IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences. - 2006. - 20. évf. E89-A , iss. 5 . — P. 1223–1226 . - doi : 10.1093/ietfec/e89-a.5.1223 .
  59. ↑ Francesco Giordano, Giuseppe Liotta, Tamara Mchedlidze, Antonios Symvonis. Algoritmusok és számítások: 18. Nemzetközi Szimpózium, ISAAC, 2007, Sendai, Japán, 2007. december 17–19., Proceedings. - Springer, 2007. - T. 4835. - S. 172-183. — (Számítástechnikai előadásjegyzetek). - doi : 10.1007/978-3-540-77120-3_17 . .
  60. ↑ Hongmei He, Ondrej Sykora. Az Információs Technológiák – Alkalmazások és Elmélet (ITAT) Workshop anyaga, Szlovákia, 2004. szeptember 15–19. - 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, Németország, 1994. június 16–18., Proceedings. - Springer, 1995. - T. 903. - S. 256-268. — (Számítástechnikai előadásjegyzetek). - doi : 10.1007/3-540-59071-4_53 . .
  62. ↑ Michael J. Bannister, David Eppstein, Joseph A. Simons. Grafikonrajz: 21. Nemzetközi Szimpózium, GD 2013, Bordeaux, Franciaország, 2013. szeptember 23–25., Revised Selected Papers. - 2013. - T. 8242. - S. 340-351. — (Számítástechnikai előadásjegyzetek). - doi : 10.1007/978-3-319-03841-4_30 . .
  63. ↑ Guillaume Blin, Guillaume Fertin, Irena Rusu, Christine Sinoquet. Kombinatorika, algoritmusok, valószínűségi és kísérleti módszertanok: Első nemzetközi szimpózium, ESCAPE 2007, Hangzhou, Kína, 2007. április 7-9., Revised Selected Papers. - 2007. - T. 4614. - S. 140-151. — (Számítástechnikai előadásjegyzetek). - doi : 10.1007/978-3-540-74450-4_13 . .
  64. ↑ Peter Clote, Stefan Dobrev, Ivan Dotu, Evangelos Kranakis, Danny Krizanc, Jorge Urrutia. Az RNS másodlagos struktúráinak oldalszámáról pszeudoknotokkal // Journal of Mathematical Biology. - 2012. - T. 65 , sz. 6–7 . - S. 1337-1357 . - doi : 10.1007/s00285-011-0493-6 . .
  65. ↑ A. Pavan, Raghunath Tewari, NV Vinodchandran. Az egyértelműség hatalmáról a log-térben // Számítási komplexitás. - 2012. - T. 21 , sz. 4 . — S. 643–670 . - doi : 10.1007/s00037-012-0047-3 . .
  66. ↑ Zvi Galil, Ravi Kannan, Szemerédi Endre. Nemtriviális elválasztókról k-oldalas gráfokhoz és szimulációkhoz nemdeterminisztikus egyszalagos Turing-gépekkel // Journal of Computer and System Sciences. - 1989. - T. 38 , sz. 1 . – S. 134–149 . - doi : 10.1016/0022-0000(89)90036-6 . .

Irodalom