Teorie-emm ke zkoušce

částečně orientovaný graf

• graf, který obsahuje orientované i neorientované hrany zároveň

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

SLED = posloupnost uzlů a hran, která spojuje dva vybrané uzly

TAH = sled, který nepoužívá žádnou hranu více než jednou

CESTA = tah, který nepoužívá žádný uzel více než jednou

CYKLUS = 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.

grafy můžeme prohledávat!!!

= systematické, ale mechanické prohledávání pomocí předem daného algoritmu, který nepožaduje jako vstup žádnou dodatečnou informaci

• typickými zástupci je prohledávání do hloubky nebo do šířky (jdeme tak dlouho do hloubky či šířky dokud to jde a pak teprve přecházíme na další větev)

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.

= snaží se prohledat graf nejen systematicky, ale i s ohledem na zadaný cíl a k tomu používají tzv. hodnotící funkci, která určuje kvalitu prohledávaného směru právě vzhledem k hledanému cílovému stavu

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

• dva základní přístupy

  • gradientní algoritmus - prosté řazení uzlů v zásobníku podle f = nejprve bere ty které jsou nejvýhodnější

  • paprskové prohledávání - hladiny uzlů, vždy zařazujeme pouze několik nejperspektivnějších – používá se v případě rozsáhlejších grafů

• další

  • Dijstrův algoritmus – u hledání nejkratší cesty

  • algoritmus A – pracuje s modifikovanou hodnotící funkcí f, která se spočítá: F= g + h > problém: obvykle hodnoty těchto funkcí neznáme > nahrazení odhady

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

• kostra: souvislý graf s minimálním počtem hran

• princip: přidáváme hrany podle ohodnocení tak, aby netvořily kružnici (obvod, cyklus)

př.: minimální délky větví síťového propojení počítačů

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

= nalezení nejkratší cesty mezi dvěma místy

• 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

  • algoritmus končí, jakmile se dostaneme do cílového místa.

př.: síť cest, některé cesty nemusí existovat

7) Charakterizujte úlohu o hledání maximálního toku v síti, stručně popište princip jejího řešení.

• proputnost produktovodů (ropovodů), elektrické distribuční sítě

Ford Fulkersonova věta (algoritmus) = maximální tok v síti je roven jejímu minimálnímu řezu