Hledej
Zobraz:
Univerzity
Kategorie
Rozšířené vyhledávání
12 659 projektů
0 nových
Cesty na neorientovaných grafech
«»
| Přípona .doc |
Typ poznámky |
Stažené 0 x |
| Velikost 0,4 MB |
Jazyk český |
ID projektu 6922 |
| Poslední úprava 09.11.2015 |
Zobrazeno 1 361 x |
Autor: blackmagic |
Sdílej na Facebooku |
||
| Detaily projektu | ||
- Cena:
2 Kreditů - kvalita:
89,5% -
Stáhni
- Přidej na srovnání
- Univerzita:České vysoké učení technické v Praze
- Fakulta:Fakulta dopravní
- Kategorie:Technika » Doprava a spoje
- Předmět:Teorie grafů a její aplikace v dopravě
- Studijní obor:-
- Ročník:3. ročník
- Formát:MS Office Word (.doc)
- Rozsah A4:16 stran
CESTY NA NEORIENTOVANÝCH GRAFECH
Uvažujme neorientovaný, souvislý, hranově ohodnocený,1) obyčejný graf, reprezentující schématické znázornění (model) silniční, železniční, letecké, vodní, potrubní, pásové nebo jiné dopravní sítě. Důležitou skupinou úloh řešených teorií grafů jsou úlohy o významných cestách na grafech. Mezi tyto úlohy patří zejména úlohy nalezení:
• nejkratší (minimální) cesty,
• nejspolehlivější cesty,
• cesty s maximální kapacitou.
Dříve než se budeme zabývat terminologií a jednotlivými algoritmy pro určení výše jmenovaných významných cest na grafech, připomeneme legendu z řecké mytologie, pojed-návající o bájném Theseovi a jeho favoritce Ariadné, kterou měl Theseus zachránit před ne-tvorem Minotaurem nacházejícím se v labyrintu na ostrově Kréta. Slovně popíšeme algoritmus, který byl na řešení úkolu Thesea vymyšlen.
Uvažujme neorientovaný, souvislý, hranově ohodnocený,1) obyčejný graf, reprezentující schématické znázornění (model) silniční, železniční, letecké, vodní, potrubní, pásové nebo jiné dopravní sítě. Důležitou skupinou úloh řešených teorií grafů jsou úlohy o významných cestách na grafech. Mezi tyto úlohy patří zejména úlohy nalezení:
• nejkratší (minimální) cesty,
• nejspolehlivější cesty,
• cesty s maximální kapacitou.
Dříve než se budeme zabývat terminologií a jednotlivými algoritmy pro určení výše jmenovaných významných cest na grafech, připomeneme legendu z řecké mytologie, pojed-návající o bájném Theseovi a jeho favoritce Ariadné, kterou měl Theseus zachránit před ne-tvorem Minotaurem nacházejícím se v labyrintu na ostrově Kréta. Slovně popíšeme algoritmus, který byl na řešení úkolu Thesea vymyšlen.
Klíčová slova:
neorientované grafy
namotávání nití
algoritmus
neohodnocený graf
spolehlivé cesty
Obsah:
- 2 CESTY NA NEORIENTOVANÝCH GRAFECH
2.1 Labyrint
2.1.1 Algoritmus rozmotávání niti
2.1.2 Algoritmus při namotávání niti
2.2 Nejkratší (minimální) cesta
2.2.1 Algoritmus nalezení minimální cesty v hranově ohodnoceném grafu
2.2.2 Určení minimální cesty v hranově neohodnoceném grafu
2.3 Nespolehlivější cesta v grafu
2.3.1 Algoritmus vyhledání nejspolehlivější cesty
2.4 Algoritmus na určení matice vzdáleností (distanční matice)
2.5 Cesta s maximální kapacitou
2.5.1 Algoritmus určení cesty s maximální kapacitou