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.