Teorie-emm ke žkoušce EMM
Níže je uveden pouze náhled materiálu. Kliknutím na tlačítko 'Stáhnout soubor' stáhnete kompletní formátovaný materiál ve formátu PDF.
vybrat uzel (místo)nejvzdálenější od centra z dosud nezařazených a tím založit okruh
vybrat k tomuto uzlu nejbližší nezařazené místo a přidat ho do okruhu
přidávat další místa, která jsou nejblíže jakémukoliv místu právě tvořeného okruhu, dokud stačí
kapacita vozidla
založit nový okruh - zpět k bodu 1
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 - matematická struktura, která zobrazuje vzájemné vztahy mezi objekty z dané množiny
orientovaný graf = uspořádaná dvojice G=(V, A)
-
V = množina vrcholů (uzlů)
-
A = množina hran (spojnic mezi vrcholy)
-
hrana je určena uspořádanou dvojicí vrcholů
neorientovaný graf – neuspořádaná dvojice G(V, E)
-
V = množina vrcholů (uzlů)
-
E = množina hran (spojnic mezi vrcholy)
-
hrana je určena neuspořádanou dvojicí vrcholů
2) Charakterizujte a odlište pojmy "sled", "tah", "cesta" a "cyklus" v teorii grafů.
Sled je posloupnost uzlů a hran, která spojuje dva vybrané uzly
Tah je sled, který nepoužívá žádnou hranu více než jednou
Cesta je tah, který nepoužívá žádný uzel více než jednou
Cyklus je cesta, která začíná a končí ve stejném uzlu
3) Popište princip neinformovaného prohledávání grafů. Uveďte a stručně popište
vybranou metodu neinformovaného prohledávání grafu. - systematické, ale mechanické prohledávání
- prohledávání do hloubky nebo do šířky
4) Popište princip informovaného prohledávání grafů. Uveďte a stručně popište
vybranou metodu informovaného prohledávání grafu.