Investice do knihy

Knižní vnoření v teorii grafů  je zobecněním rovinného vnoření grafu do vnoření v knize  – množina polorovin , které mají stejnou přímku jako hranici. Obvykle je požadováno, aby vrcholy grafu ležely na této hranici a okraje musí být uvnitř stejné stránky. Tloušťka knihy (nebo počet stránek ) grafu je nejmenší počet polorovin pro všechna knižní vložení grafu. [1] Vložení knihy se používá pro několik dalších invariantů grafu , včetně šířky stránky [2] a počtu křížků knihy [3] .

Každý graf s n vrcholy má šířku knihy nejvýše . Tato hranice je pro úplné grafy blízká [1] . Rozdělení každé hrany však může snížit tloušťku knihy na hodnotu úměrnou druhé odmocnině z n . [4] Grafy s tloušťkou knihy jedna jsou vnější rovinné grafy , [1] a grafy s tloušťkou knihy nejvýše dvě jsou subhamiltonské , které jsou vždy rovinné [2] . Libovolný rovinný graf má tloušťku knihy nepřesahující čtyři [5] . Všechny méně uzavřené rodiny grafů , a zejména grafy s omezenou šířkou stromu nebo ohraničeným rodem , mají také omezenou tloušťku knihy [6] . Určení přesné tloušťky knihy daného grafu je NP-těžký problém , ať už je pořadí vrcholů na hřbetu známé nebo ne [7] [8] .

Jedním z prvotních důvodů pro studium vnořování knih byla její aplikace v návrhu VLSI , kde vrcholy vnoření knih představují komponenty a hrany představují spojení mezi komponentami [7] [9] . Při vizualizaci grafů lze sestavit dva standardní styly znázornění grafů, obloukové diagramy [10] a kruhové uspořádání [11] , pomocí vnoření knih. Různé počáteční a koncové body provozu pro chodce a vozidla, které jsou regulovány semaforem , lze matematicky modelovat jako vrcholy grafu, s hranami představujícími dvojice začátku a konce, a knižní vnoření tohoto grafu lze použít k vytvoření semaforu. chování k zajištění regulace provozu s minimálním počtem stavů semaforu [12] . V bioinformatických problémech zabývajících se strukturami RNA představuje jednostránkové vložení knihy klasickou formu sekundární struktury nukleové kyseliny a dvoustránkové vložení představuje pseudouzly [13] . Vkládání knih se také používá v obecné algebře [14] a teorii uzlů [15] [16] .

Otevřené otázky týkající se investování do knih jsou

Historie

Název „kniha“ zavedli Persinger a Atneosen (CA Persinger, Gail Atneosen) v 60. letech [21] [22] [23] . Atneosen již používal vkládání grafů do knih, ale formální koncept vkládání knih formulovali C. Kainen a L. Taylor Ollman na počátku 70. let a byla přidána některá další omezení na metodu vkládání – v jejich formulaci se vrcholy grafu musí ležet na hřbetu knihy, každá hrana musí ležet na jedné stránce (neprotínat hřbet) a libovolné dvě hrany se protínají pouze ve společných koncových vrcholech [24] [25] .

Důležitými milníky v dalším vývoji vkládání knih jsou důkaz Michalise Giannakakise z konce 80. let 20. století, že tloušťka knihy rovinných grafů nepřesahuje čtyři [26] [5] , a objev na konci 90. let úzkého vztahu mezi knihou vkládání a bioinformatika . [13]

Definice

Kniha je zvláštní druh topologického prostoru (nazývaný také vějíř polorovin) [21] [27] . Skládá se z jedné přímky ℓ nazývané hřbet [28] knihy, spolu se sadou jedné nebo více polorovin nazývaných stránky nebo listy knihy. Každá polorovina musí mít stejnou přímku ℓ jako její hranice. Knihy s konečným počtem ( k ) stránek lze vnořit do trojrozměrného prostoru, například výběrem pravoúhlého souřadnicového systému jako čáry ℓ osy z a jako i - té stránky (z k ) jedné může mít množinu bodů p tak, že nejkratší segment spojující p s osou z má úhel 2π i / k vzhledem k rovině xz [1] .

Vizualizace knihy konečného grafu G do knihy B je nakreslením grafu G v B , takže jakýkoli vrchol G je nakreslen na hřbetu B a jakákoli hrana G je nakreslena jako křivka ležící na jedné stránce B. K- stránkový počet průsečíků grafu G  je minimální počet průsečíků ve výkresu na k - stránkové knize [3] .

Knižní vložení grafu G do B  je vložení grafu G do prostoru B . To znamená, že jde o nakreslení grafu G v B , ve kterém se hrany neprotínají. Každý konečný graf má knihu vnořenou do knihy s dostatečně velkým počtem stránek. Například je vždy možné vnořit každou hranu na vlastní stránku. Tloušťka knihy , počet stránek nebo číslo zásobníku grafu G  je minimální počet stránek potřebný pro vnoření knihy do grafu G. Dalším parametrem, který měří kvalitu knižní přílohy, je kromě počtu stran šířka stránky . Toto je maximální počet hran, které protínají paprsek kolmý ke hřbetu uvnitř jedné stránky. Ekvivalentně (u knižních vložek, ve kterých je každá hrana nakreslena jako monotónní křivka), je to maximální velikost podmnožiny hran tak, že se všechny intervaly definované na hřbetu koncovými body hran protínají [2] [29]. [30] .

Pro tyto definice je podstatné, že okraje mohou ležet pouze na jedné stránce. Jak již poznamenal Ameosen, pokud okraje mohou jít ze stránky na stránku (přes hřbet), pak lze do třístránkové knihy vložit jakýkoli graf [22] [31] [20] . Pro třístránkové vložení topologické knihy , ve kterém je povolen průnik hřbetu, však zůstává zajímavým problémem určit nejmenší číslo průsečíku hřbetu, které umožňuje vložení grafu do knihy [20] [32] .

Konkrétní grafy

Jak je znázorněno na prvním obrázku, tloušťka celého grafu je tři. Protože je nerovinný, jeho tloušťka knihy je větší než dvě, ale je zde vnořená kniha se třemi stránkami. Tloušťka knihy jakéhokoli úplného vrcholového grafu je přesně . Tento výsledek udává horní hranici maximální tloušťky knihy všech grafů s vrcholy [1] . Dvoustránkové číslo průsečíku celého grafu je

což je v souladu s neprokázanou domněnkou Anthonyho Hilla . To znamená, že pokud je Hillova domněnka pravdivá, pak je kresba tohoto grafu minimalizující počet průniků dvoustránkovou kresbou [33] .

Tloušťka knihy kompletního bipartitního grafu je téměř stejná  - pro každý vrchol menší části můžete uspořádat hrany s těmito vrcholy na jejich vlastní stránce. Tento limit není vždy přísný. Například má tloušťku knihy tři, ne čtyři. Pokud jsou však dvě strany grafu značně nevyvážené, c , tloušťka knihy je přesně . [1] [34] Tloušťka svazků binárních de Bruijnových grafů, grafů zamíchané výměny a kubických sítí s cykly (když jsou tyto grafy dostatečně velké, aby nebyly rovinné) je přesně tři. [35]

Vlastnosti

Chování pododdělení

Nevyřešené problémy v matematice : Může být tloušťka knihy grafu omezena funkcí tloušťky knihy pododdělení?

Rozdělení každé hrany grafu na dvouhranné cesty přidáním nových vrcholů pro každou hranu může někdy zvýšit tloušťku knihy (například diamant má tloušťku knihy jedna, ale jeho poddělení má tloušťku knihy dvě). Takový pododdíl však může také výrazně snížit knižní tloušťku grafu po rozdělení. Například tloušťka knihy úplného grafu K n je Θ( n ) je úměrná počtu jeho vrcholů, ale rozdělení každé hrany na dvě dává dělení s mnohem menší tloušťkou knihy, pouze O(√ n ). [4] . Navzdory existenci příkladů, jako je ten výše, Blankenship a Oporowski [31] předpokládali , že tloušťka pododdělení nemůže být podstatně menší než tloušťka původního grafu. Konkrétně předpokládali, že existuje nějaká funkce f , že pro libovolný graf G a graf H získaný nahrazením každé hrany G cestou dvou hran, je-li tloušťka grafu H t , pak tloušťka grafu G nepřesahuje f ( t ) . [31] Do roku 2013 zůstal Blankenship-Oporowski domněnka neprokázaná. [17]

Rovinnost a vnější rovinnost

Tloušťka knihy daného grafu G nepřesahuje 1 právě tehdy, když je G vnější rovina . Vnější rovinný graf je graf, který má rovinné vložení, ve kterém všechny vrcholy patří k vnější ploše vložení. U takových grafů umístění vrcholů ve stejném pořadí podél hřbetu, v jakém se objevují na vnější ploše (když se vrchol znovu objeví na vnější ploše, je pořízena pouze jedna kopie vrcholu), vede k vložení jednostránkového grafu. Naopak jednostránkové vnoření knihy je automaticky vnější rovina – pokud je graf vnořen do jedné stránky, přidáním druhé poloroviny vznikne plná rovina a vnější plocha bude obsahovat celou přidanou polorovinu se všemi vrcholy ležícími na toto vnější čelo [1] [2] .

Jakékoli vložení knihy se dvěma stránkami je zvláštním případem plošného vložení, protože spojení dvou stránek knihy je prostor, který je topologicky ekvivalentní rovině. Každý graf s tloušťkou knihy dvě je tedy automaticky rovinný . Přesněji řečeno, tloušťka grafu G je nejvýše dvě právě tehdy, když G je podgrafem rovinného grafu, který má hamiltonovský cyklus [1] . Daný graf s knižním vložením dvou stránek lze graf rozšířit na rovinný hamiltonovský graf přidáním (na libovolné stránce) dalších hran mezi libovolné dva po sobě jdoucí vrcholy podél hřbetu, pokud již nejsou spojeny hranou, a mezi prvním a posledním vrcholem páteře. Goldnerův–Harariho graf uvádí příklad rovinného grafu, který nemá tloušťku knihy dvě - jedná se o maximální rovinný graf , takže není možné přidat žádnou hranu při zachování rovinnosti a graf nemá hamiltonián cyklus [1] . Kvůli požadavku mít hamiltonovské cykly jsou grafy, které umožňují dvoustránkové vnoření, známé jako subhamiltonovské grafy [2] .

Všechny rovinné grafy s maximálním stupněm nejvýše čtyři mají hloubku vložení knihy nejvýše dvě. [36] . Rovinné 3-stromy mají maximální šířku knihy tři [37] . Všechny rovinné grafy mají tloušťku knihy nepřesahující čtyři [26] [5] . Jak uvedl Michalis Yannakakis v roce 1986 [26] , existují rovinné grafy s tloušťkou vložení knihy přesně rovnou čtyřem, ale podrobný důkaz tohoto tvrzení, oznámený v [5] , nebyl nikdy publikován. Z tohoto důvodu Duimovich [19] označil problém stanovení maximální tloušťky knižního vložení rovinných grafů za nevyřešený [19] .

Vztah s jinými invarianty grafu

Tloušťka knihy souvisí s tloušťkou grafu , počtem rovinných grafů, které jsou potřeba k pokrytí okrajů daného grafu. Graf G má tloušťku θ, pokud může být zasazen do roviny a hrany mohou být obarveny v barvách θ takovým způsobem, že se hrany stejné barvy neprotínají. Podobně má graf G šířku knihy θ, pokud jej lze nakreslit v polorovině s vrcholy na hranici poloroviny a obarvit hranou barvami θ bez křížení hran stejné barvy. Při této formulaci odpovídají okraje stejné barvy stránkám přílohy knihy. Tloušťka grafu a tloušťka knihy se však mohou výrazně lišit - existují dělení úplných grafů , které mají neomezenou tloušťku knihy [31] [20] [4] , a to přesto, že tloušťka grafu je stejná do dvou [4] .

Grafy se šířkou stromu k mají šířku knihy nejvýše k + 1 [19] [38] a této hranice je dosaženo pro k > 2. [19] . Grafy s m hranami mají šířku knihy O(√ m ) [39] a grafy s rodem g mají  šířku knihy O(√ g ) [40] . Obecněji řečeno, každá malá uzavřená rodina grafů má omezenou tloušťku knihy [6] [41] .

Jakákoli kontrahující se menší hodnota grafu ohraničené tloušťky knihy je řídký graf , jehož poměr hrany k vrcholu je ohraničen konstantou, která závisí pouze na hloubce menší části a tloušťce knihy. To znamená, že v terminologii Nexetrilu [6] mají grafy s ohraničenou tloušťkou knihy ohraničený růst [6] . Avšak i grafy s omezeným stupněm grafu, což je podstatně silnější požadavek na omezení růstu, mohou mít neomezenou tloušťku knihy [42] .

Protože dva grafy tloušťky knihy jsou rovinné grafy, splňují teorém o rovinném dělení  — mají separátory, podmnožiny vrcholů, jejichž odstranění rozdělí graf na části s nejvýše 2 n /3 vrcholy v každém kusu, pouze s O(√ n ) vrcholy v separátoru. Zde n znamená počet vrcholů grafu. Existují však grafy s tloušťkou knihy tři, které nemají sublineární oddělovače velikosti [43] .

Okraje na jedné stránce přílohy knihy se chovají jako stoh . To lze formalizovat tím, že vezmeme v úvahu libovolnou posloupnost operací push a pop (tlačení a popping) na zásobníku a vytvoříme graf, ve kterém operace zásobníku odpovídají vrcholům grafu umístěného na hřbetu knižní vložky v zásobníku. pořadí operací. Pokud nyní nakreslíme hranu z každé operace pop, která vytáhne objekt x ze zásobníku do operace push, která tento prvek zatlačí do zásobníku, bude mít výsledný graf automaticky jednostránkové vnoření. Z tohoto důvodu se počet stránek grafu nazývá také jeho číslo zásobníku . Analogicky vědci definují další vložení grafu jako kresbu grafu v knize, ve které se libovolné dvě hrany na stránce buď protínají, nebo překlenují neprotínající se intervaly na hřbetu. Taková vložení nějakým způsobem odpovídají frontám a minimální počet stránek požadovaný pro každé vložení grafu se nazývá počet front [6] [44] [45] .

Výpočetní složitost

Určení tloušťky vložení knihy je NP-těžký problém . To vyplývá ze skutečnosti, že nalezení Hamiltonova cyklu v maximálních rovinných grafech je NP-úplný problém . Tloušťka knižního vložení maximálního rovinného grafu je dvě právě tehdy, když existuje hamiltonovská cesta. Proto určení, že tloušťka vložení knihy daného maximálního rovinného grafu je dvě, je také NP-úplný problém. [7]

Pokud je pořadí vrcholů podél hřbetu při vnoření knihy předem určeno, lze v lineárním čase nalézt vnoření dvou stránek (pokud existuje) jako možnost testu rovinnosti pro graf získaný rozšířením daného grafu vytvořením smyčky spojující vrcholy podél páteře [13] . Unger tvrdil, že nalezení třístránkového vložení s předem určeným pořadím vrcholů lze provést v polynomiálním čase , ačkoliv jeho popis tohoto výsledku postrádá řadu podstatných detailů [18] . U grafů, které vyžadují čtyři nebo více stránek, však zůstává problém najít vložení s nejmenším možným počtem stránek NP-obtížný kvůli ekvivalentu k NP-těžkému problému vybarvování kruhových grafů , průsečíkových grafů kruhových tětiv . Dáme-li graf G s pevným pořadím vrcholů na páteři, umístěním těchto vrcholů ve stejném pořadí na kružnici a reprezentujícím hrany G jako segmenty získáme sadu tětiv reprezentujících graf G . Nyní lze vytvořit kruhový graf , který má tětivy tohoto diagramu jako vrcholy a protínající se dvojice tětiv jako hrany. Vybarvením kruhového grafu získáte rozdělení hran grafu G do podmnožin, které lze nakreslit bez průniků na jednu stránku. Optimální vybarvení je tedy ekvivalentní optimálnímu vložení knihy. Vzhledem k tomu, že vybarvování kruhového grafu čtyřmi nebo více barvami je NP-obtížné, a protože lze tímto způsobem vygenerovat jakýkoli kruhový graf z nějakého problému s nalezením vložení knihy, nalezení optimálního vložení knihy je také NP-těžký problém [8] [46] [47] . Pro pevné pořadí vrcholů na hřbetu pod dvoustránkovým vnořením je NP-těžký problém minimalizovat počet průsečíků, pokud je tento počet nenulový [46] .

Pokud je neznámé pořadí vrcholů na hřbetu, ale stránkování hran je dané, je možné najít 2-stránkové vnoření (pokud existuje) v lineárním čase použitím algoritmu založeného na stromech SPQR [48] [ 49] . Nalezení 2stránkového vnoření je však NP-úplné, pokud není známo ani pořadí vrcholů na hřbetu, ani stránkování hran. Najít knižní počet průsečíků grafu je také NP-obtížné kvůli NP-úplnosti problému kontroly, zda je dvoustránkový knižní počet průsečíků nula.

Problém izomorfismu podgrafu , který má určit, zda se nějaký velikostně ohraničený graf nějakého druhu nachází jako podgraf většího grafu, může být vyřešen v lineárním čase, pokud má větší graf tloušťku ohraničené knihy. Totéž platí pro určení, zda je graf nějakého druhu vygenerovaným podgrafem většího grafu, nebo zda má homeomorfismus s větším grafem [50] [51] . Ze stejného důvodu je problém kontroly, zda graf s ohraničenou tloušťkou knihy vyhovuje danému logickému vzorci prvního řádu řešitelný s ohledem na pevný parametr [52] .

Aplikace

Víceprocesorové výpočty odolné proti chybám

Jedním z hlavních důvodů pro studium vkládání knih (podle Changa, Leightona a Rosenberga [7] ) je jeho použití při vývoji VLSI k vytvoření víceprocesorových systémů odolných proti chybám . V systému DIOGENES vyvinutém těmito autory jsou procesory víceprocesorového systému organizovány v logickém řetězci odpovídajícím hřbetu knihy (ačkoliv nemusejí být na schématu fyzicky umístěny v přímce ). Komunikační linky těchto procesorů jsou seskupeny do „balíčků“, které odpovídají stránkám knihy a fungují jako stohy  – připojení jednoho z procesorů na začátek komunikační linky posune všechna předchozí spojení ve svazku a připojení dalšího procesoru na konec komunikační linky jej připojí k jednomu z nižších procesorů v paprsku a zatlačí všechny zbývající dolů. Díky tomuto chování při stohování může jeden svazek obsluhovat sadu komunikačních linek, které tvoří okraje jedné stránky přílohy knihy. Uspořádáním spojení tímto způsobem lze implementovat širokou škálu topologií, ve kterých nezáleží na tom, který procesor selže, pokud v síti zůstane dostatek procesorů. Síťové topologie, které mohou být organizovány takovým systémem, jsou přesně ty, které mají tloušťku knihy a nepřesahují počet svazků, které mají být zpřístupněny [7] .

Řazení zásobníku

Další aplikace, na kterou poukázali Chang, Leighton a Rosenberg [7] , se týká třídění permutací pomocí zásobníků . Knuth ukázal , že systém , který zpracovává tok dat tím , že vloží vstupní prvky do zásobníku a poté je ve správný čas vloží do výstupního toku , může data třídit tehdy a pouze tehdy , pokud v původním pořadí prvků neexistují žádné permutace vzorů 53 ] . Od té doby bylo na tomto a podobných problémech řazení toku dat s obecnějšími zásobníkovými a frontovými systémy hodně práce. V systému uvažovaném Changem, Leightonem a Rosenbergem musí být každý prvek ze vstupního proudu vytlačen na jeden ze zásobníků. Poté, co byla všechna data vložena do zásobníků, jsou prvky odsunuty z těchto zásobníků (ve vhodném pořadí) do výstupního proudu. Jak poznamenali Chang et al., danou permutaci lze tímto systémem třídit tehdy a pouze tehdy, když některý graf získaný z permutace má vložení knihy s pevným pořadím vrcholů podél hřbetu a počtem stránek nepřesahujícím počet hromádky [7] .

Ovládání pohybu

Jak popisuje Kainen [12] , vkládání knih lze použít k popisu fází semaforů na řízené křižovatce. Na křižovatce mohou být vjezdové a odchozí jízdní pruhy (včetně konců přechodů pro chodce a jízdních pruhů pro cyklisty) znázorněny jako vrcholy grafu umístěné na hřbetu přílohy knihy v pořadí odpovídajícím pořadí vjezdu/výjezdu z provozu podél křižovatka (ve směru hodinových ručiček). Cesty přes křižovatku, kde se pohybuje doprava, a chodci od vstupního bodu k výstupnímu bodu, lze znázornit jako okraje neorientovaného grafu. Tento graf by například mohl mít okraj od vstupního pruhu k výstupnímu pruhu, který patří ke stejnému segmentu silnice, což představuje odbočení do protisměru, pokud je na křižovatce povoleno odbočení. Daná podmnožina takových hran představuje množinu cest, které lze sledovat bez průsečíků právě tehdy, když podmnožina neobsahuje pár protínajících se hran, které jsou na stejné stránce vnořené knihy. Knižní vložení grafu tedy popisuje rozdělení cest do podmnožin, ve kterých se pohyb neprotíná, a tloušťka knihy tohoto grafu (s pevným zapuštěním na hřbet) udává minimální počet různých fází semaforu potřebných pro semaforový plán, který zahrnuje všechny možné cesty přes křižovatku [12] . Tento model však není použitelný pro složitější systémy řízení dopravy, které nemají pevný harmonogram.

Vizualizace grafu

Vkládání knih se také často používá k vizualizaci síťového datového toku. Dvě standardní grafová vizualizační schémata , obloukové grafy [10] a koláčové grafy [11] , lze považovat za investici do knihy. Vkládání knih lze také použít k vytváření shlukových schémat [48] , simultánních vkládání [54] a 3D grafových nákresů [55] .

Obloukový diagram [10] nebo vložení čáry [46] umístí vrcholy grafu na čáru a okraje grafu jsou nakresleny jako půlkruhy nad a pod touto čárou, což někdy umožňuje, aby hrany byly úsečkami. Tento styl kresby odpovídá vnoření knihy s jednou stránkou (pokud jsou všechny půlkruhy nad čarou) nebo dvěma stránkami (pokud jsou použity obě strany čáry) a byl původně zaveden jako způsob, jak studovat počet průsečíků grafů. [56] [57] Rovinné grafy, které nemají dvoustránkové knižní vnoření, lze nakreslit podobným způsobem tak, že umožníme znázornění hran dvěma půlkruhy nad a pod přímkou. Takové kresby nejsou knižními vloženími z hlediska obvyklé definice a nazývají se topologická knižní vložení [58] . Pro jakýkoli rovinný graf je vždy možné najít vložení, které protíná páteř nejvýše jednou. [59] .

V jiném stylu kreslení je kruhové uspořádání , vrcholy grafu jsou umístěny na kružnici a hrany jsou nakresleny uvnitř nebo vně kruhu [11] . Uspořádání hran uvnitř kruhu (např. jako úsečky) opět odpovídá jednostránkové knižní kresbě, zatímco uspořádání hran na obou stranách kruhu odpovídá dvoustránkové knižní kresbě [60] .

U jednostránkových kreseb libovolného stylu je důležité udržovat nízký počet průsečíků, aby se snížil vizuální chaos kresby. Minimalizace počtu průsečíků je NP-úplný problém [46] , ale problém lze aproximovat vztahem O (log 2 n ), kde n je počet vrcholů [61] . Minimalizace jednostránkového nebo dvoustránkového čísla průsečíku je rozhoditelná s ohledem na pevný parametr při parametrizaci cyklomatickým číslem daného grafu [62] . Ke snížení složitosti průniků byly vyvinuty také heuristické metody založené například na přesném pořadí vkládání vrcholů a na lokální optimalizaci [11] .

Dvoustránkové vložení knihy s pevným rozložením hran napříč stránkami lze znázornit jako druh shlukové rovinnosti , ve které musí být daný graf nakreslen tak, aby části grafu (dvě podmnožiny hran) byly uspořádány v obrázek odráží jejich shlukování [48] . Dvoustránkové vložení knihy se také používá k nalezení současného vložení grafu, ve kterém jsou dva grafy uvedeny na stejné množině vrcholů a je třeba najít umístění vrcholů, ve kterých jsou oba grafy nakresleny rovinně pomocí přímky segmenty [54] .

Knižní přílohy, které mají více než dvě stránky, se používají k vytváření trojrozměrných nákresů grafů. Zejména Wood použil konstrukci knižních vložení, které zachovávají nízký stupeň každého vrcholu na každé stránce, jako metodu vkládání grafů do trojrozměrné mřížky malého objemu [55] .

Skládací RNA

Při studiu toho, jak se molekuly RNA skládají do struktury RNA, lze standardní pohled na sekundární strukturu nukleové kyseliny popsat pomocí diagramu jako řetězce bází (sekvence RNA) nakresleného podél přímky spolu se sadou oblouků nad čarou, které popisují spárované základy struktury. To znamená, že ačkoli má tato struktura složitý trojrozměrný vzhled, její spojení (pokud existuje sekundární struktura) lze popsat abstraktnější strukturou, jednostránkovou knižní přílohou. Ne všechny RNA se však chovají takto jednoduše. Haslinger a Stadler navrhli takzvanou "bisekundární strukturu" pro určité pseudouzly RNA , které mají formu dvoustránkového vnoření knihy - sekvence RNA je opět nakreslena podél přímky, ale párové báze jsou nakresleny jako oblouky nad a pod tímto řádkem. Pro vytvoření bisekundární struktury musí mít graf stupeň nepřesahující tři - každá báze může být pouze v jednom okraji diagramu a také ve dvou vazbách se sousedními bázemi v sekvenci. Výhodou této formulace je skutečnost, že vylučuje struktury, které jsou skutečně v prostoru zauzlované, a že pokrývá většinu známých pseudouzlů RNA [13] .

Vzhledem k tomu, že pořadí na páteři je zpočátku známé, je přímo kontrolována existence bisekundární struktury pro dané párové báze. Úlohu rozložení hran na dvě stránky lze formulovat jako speciální případ problému splnitelnosti booleovských formulí ve 2-konjunktivním normálním tvaru nebo jako problém kontroly bipartitnosti kruhového grafu , jehož vrcholy jsou párové báze, a hrany popisují křížení mezi párovými bázemi [13] . Dalším a účinnějším způsobem, jak ukázal Haslinger a Stadler [13] , jak určit, že existuje bisekundární struktura, je skutečnost, že k ní dojde právě tehdy, když vstupní graf (graf vytvořený smyčkou bází v následujícím a přidání párových bází jako hran) je rovinné [13] . Tato skutečnost umožňuje rozpoznat bisekundární strukturu v lineárním čase jako speciální případ testu rovinnosti .

Blin, Fertin, Rusu a Sinokvet použili vztah mezi sekundárními strukturami a přílohami knihy jako součást důkazu , že některé problémy srovnávání sekundárních struktur RNA jsou NP-těžké [63] . A pokud je struktura RNA spíše terciární než bisekundární (tj. pokud je v jejím diagramu vyžadováno více než dvě stránky), pak je určení počtu stránek opět NP-těžký problém [64] .

Teorie výpočetní složitosti

Paian, Tewari a Vinodsoandran použili vkládání knih ke studiu výpočetní složitosti problému dosažitelnosti v orientovaných grafech . Jak poznamenali, problém dosažitelnosti pro dvoustránkové orientované grafy lze vyřešit v jednohodnotovém logaritmickém prostoru (analogickém k deterministické logaritmické paměťové složitosti problémů třídy UP ). Problém dosažitelnosti pro třístránkové orientované grafy však dává nedeterministickou logaritmickou paměťovou složitost . Zdá se tedy, že vkládání knih úzce souvisí s rozdíly mezi těmito dvěma třídami složitosti [65] .

Existence expandérů s konstantním počtem stran [43] je klíčovým krokem k prokázání, že neexistuje žádná časově subkvadratická simulace dvoupáskových nedeterministických Turingových strojů jednopáskovými nedeterministickými stroji [66] .

Jiné oblasti matematiky

Mackenzie a Overbey [14] studovali aplikace tloušťky knihy v obecné algebře pomocí grafů odvozených z nulových dělitelů konečného lokálního kruhu vytvořením vrcholu pro každého nulového dělitele a hrany pro každou dvojici hodnot, jejichž součin je nula [14] .

V řadě článků studoval Dynnikov vkládání uzlů a odkazů v topologických knihách a ukázal, že tato vložení lze popsat kombinatorickou sekvencí symbolů a že topologická ekvivalence dvou odkazů může být ukázána sekvencí lokálních změn vložení [15 ] [16] .

Poznámky

  1. ↑ 1 2 3 4 5 6 7 8 9 Bernhart a Kainen, 1979 , str. 320–331.
  2. ↑ 1 2 3 4 5 Heath, 1987 , str. 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 , str. 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 a kol., 1987 , str. 33–58.
  8. ↑ 12 Unger , 1988 , s. 61–72.
  9. ↑ Arnold L. Rosenberg. Sborník ze sedmnácté mezinárodní konference Southeastern o kombinatorice, teorii grafů a počítačích (Boca Raton, Florida, 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 , str. 332–343.
  12. ↑ 1 2 3 Kainen, 1990 , str. 127–132.
  13. ↑ 1 2 3 4 5 6 7 Haslinger a kol., 1999 , str. 437–467.
  14. ↑ 1 2 3 McKenzie, Overbay, 2010 , str. 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: 9. výroční symposium o teoretických aspektech informatiky, Cachan, Francie, 13.–15. února 1992, sborník příspěvků. - Berlin: Springer, 1992. - T. 577. - S. 389-400. — (Poznámky z informatiky). - 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 , str. 337–341.
  21. ↑ 12 Persinger , 1966 , s. 169–173.
  22. ↑ 1 2 Atneosen, 1968 , str. 79.
  23. ↑ Gail H. Atneosen. Jednorozměrné n - listé kontinuum // Fundamenta Mathematicae . - 1972. - T. 74 , čís. 1 . — s. 43–45 . .
  24. ↑ Paul C. Kainen. Grafy a kombinatorika (Sborník příspěvků z Capital Conference on Graph Theory and Combinatorics na Univerzitě George Washingtona 18.–22. června 1973) / Ruth A. Bari, Frank Harary. - 1974. - T. 406. - S. 76-108. — (Poznámky z matematiky). .
  25. ↑ L. Taylor Ollmann. Proč. 4. 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 , str. 104–108.
  27. ↑ T. C. Hales. Kulové obaly. II // Diskrétní a výpočetní geometrie. - 1997. - T. 18 , no. 2 . — S. 135–149 . - doi : 10.1007/PL00009312 . .
  28. ↑ Původně páteř nebo záda
  29. ↑ Elena Stohrová. Kompromis mezi číslem stránky a šířkou stránky knižního vložení grafů // Informace a výpočty. - 1988. - T. 79 , no. 2 . — S. 155–162 . - doi : 10.1016/0890-5401(88)90036-3 . .
  30. ↑ Elena Stohrová. Šířka stránky trivalentních rovinných grafů // Diskrétní matematika . - 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. Dolní hranice pro počet přechodů hran přes hřbet v topologické knize vložení grafu // Diskrétní aplikovaná matematika. - 1999. - T. 92 , č. 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. Sborník příspěvků z 28. výročního sympozia o výpočetní geometrii (SCG'12). - ACM, New York, 2012. - S. 397-403. - doi : 10.1145/2261250.2261310 . .
  34. ↑ Další výsledky o tloušťce knihy úplných bipartitních grafů viz Etienne de Klerk, Dmitrii V. Pasechnik, Gelasio Salazar. Knižní kresby kompletních bipartitních grafů // Diskrétní aplikovaná matematika. - 2014. - T. 167 . — S. 80–93 . - doi : 10.1016/j.dam.2013.11.001 . .
  35. ↑ Toru Hasunuma, Yukio Shibata. Vkládání sítí de Bruijn, Kautz a shuffle-exchange network do knih // Diskrétní aplikovaná matematika. - 1997. - T. 78 , no. 1-3 . — S. 103–116 . - doi : 10.1016/S0166-218X(97)00009-7 . Yuuki Tanaka, Yukio Shibata Na stránce číslo cyklů spojených krychlí // Matematika v informatice. - 2010. - Vol. 3 , vydání. 1 . — S. 109–117 . - doi : 10.1007/s11786-009-0012-y . Viz také Bojana Obrenic. Vložení de Bruijn a grafy pro náhodné výměny na pěti stránkách // SIAM Journal on Discrete Mathematics. - 1993. - T. 6 , no. 4 . — S. 642–654 . - doi : 10.1137/0406049 . .
  36. ↑ Bekos et al, 2014 , pp. 137–148.
  37. ↑ Lenny Heath. Sborník příspěvků z 25. výročního sympozia o základech informatiky. - 1984. - S. 74-83. - doi : 10.1109/SFCS.1984.715903 .
  38. ↑ Joseph L. Ganley, Lenwood S. Heath. Číslo stránky k -stromů je O ( k ) // Diskrétní aplikovaná matematika. - 2001. - T. 109 , vydání. 3 . — S. 215–221 . - doi : 10.1016/S0166-218X(00)00178-5 . .
  39. ↑ Seth M. Malitz. Grafy s E hranami mají číslo stránky O (√ E ) // Journal of Algorithms : journal. - 1994. - Červenec ( díl 17 , číslo 1 ). — s. 71–84 . - doi : 10.1006/jagm.1994.1027 .
  40. ↑ Seth M. Malitz. Grafy rodu g mají číslo stránky O (√ g ) // Journal of Algorithms. - 1994. - T. 17 , no. 1 . — S. 85–109 . - doi : 10.1006/jagm.1994.1028 . .
  41. ↑ R. Blankenship. Kniha vkládání grafů. — Katedra matematiky, Louisiana State University, 2003. . Jak cituje Neshetri.
  42. ↑ János Barát, Jiří Matoušek, David R. Wood. Grafy s ohraničeným stupněm mají libovolně velkou geometrickou tloušťku // Electronic Journal of Combinatorics. - 2006. - T. 13 , no. 1 . — C. R3 . .
  43. ↑ 1 2 Vida Dujmovic, Anastasios Sidiropoulos, David R. Wood. 3-monotónní expandéry. - arXiv : 1501.05020 . , zlepšení oproti dřívějšímu výsledku Jean Bourgain. Expandéry a rozměrová expanze // Comptes Rendus Mahematique. - 2009. - T. 347 , č.p. 7-8 . — S. 357–362 . - doi : 10.1016/j.crma.2009.02.009 . ; Jean Bourgain, Amir Yehudayoff. Expanze v a monotónních expandérech // Geometric and Functional Analysis. - 2013. - T. 23 , no. 1 . — S. 1–41 . - doi : 10.1007/s00039-012-0200-9 . . Viz také Zvi Gali, Ravi Kannan, Endre Szemerédi. Na 3tlačítkových grafech s velkými oddělovači  // Combinatorica. - 1989. - T. 9 , no. 1 . — S. 9–19 . - doi : 10.1007/BF02122679 . ; Zeev Dvir, Avi Wigderson. Monotónní expandéry: konstrukce a aplikace // Theory of Computing. - 2010. - T. 6 . — S. 291–308 . - doi : 10.4086/toc.2010.v006a012 . .
  44. ↑ Lenwood S. Heath, Arnold L. Rosenberg. Rozvržení grafů pomocí front // SIAM Journal on Computing. - 1992. - T. 21 , no. 5 . — S. 927–958 . - doi : 10.1137/0221055 . .
  45. ↑ Vida Dujmovic, David R. Wood. O lineárních rozloženích grafů // Diskrétní matematika a teoretická informatika. - 2004. - T. 6 , no. 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. Složitost barvení kruhových oblouků a tětiv // SIAM Journal on Algebraic and Discrete Methods. - 1980. - svazek 1 , vydání. 2 . — S. 216–227 . - doi : 10.1137/0601025 . .
  48. ↑ 1 2 3 Hong, Nagamochi, 2009 .
  49. ↑ Patrizio Angelini, Marco Di Bartolomeo, Giuseppe Di Battista. Grafická kresba: 20. mezinárodní symposium, GD 2012, Redmond, WA, USA, 19.–21. září 2012, Revised Selected Papers. - Springer, 2013. - T. 7704. - S. 79–89. — (Poznámky z informatiky). - 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 , Důsledek 18.1, str. 401.
  52. ↑ Nešetřil, Ossona de Mendez, 2012 , Věta 18.7, str. 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 , pp. 150–172.
  55. ↑ 12 Dřevo , 2002 , s. 312–327.
  56. ↑ Thomas L. Saaty. Minimální počet průsečíků v kompletních grafech // 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. Permutační postup pro minimalizaci počtu křížení v síti // Proceedings of the Institution of Electrical Engineers. - 1968. - T. 115 . — S. 21–26 . - doi : 10.1049/piee.1968.0004 . .
  58. ↑ Miki Miyauchi. Topological book embedding of bipartite graphs  (anglicky)  // IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences. - 2006. - Sv. E89-A , iss. 5 . — S. 1223–1226 . - doi : 10.1093/ietfec/e89-a.5.1223 .
  59. ↑ Francesco Giordano, Giuseppe Liotta, Tamara Mcchedlidze, Antonios Symvonis. Algoritmy a výpočty: 18. mezinárodní symposium, ISAAC 2007, Sendai, Japonsko, 17.–19. prosince 2007, Proceedings. - Springer, 2007. - T. 4835. - S. 172-183. — (Poznámky z informatiky). - doi : 10.1007/978-3-540-77120-3_17 . .
  60. ↑ Hongmei He, Ondřej Sýkora. Sborník příspěvků z workshopu o informačních technologiích – aplikace a teorie (ITAT), Slovensko, 15.–19. září 2004. - 2004. .
  61. ↑ Farhad Shahrokhi, Ondrej Sýkora, László A. Székely, Imrich Vrt'o. Graf-teoretické koncepty v informatice: 20. mezinárodní workshop, WG '94, Herrsching, Německo, 16.–18. června 1994, Proceedings. - Springer, 1995. - T. 903. - S. 256-268. — (Poznámky z informatiky). - doi : 10.1007/3-540-59071-4_53 . .
  62. ↑ Michael J. Bannister, David Eppstein, Joseph A. Simons. Grafická kresba: 21. mezinárodní symposium, GD 2013, Bordeaux, Francie, 23.–25. září 2013, Revised Selected Papers. - 2013. - T. 8242. - S. 340-351. — (Poznámky z informatiky). - doi : 10.1007/978-3-319-03841-4_30 . .
  63. ↑ Guillaume Blin, Guillaume Fertin, Irena Rusu, Christine Sinoquet. Kombinatorika, algoritmy, pravděpodobnostní a experimentální metodologie: První mezinárodní symposium, ESCAPE 2007, Hangzhou, Čína, 7.–9. dubna 2007, Revised Selected Papers. - 2007. - T. 4614. - S. 140-151. — (Poznámky z informatiky). - doi : 10.1007/978-3-540-74450-4_13 . .
  64. ↑ Peter Clote, Stefan Dobrev, Ivan Dotu, Evangelos Kranakis, Danny Krizanc, Jorge Urrutia. Na stránce číslo sekundárních struktur RNA s pseudouzly // Journal of Mathematical Biology. - 2012. - T. 65 , č.p. 6–7 . - S. 1337-1357 . - doi : 10.1007/s00285-011-0493-6 . .
  65. ↑ A. Pavan, Raghunath Tewari, NV Vinodchandran. O síle jednoznačnosti v log-prostoru // 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. O netriviálních oddělovačích pro k-stránkové grafy a simulace nedeterministickými jednopáskovými Turingovými stroji // Journal of Computer and System Sciences. - 1989. - T. 38 , no. 1 . — S. 134–149 . - doi : 10.1016/0022-0000(89)90036-6 . .

Literatura