------------------------------------------
Gazdaságinformatika gyakorlat, 2016-17 ősz
------------------------------------------
------
2. óra
------

- legrövidebb utak (Dijkstra algoritmus)
- szélességi és mélységi keresés
- maximális folyam

1. Feladat

Eyg turistatérképen egy mentőállomásról indulva egy térkép jelzi a turistautakat, melyek csomópontjai különböző hegycsúcsok, völgyek, barlangok, stb. Tervet kell készíteni, hogy turistaút mentén történő baleset esetén mely útvonalakat érdemes használni, ha mentőhelikopter nem áll rendelkezésre.

Megoldás: legrövidebb útak probléma megoldása

2. Feladat:
Egy táblázat megmutatja, hogy egy város öt csomópontja között vezető utaknak mekkora a forgalomáteresztő képessége, azaz időegység alatt a két csomópont között maximálisan hány jármű haladhat át. Ezeket az értékeket csúcsforgalom idején statisztikai elemzéssel határozták meg. A város vezetése katasztrófa tervet dolgoz ki, ezért szeretné megtudni hogy két kitüntetett csomópontok között időegység alatt maximálisan áthaladható járművek számát.

Megoldás:
maximális folyam keresés,
maximális folyam - minimális vágás tétel

Néhány számítógépes lehetőség:
MATLAB: 
http://www.mathworks.com/help/bioinfo/ref/graphshortestpath.html
http://www.mathworks.com/help/bioinfo/ref/graphmaxflow.html