Topologická teorie grafů - Topological graph theory

Tento článek je o studiu vkládání grafů. Grafy v rovině s křížením viz topologický graf.

v matematika, teorie topologických grafů je pobočkou teorie grafů. Studuje vkládání z grafy v povrchy, prostorové vkládání grafů a grafy jako topologické prostory.[1] Také to studuje ponoření grafů.

Vložení grafu do povrchu znamená, že chceme nakreslit graf na povrch, a koule například bez dvou hrany protínající se. Základní problém s vkládáním často prezentovaný jako a matematické puzzle je problém tří chat. Další aplikace najdete v tisku elektronické obvody kde cílem je vytisknout (vložit) obvod (graf) na a obvodová deska (povrch), aniž by se navzájem protínaly dvě spojení, což by vedlo k a zkrat.

Grafy jako topologické prostory

Viz také: Graf (topologie) a Homologie grafů

K neorientovanému grafu můžeme přiřadit abstraktní zjednodušený komplex C se sadou jednoho prvku na vrchol a sadou dvou prvků na hranu.[2] Geometrická realizace |C| komplexu se skládá z kopie jednotkového intervalu [0,1] na hranu s koncovými body těchto intervaly slepené dohromady na vrcholech. V tomto pohledu vložení grafů do povrchu nebo jako dělení dalších grafů jsou oba případy topologického vkládání, homeomorfismus grafů je jen specializace topologické homeomorfismus, pojem a připojený graf se shoduje s topologická propojenost a připojený graf je a strom jen a jen pokud základní skupina je triviální.

Mezi další zjednodušené komplexy spojené s grafy patří Whitney komplex nebo klikový komplex, se sadou za klika grafu a odpovídající komplex, se sadou za vhodný grafu (ekvivalentně klikový komplex doplňku hranový graf ). Odpovídající komplex a kompletní bipartitní graf se nazývá a šachovnicový komplex, jak lze také popsat jako komplex sad nepřátelských věžiček na šachovnici.[3]

Ukázkové studie

John Hopcroft a Robert Tarjan[4] odvozený prostředek testování rovinnosti grafu v čase lineárně k počtu hran. Jejich algoritmus to dělá konstrukcí vložení grafu, který nazývají „palma“. Efektivní testování rovinnosti je základem kreslení grafu.

Fan Chung et al.[5] studoval problém vložení grafu do knihy s vrcholy grafu v linii podél hřbetu knihy. Jeho okraje jsou nakresleny na samostatných stránkách tak, aby se hrany na stejné stránce nepřekřížily. Tento problém abstrahuje problémy s uspořádáním vznikající při směrování vícevrstvých desek plošných spojů.

Vkládání grafů se také používají k prokázání strukturálních výsledků o grafech prostřednictvím teorie grafů a věta o struktuře grafu.

Viz také

Poznámky

  1. ^ J.L. Gross a T.W. Tucker, Topological graph theory, Wiley Interscience, 1987
  2. ^ Topologie grafu, z PlanetMath.
  3. ^ Shareshian, John; Wachs, Michelle L. (2004). "Torze v odpovídajícím komplexu a šachovnicovém komplexu". arXiv:math.CO/0409054.CS1 maint: více jmen: seznam autorů (odkaz)
  4. ^ Hopcroft, Johne; Tarjan, Robert E. (1974). „Efektivní testování rovinnosti“ (PDF). Deník ACM. 21 (4): 549–568. doi:10.1145/321850.321852. hdl:1813/6011.
  5. ^ Chung, F. R. K.; Leighton, F. T.; Rosenberg, A. L. (1987). „Vkládání grafů do knih: problém s rozložením aplikací do designu VLSI“ (PDF). SIAM Journal o algebraických a diskrétních metodách. 8 (1): 33–58. doi:10.1137/0608002.