ZARZ
DZANIE PROJEKTAMI
Prowadzący: Dorota Górecka
Katedra Ekonometrii i Statystyki
WNEiZ UMK
PROGRAMOWANIE SIECIOWE
" Wiele problemów zarządzania, związanych m.in. z optymalizacją
systemów transportowych, projektowaniem systemów
informatycznych, czy te\
pewnymi zagadnieniami logistycznymi,
mo\
na przedstawić jako zagadnienia sieciowe i rozwiązać za
pomocą odpowiednich metod.
" Jedną z takich metod jest algorytm znajdowania minimalnego
" Jedną z takich metod jest algorytm znajdowania minimalnego
drzewa rozpinającego.
" Drzewo rozpinające w grafie liczącym n wierzchołków to zbiór
n-1 jego krawędzi, takich, \
e dowolne dwa wierzchołki grafu
mo\
na połączyć za pomocą krawędzi nale\
ących do tego zbioru.
" Minimalne drzewo rozpinające to drzewo wybrane spośród
wszystkich istniejących drzew rozpinających, dla którego łączna
długość krawędzi jest najmniejsza.
MDR  REGUA
Y POST
POWANIA
" Iteracja 1
Wybieramy w sposób arbitralny dowolny wierzchołek i łączymy go
z wierzchołkiem le\
ącym najbli\
ej.
" Iteracja k (k=2, 3,& , n-1)
W konstruowanym drzewie znajduje się ju\
k wierzchołków oraz
k-1 łączących je krawędzi.
k-1 łączących je krawędzi.
Wierzchołki te nazywamy wierzchołkami połączonymi, pozostałe
tworzą zbiór wierzchołków niepołączonych.
Identyfikujemy najbli\
szy zbiorowi wierzchołków połączonych
wierzchołek niepołączony i dołączamy go do zbioru wierzchołków
połączonych. Jeśli krawędzi o najmniejszej długości jest kilka, to
arbitralnie wybieramy jedną z nich.
Krok ten wykonujemy tak długo, a\
do zbioru wierzchołków
połączonych dołączymy ostatni wierzchołek niepołączony.
BIBLIOGRAFIA
1. Trzaskalik T., Wprowadzenie do badań operacyjnych
1. Trzaskalik T., Wprowadzenie do badań operacyjnych
z komputerem, PWE, Warszawa 2008, ss. 366-368.