Teória grafov - Biblioteka.sk

Upozornenie: Prezeranie týchto stránok je určené len pre návštevníkov nad 18 rokov!
Zásady ochrany osobných údajov.
Používaním tohto webu súhlasíte s uchovávaním cookies, ktoré slúžia na poskytovanie služieb, nastavenie reklám a analýzu návštevnosti. OK, súhlasím


Panta Rhei Doprava Zadarmo
...
...


A | B | C | D | E | F | G | H | CH | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Teória grafov

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:

  • orientovaný graf: hrany grafu majú určenú orientáciu, ktorá sa na obrázkoch väčšinou zobrazuje ako šípka.
  • neorientovaný graf: hrany grafu nie sú orientované, respektíve všetky hrany sú orientované oboma smermi.
  • ohodnotený graf: hrany grafu majú priradenú hodnotu (cenu), ktorá označuje napr. dĺžku, priepustnosť, rýchlosť...

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 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 Otakar Borůvka už v roku 1926. Popísal v nej metódu, ako nájsť najkratšiu elektrovodnú sieť.

Iné projekty

Zdroj:
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.
Zdroj: Wikipedia.org - čítajte viac o Teória grafov





Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok.
Podrobnejšie informácie nájdete na stránke Podmienky použitia.

Your browser doesn’t support the object tag.

www.astronomia.sk | www.biologia.sk | www.botanika.sk | www.dejiny.sk | www.economy.sk | www.elektrotechnika.sk | www.estetika.sk | www.farmakologia.sk | www.filozofia.sk | Fyzika | www.futurologia.sk | www.genetika.sk | www.chemia.sk | www.lingvistika.sk | www.politologia.sk | www.psychologia.sk | www.sexuologia.sk | www.sociologia.sk | www.veda.sk I www.zoologia.sk