Investiție de carte

O încorporare de carte în teoria grafurilor  este o generalizare a unei înglobări plane a unui graf la o încorporare într-o carte  - un set de semiplanuri care au aceeași linie dreaptă ca o limită. De obicei, este necesar ca vârfurile graficului să se afle pe această limită, iar marginile trebuie să fie în interiorul aceleiași pagini. Grosimea cărții (sau numărul de pagini ) a unui grafic este cel mai mic număr de semiplanuri pentru toate înglobările de cărți ale graficului. [1] Încorporarea cărții este utilizată pentru mai multe alte invariante ale graficului , inclusiv lățimea paginii [2] și numărul de cruci [3] ale cărții .

Orice grafic cu n vârfuri are cel mult o lățime de carte . Această limită este apropiată pentru graficele complete [1] . Cu toate acestea, subdivizarea fiecărei muchii poate reduce grosimea cărții la o cantitate proporțională cu rădăcina pătrată a lui n . [4] Graficele cu grosimea cărții unu sunt grafice exterioare planare , [1] iar graficele cu grosimea cărții cel mult două sunt sub-Hamiltoniene , care sunt întotdeauna plane [2] . Orice graf plan are o grosime de carte care nu depășește patru [5] . Toate familiile minor închise de grafice , și în special graficele cu lățime de arbore mărginită sau gen mărginit , au și grosimea cărții mărginite [6] . Determinarea grosimii exacte a cărții a unui graf dat este o problemă NP-hard , indiferent dacă ordinea vârfurilor de pe coloana vertebrală este cunoscută sau nu [7] [8] .

Unul dintre motivele inițiale pentru studierea imbricației cărților a fost aplicarea sa în proiectarea VLSI , unde vârfurile de imbricare a cărților reprezintă componente, iar marginile reprezintă conexiuni între componente [7] [9] . Când se vizualizează grafice, pot fi construite două stiluri standard de reprezentare grafică, diagrame cu arc [10] și aranjamente circulare [11] , folosind imbricarea cărților. Diferitele puncte de început și de sfârșit ale traficului pentru pietoni și vehicule care sunt reglementate de un semafor pot fi modelate matematic ca vârfuri grafice, cu muchiile reprezentând perechi de început-sfârșit, iar imbricarea de carte a acestui grafic poate fi folosită pentru a crea un semafor. comportament pentru a asigura reglementarea traficului cu un număr minim de stări de semafor [12] . În problemele de bioinformatică care se ocupă de structurile ARN , o înglobare de carte de o pagină reprezintă forma clasică a unei structuri secundare de acid nucleic , iar o înglobare de două pagini reprezintă pseudonoduri [13] . Încorporarea cărților este folosită și în algebra generală [14] și teoria nodurilor [15] [16] .

Problemele deschise privind investițiile în carte sunt

Istorie

Denumirea „carte” a fost introdusă de Persinger și Atneosen (CA Persinger, Gail Atneosen) în anii 1960 [21] [22] [23] . Atneosen utilizase deja încorporarea graficelor în cărți, dar conceptul formal de încorporare a cărților a fost formulat de C. Kainen și L. Taylor Ollman la începutul anilor 1970 și au fost adăugate câteva restricții suplimentare asupra metodei de încorporare - în formularea lor, vârfurile graficului trebuie să se afle pe cotorul unei cărți, fiecare margine trebuie să se afle pe o singură pagină (nu se intersectează cotorul) și oricare două muchii se intersectează numai la vârfurile comune ale capătului [24] [25] .

Etape importante în dezvoltarea ulterioară a înglobării cărților sunt dovada lui Michalis Giannakakis la sfârșitul anilor 1980 că grosimea cărții a grafurilor plane nu depășește patru [26] [5] , și descoperirea la sfârșitul anilor 1990 a unei relații strânse între carte. încorporare și bioinformatică . [13]

Definiții

O carte este un tip special de spațiu topologic (numit și evantai semiplanuri) [21] [27] . Constă dintr-o singură linie dreaptă ℓ numită cotor [28] a cărții, împreună cu un set de unul sau mai multe semiplanuri numite paginile sau foile cărții. Fiecare semiplan trebuie să aibă aceeași linie ℓ ca granița sa. Cărțile cu un număr finit ( k ) de pagini pot fi imbricate în spațiul tridimensional, de exemplu, alegând un sistem de coordonate dreptunghiular ca linie ℓ a axei z și ca pagina i - a (din k ) poate lua o mulțime de puncte p astfel încât cel mai scurt segment , care leagă p cu axa z , să aibă un unghi de 2π i / k față de planul xz [1] .

Vizualizarea unei cărți cu graficul finit G în cartea B este un desen al graficului G în B , astfel încât orice vârf al lui G este desenat pe coloana B și orice margine a lui G este desenată ca o curbă situată pe o pagină a lui B. Numărul de intersecții de carte de k pagini ale unui grafic G  este numărul minim de intersecții dintr-un desen pe o carte de k pagini [3] .

O încorporare de carte a unui grafic G în B  este o încorporare a unui grafic G într-un spațiu B . Adică este un desen al unui grafic G în B în care muchiile nu se intersectează. Orice grafic finit are o carte încorporată într-o carte cu un număr suficient de mare de pagini. De exemplu, este întotdeauna posibil să imbricați fiecare margine pe propria pagină. Grosimea cărții , numărul de pagini sau numărul de stivă de graficul G  este numărul minim de pagini necesar pentru o imbricare de carte a graficului G. Un alt parametru care măsoară calitatea unui atașament de carte, pe lângă numărul de pagini, este lățimea paginii . Acesta este numărul maxim de margini care traversează raza perpendicular pe coloana vertebrală în interiorul unei singure pagini. În mod echivalent (pentru înglobările de cărți, în care fiecare margine este desenată ca o curbă monotonă), aceasta este dimensiunea maximă a unui subset de margini, astfel încât intervalele definite pe cotor de către punctele de capăt ale marginilor se intersectează toate [2] [29] [30] .

Este esențial pentru aceste definiții ca marginile să se afle pe o singură pagină. După cum a menționat deja Ameosen, dacă marginile pot merge de la o pagină la alta (prin cotor), atunci orice grafic poate fi încorporat într-o carte de trei pagini [22] [31] [20] . Totuși, pentru o încorporare topologică de carte de trei pagini , în care intersecția coloanei vertebrale este permisă, rămâne o problemă interesantă determinarea celui mai mic număr de intersecție a coloanei vertebrale care permite ca graficul să fie încorporat într-o carte [20] [32] .

Grafice specifice

După cum se arată în prima figură, grosimea cărții a graficului complet este de trei. Deoarece nu este plană, grosimea cărții este mai mare de două, dar există o carte cu trei pagini. Grosimea cărții a oricărui grafic vertex complet este exact . Acest rezultat oferă o limită superioară pe grosimea maximă a cărții a oricăror grafice cu vârfuri [1] . Numărul de intersecție de două pagini al graficului complet este

care este în concordanță cu conjectura nedovedită a lui Anthony Hill . Adică, dacă conjectura lui Hill este adevărată, atunci desenul acestui grafic care minimizează numărul de intersecții este un desen de două pagini [33] .

Grosimea cărții unui graf bipartit complet este aproape egală  - pentru fiecare vârf al unei părți mai mici, puteți aranja marginile incidente acestor vârfuri pe propria pagină. Această limită nu este întotdeauna strictă. De exemplu, are o grosime de carte de trei, nu de patru. Cu toate acestea, atunci când cele două părți ale graficului sunt foarte dezechilibrate, c , grosimea cărții este exact . [1] [34] Grosimea cărților de grafice binare de Bruijn , grafice de schimb amestecate și rețele cubice cu cicluri (când aceste grafice sunt suficient de mari pentru a nu fi plane) este exact trei. [35]

Proprietăți

Comportamentul subdiviziunii

Probleme nerezolvate în matematică : Grosimea cărții a unui grafic poate fi limitată de o funcție a grosimii subdiviziunilor de carte?

Împărțirea fiecărei margini a unui grafic în căi cu două muchii prin adăugarea de noi vârfuri pentru fiecare muchie poate crește uneori grosimea cărții (de exemplu, un diamant are o grosime de carte de unu, dar subdiviziunea sa are o grosime de carte de două). Cu toate acestea, o astfel de subpartiție poate reduce semnificativ și grosimea cărții a graficului după partiție. De exemplu, grosimea cărții a unui grafic complet K n este Θ( n ) este proporțională cu numărul vârfurilor sale, dar împărțirea fiecărei muchii în două dă o subdiviziune cu o grosime a cărții mult mai mică, doar O(√ n ). [4] . În ciuda existenței unor exemple precum cel de mai sus, Blankenship și Oporowski [31] au presupus că grosimea cărții a subdiviziunilor nu poate fi substanțial mai mică decât cea a graficului original. În special, ei au presupus că există o anumită funcție f , că pentru orice grafic G și grafic H obținut prin înlocuirea fiecărei muchii a lui G cu un drum de două muchii, dacă grosimea cărții a graficului H este t , atunci grosimea cărții a graficului G nu depăşeşte f ( t ) . [31] Până în 2013 , conjectura Blankenship-Oporowski a rămas nedovedită. [17]

Planaritatea și planaritatea exterioară

Grosimea cărții a unui grafic dat G nu depășește 1 dacă și numai dacă G este plan exterior . Un graf exterior planar este un graf care are o încorporare plană în care toate vârfurile aparțin feței exterioare a înglobării. Pentru astfel de grafice, plasarea vârfurilor în aceeași ordine de-a lungul coloanei vertebrale așa cum apar pe fața exterioară (când un vârf reapare pe fața exterioară, se ia doar o copie a vârfului) produce o încorporare a graficului de o pagină. În schimb, o imbricare de carte de o pagină este automat exterioară - dacă graficul este imbricat într-o singură pagină, adăugarea unui al doilea semiplan dă un plan complet, iar fața exterioară va conține întregul semiplan adăugat, cu toate vârfurile situate pe această față exterioară [1] [2] .

Orice încorporare de carte cu două pagini este un caz special de încorporare plană, deoarece unirea a două pagini de carte este un spațiu care este echivalent topologic cu un plan. Astfel, orice grafic cu grosimea de carte doi este automat planar . Mai precis, grosimea cărții a unui graf G este de cel mult două dacă și numai dacă G este un subgraf al unui graf plan care are un ciclu Hamiltonian [1] . Având în vedere un grafic cu o carte încorporată de două pagini, graficul poate fi extins la un grafic hamiltonian plan prin adăugarea (pe orice pagină) de muchii suplimentare între oricare două vârfuri consecutive de-a lungul coloanei vertebrale, dacă acestea nu sunt deja conectate printr-o muchie și între primul şi ultimul vârf al coloanei vertebrale . Graficul Goldner-Harari oferă un exemplu de graf plan care nu are grosimea cărții doi - este un graf planar maximal , deci este imposibil să adăugați orice muchie menținând planaritatea, iar graficul nu are un hamiltonian ciclu [1] . Datorită cerinței de a avea cicluri hamiltoniene, graficele care permit imbricarea pe două pagini sunt cunoscute sub denumirea de grafice sub-hamiltoniene [2] .

Toate graficele plane cu gradul maxim de cel mult patru au o adâncime de încorporare a cărții de cel mult două. [36] . Arborii planari 3 au o lățime maximă a cărții de trei [37] . Toate graficele plane au o grosime de carte care nu depășește patru [26] [5] . După cum a afirmat Michalis Yannakakis în 1986 [26] , există grafice plane cu o grosime de încorporare a cărții exact egală cu patru, dar o dovadă detaliată a acestei afirmații, anunțată în [5] , nu a fost niciodată publicată. Din acest motiv, Duimovich [19] a marcat ca nerezolvată problema determinării grosimii maxime a unei cărți de încorporare a grafurilor plane [19] .

Relația cu alți invarianți grafici

Grosimea cărții este legată de grosimea graficului , numărul de grafice plane care sunt necesare pentru a acoperi marginile unui grafic dat. Un grafic G are grosimea θ dacă poate fi încorporat într-un plan, iar muchiile pot fi colorate în culori θ în așa fel încât marginile de aceeași culoare să nu se intersecteze. În mod similar, un grafic G are lățimea cărții θ dacă poate fi desenat într -un semiplan cu vârfuri la granița semiplanului și colorate cu muchii în culori θ fără margini încrucișate de aceeași culoare. Cu această formulare, marginile de aceeași culoare corespund paginilor atașării cărții. Cu toate acestea, grosimea graficului și grosimea cărții pot diferi semnificativ - există diviziuni de grafice complete care au o grosime nelimitată a cărții [31] [20] [4] , în ciuda faptului că grosimea graficului este egală la doi [4] .

Graficele cu lățimea arborelui k au o lățime de carte de cel mult k + 1 [19] [38] și această limită este atinsă pentru k > 2. [19] . Graficele cu m muchii au lățimea cărții O(√ m ) [39] , iar graficele cu genul g au  lățimea cărții O(√ g ) [40] . Mai general, orice familie minoră închisă de grafice are o grosime de carte mărginită [6] [41] .

Orice minor contractant al unui grafic cu grosimea cărții mărginită este un grafic rar al cărui raport margine-vârf este mărginit de o constantă care depinde numai de adâncimea minorului și de grosimea cărții. Adică, în terminologia lui Nexetril [6] , graficele cu grosimea cărții mărginite au creștere mărginită [6] . Totuși, chiar și graficele cu un grad de grafic mărginit , o cerință de restricție de creștere substanțial mai puternică, pot avea o grosime de carte nemărginită [42] .

Deoarece graficele cu grosimea cărții două sunt grafice plane, ele satisfac teorema de partiționare plană  — au separatori, submulțimi de vârfuri a căror eliminare împarte graficul în bucăți cu cel mult 2 n /3 vârfuri în fiecare piesă, cu doar O(√ n ) vârfuri în separator. Aici n înseamnă numărul de vârfuri ale graficului. Cu toate acestea, există grafice cu grosimea cărții trei care nu au separatori subliniari de dimensiune [43] .

Marginile unei pagini ale unui atașament de carte se comportă ca o stivă . Acest lucru poate fi formalizat luând în considerare o succesiune arbitrară de operații de împingere și pop (împingere și pop) pe stivă și formând un grafic în care operațiunile stivei corespund vârfurilor graficului situat pe cotorul cărții inserate în ordinea operațiunilor. Dacă acum desenăm o margine din fiecare operație pop care scoate un obiect x din stivă la operația de împingere care împinge acel element pe stivă, graficul rezultat va avea automat o imbricare de o pagină. Din acest motiv, numărul de pagini ale unui grafic este numit și numărul său de stivă . Prin analogie, cercetătorii definesc următoarea încorporare a graficului ca un desen al unui grafic într-o carte în care oricare două margini ale paginii fie se intersectează, fie acoperă intervale care nu se intersectează pe coloana vertebrală. Astfel de înglobări corespund într-un fel cozilor , iar numărul minim de pagini necesar pentru fiecare încorporare a graficului se numește numărul său de cozi [6] [44] [45] .

Complexitate computațională

Determinarea grosimii unei cărți încorporate este o problemă dificilă NP . Aceasta rezultă din faptul că găsirea unui ciclu hamiltonian în graficele planare maxime este o problemă NP-completă . Grosimea înglobării cărții a unui graf planar maximal este de două dacă și numai dacă există o cale hamiltoniană. Prin urmare, determinarea faptului că grosimea înglobării cărții a unui graf planar maxim dat este de două este, de asemenea, o problemă NP-completă. [7]

Dacă ordinea vârfurilor de-a lungul cotorului în imbricarea cărților este predeterminată, o imbricare de două pagini (dacă există una) poate fi găsită în timp liniar ca opțiune de test de planaritate pentru un grafic obținut prin extinderea unui grafic dat prin crearea unei bucle de conectare. vârfuri de-a lungul coloanei vertebrale [13] . Unger a susținut că găsirea unei înglobări de trei pagini cu o ordine predeterminată a vârfurilor ar putea fi făcută în timp polinomial , deși descrierea sa a acestui rezultat lipsește o serie de detalii esențiale [18] . Cu toate acestea, pentru graficele care necesită patru sau mai multe pagini, problema găsirii unei înglobări cu cel mai mic număr posibil de pagini rămâne NP-hard datorită echivalenței cu problema NP-hard a colorării graficelor cercurilor , graficelor de intersecție a coardelor cercurilor . Având în vedere un grafic G cu o ordine fixă ​​a vârfurilor pe coloana vertebrală, plasând aceste vârfuri în aceeași ordine pe cerc și reprezentând marginile lui G ca segmente, dă un set de coarde reprezentând graficul G . Acum se poate forma un grafic circular având coardele acestei diagrame ca vârfuri și perechi de coarde care se intersectează ca muchii. Colorarea unui grafic circular oferă o partiție a marginilor graficului G în subseturi care pot fi desenate fără intersecții pe o singură pagină. Astfel, o colorare optimă echivalează cu o încorporare optimă a cărții. Deoarece colorarea unui grafic cerc cu patru sau mai multe culori este NP-hard, și deoarece orice cerc grafic poate fi generat în acest fel dintr-o problemă de găsire a unei cărți încorporate, găsirea optimă a cărții înglobare este, de asemenea, o problemă NP-hard [8] [46] [47 ] . Pentru o ordine fixă ​​de vârfuri pe coloana vertebrală sub o imbricare de două pagini, este o problemă dificilă de a minimiza numărul de intersecții dacă acest număr este diferit de zero [46] .

Dacă ordinea vârfurilor de pe coloana vertebrală este necunoscută, dar este dată paginarea marginilor, este posibil să se găsească o imbricare de 2 pagini (dacă există) în timp liniar prin aplicarea unui algoritm bazat pe arbori SPQR [48] [ 49] . Cu toate acestea, găsirea unui imbricare de 2 pagini este NP-complet dacă nu se cunoaște nici ordinea vârfurilor de pe coloana vertebrală, nici paginarea marginilor. Găsirea numărului de carte de intersecții ale unui grafic este, de asemenea, dificilă din cauza NP-completitudinii problemei de a verifica dacă numărul de intersecții de carte de două pagini este zero.

Problema izomorfismului subgrafului , care este de a determina dacă un graf mărginit de mărime de un fel este găsit ca subgraf al unui graf mai mare, poate fi rezolvată în timp liniar dacă graficul mai mare are o grosime de încorporare a cărții mărginite. Același lucru este valabil și pentru a determina dacă un graf de un fel este un subgraf generat al unui graf mai mare sau dacă are un homeomorfism cu graful mai mare [50] [51] . Din același motiv, problema verificării dacă un grafic cu grosimea cărții mărginită satisface o formulă logică de ordinul întâi dată este rezolvabilă în raport cu un parametru fix [52] .

Aplicații

Calcul multiprocesor tolerant la erori

Unul dintre motivele principale pentru studierea înglobării cărților (conform lui Chang, Leighton și Rosenberg [7] ) este utilizarea sa în dezvoltarea VLSI pentru a crea sisteme multiprocesoare tolerante la erori . În sistemul DIOGENES dezvoltat de acești autori, procesoarele unui sistem multiprocesor sunt organizate într-un lanț logic corespunzător cotorului cărții (deși nu trebuie să fie situate în linie dreaptă fizic pe diagramă ). Legăturile de comunicare ale acestor procesoare sunt grupate în „pachete” care corespund paginilor unei cărți și funcționează ca stive  - conectarea unuia dintre procesoare la începutul liniei de comunicare împinge în sus toate conexiunile anterioare din pachet și conectarea unui alt procesor. până la capătul liniei de comunicație îl conectează la unul dintre procesoarele inferioare din fascicul și împinge toate rămase în jos. Datorită acestui comportament de stivuire, un singur pachet poate servi unui set de linii de comunicare care formează marginile unei singure pagini a unui atașament de carte. Prin aranjarea legăturilor în acest fel, pot fi implementate o gamă largă de topologii în care nu contează ce procesor eșuează atâta timp cât în ​​rețea rămân suficiente procesoare. Topologiile de rețea care pot fi organizate de un astfel de sistem sunt exact acelea care sunt groase de carte, nedepășind numărul de pachete care trebuie puse la dispoziție [7] .

Sortare stivă

O altă aplicație, subliniată de Chang, Leighton și Rosenberg [7] , se referă la sortarea permutărilor folosind stive . Knuth a arătat că un sistem care procesează un flux de date împingând elementele de intrare în stivă și apoi introducându - le în fluxul de ieșire la momentul potrivit poate sorta datele dacă și numai dacă nu există permutări de model în ordinea originală a elementelor 53 ] . De atunci, s-a lucrat mult la aceasta și la probleme similare de sortare a unui flux de date cu sisteme de stivă și cozi mai generale. În sistemul luat în considerare de Chang, Leighton și Rosenberg, fiecare element din fluxul de intrare trebuie să fie împins pe unul dintre stive. După ce toate datele au fost împinse în stive, elementele sunt împinse din acele stive (în ordinea corespunzătoare) în fluxul de ieșire. După cum au observat Chang și colab., o anumită permutare poate fi sortată printr-un astfel de sistem dacă și numai dacă un grafic obținut din permutare are o carte încorporată cu o ordine fixă ​​a vârfurilor de-a lungul coloanei și numărul de pagini care nu depășește numărul de stive [7] .

Controlul mișcării

După cum descrie Kainen [12] , încorporarea cărții poate fi folosită pentru a descrie fazele semafoarelor la o intersecție controlată. La o intersecție, benzile de trafic de intrare și de ieșire (inclusiv capetele trecerilor de pietoni și ale pistelor pentru biciclete) pot fi reprezentate ca vârfuri grafice situate pe cotorul unui atașament de carte, în ordinea corespunzătoare ordinii de intrare/ieșire a traficului de-a lungul intersecție (în sensul acelor de ceasornic). Traseele prin intersecție, unde se deplasează traficul și pietonii de la punctul de intrare până la punctul de ieșire, pot fi reprezentate ca marginile unui grafic nedirecționat. De exemplu, acest grafic ar putea avea o margine de la o bandă de intrare la o bandă de ieșire aparținând aceluiași segment de drum, reprezentând astfel o întoarcere în U dacă sunt permise întoarceri în U la intersecție. Un subset dat de astfel de muchii reprezintă un set de căi care pot fi urmate fără intersecții dacă și numai dacă subsetul nu conține o pereche de muchii care se intersectează care se află pe aceeași pagină a unei cărți imbricate. Astfel, încorporarea cărții a graficului descrie împărțirea traseelor ​​în submulțimi în care mișcarea nu se intersectează, iar grosimea cărții a acestui grafic (cu o încorporare fixă ​​pe cotor) oferă numărul minim de faze diferite de semafor necesar pentru un grafic al semaforului care include toate căile posibile prin intersecție [ 12] . Cu toate acestea, acest model nu este aplicabil sistemelor mai complexe de control al traficului care nu au un program fix.

Vizualizare grafică

Încorporarea cărților este adesea folosită și pentru a vizualiza fluxul de date din rețea. Cele două scheme standard de vizualizare grafică , diagrame cu arc [10] și diagrame circulare [11] , pot fi considerate investiții în carte. Încorporarea cărților poate fi folosită și pentru a construi scheme de cluster [48] , înglobări simultane [54] și desene grafice 3D [55] .

O diagramă cu arc [10] sau o încorporare a unei linii [46] plasează vârfurile graficului pe o linie, iar marginile graficului sunt desenate ca semicercuri deasupra și dedesubtul acelei linii, permițând uneori marginile să fie segmente de linie. Acest stil de desen corespunde unei cărți imbricate cu o pagină (dacă toate semicercurile sunt deasupra liniei) sau două pagini (dacă sunt folosite ambele părți ale liniei) și a fost introdus inițial ca o modalitate de a studia numărul de intersecție a graficelor. [56] [57] Graficele plane care nu au o imbricare de cărți de două pagini pot fi desenate într-un mod similar, permițând ca marginile să fie reprezentate prin două semicercuri deasupra și sub o linie dreaptă. Astfel de desene nu sunt înglobări de carte în termenii definiției obișnuite și se numesc înglobare de carte topologică [58] . Pentru orice grafic plan, este întotdeauna posibil să găsiți o încorporare care traversează coloana vertebrală cel mult o dată. [59] .

Într-un alt stil de desen, aranjamentul circular , vârfurile graficului sunt plasate pe un cerc, iar muchiile sunt desenate în interiorul sau în afara cercului [11] . Din nou, aranjarea marginilor în cadrul cercului (de exemplu, ca segmente de linie) corespunde unui desen de carte de o pagină, în timp ce aranjarea marginilor de ambele părți ale cercului corespunde unui desen de carte de două pagini [60] .

Pentru desenele de o pagină de orice stil, este important să mențineți un număr redus de intersecții pentru a reduce haosul vizual al desenului. Minimizarea numărului de intersecții este o problemă NP-completă [46] , dar problema poate fi aproximată cu relația O (log 2 n ), unde n este numărul de vârfuri [61] . Minimizarea numărului de intersecție de o pagină sau două pagini este decidabilă în raport cu un parametru fix atunci când este parametrizat de numărul ciclomatic al graficului dat [62] . Au fost dezvoltate și metode euristice pentru a reduce complexitatea intersecțiilor, bazate, de exemplu, pe ordinea precisă de inserare a vârfurilor și pe optimizarea locală [11] .

O încorporare a unei cărți de două pagini cu o distribuție fixă ​​a muchiilor de-a lungul paginilor poate fi reprezentată ca un fel de planaritate de grup , în care un anumit grafic trebuie să fie desenat astfel încât părți ale graficului (două subseturi de muchii) să fie aranjate în figura pentru a reflecta gruparea lor [48] . O încorporare de carte de două pagini este, de asemenea, utilizată pentru a găsi o încorporare simultană a unui grafic, în care două grafice sunt date pe același set de vârfuri și trebuie să găsiți locația vârfurilor, în care ambele grafice sunt desenate plan folosind o linie dreaptă segmente [54] .

Atașamentele de cărți care au mai mult de două pagini sunt folosite pentru a construi desene tridimensionale ale graficelor. În special, Wood a folosit construcția înglobărilor de cărți, care păstrează gradul scăzut al fiecărui vârf din cadrul fiecărei pagini, ca metodă de încorporare a graficelor într-o rețea tridimensională de volum mic [55] .

Folding ARN

Când se studiază modul în care moleculele de ARN se pliază pentru a forma o structură de ARN, imaginea standard a structurii secundare a unui acid nucleic poate fi descrisă folosind o diagramă ca un lanț de baze (secvență de ARN) desenat de-a lungul unei linii drepte împreună cu un set. de arce deasupra liniei care descriu bazele pereche ale structurii. . Adică, deși această structură are un aspect tridimensional complex, conexiunile sale (dacă există o structură secundară) pot fi descrise printr-o structură mai abstractă, un insert de carte de o pagină. Cu toate acestea, nu toți ARN-urile se comportă într-un mod atât de simplu. Haslinger și Stadler au propus o așa-numită „structură bisecundară” pentru anumite pseudonoduri ARN , care iau forma unei cărți de cuibărit de două pagini - secvența ARN este din nou desenată de-a lungul unei linii drepte, dar bazele pereche sunt desenate ca arce deasupra și sub această linie. Pentru a forma o structură bisecundară, graficul trebuie să aibă un grad care să nu depășească trei - fiecare bază poate fi într-o singură margine a diagramei, precum și în două legături cu baze învecinate din succesiune. Avantajul acestei formulări include faptul că exclude structurile care sunt efectiv înnodate în spațiu și că acoperă majoritatea pseudonodurilor ARN cunoscute [13] .

Deoarece ordinea pe coloana vertebrală este cunoscută inițial, existența unei structuri bisecundare pentru bazele pereche date este verificată direct. Sarcina de a distribui muchiile pe două pagini poate fi formulată ca un caz special al problemei de satisfacție a formulelor booleene în formă normală 2-conjunctive sau ca o problemă de verificare a bipartității unui graf circular ale cărui vârfuri sunt baze pereche, iar muchiile descriu încrucișarea dintre bazele pereche [13] . Un alt mod și mai eficient, așa cum arată Haslinger și Stadler [13] , de a determina existența unei structuri bisecundare este prin faptul că aceasta se întâmplă dacă și numai dacă graficul de intrare (graful format prin buclarea bazelor în ordinea următoare și adăugarea bazelor pereche ca muchii) este plană [13] . Acest fapt face posibilă recunoașterea unei structuri bisecundare în timp liniar ca un caz special al testului de planaritate .

Blin, Fertin, Rusu și Sinokvet au folosit relația dintre structurile secundare și atașamentele de carte ca parte a dovezii că unele probleme de comparare a structurilor secundare ARN sunt NP-hard [63] . Și dacă structura ARN-ului este terțiară mai degrabă decât bisecundară (adică dacă sunt necesare mai mult de două pagini în diagrama sa), atunci determinarea numărului de pagini este din nou o problemă NP-hard [64] .

Teoria complexității computaționale

Paian, Tewari și Vinodsoandran au folosit încorporarea cărților pentru a studia complexitatea computațională a problemei de accesibilitate în graficele direcționate . După cum au observat, problema accesibilității pentru graficele direcționate de două pagini poate fi rezolvată într-un spațiu logaritmic cu o singură valoare (analog cu complexitatea deterministă a memoriei logaritmice a problemelor din clasa UP ). Cu toate acestea, problema accesibilității pentru graficele direcționate de trei pagini oferă complexitate nedeterministă a memoriei logaritmice . Astfel, încorporarea cărții pare a fi strâns legată de diferențele dintre aceste două clase de complexitate [65] .

Existența expansoarelor cu un număr constant de pagini [43] este un pas cheie în demonstrarea faptului că nu există o simulare în timp-subquadratică a mașinilor Turing nedeterministe cu două benzi de către mașini nedeterministe cu o singură bandă [66] .

Alte domenii ale matematicii

Mackenzie și Overbey [14] au studiat aplicațiile despre grosimea cărților în algebra generală folosind grafice derivate din divizorii zero ai unui inel local finit , creând un vârf pentru fiecare divizor zero și o muchie pentru fiecare pereche de valori al cărei produs este zero [14] .

Într-o succesiune de articole, Dynnikov a studiat înglobarea topologică a nodurilor și legăturilor , arătând că aceste înglobări pot fi descrise printr-o succesiune combinatorie de simboluri și că echivalența topologică a două legături poate fi arătată printr-o succesiune de modificări locale în înglobări [15]. ] [16] .

Note

  1. ↑ 1 2 3 4 5 6 7 8 9 Bernhart și 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. Lucrările celei de-a șaptesprezecea conferințe internaționale din sud-est despre combinatorică, teoria grafurilor și calcul (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, Franța, 13–15 februarie 1992, Proceedings. - Berlin: Springer, 1992. - T. 577. - S. 389-400. — (Note de curs în Informatică). - 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. Continuă unidimensională n - leaved // Fundamenta Mathematicae . - 1972. - T. 74 , nr. 1 . — p. 43–45 . .
  24. ↑ Paul C. Kainen. Graphs and Combinatorics (Proceedings of the Capital Conference on Graph Theory and Combinatorics at the George Washington University 18–22 iunie 1973) / Ruth A. Bari, Frank Harary. - 1974. - T. 406. - S. 76-108. — (Note de curs la matematică). .
  25. ↑ L. Taylor Ollmann. Proc. A 4-a Conferință de Sud-Est despre combinatorică, teoria graficelor și calcul / 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. Ambalaje sferice. II // Geometrie discretă și computațională. - 1997. - T. 18 , nr. 2 . — S. 135–149 . - doi : 10.1007/PL00009312 . .
  28. ↑ Inițial coloana vertebrală sau spate
  29. ↑ Elena Stohr. Un compromis între numărul paginii și lățimea paginii înglobărilor de cărți ale graficelor // Informații și calcul. - 1988. - T. 79 , nr. 2 . — S. 155–162 . - doi : 10.1016/0890-5401(88)90036-3 . .
  30. ↑ Elena Stohr. Lățimea de pagină a graficelor plane trivalente // Matematică discretă . - 1991. - T. 89 , nr. 1 . — p. 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. Limite inferioare pentru numărul de încrucișări de margini peste coloana vertebrală într-o carte topologică încorporarea unui grafic // Matematică aplicată discretă. - 1999. - T. 92 , nr. 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. ↑ Pentru rezultate suplimentare cu privire la grosimea cărții de Complete Bipartite Graphs, a se vedea Etienne de Klerk, Dmitrii V. Pasechnik, Gelasio Salazar. Desene de carte ale graficelor bipartite complete // Matematică aplicată discretă. - 2014. - T. 167 . — S. 80–93 . - doi : 10.1016/j.dam.2013.11.001 . .
  35. ↑ Toru Hasunuma, Yukio Shibata. Încorporarea rețelelor de Bruijn, Kautz și shuffle-schimb în cărți // Matematică aplicată discretă. - 1997. - T. 78 , nr. 1-3 . — S. 103–116 . - doi : 10.1016/S0166-218X(97)00009-7 . Yuuki Tanaka, Yukio Shibata Pe numărul de pagină al ciclurilor conectate în cub // Matematică în informatică. - 2010. - Vol. 3 , numărul. 1 . — S. 109–117 . - doi : 10.1007/s11786-009-0012-y . Vezi și Bojana Obrenic. Încorporarea de Bruijn și a graficelor de schimb aleatoriu în cinci pagini // SIAM Journal on Discrete Mathematics. - 1993. - T. 6 , nr. 4 . — S. 642–654 . - doi : 10.1137/0406049 . .
  36. ↑ Bekos et al, 2014 , pp. 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. Numărul de pagină al k -arborilor este O ( k ) // Matematică aplicată discretă. - 2001. - T. 109 , nr. 3 . — S. 215–221 . - doi : 10.1016/S0166-218X(00)00178-5 . .
  39. ↑ Seth M. Malitz. Graficele cu margini E au numărul de pagină O (√ E ) // Journal of Algorithms : journal. - 1994. - iulie ( vol. 17 , numărul 1 ). — p. 71–84 . - doi : 10.1006/jagm.1994.1027 .
  40. ↑ Seth M. Malitz. Graficele genului g au numărul de pagină O (√ g ) // Journal of Algorithms. - 1994. - T. 17 , nr. 1 . — S. 85–109 . - doi : 10.1006/jagm.1994.1028 . .
  41. ↑ R. Blankenship. Încorporarea de carte a graficelor. — Departamentul de Matematică, Universitatea de Stat din Louisiana, 2003. . După cum este citat de Neshetri.
  42. ↑ János Barát, Jiří Matoušek, David R. Wood. Graficele cu grade mărginite au o grosime geometrică arbitrar mare // Electronic Journal of Combinatorics. - 2006. - T. 13 , nr. 1 . — C. R3 . .
  43. ↑ 1 2 Vida Dujmovic, Anastasios Sidiropoulos, David R. Wood. Expansoare 3-monotone. - arXiv : 1501.05020 . , o îmbunătățire față de un rezultat anterior al lui Jean Bourgain. Expansori și extindere dimensională // Comptes Rendus Mathematique. - 2009. - T. 347 , nr. 7-8 . — S. 357–362 . - doi : 10.1016/j.crma.2009.02.009 . ; Jean Bourgain, Amir Yehudayoff. Expansiune în și expandoare monotone // Analiză geometrică și funcțională. - 2013. - T. 23 , nr. 1 . — S. 1–41 . - doi : 10.1007/s00039-012-0200-9 . . Vezi și Zvi Gali, Ravi Kannan, Endre Szemerédi. Pe grafice cu 3 pushdown cu separatoare mari  // Combinatorica. - 1989. - T. 9 , nr. 1 . — P. 9–19 . - doi : 10.1007/BF02122679 . ; Zeev Dvir, Avi Wigderson. Expansoare monotone: construcții și aplicații // Teoria calculului. - 2010. - T. 6 . — S. 291–308 . - doi : 10.4086/toc.2010.v006a012 . .
  44. ↑ Lenwood S. Heath, Arnold L. Rosenberg. Aranjarea graficelor folosind cozi // SIAM Journal on Computing. - 1992. - T. 21 , nr. 5 . — S. 927–958 . - doi : 10.1137/0221055 . .
  45. ↑ Vida Dujmovic, David R. Wood. Pe aspecte liniare ale graficelor // Matematică discretă și informatică teoretică. - 2004. - T. 6 , nr. 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. Complexitatea colorării arcurilor circulare și a acordurilor // SIAM Journal on Algebric and Discrete Methods. - 1980. - Vol. 1 , număr. 2 . — S. 216–227 . - doi : 10.1137/0601025 . .
  48. ↑ 1 2 3 Hong, Nagamochi, 2009 .
  49. ↑ Patrizio Angelini, Marco Di Bartolomeo, Giuseppe Di Battista. Graph Drawing: 20th International Symposium, GD 2012, Redmond, WA, SUA, 19–21 septembrie 2012, Revised Selected Papers. - Springer, 2013. - T. 7704. - S. 79–89. — (Note de curs în Informatică). - 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 , Corolarul 18.1, p. 401.
  52. ↑ Nešetřil, Ossona de Mendez, 2012 , Teorema 18.7, p. 405.
  53. ↑ Donald E. Knuth. Arta programarii computerelor 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. Numărul minim de intersecții în grafice complete // 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. Procedura de permutare pentru minimizarea numarului de treceri intr-o retea // Proceedings of the Institution of Electrical Engineers. - 1968. - T. 115 . — S. 21–26 . - doi : 10.1049/piee.1968.0004 . .
  58. ↑ Miki Miyauchi. Încorporare topologică a graficelor bipartite  (engleză)  // IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences. - 2006. - Vol. E89-A , iss. 5 . — P. 1223–1226 . - doi : 10.1093/ietfec/e89-a.5.1223 .
  59. ↑ Francesco Giordano, Giuseppe Liotta, Tamara Mchedlidze, Antonios Symvonis. Algoritmi și calcul: 18th International Symposium, ISAAC 2007, Sendai, Japonia, 17–19 decembrie 2007, Proceedings. - Springer, 2007. - T. 4835. - S. 172-183. — (Note de curs în Informatică). - 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), Slovacia, 15–19 septembrie 2004. - 2004. .
  61. ↑ Farhad Shahrokhi, Ondrej Sýkora, László A. Székely, Imrich Vrt'o. Concepte graf-teoretice în informatică: 20th International Workshop, WG '94, Herrsching, Germania, 16–18 iunie 1994, Proceedings. - Springer, 1995. - T. 903. - S. 256-268. — (Note de curs în Informatică). - doi : 10.1007/3-540-59071-4_53 . .
  62. ↑ Michael J. Bannister, David Eppstein, Joseph A. Simons. Desen grafic: 21st International Symposium, GD 2013, Bordeaux, Franța, 23–25 septembrie 2013, Lucrări selectate revizuite. - 2013. - T. 8242. - S. 340-351. — (Note de curs în Informatică). - doi : 10.1007/978-3-319-03841-4_30 . .
  63. ↑ Guillaume Blin, Guillaume Fertin, Irena Rusu, Christine Sinoquet. Combinatorică, algoritmi, metodologii probabilistice și experimentale: primul simpozion internațional, ESCAPE 2007, Hangzhou, China, 7-9 aprilie 2007, lucrări selectate revizuite. - 2007. - T. 4614. - S. 140-151. — (Note de curs în Informatică). - doi : 10.1007/978-3-540-74450-4_13 . .
  64. ↑ Peter Clote, Stefan Dobrev, Ivan Dotu, Evangelos Kranakis, Danny Krizanc, Jorge Urrutia. Pe numărul de pagină al structurilor secundare ARN cu pseudonoduri // Journal of Mathematical Biology. - 2012. - T. 65 , nr. 6–7 . - S. 1337-1357 . - doi : 10.1007/s00285-011-0493-6 . .
  65. ↑ A. Pavan, Raghunath Tewari, NV Vinodchandran. Despre puterea neambiguității în spațiul-log // Complexitatea computațională. - 2012. - T. 21 , nr. 4 . — S. 643–670 . - doi : 10.1007/s00037-012-0047-3 . .
  66. ↑ Zvi Galil, Ravi Kannan, Endre Szemerédi. Despre separatoare netriviale pentru grafice de k-pagini și simulări cu mașini Turing nedeterministe cu o bandă // Journal of Computer and System Sciences. - 1989. - T. 38 , nr. 1 . — S. 134–149 . - doi : 10.1016/0022-0000(89)90036-6 . .

Literatură