KCKurzy - Jak udělat zkoušku z EMM 1

46 

Krok 4: Z nevyškrtnutých prvků v prvním sloupci vybereme minimální (v případě shody ten vyšší) 
prvek. Ten označuje místo, které půjde jako další do okružní trasy (Brno). Odpovídající sloupec opět 
zvýrazníme, příslušný řádek vyškrtneme a zvýrazníme příslušný požadavek (13).  

Krok 5: Sečteme všechny zvýrazněné požadavky (14+13) a pro ta místa, kde přičtením jejich 
požadavku s uvedeným součtem bude překročena kapacita 30 t, buňky v daných řádcích 
vyznačeného sloupce škrtneme. Z nevyškrtaných prvků v označeném sloupci bychom opět vybrali 
nejmenší prvek a zařadili do okružní trasy. Vidíme ale, že ve druhém sloupci jsou všechny prvky 
vyškrtnuty – máme první okruh: Praha, Ostrava, Brno.

Krok 6: Ve zbylé části tabulky hledáme opět stejným způsobem místa do dalších okružních tras.  

47 

Krok 7: Vyšel druhý (a poslední) okruh: Praha, Č. Bud, Plzeň, Ústí, Hr. Kr   

Krok 8: V každém ze samostatných okruhů najdu optimální trasu jako u jednookružního dopravního 
problému (metodou nejbližšího souseda, nebo VAM metodou) 

Výsledek: 

1.  okruh: Praha-202-Brno-165-Ostrava-202 -zpět : 569 Km

2.  okruh: Praha-92-Ústí-146-Plzeň-133–Č. Bud–217-Hr. Kr.-112-zpět : 700 Km

48 

9. Optimální propojení míst (Minimální kostra) 

Používá se k nalezení nejkratšího propojení míst např. drahým kabelem. Na rozdíl od předchozího 
okružního problému se nevracíme zpátky a stačí jen místa propojit (graf má tvar stomu – minimální 
kostra v grafu).   

Příklad 1: Máme kabelem propojit 5 vesnic (svítidel na pozemku atd.), aby celková délka kabelu 
byla co nejkratší. 

Řešení:  
Krok 1: Hrany seřadíme pod sebe podle rostoucí délky 
Krok 2: Postupně zařazujeme hrany do minimálního stromu, pokud narazíme na hranu, která by 
uzavřela předčasně okruh (např 24, 13, 12), přeskočíme ji a pokračujeme dále. 
Krok 3: Algoritmus končí, je-li vybráno n-1 hran, kde n je počet „uzlů“