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.