Počet front grafů

Počet front grafů je graf invariant , definovaný podobně jako číslo zásobníku (tloušťka knihy) a pomocí řazení FIFO (první dovnitř, první ven, fronta) namísto řazení LIFO (poslední dovnitř, první ven, zásobník).

Definice

Reprezentace grafu ve formě front (rozvržení fronty) pro daný graf je dána úplným uspořádáním vrcholů grafu spolu s rozkladem hran grafu do několika „front“. Je požadováno, aby množina hran každé fronty nebyla vnořena podle pořadí vrcholů v tom smyslu, že pokud ab a cd jsou dvě hrany ve stejné frontě, pak zde nesmí být a < c < d < b . Počet front qn( G ) grafu G je minimální počet front pro znázornění grafu jako fronty [1] .

Pomocí rozložení fronty grafů je možné vyčíslit okraje jedné fronty pomocí standardní struktury fronty iterací přes vrcholy v daném pořadí a když dosáhneme vrcholu, vybrat všechny okraje, pro které je vrchol druhým vrcholem oblouku a zařaďte do fronty oblouky, pro které je vrchol první. Podmínka nevnořování zajišťuje, že když je dosaženo vrcholu, všechny hrany, které mají tento vrchol jako terminál, jsou ve frontě a připraveny k načtení. Za alternativní definici lze považovat rozklad grafu do front s popsanými vlastnostmi [1] . Další ekvivalentní definice rozvržení fronty používá pojem vložení daného grafu do válce s vrcholy umístěnými na přímce, která je na povrchu válce, a každá hrana se ovine kolem válce. Hrany zařazené do stejné fronty se nesmí protínat, ale průsečíky hran různých front jsou povoleny [2] .

Rozvržení front definovali Heath a Rosenberg [1] analogicky s předchozí prací o knižním vkládání grafů, které jsou definovány stejným způsobem pomocí zásobníků namísto front. Jak poznamenali, tato rozložení také souvisí s dřívější prací na řazení permutací pomocí paralelních front. Uspořádání fronty bylo motivováno požadavky na návrh integrovaných obvodů a řízení komunikace v distribuovaných algoritmech [1] .

Třídy grafů s omezeným počtem front

Libovolný strom má počet front 1 s řazením vrcholů daným vyhledáváním do šířky [3] . Pseudolesy a mříže mají také počet front 1 [4] . Počet front vnějších rovinných grafů je maximálně 2. Sluneční 3-graf (trojúhelník s každou hranou nahrazenou trojúhelníkem) je příkladem vnějšího rovinného grafu, jehož počet front je přesně 2 [5] [6] . Počet front paralelně-sekvenčního grafu nepřesahuje 3 [6] .

Počet front pro binární de Bruijnovy grafy je 2 [7] . Počet front v grafu d - rozměrné hyperkrychle nepřesahuje d − 1 [8] . Počet front úplných grafů K n a úplných bipartitních grafů K a , b je přesně znám — je roven resp . [9] .

Nevyřešené problémy v matematice : Má každý rovinný graf konečný počet front?

Jakýkoli graf s jednou frontou je rovinný graf s rovinným vnořením „obloukové úrovně“, ve kterém jsou vrcholy na rovnoběžných liniích (úrovních) a každá hrana buď spojuje vrcholy dvou sousedních úrovní, nebo tvoří oblouk spojující dva vrcholy na stejná úroveň. Naopak jakýkoli rovinný graf na úrovni oblouku má uspořádání jedné fronty [10] . Heath, Layton a Rosenberg [5] navrhli, že každý rovinný graf má omezený počet front, ale toto tvrzení zatím není potvrzeno. Pokud je počet front planárních grafů omezený, platí totéž pro 1-rovinné grafy a navíc pro k - planární grafy [11] . Nejsilnější hranice známá pro počet front v rovinných grafech není konstanta, je rovna O (log n ) [12] Polylogaritmické hranice počtu front jsou známé pro grafy s ohraničeným rodem a obecnější grafy z méně uzavřených grafů. rodiny [13] .

Pokud použijeme variantu počtu front nazvanou „silný počet front“, lze počet front součinu grafů omezit funkcí počtu front a striktním počtem front součinových faktorů [14] .

Související invarianty

Grafy s malým počtem front jsou řídké — grafy s n vrcholy a jednou frontou nemají více než 2 n  − 3 hran [15] a obecnější grafy s  q frontami nemají více než 2 qn − q (2 q + 1 ) hrany [16] . Z toho vyplývá, že tyto grafy mají malé chromatické číslo . Zejména grafy s jednou frontou mají zbarvení 3 barev a grafy s frontami q mohou vyžadovat alespoň 2 q + 1 a maximálně 4 q barev [16] . Naopak hranice počtu hran znamená dolní mez počtu front grafů — počet front u grafů s n vrcholy a m hranami nepřesahuje O (√ m ) [17] . Hranice je blízká striktní, protože pro náhodné d -regulární grafy je počet front s vysokou pravděpodobností [5] [18]

Nevyřešené problémy v matematice : Měl by mít jakýkoli graf s omezeným počtem front omezenou tloušťku knihy a naopak?

Grafy s jednou frontou mají šířku knihy nepřesahující dvě [5] . Pro jakékoli pevné pořadí vrcholů je součinem tloušťky knihy a počtu front pro toto pořadí vrcholů alespoň šířka úseku grafu dělená maximálním stupněm vrcholů [5] . Tloušťka knihy může být mnohem větší než počet front – ternární Hammingovy grafy mají logaritmický počet front, ale polynomiální tloušťku knih [5] . Zůstává neznámé, zda je tloušťka knihy omezena nějakou funkcí počtu front. Heath, Leighton a Rosenberg [5] navrhli, že počet front je nanejvýš lineární s tloušťkou knih, ale v tomto směru nebylo dosaženo žádného pokroku. Je známo, že pokud všechny bipartitní grafy s 3stránkovým vložením knih mají omezený počet front, pak všechny grafy s omezenou tloušťkou knihy mají omezený počet front [11] .

Ganley a Heath 19] se zeptali, zda je počet front v grafu omezen funkcí jeho stromové šířky , a citovali nepublikovanou disertační práci S. V. Ukázalo se však, že počet front je omezen (dvojitě exponenciální) funkcí šířky stromu [20]

Výpočetní složitost

Určení počtu front v grafu je NP-úplný problém . I kontrola, že počet front je roven jedné, je NP-úplná [21] .

Pokud je však pořadí vrcholů předem určeno, pak se optimální počet front rovná maximálnímu počtu hran v k -duze, množině k hran, z nichž každý pár má jednu hranu vnořenou do druhé (v popsaném smyslu výše). Rozdělení hran do front lze provést zahrnutím hrany e , což je vnější okraj i -duhy (ale ne větší duhy) do i -té fronty. Optimální rozložení je možné sestrojit v čase O ( m log log n ) , kde n je počet vrcholů grafu a m je počet hran [22] .

Grafy vázané na frontu mají také omezenou expanzi , což znamená, že jejich mělké minority jsou řídké grafy s poměrem hrany k vrcholu (nebo ekvivalentně degenerací nebo stromovostí ) ohraničeným funkcí počtu front a hloubkou menší. V důsledku toho některé algoritmické problémy, včetně problému isomorfismu grafu pro grafy omezené velikosti, mají pro takové grafy algoritmy s lineárním časem [23] [24] . Obecněji, díky omezenému rozšíření lze v lineárním čase zkontrolovat, zda je logický výrok prvního řádu pravdivý pro graf s omezeným počtem front [25] .

Aplikace ve vizualizaci grafů

Ačkoli rozvržení fronty nemusí nutně poskytovat dobré 2D vizualizace , používají se k reprezentaci grafů ve 3D. Konkrétně graf G má omezený počet front tehdy a jen tehdy, když je možné uspořádat vrcholy grafu G na trojrozměrné mřížce o velikosti O ( n ) × O (1) × O (1) v takovým způsobem, že se žádné dvě hrany neprotínají [26] Například de Bruijnovy grafy a ohraničené grafy šířky stromu mají vložení trojrozměrného lineárního objemu [27] [28] .

Logaritmické nebo polylogaritmické hranice počtu front se takovými investicemi do trojrozměrných mřížek přemění na téměř lineární objemy, mřížka v jednom směru bude mít lineární velikost a ve zbývajících dvou - polylogaritmická. Rovinné grafy, grafy s ohraničeným rodem a grafy s ohraničenou lokální šířkou stromu mají vložení velikosti O ( n log n ) [12] , zatímco grafy menších uzavřených čeledí mají velikost O ( n log O (1) n ) [13 ] .

Poznámky

  1. ↑ 1 2 3 4 Heath, Rosenberg, 1992 .
  2. ↑ Auer, Bachmaier, Brandenburg, Brunner, 2011 .
  3. ↑ Heath a Rosenberg 1992 , str. Návrh 4.1.
  4. ↑ Heath a Rosenberg 1992 , str. Propozice 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 a Rosenberg 1992 , str. Návrh 4.6.
  8. ↑ Heath, Rosenberg, 1992 , Tvrzení 4.10; Hasunuma, Hirota, 2007 ; Pai, Chang, Wang, 2008 ; Gregor, Škrekovski, Vukašinović, 2011 .
  9. ↑ Heath a Rosenberg 1992 , str. Propozice 4.7, 4.8.
  10. ↑ Heath a Rosenberg 1992 , str. Věta 3.2.
  11. ↑ 1 2 Dujmovic, Wood, 2005 .
  12. ↑ 1 2 Dujmović ( Dujmović 2015 ), zlepšení dřívější hranice Di Battista, Frati a Pach ( Di Battista, Frati, Pach 2013 ).
  13. ↑ 1 2 Dujmovic, Morin, Wood, 2013 .
  14. ↑ Dřevo, 2005 .
  15. ↑ Heath a Rosenberg 1992 , str. Věta 3.6.
  16. ↑ 1 2 Dujmovic, Wood, 2004 .
  17. ↑ Heath, Leighton, Rosenberg, 1992 . Polynomiální časový algoritmus pro nalezení rozvržení s téměř tímto počtem front byl dán Shahrokhi a Shi ( Shahrokhi, Shi 2000 ). Dujmovic a Wood ( Dujmović, Wood 2004 ) zlepšili konstantu v této vazbě na e √ m , kde e je základ přirozeného logaritmu .
  18. ↑ Dřevo, 2008 .
  19. ↑ Ganley, Heath, 2001 .
  20. ↑ Dujmovic, Dřevo, 2003 ; Dujmovic, Mořín, Dřevo, 2005 . Slabší předběžný výsledek omezující počet front podle šířky cesty nebo kombinace šířky stromu a stupně grafu najdete ve Wood 2002 .
  21. ↑ Heath a Rosenberg 1992 , str. Důsledek 3.9.
  22. ↑ Heath a Rosenberg 1992 , str. Věta 2.3.
  23. ↑ Nešetřil, Ossona de Mendez, Wood, 2012 .
  24. ↑ Nešetřil, Ossona de Mendez, 2012 , str. 321–327.
  25. ↑ Nešetřil, Ossona de Mendez, 2012 , str. 401, Věta 18.2.
  26. ↑ Dřevo, 2002 ; Dujmović, Pór, Dřevo, 2004 ; Dujmovic, Mořín, Dřevo, 2005 . Viz Di Giacomo, Meijer, 2004 pro užší hranice rozměrů mřížky pro grafy malých čísel ve frontě.
  27. ↑ Dujmovic, Wood, 2003 .
  28. ↑ Dujmovic, Morin, Wood, 2005 .

Literatura

Odkazy