Topologická teória grafov

z Wikipédie, slobodnej encyklopédie
Skočit na navigaci Skočit na vyhledávání

Topologická teória grafov je matematická disciplína a podoblasť teórie grafov zaoberajúca sa predovšetkým vnáraním grafov do plôch. Skúma tiež grafy ako topologické priestory.

Vnáranie grafov do plôch znamená kreslenie grafov na rôzne plochy, pričom cieľom je dosiahnuť nakreslenie grafu bez krížiacich sa hrán. Grafy, pre ktoré existuje takéto nakreslenie v rovine, sa nazývajú rovinné grafy. Pre iné grafy zas v rovine takéto nakreslenie existovať nemusí, ale na iných plochách, ako napr. na povrchu gule, môže.

Medzi praktické aplikácie topologickej teórie grafov patrí napríklad návrh integrovaných obvodov, kde je dôležité, aby sa linky navzájom nekrížili.

Pozri aj[upraviť | upraviť kód]

Literatúra[upraviť | upraviť kód]

  • Gross, J. L., Tucker, T. W.: Topological Graph Theory. Wiley Interscience, 1987.
  • Nishizeki, T., Chiba, N.: Planar Graphs: Theory and Algorithms. North-Holland, 1988.

Externé odkazy[upraviť | upraviť kód]