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

- motivációk
- követelmények
- gráfelméleti alapfogalmak, fák, minimális súlyú feszítőfa: Prim- és Kruskal algoritmusa

Feladat:

Egy ipari telephelyen belső áramellátó rendszert terveznek, mely egy központi ellátóból látja el a telep összes épületét. Nem szükséges, hogy az egyes épületek közvetlenül legyenek összekötve a központtal, elég ha közvetetten, más éplületen keresztül vannak bekötve, de minden épületnek kell biztosítani áramellátást. A kiépítés költsége arányos távolsággal. A telephelyen az egyes távolságokat egy táblázat tartalmazza (ld. órai példa).
A cél a lehető legkisebb költségen kiépíteni a rendszert.

Megoldás:

A problémát egy súlyozott gráffal reprezentálhatjuk, ahol a gráf pontjai az épületek és a központ, bármely két pont össze van kötve és az él súlya a távolság. Konstruáljuk meg a gráf minimális feszítőfáját.

Néhány számítógépes lehetőség:

WinQSB (network modelling eszöztár; ingyenes program GUI-val)
MATLAB: Prim algoritmus (https://www.math.washington.edu/~greenbau/Math_381/programs/prim.m)
Kruskal algoritmus (http://www.mathworks.com/matlabcentral/fileexchange/41963-kruskal-s-algorithm/content/kruskal.m)