Teória grafov
Z Wikipédie
Teória grafov je časť matematiky, ktorá skúma vlastnosti grafov.
Na rôzne aplikácie sa používajú rôzne typy grafov. Hrany orientovaného grafu majú určenú orientáciu, ktorá sa na obrázkoch väčšinou zobrazuje ako šípka. Niekedy sa v grafoch dovoľujú hrany idúce do vrcholu, v ktorom začali. Niekedy majú hrany grafu priradenú hodnotu (cenu), ktorá označuje napr. dĺžku.
Mnoho praktických problémov možno sformulovať ako problém týkajúci sa určitého grafu. Grafy sa hodia na reprezentáciu rôznych typov sietí, napríklad cestnej siete, počítačovej siete, sústavy vodovodov atď. Algoritmy na riešenie úloh na grafoch sú dôležitou časťou informatiky.
Jeden z prvých výsledkov v teórii grafov bola práca Leonharda Eulera o siedmych mostoch v Kráľovci (dnešný Kaliningrad) z roku 1736. Zaoberal sa otázkou, či existuje taká trasa, ktorá prechádza cez každý z vtedajších siedmych mostov mesta práve raz a vracia sa do začiatočného bodu. Euler sformuloval problém ako graf a dokázal, že takáto trasa existuje iba ak každý vrchol grafu má párny počet hrán (čo nebol prípad Kráľovca).
Na Slovensku (resp. Česko-Slovensku) má teória grafov dlhú tradíciu. Prvú prácu publikoval O. Boruvka už v roku 1926. Popísal v nej metódu ako nájsť najkratšiu elektrovodnú sieť.
