EMM_I_dlya_ustnoy

b) Neorientovaný graf

- máli všechny hrany neorientované

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

- G=({A, B, C, D, E}, {(A,B), (D,A), (B,D), (B,C), (B,E), (C,D)}

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.

Metody neinformovaného prohledávání – tzv. „slepé“

- systematické, ale mechanické prohledávání;

- prohledávání do hloubky (nejdříve se expanduje uzel s maximální hloubkou) nebo do šířky (nejdříve se expanduje uzel s minimální hloubkou)

- nemají k dispozici žádné vhodné znalosti o stavovém prostoru, které by jim umožnily urychlit cestu k cíli. Jsou tak odsouzeny k systematickému procházení všech uzlů, dokud nenaleznou řešení. Jednotlivé algoritmy se od sebe liší jen způsobem, jakým toto systematické procházení provádějí.

1. Popište princip informovaného prohledávání grafů. Uveďte a stručně popište vybranou metodu informovaného prohledávání grafu.

- dána nezáporná hodnotící funkce f

- gradientní algoritmus - prosté řazení uzlů v zásobníku podle f

- paprskové prohledávání - hladiny uzlů, vždy zařazujeme k nejperspektivnějích

- dle charakteru úlohy je v nich možné definovat hodnotící funkci f, která pro každý uzel stromu řešení určí jeho ohodnocení

• Dijkstrův algoritmus

- Nalezení nejkratší cesty mezi dvěma místy

- Síť cest (Síť je graf, který je souvislý; orientovaný; acyklický; orientovaný;má jeden počáteční a jeden koncový uzel)

- Některé cesty nemusí existovat

Postup řešení

- Vypočteme délku tras od počátku do všech uzlů, do nichž se lze dostat z uzlu aktuálního

- Přesuneme se do uzlu, který je nejblíže počátku a v němž jsme ještě nebyli a pokračujeme stejně

- Algoritmus končí, jakmile se dostaneme do cílového místa

1. Charakterizujte úlohu o hledání minimální kostry grafu, stručně popište princip jejího řešení.

- neorientovaný, souvislý, konečný a hranově ohodnocený graf

- cílem je najít kostru s minimálním součtem ohodnocení hran

- řeší např. Kruskalův algoritmus

Postup

- připojujeme hrany od nejmenších, vezmem vždy tu nejmenší hranu a zapracujeme ji do řešení, ale nesmí vzniknout cyklus (križnice), hrany které by tvořili cyklus do řešení nezahrnujeme

- celkovou délku kostry zjistíme tak, že sečteme ohodnocení hran, které jsou zahrnuty v řešení

1. Charakterizujte úlohu o hledání nejkratší cesty v grafu, stručně popište princip jejího řešení.