teorie grafů
teorie grafů, 1. jedna z moderních částí mat. zahrnovaná zpravidla do kombinatorické analýzy nebo do topologie. Hl. pojmem v t. g. je graf (neorientovaný nebo orientovaný) nebo v obecnějším případě pseudograf, hypergraf. T. g. má mnoho styčných bodů s ostatními mat. disciplínami a také s aplikacemi (ve fyz., chem., ekon., systémovém inženýrství, lingvistice). Podle použitých metod a podle svých cílů se t. g. dělí na různé směry. Tzv. relativní t. g. se zabývá zobrazováním grafů v rovině nebo na jiných plochách, v chromatické t. g. jde o barvení uzlů nebo hran daného grafu za určitých podmínek, algebraická t. g. 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 nejst. grafový problém se považuje známá úloha o sedmi mostech města Královce, kterou se v 18.st. zabýval L. Euler. V 19.st. dostala t. g. řadu podnětů většinou přímo z praxe (G. Kirchhoff a jeho práce o el. obvodech, A. Cayley zabývající se z mat. hlediska strukturními vzorci v org. chem.). Zvl. místo v t. g. má problém čtyř barev, formulovaný asi v polovině 19. století a rozřešený 1976; 2. sociol. teorie využívající geom. schémata pro vyjádření a analýzu vztahů v systémech (strukturní schémata organizačních vztahů, sociogramy), pro analýzu efektivnosti uspořádání a činnosti organizace (analýza toků informací, zvýšení soudržnosti skupiny, optimalizace organizačních vztahů).
