Kaaviojonojen määrä

Graafijonojen määrä on graafin invariantti , joka määritellään samalla tavalla kuin pinon numero (kirjan paksuus) ja jossa käytetään FIFO - järjestystä (first in, first out, queue) LIFO -järjestyksen (viimeinen sisään, ensimmäinen ulos, pino) sijaan.

Määritelmä

Graafin esitys jonojen muodossa (jonoasettelu) tietylle graafille määräytyy graafin kärkien täydellisellä järjestyksellä sekä graafin reunojen hajoamisella useiksi "jonoksi". Jokaisen jonon reunojen joukkoa ei vaadita sisäkkäin kärkijärjestyksen mukaan siinä mielessä, että jos ab ja cd ovat kaksi reunaa samassa jonossa, ei saa olla a < c < d < b . Kuvaajan G jonojen lukumäärä qn( G ) on jonojen vähimmäismäärä kuvaajan esittämiseksi jonoina [1] .

Graafijonoasettelun avulla on mahdollista luetella yksittäisen jonon reunat käyttämällä standardia jonorakennetta iteroimalla kärjet tietyssä järjestyksessä ja kun saavutamme kärkipisteen, valitaan kaikki reunat, joiden kärki on toinen kärki. kaaresta ja jonoon ne kaaret, joiden kärkipiste on ensimmäinen. Ei-sisäkkäisyysehto varmistaa, että kun kärkipiste saavutetaan, kaikki reunat, joilla on tämä kärki päätepisteenä, ovat jonossa ja valmiina noudettavaksi. Kuvaajan hajottamista jonoihin, joilla on kuvatut ominaisuudet, voidaan pitää vaihtoehtoisena määritelmänä [1] . Toinen vastaava jonoasettelun määritelmä käyttää ajatusta tietyn graafin upottamisesta sylinteriin , jonka kärjet sijaitsevat linjalla, joka on sylinterin pinnalla, ja jokainen reuna kiertyy sylinterin ympärille. Saman jonon reunat eivät saa leikata, mutta eri jonojen reunojen leikkauspisteet ovat sallittuja [2] .

Jonojen asettelun määrittelivät Heath ja Rosenberg [1] analogisesti aikaisempien graafien upottamista koskevien töiden kanssa , jotka määritellään samalla tavalla pinoja jonojen sijaan. Kuten he huomauttivat, nämä asettelut liittyvät myös aikaisempaan työhön permutaatioiden lajittelussa rinnakkaisjonojen avulla. Jonoasettelun motiivina olivat integroidun piirin suunnittelun ja hajautettujen algoritmien tietoliikenteen hallinnan vaatimukset [1] .

Graafiluokat, joissa on rajoitettu määrä jonoja

Minkä tahansa puun jonomäärä on 1 ja kärkijärjestys on annettu leveyshaulla [3] . Pseudometsillä ja hilailla on myös jonoluku 1 [4] . Ulompitasoisten graafien jonojen lukumäärä on enintään 2. Solaarinen 3-graafi (kolmio, jonka jokainen reuna on korvattu kolmiolla) on esimerkki ulompitasoisesta graafista, jonka jonoja on tasan 2 [5] [6] . Rinnakkaisen peräkkäisen graafin jonojen määrä ei ylitä 3 [6] .

Binääristen de Bruijn-graafien jonojen määrä on 2 [7] . Jonojen lukumäärä d - ulotteisen hyperkuution kaaviossa ei ylitä d − 1 [8] . Täydellisten graafien K n ja täydellisten kaksiosaisten graafien Ka a , b jonojen lukumäärä tunnetaan tarkasti — se on yhtä suuri ja vastaavasti [9] .

Ratkaisemattomat matematiikan ongelmat : Onko jokaisessa tasograafissa rajallinen määrä jonoja?

Mikä tahansa graafi, jossa on yksi jono, on tasograafi , jossa on "kaaritason" tasoupottaminen, jossa kärjet ovat yhdensuuntaisilla viivoilla (tasoilla) ja jokainen reuna joko yhdistää kahden vierekkäisen tason kärjet tai muodostaa kaaren, joka yhdistää kaksi kärkeä sama taso. Sitä vastoin missä tahansa kaaritason tasograafissa on yhden jonon asettelu [10] . Heath, Layton ja Rosenberg [5] ehdottivat, että missä tahansa tasograafissa on rajoitettu määrä jonoja, mutta tälle väitteelle ei ole vielä vahvistusta. Jos tasograafien jonojen lukumäärä on rajoitettu, sama pätee 1-tasograafisiin ja lisäksi k - tasograafisiin [11] . Tasograafien jonojen lukumäärälle tunnettu vahvin raja ei ole vakio, se on yhtä kuin O (log n ) [12] Jonojen lukumäärän polylogaritmiset rajat tunnetaan kaavioille, joiden suku on rajoitettu, ja yleisemmille graafiille vähän suljetuista . perheet [13] .

Jos käytämme jonojen lukumäärän muunnelmaa, jota kutsutaan "vahvaksi jonomääräksi", kaavioiden tulon jonojen määrää voidaan rajoittaa jonojen lukumäärän ja tulokertoimien tiukan jonomäärän funktiolla [14] . .

Aiheeseen liittyvät invariantit

Graafit, joissa on pieni määrä jonoja, ovat harvassa — graafissa, jossa on n kärkeä ja yksi jono, on korkeintaan 2 n  − 3 reunaa [15] ja yleisemmissä kaavioissa, joissa on  q jonoja, on enintään 2 qn − q (2 q + 1 ) reunat [16] . Tästä seuraa, että näillä kaavioilla on pieni kromaattinen luku . Erityisesti kaavioissa, joissa on yksi jono, on 3 värin väritys, ja q - jonoa sisältävät kaaviot voivat vaatia vähintään 2 q + 1 ja enintään 4 q väriä [16] . Päinvastoin, reunalukurajoitus merkitsee alarajaa graafijonojen lukumäärälle — n pisteen ja m reunan graafien jonot eivät ylitä arvoa O (√ m ) [17] . Raja on lähellä tiukkaa, koska satunnaisissa d -säännöllisissä kaavioissa jonojen määrä suurella todennäköisyydellä on [5] [18]

Ratkaisemattomat matematiikan ongelmat : Pitäisikö jollakin rajatulla määrällä jonoja sisältävällä kaaviolla olla rajoitettu kirjan paksuus ja päinvastoin?

Yhden jonon kaavioiden kirjan leveys on enintään kaksi [5] . Minkä tahansa kiinteän kärkijärjestyksen kohdalla kirjan paksuuden ja tämän kärkijärjestyksen jonojen määrän tulo on vähintään graafin osuuden leveys jaettuna pisteiden maksimiasteessa [5] . Kirjan paksuus voi olla paljon suurempi kuin jonojen lukumäärä - ternaarisissa Hamming-kaavioissa on logaritminen jonomäärä, mutta kirjojen polynomipaksuus [5] . On edelleen epäselvää, rajoittaako kirjan paksuutta jokin jonojen lukumäärän funktio. Heath, Leighton ja Rosenberg [5] ehdottivat, että jonojen määrä on korkeintaan lineaarinen kirjojen paksuuden kanssa, mutta tähän suuntaan ei ole edistytty. Tiedetään, että jos kaikissa kaksiosaisissa kaavioissa , joissa on 3-sivuinen kirjan upottaminen, on rajoitettu määrä jonoja, niin kaikissa graafisissa, joissa on rajoitettu kirjanpaksuus, on rajoitettu määrä jonoja [11] .

Ganley ja Heath 19] kysyivät, rajoittaako graafin jonojen lukumäärä sen puunleveyden funktio , ja lainasivat julkaisematonta väitöskirjaa S. V. Jonojen määrää on kuitenkin osoitettu rajoittavan puunleveyden (kaksinkertaisesti eksponentiaalinen) funktio [20]

Laskennallinen monimutkaisuus

Jonojen lukumäärän määrittäminen kaaviossa on NP-täydellinen ongelma . Jopa sen tarkistaminen, että jonojen lukumäärä on yhtä suuri, on NP-täydellinen [21] .

Kuitenkin, jos kärkijärjestys on ennalta määrätty, niin optimaalinen jonojen lukumäärä on yhtä suuri kuin reunojen enimmäismäärä k -sateenkaaressa, k reunojen joukossa, joiden jokaisessa parissa on yksi reuna sisäkkäin toisen sisällä (kuvatussa mielessä). edellä). Reunojen jakaminen jonoihin voidaan tehdä sisällyttämällä reuna e , joka on i -sateenkaaren ulkoreuna (mutta ei suurempaa sateenkaaren reunaa) i - jonoon. On mahdollista rakentaa optimaalinen asettelu O ( m log log n ) -ajassa , missä n on graafin kärkien lukumäärä ja m on reunojen lukumäärä [22] .

Jonosidottuilla graafilla on myös rajoitettu laajennus , mikä tarkoittaa, että niiden matalat alavärit ovat harvalukuisia graafisia , joiden reuna-vertex-suhde (tai vastaavasti rappeutuminen tai puuisuus ) on rajattu jonojen lukumäärän ja mollin syvyyden funktiolla. Seurauksena on, että joillakin algoritmisilla ongelmilla, mukaan lukien graafisen isomorfismin ongelma rajoitetun kokoisille graafiille, on lineaariaikaisia ​​algoritmeja tällaisille kaavioille [23] [24] . Yleisemmin rajatun laajennuksen ansiosta voidaan lineaarisessa ajassa tarkistaa, onko ensimmäisen asteen logiikkalause totta graafille, jossa on rajoitettu määrä jonoja [25] .

Sovellus graafin visualisoinnissa

Vaikka jonoasettelut eivät välttämättä anna hyviä 2D - visualisointeja , niitä käytetään kuvaajien esittämiseen 3D-muodossa. Erityisesti graafilla G on rajoitettu määrä jonoja, jos ja vain jos on mahdollista järjestää graafin G kärjet kolmiulotteiseen hilaan, jonka koko on O ( n ) × O (1) × O (1 ) siten, että kaksi reunaa ei leikkaa [26] Esimerkiksi de Bruijn-graafit ja rajalliset puunleveydet sisältävät kolmiulotteisen lineaarisen tilavuusupotuksen [27] [28] .

Jonojen lukumäärän logaritmiset tai polylogaritmiset rajat muunnetaan sellaisilla investoinneilla kolmiulotteisiin hilakoihin lähes lineaariseksi tilavuudeksi, hilassa yhdessä suunnassa on lineaarinen koko ja kahdessa muussa - polylogaritminen. Tasograafit, graafit, joissa on rajattu suku, ja graafit, joissa on rajoitettu paikallinen puuleveys, sisältävät upotuksia, joiden koko on O ( n log n ) [12] , kun taas pienten suljettujen perheiden kaavioiden koko on O ( n log O (1) n ) [13 ] .

Muistiinpanot

  1. ↑ 1 2 3 4 Heath, Rosenberg, 1992 .
  2. ↑ Auer, Bachmaier, Brandenburg, Brunner, 2011 .
  3. ↑ Heath ja Rosenberg 1992 , s. Ehdotus 4.1.
  4. ↑ Heath ja Rosenberg 1992 , s. Ehdotukset 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 ja Rosenberg 1992 , s. Ehdotus 4.6.
  8. ↑ Heath, Rosenberg, 1992 , Proposition 4.10; Hasunuma, Hirota, 2007 ; Pai, Chang, Wang, 2008 ; Gregor, Škrekovski, Vukašinović, 2011 .
  9. ↑ Heath ja Rosenberg 1992 , s. Ehdotukset 4.7, 4.8.
  10. ↑ Heath ja Rosenberg 1992 , s. Lause 3.2.
  11. ↑ 1 2 Dujmovic, Wood, 2005 .
  12. ↑ 1 2 Dujmović ( Dujmović 2015 ), parannus Di Battistan, Fratin ja Pachin aikaisemmasta rajasta ( Di Battista, Frati, Pach 2013 ).
  13. ↑ 1 2 Dujmovic, Morin, Wood, 2013 .
  14. ↑ Puu, 2005 .
  15. ↑ Heath ja Rosenberg 1992 , s. Lause 3.6.
  16. ↑ 1 2 Dujmovic, Wood, 2004 .
  17. ↑ Heath, Leighton, Rosenberg, 1992 . Shahrokhi ja Shi ( Shahrokhi, Shi 2000 ) antoivat polynomisen aika-algoritmin asettelun löytämiseksi, jossa on lähellä tätä määrää jonoja . Dujmovic ja Wood ( Dujmović, Wood 2004 ) paransivat vakiota tässä sidottuna arvoon e √ m , missä e on luonnollisen logaritmin kanta .
  18. ↑ Puu, 2008 .
  19. ↑ Ganley, Heath, 2001 .
  20. ↑ Dujmovic, Wood, 2003 ; Dujmovic, Morin, Wood, 2005 . Katso Wood 2002 :sta heikompi alustava tulos, joka rajoittaa jonojen määrää polun leveydellä tai puunleveyden ja graafin asteen yhdistelmällä.
  21. ↑ Heath ja Rosenberg 1992 , s. Seuraus 3.9.
  22. ↑ Heath ja Rosenberg 1992 , s. Lause 2.3.
  23. ↑ Nešetřil, Ossona de Mendez, Wood, 2012 .
  24. ↑ Nešetřil, Ossona de Mendez, 2012 , s. 321-327.
  25. ↑ Nešetřil, Ossona de Mendez, 2012 , s. 401, Lause 18.2.
  26. ↑ Puu, 2002 ; Dujmović, Pór, Wood, 2004 ; Dujmovic, Morin, Wood, 2005 . Katso Di Giacomo, Meijer, 2004 tiukemmista rajoista ruudukon mitoissa pienien jononumeroiden kuvaajille.
  27. ↑ Dujmovic, Wood, 2003 .
  28. ↑ Dujmovic, Morin, Wood, 2005 .

Kirjallisuus

Linkit