Antal grafkøer

Antallet af grafkøer er en grafinvariant , defineret på samme måde som staknummeret (bogtykkelse) og bruger FIFO (først ind, først ud, kø) bestilling i stedet for LIFO (sidst ind, først ud, stak) bestilling.

Definition

Grafrepræsentationen i form af køer (kølayout) for en given graf bestemmes af den fuldstændige rækkefølge af grafens hjørner , sammen med dekomponeringen af ​​grafens kanter i flere "køer". Det er påkrævet, at sættet af kanter af hver kø ikke er indlejret efter toppunktsrækkefølge i den forstand, at hvis ab og cd er to kanter i samme kø, så må der ikke være a < c < d < b . Antallet af køer qn( G ) i grafen G er det mindste antal køer til at repræsentere grafen som køer [1] .

Ved at bruge grafkølayoutet er det muligt at opregne kanterne på en enkelt kø ved hjælp af standardkøstrukturen ved at iterere over hjørnerne i en given rækkefølge, og når vi når et toppunkt, skal du vælge alle de kanter, for hvilke toppunktet er det andet toppunkt af buen og kør de buer, hvor toppunktet er det første. Den ikke-nesting-tilstand sikrer, at når et toppunkt nås, er alle kanter, der har det toppunkt som terminal, i køen og klar til at blive hentet. Dekomponering af en graf i køer med de beskrevne egenskaber kan betragtes som en alternativ definition [1] . En anden tilsvarende definition af kø-layout bruger ideen om at indlejre en given graf i en cylinder med spidser placeret på en linje, der er på overfladen af ​​cylinderen, og hver kant vikler sig rundt om cylinderen. Kanter, der er inkluderet i samme kø, må ikke krydse hinanden, men skæringer af kanter af forskellige køer er tilladt [2] .

Layoutet af køer blev defineret af Heath og Rosenberg [1] i analogi med tidligere arbejde med bogindlejringer af grafer, som er defineret på samme måde ved hjælp af stakke i stedet for køer. Som de bemærkede, er disse layouts også relateret til tidligere arbejde med at sortere permutationer ved hjælp af parallelle køer. Kølayoutet var motiveret af kravene til integreret kredsløbsdesign og kommunikationsstyring i distribuerede algoritmer [1] .

Klasser af grafer med et begrænset antal køer

Ethvert træ har et køantal på 1 med toppunktsrækkefølge givet ved bredde-først søgning [3] . Pseudoskove og gitter har også et køantal på 1 [4] . Antallet af køer af ydreplanære grafer er højst 2. En solar 3-graf (en trekant med hver kant erstattet af en trekant) er et eksempel på en ydreplanær graf, hvis antal køer er nøjagtigt 2 [5] [6] . Antallet af køer i en parallel-sekventiel graf overstiger ikke 3 [6] .

Antallet af køer for binære de Bruijn-grafer er 2 [7] . Antallet af køer i en graf af en d - dimensional hyperkube overstiger ikke d − 1 [8] . Antallet af køer af komplette grafer K n og komplette todelte grafer K a , b er kendt nøjagtigt - det er lig med henholdsvis [ 9] .

Uløste problemer i matematik : Har hver plan graf et begrænset antal køer?

Enhver graf med én kø er en plan graf med en "bueniveau" plan indlejring, hvor toppunkterne er på parallelle linjer (niveauer), og hver kant enten forbinder toppunkterne på to tilstødende niveauer eller danner en bue, der forbinder to toppunkter ved samme niveau. Omvendt har enhver plangraf på bueniveau et enkelt-kø-layout [10] . Heath, Layton og Rosenberg [5] foreslog, at enhver plan graf har et begrænset antal køer, men der er endnu ingen bekræftelse af denne erklæring. Hvis antallet af køer af plane grafer er begrænset, gælder det samme for 1-plane grafer og desuden for k - planære grafer [11] . Den stærkeste grænse kendt for antallet af køer i plane grafer er ikke en konstant, den er lig med O (log n ) [12] Polylogaritmiske grænser for antallet af køer er kendt for grafer med afgrænset slægt og mere generelle grafer fra mindre lukkede familier [13] .

Hvis vi bruger en variant af antallet af køer kaldet "stærkt antal køer", kan antallet af køer af produktet af grafer begrænses af en funktion af antallet af køer og det strenge antal køer af produktfaktorer [14] .

Relaterede invarianter

Grafer med et lille antal køer er sparsomme — grafer med n toppunkter og en kø har ikke mere end 2 n  − 3 kanter [15] , og mere generelle grafer med  q køer har ikke mere end 2 qn − q (2 q + 1 ) kanter [16] . Det følger heraf, at disse grafer har et lille kromatisk tal . Især grafer med én kø har en farvning på 3 farver, og grafer med q -køer kan kræve mindst 2 q + 1 og højst 4 q farver [16] . Omvendt medfører kantnummeret bundet en nedre grænse for antallet af grafkøer — antallet af køer for grafer med n toppunkter og m kanter overstiger ikke O (√ m ) [17] . Grænsen er tæt på streng, da antallet af køer med høj sandsynlighed for tilfældige d -regulære grafer er [5] [18]

Uløste problemer i matematik : Skal enhver graf med et begrænset antal køer have en begrænset bogtykkelse og omvendt?

Grafer med én kø har en bogbredde, der ikke overstiger to [5] . For enhver fast rækkefølge af hjørner er produktet af tykkelsen af ​​bogen og antallet af køer for den rækkefølge af hjørner mindst bredden af ​​sektionen af ​​grafen divideret med den maksimale grad af hjørner [5] . Tykkelsen af ​​en bog kan være meget større end antallet af køer - ternære Hamming-grafer har et logaritmisk antal køer, men en polynomisk tykkelse af bøger [5] . Det er fortsat uvist, om bogtykkelsen er begrænset af en eller anden funktion af antallet af køer. Heath, Leighton og Rosenberg [5] foreslog, at antallet af køer højst er lineært med bøgernes tykkelse, men der er ikke gjort fremskridt i denne retning. Det er kendt, at hvis alle todelte grafer med 3-siders bogindlejringer har et begrænset antal køer, så har alle grafer med en begrænset bogtykkelse et begrænset antal køer [11] .

Ganley og Heath 19] spurgte, om antallet af køer i en graf er afgrænset af en funktion af dens træbredde , og citerede en upubliceret afhandling af S. V. Imidlertid har antallet af køer vist sig at være begrænset af en (dobbelt eksponentiel) funktion af træbredden [20]

Beregningsmæssig kompleksitet

At bestemme antallet af køer i en graf er et NP-komplet problem . Selv at kontrollere, at antallet af køer er lig med én, er NP-komplet [21] .

Men hvis toppunktsrækkefølgen er forudbestemt, så er det optimale antal køer lig med det maksimale antal kanter i en k -regnbue, et sæt af k kanter, hvor hvert par har en kant indlejret i en anden (i den beskrevne betydning over). Opdelingen af ​​kanter i køer kan gøres ved at inkludere kanten e , som er den yderste kant af i -regnbuen (men ikke den større regnbue) i den i -te kø. Det er muligt at konstruere et optimalt layout i O ( m log log n ) tid , hvor n er antallet af grafens toppunkter og m er antallet af kanter [22] .

Købundne grafer har også afgrænset ekspansion , hvilket betyder, at deres lavvandede minorer er sparsomme grafer med et kant-til-vertex-forhold (eller tilsvarende degeneration eller treeness ) afgrænset af en funktion af antallet af køer og dybden af ​​minor. Som en konsekvens heraf har nogle algoritmiske problemer, herunder grafisomorfiproblemet for grafer af begrænset størrelse, lineære- tidsalgoritmer for sådanne grafer [23] [24] . Mere generelt kan man på grund af begrænset forlængelse kontrollere i lineær tid, om en førsteordens logiksætning er sand for en graf med et begrænset antal køer [25] .

Anvendelse i grafvisualisering

Selvom kølayout ikke nødvendigvis giver gode 2D- visualiseringer , bruges de til at repræsentere grafer i 3D. Især har en graf G et afgrænset antal køer, hvis og kun hvis det er muligt at arrangere toppunkterne af grafen G på et tredimensionelt gitter af størrelsen O ( n ) × O (1) × O (1) i sådan, at ingen to kanter skærer hinanden [26] For eksempel har de Bruijn-grafer og grafer med afgrænset træbredde en tredimensionel lineær volumenindlejring [27] [28] .

Logaritmiske eller polylogaritmiske grænser for antallet af køer omdannes med sådanne investeringer i tredimensionelle gitter til næsten lineære volumener, gitteret i den ene retning vil have en lineær størrelse, og i de to andre - polylogaritmisk. Plane grafer, grafer med afgrænset slægt og grafer med afgrænset lokal træbredde har indlejringer af størrelse O ( n log n ) [12] , mens grafer for mindre lukkede familier har størrelse O ( n log O (1) n ) [13] .

Noter

  1. ↑ 1 2 3 4 Heath, Rosenberg, 1992 .
  2. ↑ Auer, Bachmaier, Brandenburg, Brunner, 2011 .
  3. ↑ Heath og Rosenberg 1992 , s. Forslag 4.1.
  4. ↑ Heath og Rosenberg 1992 , s. Forslag 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 og Rosenberg 1992 , s. Forslag 4.6.
  8. ↑ Heath, Rosenberg, 1992 , Proposition 4.10; Hasunuma, Hirota, 2007 ; Pai, Chang, Wang, 2008 ; Gregor, Škrekovski, Vukašinović, 2011 .
  9. ↑ Heath og Rosenberg 1992 , s. Forslag 4.7, 4.8.
  10. ↑ Heath og Rosenberg 1992 , s. Sætning 3.2.
  11. ↑ 1 2 Dujmovic, Wood, 2005 .
  12. ↑ 1 2 Dujmović ( Dujmović 2015 ), en forbedring af den tidligere grænse mellem Di Battista, Frati og Pach ( Di Battista, Frati, Pach 2013 ).
  13. ↑ 1 2 Dujmovic, Morin, Wood, 2013 .
  14. ↑ Wood, 2005 .
  15. ↑ Heath og Rosenberg 1992 , s. Sætning 3.6.
  16. ↑ 1 2 Dujmovic, Wood, 2004 .
  17. ↑ Heath, Leighton, Rosenberg, 1992 . En polynomisk tidsalgoritme til at finde et layout med tæt på dette antal køer blev givet af Shahrokhi og Shi ( Shahrokhi, Shi 2000 ). Dujmovic og Wood ( Dujmović, Wood 2004 ) forbedrede konstanten i denne binding til e √ m , hvor e er bunden af ​​den naturlige logaritme .
  18. ↑ Wood, 2008 .
  19. ↑ Ganley, Heath, 2001 .
  20. ↑ Dujmovic, Wood, 2003 ; Dujmovic, Morin, Wood, 2005 . Se Wood 2002 for et svagere foreløbigt resultat, der begrænser antallet af køer efter stibredde eller en kombination af træbredde og grafgrad.
  21. ↑ Heath og Rosenberg 1992 , s. Konsekvens 3.9.
  22. ↑ Heath og Rosenberg 1992 , s. Sætning 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, sætning 18.2.
  26. ↑ Wood, 2002 ; Dujmović, Pór, Wood, 2004 ; Dujmovic, Morin, Wood, 2005 . Se Di Giacomo, Meijer, 2004 for strammere grænser for gitterdimensionerne for grafer med små kønummer.
  27. ↑ Dujmovic, Wood, 2003 .
  28. ↑ Dujmovic, Morin, Wood, 2005 .

Litteratur

Links