Numărul de cozi de grafice

Numărul de cozi de grafice este un invariant de grafic , definit în mod similar cu numărul stivei (grosimea cărții) și folosind ordinea FIFO (primul intrat, primul ieșit, coadă) în loc de ordinea LIFO (ultimul intrat, primul ieșit, stivă).

Definiție

Reprezentarea graficului sub formă de cozi (dispunerea cozii) pentru un graf dat este determinată de ordonarea completă a vârfurilor grafului , împreună cu descompunerea muchiilor graficului în mai multe „cozi”. Este necesar ca mulțimea de muchii ale fiecărei cozi să nu fie imbricată după ordinea vârfurilor în sensul că dacă ab și cd sunt două muchii în aceeași coadă, atunci nu trebuie să existe a < c < d < b . Numărul de cozi qn( G ) al graficului G este numărul minim de cozi pentru reprezentarea graficului ca cozi [1] .

Folosind aspectul cozii de grafic, este posibil să enumerăm muchiile unei singure cozi folosind structura standard de coadă prin iterarea peste vârfuri într-o ordine dată și când ajungem la un vârf, selectăm toate muchiile pentru care vârful este al doilea vârf. a arcului și puneți în coadă arcele pentru care vârful este primul. Condiția de non-imbricare asigură că, atunci când se atinge un vârf, toate muchiile care au acel vârf ca terminal sunt în coadă și gata pentru a fi preluate. Descompunerea unui grafic în cozi cu proprietățile descrise poate fi considerată o definiție alternativă [1] . O altă definiție echivalentă a aspectului de coadă folosește noțiunea de încorporare a unui grafic dat într-un cilindru cu vârfuri situate pe o linie care se află pe suprafața cilindrului și fiecare margine se înfășoară în jurul cilindrului. Muchiile incluse în aceeași coadă nu trebuie să se intersecteze, dar sunt permise intersecții ale muchiilor diferitelor cozi [2] .

Dispunerea cozilor a fost definită de Heath și Rosenberg [1] prin analogie cu lucrările anterioare privind înglobarea de cărți a graficelor, care sunt definite în același mod folosind stive în loc de cozi. După cum au observat, aceste aspecte sunt, de asemenea, legate de lucrările anterioare privind sortarea permutărilor folosind cozi paralele. Dispunerea cozii a fost motivată de cerințele de proiectare a circuitelor integrate și de management al comunicațiilor în algoritmi distribuiți [1] .

Clase de grafice cu un număr limitat de cozi

Orice arbore are un număr de coadă de 1 cu ordonarea vârfurilor dată de căutarea pe lățimea întâi [3] . Pseudopădurile și zăbrelele au, de asemenea, un număr de coadă de 1 [4] . Numărul de cozi de grafuri exterioare planare este de cel mult 2. Un graf solar cu 3-uri (un triunghi cu fiecare muchie înlocuită cu un triunghi) este un exemplu de graf exterior planar al cărui număr de cozi este exact 2 [5] [6] . Numărul de cozi ale unui grafic paralel-secvențial nu depășește 3 [6] .

Numărul de cozi pentru graficele binare de Bruijn este 2 [7] . Numărul de cozi dintr-un grafic al unui hipercub d - dimensional nu depășește d − 1 [8] . Numărul de cozi de grafuri complete K n și grafuri bipartite complete K a , b este cunoscut exact — este egal cu și respectiv [9] .

Probleme nerezolvate în matematică : Fiecare graf plan are un număr finit de cozi?

Orice grafic cu o singură coadă este un grafic plan cu o încorporare plană „nivel de arc”, în care vârfurile sunt pe linii paralele (nivele), iar fiecare muchie fie conectează vârfurile a două niveluri adiacente, fie formează un arc care leagă două vârfuri la nivelul acelasi nivel. În schimb, orice graf planar la nivel de arc are un aspect cu o singură coadă [10] . Heath, Layton și Rosenberg [5] au sugerat că orice graf plan are un număr limitat de cozi, dar nu există încă o confirmare a acestei afirmații. Dacă numărul de cozi de grafuri plane este limitat, același lucru este valabil și pentru grafurile 1-planare și, în plus, pentru grafurile k - planare [11] . Cea mai puternică limită cunoscută pentru numărul de cozi din graficele plane nu este o constantă, este egală cu O (log n ) [12] Limitele polilogaritmice ale numărului de cozi sunt cunoscute pentru graficele cu gen mărginit și pentru graficele mai generale din minor închis familii [13] .

Dacă folosim o variantă a numărului de cozi numită „număr puternic de cozi”, numărul de cozi din produsul graficelor poate fi limitat de o funcție a numărului de cozi și a numărului strict de cozi de factori de produs [14] .

Invariante înrudite

Graficele cu un număr mic de cozi sunt rare — graficele cu n vârfuri și o coadă nu au mai mult de 2 n  − 3 muchii [15] , iar graficele mai generale cu  q cozi nu au mai mult de 2 qn − q (2 q + 1 ) marginile [16] . Rezultă că aceste grafice au un număr cromatic mic . În special, graficele cu o singură coadă au o colorare de 3 culori, iar graficele cu cozi q pot necesita cel puțin 2 q + 1 și cel mult 4 q culori [16] . În schimb, limitarea numărului de muchii implică o limită inferioară a numărului de cozi de grafice — numărul de cozi pentru graficele cu n vârfuri și m muchii nu depășește O (√ m ) [17] . Limita este aproape de strictă, deoarece pentru graficele aleatoare d -regular numărul de cozi cu probabilitate mare este [5] [18]

Probleme nerezolvate la matematică : orice grafic cu un număr limitat de cozi ar trebui să aibă o grosime limitată a cărții și invers?

Graficele cu o singură coadă au o lățime a cărții care nu depășește două [5] . Pentru orice ordine fixă ​​de vârfuri, produsul dintre grosimea cărții și numărul de cozi pentru acea ordine de vârfuri este cel puțin lățimea secțiunii graficului împărțit la gradul maxim de vârfuri [5] . Grosimea unei cărți poate fi mult mai mare decât numărul de cozi - graficele Hamming ternare au un număr logaritmic de cozi, dar o grosime polinomială a cărților [5] . Rămâne necunoscut dacă grosimea cărții este limitată de o anumită funcție a numărului de cozi. Heath, Leighton și Rosenberg [5] au sugerat că numărul de cozi este cel mult liniar cu grosimea cărților, dar nu s-a făcut niciun progres în această direcție. Se știe că dacă toate graficele bipartite cu înglobare de cărți de 3 pagini au un număr limitat de cozi, atunci toate graficele cu o grosime limitată de carte au un număr limitat de cozi [11] .

Ganley și Heath 19] au întrebat dacă numărul de cozi dintr-un grafic este delimitat de o funcție a lățimii arborelui său și au citat o disertație nepublicată a lui S. V. numărul de cozi. Cu toate acestea, s-a demonstrat că numărul de cozi este limitat de o funcție (dublu exponențială) a lățimii arborelui [20]

Complexitate computațională

Determinarea numărului de cozi dintr-un grafic este o problemă NP-completă . Chiar și verificarea faptului că numărul de cozi este egal cu unul este NP-complet [21] .

Cu toate acestea, dacă ordinea vârfurilor este predeterminată, atunci numărul optim de cozi este egal cu numărul maxim de muchii dintr-un k -curcubeu, un set de k muchii, fiecare pereche având o muchie imbricată în alta (în sensul descris de mai sus). Împărțirea muchiilor în cozi se poate face prin includerea muchiei e , care este marginea exterioară a curcubeului i (dar nu a curcubeului mai mare) în coada i -a. Este posibil să se construiască un aspect optim în timp O ( m log log n ) , unde n este numărul de vârfuri ale graficului și m este numărul de muchii [22] .

Graficele legate la coadă au, de asemenea, o expansiune mărginită , ceea ce înseamnă că minorele lor superficiale sunt grafice rare cu un raport margine la vârf (sau, în mod echivalent, degenerare sau arbore ) delimitat de o funcție a numărului de cozi și adâncimea minorului. Ca o consecință, unele probleme algoritmice, inclusiv problema izomorfismului de graf pentru grafuri de mărime mărginită, au algoritmi de timp liniar pentru astfel de grafuri [23] [24] . Mai general, datorită extensiei mărginite, se poate verifica în timp liniar dacă o declarație logică de ordinul întâi este adevărată pentru un grafic cu un număr mărginit de cozi [25] .

Aplicație în vizualizarea grafică

Deși aspectul cozii nu oferă neapărat vizualizări 2D bune , ele sunt folosite pentru a reprezenta grafice în 3D. În special, un grafic G are un număr mărginit de cozi dacă și numai dacă este posibil să se aranjeze vârfurile graficului G pe o rețea tridimensională de dimensiunea O ( n ) × O (1) × O (1) în astfel încât să nu se intersecteze două muchii [26] De exemplu, graficele de Bruijn și graficele cu lățime de arbore mărginite au o încorporare de volum liniară tridimensională [27] [28] .

Limitele logaritmice sau polilogaritmice ale numărului de cozi sunt transformate cu astfel de investiții în rețele tridimensionale în volume aproape liniare, rețeaua într-o direcție va avea o dimensiune liniară, iar în celelalte două - polilogaritmică. Graficele plane, graficele cu gen mărginit și graficele cu lățime locală de arbore mărginită au înglobare de dimensiunea O ( n log n ) [12] , în timp ce graficele familiilor minore închise au dimensiunea O ( n log O (1) n ) [13 ] .

Note

  1. ↑ 1 2 3 4 Heath, Rosenberg, 1992 .
  2. ↑ Auer, Bachmaier, Brandenburg, Brunner, 2011 .
  3. ↑ Heath și Rosenberg 1992 , p. Propunerea 4.1.
  4. ↑ Heath și Rosenberg 1992 , p. Propozițiile 4.2, 4.3.
  5. ↑ 1 2 3 4 5 6 7 Heath, Leighton, Rosenberg, 1992 .
  6. ↑ 1 2 Rengarajan, Veni Madhavan, 1995 .
  7. ↑ Heath și Rosenberg 1992 , p. Propunerea 4.6.
  8. ↑ Heath, Rosenberg, 1992 , Propunerea 4.10; Hasunuma, Hirota, 2007 ; Pai, Chang, Wang, 2008 ; Gregor, Škrekovski, Vukašinović, 2011 .
  9. ↑ Heath și Rosenberg 1992 , p. Propozițiile 4.7, 4.8.
  10. ↑ Heath și Rosenberg 1992 , p. Teorema 3.2.
  11. ↑ 1 2 Dujmovic, Wood, 2005 .
  12. ↑ 1 2 Dujmović ( Dujmović 2015 ), o îmbunătățire a limitei anterioare dintre Di Battista, Frati și Pach ( Di Battista, Frati, Pach 2013 ).
  13. ↑ 1 2 Dujmovic, Morin, Wood, 2013 .
  14. ↑ Wood, 2005 .
  15. ↑ Heath și Rosenberg 1992 , p. Teorema 3.6.
  16. ↑ 1 2 Dujmovic, Wood, 2004 .
  17. ^ Heath, Leighton, Rosenberg, 1992 . Un algoritm de timp polinomial pentru găsirea unui aspect cu un număr apropiat de acest număr de cozi a fost dat de Shahrokhi și Shi ( Shahrokhi, Shi 2000 ). Dujmovic și Wood ( Dujmović, Wood 2004 ) au îmbunătățit constanta acestei legături la e √ m , unde e este baza logaritmului natural .
  18. ↑ Wood, 2008 .
  19. ↑ Ganley, Heath, 2001 .
  20. ↑ Dujmovic, Wood, 2003 ; Dujmovic, Morin, Wood, 2005 . Vezi Wood 2002 pentru un rezultat preliminar mai slab care limitează numărul de cozi prin lățimea căii sau o combinație de lățime a arborelui și gradul graficului.
  21. ↑ Heath și Rosenberg 1992 , p. Corolarul 3.9.
  22. ↑ Heath și Rosenberg 1992 , p. Teorema 2.3.
  23. ↑ Nešetřil, Ossona de Mendez, Wood, 2012 .
  24. ↑ Nešetřil, Ossona de Mendez, 2012 , p. 321–327.
  25. ↑ Nešetřil, Ossona de Mendez, 2012 , p. 401, Teorema 18.2.
  26. ↑ Wood, 2002 ; Dujmović, Pór, Wood, 2004 ; Dujmovic, Morin, Wood, 2005 . Vezi Di Giacomo, Meijer, 2004 pentru limite mai strânse ale dimensiunilor grilei pentru graficele cu număr mic de coadă.
  27. ↑ Dujmovic, Wood, 2003 .
  28. ↑ Dujmovic, Morin, Wood, 2005 .

Literatură

Link -uri