Topologická teória grafov

z Wikipédie, slobodnej encyklopédie
Prejsť na: navigácia, hľadanie

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ť zdroj]

Literatúra[upraviť | upraviť zdroj]

  • 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ť zdroj]