Teória grafov: Rozdiel medzi revíziami
Smazaný obsah Přidaný obsah
d wiki |
d , |
||
Riadok 10:
Mnoho praktických problémov možno preformulovať na problémy týkajúce sa určitej triedy grafov. Grafy sa hodia na reprezentáciu rôznych typov sietí, napríklad cestnej siete, počítačovej siete, sústavy vodovodov atď. [[Algoritmus|Algoritmy]] na riešenie úloh na grafoch sú dôležitou časťou [[informatika|informatiky]].
Jedným z prvých výsledkov v teórii grafov bola práca [[Leonhard Euler|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 [[Slovensko|Slovensku]] (resp. [[Česko-Slovensko|Česko-Slovensku]]) má teória grafov dlhú tradíciu. Prvú prácu publikoval [[Otakar Borůvka]] už v roku [[1926]]. Popísal v nej metódu ako nájsť najkratšiu elektrovodnú sieť.
|