Poznámky: Cesty na neorientovaných grafech
Skrýt detaily | Oblíbený- Kvalita:89,5 %
- Typ:Poznámky
- Univerzita:České vysoké učení technické v Praze
- Fakulta:Fakulta dopravní
- Kategorie:Technika
- Podkategorie:Doprava a spoje
- Předmět:Teorie grafů a její aplikace v dopravě
- Autor:blackmagic
- Ročník:3. ročník
- Rozsah A4:16 strán
- Zobrazeno:1 358 x
- Stažené:0 x
- Velikost:0,4 MB
- Formát a přípona:MS Office Word (.doc)
- Jazyk:český
- ID projektu:6922
- Poslední úprava:09.11.2015
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.