Vložení grafu

Vložení grafu je zobrazení grafu na daném povrchu   studované v rámci topologické teorie grafů , ve kterém jsou body asociovány s vrcholy grafu a jednoduché oblouky ( homeomorfní obrázky [0,1]) na ploše jsou asociovány s hranami grafu. takovým způsobem, že:

Zde je povrch kompaktní , připojený 2 - rozdělovač .

Neformálně je vložení grafu do plochy zobrazením grafu na ploše takovým způsobem, že se jeho hrany mohou protínat pouze v koncových bodech. Je dobře známo, že jakýkoli konečný graf lze vložit do trojrozměrného euklidovského prostoru [1] a rovinné grafy lze vložit do dvourozměrného euklidovského prostoru .

Na vložení se často pohlíží jako na třídu ekvivalence (homeomorfismy ) reprezentací popsaného druhu.

V kontextu problémů s vizualizací grafů se uvažuje i o slabé verzi definice vkládání grafu, ve které není vyžadována absence průsečíků hran. V souladu s tím je silná definice popsána jako „vložení grafu bez průniků“ [2] .

Terminologie

Pokud je graf vnořen do uzavřeného povrchu , pak doplňkem spojení bodů a oblouků spojených s vrcholy a hranami grafu je rodina rodiny oblastí (nebo ploch) [3] . Dvourozměrné vložení buněk nebo mapa  je vložení, ve kterém je každá tvář homeomorfní k otevřenému disku [4] . Dvourozměrné vložení uzavřených buněk  je vložení, ve kterém je uzavření jakékoli plochy homeomorfní uzavřenému disku.

Skládání grafů se často používá jako synonymum pro vnoření, zejména v případě rovinných grafů.

Rod grafu  je nejmenší celé číslo , takže graf může být vložen do povrchu rodu . Zejména rovinný graf má rod 0, protože jej lze nakreslit na kouli bez průniků. Neorientovatelný rod grafu je nejmenší celé číslo , takže graf lze vložit do neorientovaného povrchu (neorientovatelného) rodu [3] .

Eulerův rod grafu je nejmenší celé číslo , takže graf může být vložen do orientovatelného povrchu (orientovatelného) rodu nebo neorientovaného povrchu (neorientovatelného) rodu . Graf je jednoduše orientovatelný , pokud je jeho rod Euler menší než jeho neorientovatelný rod.

Maximální rod grafu  je maximální celé číslo , takže graf může být vložen jako plochá buňka (vložení je plochá buňka, pokud jakákoli uzavřená křivka, která neprotíná okraje grafu, se stahuje do bodu) do orientovatelného povrchu grafu . rod .

Kombinatorické vkládání

Vnořený graf jednoznačně definuje cyklické pořadí hran dopadajících do stejného vrcholu. Množina všech těchto cyklických řádů se nazývá kruhový systém . Vložení se stejným kruhovým systémem se považuje za ekvivalentní a odpovídající třída ekvivalence vložení se nazývá kombinatorické vložení (na rozdíl od termínu topologické vložení , který odkazuje na předchozí definici bodů a křivek). Někdy se sám kruhový systém nazývá „kombinatorické vložení“ [5] [6] [7] .

Vnořený graf také definuje přirozené cyklické pořadí hran, které definují hranice vnořených ploch. Práce s těmito fasetově orientovanými řády je však méně zřejmá, protože v některých případech mohou být některé hrany překročeny dvakrát při přecházení hranice plochy. To platí například vždy při hnízdění stromů, které mají jednu hranu. K překonání této kombinatorické překážky lze považovat každou hranu za „rozdělenou“ na dvě „poloviční hrany“ nebo „strany“. Podle těchto konvencí hranice ve všech plochách prochází každou poloviční hranou pouze jednou a každá polovina jedné hrany je vždy procházena v opačných směrech.

Výpočetní složitost

Problém určení rodu grafu je NP-úplný (problém určení, zda má graf s vrcholy rod je NP-úplný ) [8] .

Zároveň je problém určení rodu grafu pevně-parametricky řešitelný , tedy jsou známy algoritmy s polynomiálním časem pro kontrolu, zda lze graf vložit do plochy s daným rodem. Totéž platí pro hledání přílohy.

První průlom přišel v roce 1979 , kdy byly algoritmy časové složitosti nezávisle hlášeny na výročním sympoziu ACM o výpočetní teorii  – jeden navrhl Ion Filotti a Gary Miller a další John Reif . Jejich přístupy byly zcela odlišné, ale na návrh organizačního výboru předložili sloučený článek [9] .

V roce 1999 se ukázalo, že případ fixního rodu lze řešit v lineárním čase ve velikosti grafu a ve dvojnásobném exponenciálním čase v rodu [10] .

Vložení grafu do prostorů vyšších dimenzí

Je známo, že jakýkoli konečný graf lze vložit do trojrozměrného prostoru [1] .

Jednou z metod takového vkládání je umístit body (vrcholy grafu) na čáru a nakreslit hrany jako křivky ležící v samostatných polorovinách , které mají tuto čáru jako hranici společnou pro všechny poloroviny. Tento druh vkládání se nazývá vkládání knih grafů . Tato metafora se vyjasní, představíme-li si každou polorovinu jako stránku knihy. Je jasné, že některé hrany lze na stejné „stránce“ nakreslit bez průsečíků. Tloušťka knihy grafu je minimální počet polorovin ve vložení knihy.

Na druhou stranu, jakýkoli konečný graf lze nakreslit bez průsečíků v trojrozměrném prostoru s rovnými hranami umístěním vrcholů do obecné polohy tak, že žádné čtyři nejsou koplanární (neleží ve stejné rovině). Toho lze například dosáhnout umístěním -tého vrcholu do bodu na momentové křivce .

Vložení grafu do trojrozměrného prostoru, ve kterém nejsou topologicky propojeny žádné dva cykly, se nazývá nespojené vkládání . Graf má nepropojené vložení tehdy a pouze tehdy, když neobsahuje žádný ze sedmi grafů rodiny Petersonů jako nezletilé .

Viz také

Poznámky

  1. ↑ 1 2 Cohen, Eades, Lin, Ruskey, 1995 , str. 1–11.
  2. ↑ Katoh, Tanigawa, 2007 , str. 243–253.
  3. ↑ 12 Gross , Tucker, 2001 .
  4. ↑ Zvonkin, Lando, 2010 .
  5. ↑ Mutzel, Weiskircher, 2000 , s. 95–104.
  6. ↑ Didjev, 1995 , str. 76–83.
  7. ↑ Duncan, Goodrich, Kobourov, 2010 , str. 45–56.
  8. ↑ Thomassen, 1989 , s. 568–576.
  9. ↑ Filotti, Miller, Reif, 1979 , str. 27–37.
  10. ↑ Mohar, 1999 , str. 6–26.

Literatura