Cesty na neorientovaných grafech
Poznámky16 s. / 3. roč. / doc
CESTY NA NEORIENTOVANÝCH GRAFECHUvaž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 jednotli...
|
|
0,4 |
0x |
|
Přiřazovací problém (PP)
Poznámky23 s. / 3. roč. / docx
Přiřazovací problém (PP)1 Praktické úlohy přiřazováníPři formulaci obecného přiřazovacího problému vyjdeme z úloh praktického charakteru, které vedou na využití metod aplikované matematiky vyvinutých pro jejich řešení.1.1 Úloha o přiřazení pracovníkůVýrobní podnik disponuje m pracovníky, které je nutné přiřadit na m pracovišť. Efektivnost „nasazení“ i. pracovníka na j. tou práci je možné kvantifikovat pomocí koeficientu cij , který vyjadřuje průměrnou úsporu materiálu na jednotku produkce, nebo ...
|
|
0,3 |
1x |
|
Teorie z předmětu Teorie grafů a její aplikace v dopravě
Poznámky7 s. / 3. roč. / doc
1. Definice základních pojmů (graf, vrchol, hrana, stupeň vrcholu, incidence)• Neorientovaný graf - uspořádaná trojice G = (V,X,p) {Vrcholy, X hrany, p incidence}• Incidence - Přiřazení množiny hran na množinu všech neuspořádaných dvojic V• Stupeň vrcholu - Počet hran incidujících s vrcholem• Multigraf - připouští existenci násobných hran.• Prostý graf - Nepřipouští existenci násobných hran• Obyčejný - Nepřipouští existenci násobných hran a smyček• Triviální - Pouze 1 V• Prázdný - V = ; X = • Di...
|
|
0,1 |
2x |
|
Úloha obchodního cestujícího, Littlův algoritmus
Poznámky7 s. / 3. roč. / doc
Littův algoritmus slouží pro nalezení minimálních (maximálních) hamiltonovských kružnic grafu. Název úlohy vychází z toho, že hamiltonovskou kružnici je možné pokládat za cestu obchodního cestujícího, který musí navštívit všechna místa (vrcholy grafu), každé pouze jednou a vrátit se do místa odkud vyšel s tím, že celková projetá vzdálenost (celkový čas strá-vený v dopravním prostředku) bude minimální. Úloha dlouhou dobu odolávala úsilí o její úspěšné řešení. Teprve v roce 1963 Little publikoval ...
|
|
0,3 |
1x |
|
Podgrafy a jejich konstrukce
Poznámky9 s. / 3. roč. / doc
1.1 Kostra grafuKostra grafu G = (V, X) je graf T = (W, Y) | W = V, Y c X, který je stromem. V každém souvislém neorientovaném grafu existuje alespoň jedna kostra. V grafu s n vrcholy má každá kostra právě n-1 hran.V hranově ohodnocených grafech definujeme minimální a maximální kostru grafu. Minimální kostrou souvislého hranově ohodnoceného grafu je kostra, pro kterou je součet ohodnocení hran minimální. Analogicky maximální kostrou grafu je kostra s maximálním součtem ohodnocení hran.
|
|
1,1 |
0x |
|
Lokační úlohy
Poznámky9 s. / 3. roč. / doc
V praxi se setkáváme s řešením úloh, které zařazujeme do skupiny tzv. lokačně-alokačních úloh. Jde například o:a) rozmístění stanovišť vozidel hasičské ochrany,b) rozmístění stanovišť záchranné služby,c) rozmístění pekáren, skladů, apod.,d) rozmístění poštovních úřadů, bankomatů, apod.,e) rozmístění opraven osobních a nákladních automobilů,f) rozmístění čistíren, sběren prádla, apod.,g) rozmístění skládek posypového materiálu pro zimní údržbu cest, apod.
|
|
0,3 |
5x |
|
Fordova metoda výpočtu minimální cesty
Poznámky4 s. / 3. roč. / doc
K výpočtu minimální cesty touto metodou potřebujeme tabulku, která sestává z n+2 sloupců a n+1 řádků (n je počet vrcholů grafu ( )). V tabulce označíme n sloupců označením vrcholů grafu , respektive . Předposlední sloupec označíme W (množina definitivně označených vrcholů grafu), poslední sloupec potom D (vektor definitivního ohodnocení vrcholů grafu ). Složka vektoru definitivního ohodnocení dj odpovídající příslušnému vrcholu určuje délku minimální cesty z počátečního vrcholu do vrcholu . Podl...
|
|
0,3 |
0x |
|
Okružní jízdy
Poznámky9 s. / 3. roč. / doc
V této kapitole bude vysvětlena metoda na řešení okružních jízd. O okružní jízdě hovoříme tehdy, je-li kapacita obslužného vozidla dostatečná na postupnou obsluhu více než jednoho požadavku. Uvažujme úlohu, kdy jistá firma disponuje centrálním skladem hotových výrobků v místě v0 a n pobočnými sklady v1, v2,...,vn. Předpokládejme, že firma disponuje dostatečným počtem nákladních automobilů se stejnou ložnou kapacitou - c. Je známá délka nejkratších cest mezi centrálním skladem v0 a ostatními skla...
|
|
1,0 |
0x |
|
Modely a modelování
Poznámky2 s. / 3. roč. / doc
Představivost a tvůrčí schopnosti umožňují lidským bytostem uvědomění jejich existence v prostředí. Představivost je schopnost tvořit mentální obrazy složitých objektů reálného světa bez nutnosti je přímo pozorovat. Jinými slovy lidské bytosti jsou schopny řešit problémy pomocí budování modelů.
|
|
0,1 |
0x |
|