Topologická teorie grafů

Topologická teorie grafů  je odvětví teorie grafů , které studuje vkládání grafů do povrchů , prostorové vkládání a grafy jako topologické prostory [1] . V tomto oboru jsou také studovány imerze grafů .

Vložení grafu do plochy znamená, že chceme nakreslit graf na plochu, jako je koule , bez křížení hran . Hlavním problémem vnoření, prezentovaným jako matematická hádanka  , je problém „ domů a studní “. Důležitější aplikace nalezneme v přípravě tištěných elektronických obvodů , kde je cílem rozmístit (vložit) elektronické obvody (graf) na desku tištěných spojů (povrch) bez křížení obvodů, aby nedocházelo ke zkratům .

Grafy jako topologické prostory

Na neorientovaný graf lze nahlížet jako na abstraktní simpliciální komplex C , kde podmnožinami jsou jednoprvkové množiny (odpovídající vrcholům) a dvouprvkové (odpovídající hranám) [2] . Geometrická realizace komplexu | c | sestává z kopií jednotkového intervalu [0,1] pro každou hranu, přičemž konce těchto intervalů jsou ve vrcholech slepeny k sobě. Z tohoto pohledu je speciálním případem topologického vnoření vnoření grafu do plochy nebo dělení jiného grafu. Homeomorfismus grafu  je jen specializací topologického homeomorfismu , pojem souvislého grafu je stejný jako topologického spojení a souvislý graf je strom právě tehdy, když je jeho základní grupa triviální.

Mezi další jednoduché komplexy spojené s grafy patří Whitney nebo klikové komplexy , kde podmnožiny jsou kliky grafu, a porovnávací komplexy , kde podmnožiny jsou shody grafu (ekvivalentně klikové komplexy doplňku čárového grafu ). Odpovídající komplex úplného bipartitního grafu se nazývá šachovnicový komplex , protože jej lze popsat jako komplex souborů vzájemně neútočících věží na šachovnici. [3]

Studijní oblasti

John Hopcroft a Robert Tarjan [4] dosáhli průměrného času pro kontrolu rovinnosti grafu, který je lineární v počtu hran. Jejich algoritmus to dělá vytvořením vložení grafu, kterému říkají „palma“. Účinnost kontroly rovinnosti je základem grafové vizualizace .

Fan Chang et al [5] studovali problém knižního vkládání grafu s vrcholy na čáru na hřbetu knihy. Okraje grafu se kreslí na různé stránky knihy tak, aby se hrany ležící na stejné stránce neprotínaly. Tento problém je abstrakcí problému rozvržení vícevrstvých desek plošných spojů.

Vložení grafu se také používá k prokázání strukturálních výsledků na grafech prostřednictvím teorie grafů a teorému o struktuře grafu .

Viz také

Poznámky

  1. Gross, Tucker, 1987 .
  2. Topologie grafu Archivováno 14. května 2011 na Wayback Machine , z PlanetMath .
  3. John Shareshian, Michelle L. Wachs (2004), Torsion in the matching complex and chessboard complex, arΧiv : math.CO/0409054 . 
  4. Hopcroft, Tarjan, 1974 , str. 549–568.
  5. Chung, Leighton, Rosenberg, 1987 .

Literatura