PROGRAMOWANIE SIECIOWE 

 
 
 
Minimalne drzewo rozpinające 
 
 

Zadanie 1 

WyŜsza  uczelnia  planuje  wyposaŜenie  ośrodka  akademickiego  w  sieć  komputerową.  W  tym 

celu  konieczne  jest  połączenie  budynków  liniami  światłowodowymi.  PoniewaŜ  koszt 

załoŜenia  linii  jest  bardzo  wysoki,  uczelnia  chce  zaprojektować  taką  sieć  połączeń,  która 

łączyłaby  wszystkie  budynki  przy  jak  najmniejszym  koszcie,  nawet  jeśli  oznaczałoby  to,  Ŝe 

nie wszystkie budynki są ze sobą bezpośrednio połączone.  

Na  podstawie  zamieszczonego  poniŜej  grafu,  którego  krawędzie  odpowiadają  tym 

połączeniom,  które  mogą  zostać  zrealizowane  (wartość  parametru  opisującego  kaŜdą  

z  krawędzi  oznacza  koszt  realizacji  danego  połączenia),  zaprojektuj  sieć  powiązań 

ś

wiatłowodowych  minimalizujących  koszty  budowy  tuneli  i  umoŜliwiających  przesyłanie 

informacji  między  dowolnymi  budynkami  uczelni.  Znajdź  całkowity  koszt  budowy  takiego 

systemu. 

 

 

 

 
 
 
 
 

Zadanie 2 

Na  podstawie  zamieszczonego  poniŜej  grafu  zaprojektuj  sieć  dróg  o  minimalnej  długości 

łączącą 6 miast. Wyznacz jej całkowitą długość. Wartości parametrów opisujących krawędzie 

oznaczają odległości w kilometrach. 

 

 

Zadanie 3 

Na  podstawie  zamieszczonego  poniŜej  grafu  zaprojektuj  sieć  wodociągową  o  minimalnej 

długości  łączącą  8  domów  i  pozwalającą  na  dostarczanie  do  nich  wody.    Wyznacz  jej 

całkowitą  długość.  Wartości  parametrów  opisujących  krawędzie  oznaczają  odległości  

w setkach stóp. 

 

Zadanie 4 

Określ  minimalne  drzewo  rozpinające  dla  sieci  przedstawionej  na  rysunku  zamieszczonym 

poniŜej. 

 

 

 
 

Zadanie 5 

Określ  minimalne  drzewo  rozpinające  dla  sieci  przedstawionej  na  rysunku  zamieszczonym 

poniŜej. 

 

 

 

Zadanie 6 

Na  podstawie  zamieszczonego  poniŜej  grafu  zaprojektuj  sieć  dróg  o  minimalnej  długości 

łączącą  9  miast  w  Wielkiej  Brytanii.  Wyznacz  jej  całkowitą  długość.  Wartości  parametrów 

opisujących krawędzie oznaczają odległości w kilometrach. 

 

 

Zadanie 7 

Na  podstawie  zamieszczonego  poniŜej  grafu  zaprojektuj  sieć  dróg  o  minimalnej  długości 

łączącą  miasta  w  USA.  Wyznacz  jej  całkowitą  długość.  Wartości  parametrów  opisujących 

krawędzie oznaczają odległości w kilometrach.