From Wikipedia, the free encyclopedia
Teória grafov je časť diskrétnej matematiky, ktorá skúma vlastnosti grafov.
Na rôzne aplikácie sa používajú rôzne typy grafov:
Niekedy sa v grafoch dovoľujú hrany idúce do vrcholu, v ktorom začali.
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ď. Algoritmy na riešenie úloh na grafoch sú dôležitou časťou informatiky.
Jedným z prvých výsledkov v teórii grafov bola práca Leonharda Eulera o siedmich 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 siedmich 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 (cesta v grafe) existuje, iba ak každý vrchol grafu má párny počet hrán (čo nebol prípad Kráľovca).
Na Slovensku (resp. aj v Česko-Slovensku) má výskum v oblasti teórie grafov dlhú tradíciu.[1][2] Prvú prácu publikoval Otakar Borůvka už v roku 1926. Popísal v nej metódu, ako nájsť najkratšiu elektrovodnú sieť.
Medzi významnejších slovenských matematikov a teoretických informatikov, ktorí sa teórii grafov venovali alebo venujú, patria napr. Juraj Bosák, Mirko Horňák, Anton Kotzig, Roman Nedela, Ján Plesník, Alexander Rosa, Jozef Širáň, Martin Škoviera alebo Štefan Znám.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.