Vypracovane-zkouskove-otazky - teorie

Princip metody nejbližšího souseda:

1. Stanovit výchozí místo pro tvorbu okruhu

2. Přejít k místu, které je nejbližší aktuálnímu místu (nesmí se do výchozího ani tam, kde už jsme byli)

3. Postup opakovat tak dlouho, dokud se nevrátíme do výchozího místa

4. Prověřit všechna místa jako výchozí

6) Popište modifikaci Vogelovy aproximační metody pro řešení okružních dopravních problémů.

Pomocí modifikované VAM určíme nejvýhodnější pořadí míst v daném okruhu.

Princip modifikované VAM:

1. Výpočet diferencí mezi dvěma nejvýhodnějšími trasami v každém řádku i sloupci úlohy

2. Výběr řady/sloupce s maximální diferencí

3. Výběr nejvýhodnější trasy(nejnižší vzdálenosti) z této řady a její zařazení do okruhu

4. Aktualizace náčrtku

5. Zákaz všech tras, které již není možno použít(=> vyškrtnout řádek i sloupec dané trasy + cestu zpět)

6. Návrat k bodu 1

7) Kde a k čemu se používá Mayerova metoda? Stručně popište její princip.

Mayerova metoda se používá u více-okruhového trasovacího problému, kdy je úloha nejčastěji rozšířena o kapacitní podmínky. Nevyřeší problém úplně, pouze rozdělí místa do jednotlivých okruhů, s ohledem na minimalizaci celkových nákladů na přepravu.

Algoritmus Mayerovy metody:

1. Vybrat uzel (místo)nejvzdálenější od centra z dosud nezařazených a tím založit okruh

2. Vybrat k tomuto uzlu nejbližší nezařazené místo a přidej ho do okruhu

3. Přidávat další místa, která jsou nejblíže jakémukoliv místu právě tvořeného okruhu, dokud stačí kapacita vozidla

4. Založit nový okruh - zpět k bodu 1.

Pořadí míst v okruzích lze stanovit např. metodou VAM.

Téma 11: Modely teorie grafů
1) Co rozumíme termínem "graf" v teorii grafů? Jaký je rozdíl mezi orientovaným a neorientovaným grafem?

Graf = množina, která se skládá z bodů a jejich spojnic. Body se nazývají uzly a jejich spojnice hrany. Uzly se označují symboly u1, u2..un a hrany, které spojují uzel ui s uzlem uj, symbolem (i,j).

Graf je matematická struktura, která zobrazuje vzájemné vztahy mezi objekty z dané množiny

Orientovaný graf = hranám grafu lze přisuzovat určitý směr, který vyznačujeme šipkou.

• Orientovaný graf je uspořádaná dvojice

G = (V, A)

• V je množina vrcholů

• A je množina hran (spojnic mezi vrcholy)

• Hrana je určena uspořádanou dvojicí vrcholů

Neorientovaný graf = nemá šipky

• Neorientovaný graf je uspořádaná dvojice

G = (V,E)

• V je množina vrcholů

• E je množina hran (spojnic mezi vrcholy)

• Hrana je určena neuspořádanou dvojicí vrcholů

1. Charakterizujte a odlište pojmy "sled", "tah", "cesta" a "cyklus" v teorii grafů.

2. Sled je posloupnost uzlů a hran, která spojuje dva vybrané uzly

3. Tah je sled, který nepoužívá žádnou hranu více než jednou

4. Cesta je tah, který nepoužívá žádný uzel více než jednou

5. Cyklus je cesta, která začíná a končí ve stejném uzlu