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 – REGUŁ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.