teorie grafů

Matematika

Jedna z moderních částí matematiky zahrnovaná zpravidla do kombinatorické analýzy nebo do topologie. Hlavním pojmem v teorii grafů je graf (neorientovaný nebo orientovaný) nebo v obecnějším případě pseudograf, hypergraf. Teorie grafů má mnoho styčných bodů s ostatními matematickými disciplínami a také s aplikacemi (ve fyzice, chemii, ekonomii, systémovém inženýrství, lingvistice). Podle použitých metod a podle svých cílů se dělí na různé směry. Tzv. relativní teorie grafů se zabývá zobrazováním grafů v rovině nebo na jiných plochách, v chromatické teorii grafů jde o barvení uzlů nebo hran daného grafu za určitých podmínek, algebraická teorie grafů sleduje vztahy k algebře (grupy, matice), další směr se věnuje grafovým algoritmům, jiný enumeračním problémům (určování počtu grafů daného typu) ap. Za nejstarší grafový problém se považuje známá úloha o sedmi mostech města Královce, kterou se v 18. století zabýval L. Euler. V 19. století dostala teorie grafů řadu podnětů většinou přímo z praxe (G. Kirchhoff a jeho práce o elektrických obvodech, A. Cayley zabývající se z matematického hlediska strukturními vzorci v organické chemii). Zvláštní místo v teorii grafů má problém čtyř barev, formulovaný asi v polovině 19. století a rozřešený v roce 1976.

Vytvořeno: 14. 3. 2000
Aktualizováno: 19. 8. 2005
Autor: -red-

Odkazující hesla: graf, kombinatorika.