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.