Topologická teória grafov

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

• Rovinný graf
• Priesečníkové číslo (teória grafov)
• Génus (matematika)
• Kuratowského veta
• Napäťový graf
• Topologická kombinatorika

Literatúra

• 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

• Stránka o otvorených problémoch Archivované 2010-05-16 na Wayback Machine v topologickej teórii grafov (po anglicky)