392 393

392 Programowanie sieciowe

Korzystając z tablicy 8.7, znajdujemy wykorzystywane do przepływu odcinki rurociągu i wielkość przepływu. Otrzymane wyniki zawiera tablica 8.8.

Tablica 8.8

Odcinek	Przepływ
1-2	50
1-3	40
1-4	30
2-3	30
2-5	50
3-2	30
3-5	20
3-6	10
3-7	10
4-3	20
4-7	30
5-6	30
5-8	40
6-8	40
7-8	40

Uwzględniając możliwość awarii odcinka 2-3, modyfikujemy sieć, wyłączając z niej to połączenie, i ponownie rozwiązujemy zadanie dla zmodyfikowanej sieci. Maksymalny przepływ osiąga ponownie wielkość 120 tys. nr³ gorącej wody. Przepływ ten osiągamy zgodnie z planem podanym w tablicy 8.9.

Tablica 8.9

Droga	Wielkość przepływu
1-2-5-8	40
I-2-5-6-8	10
1-3—4—7—8	20
1-3—5-6-8	20
I-4-3-6-8	10
00 1 r- 1 m 1 ■sf	10
1 -U 1 i 00	10

8.5.3. Optymalizacja przebiegu linii światłowodowej

Przykład 8.6

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, naw'et jeśli oznaczałoby to, że nie wszystkie budynki są ze sobą bezpośrednio połączone. Tablica 8.10 zawiera informacje dotyczące kosztów budowy linii między poszczególnymi budynkami. Ponadto ze względu na topografię terenu niektóre połączenia są niemożliwe (w tablicy 8.10 jest to zaznaczone jako -).

Tablica 8.10

Koszty budowy połączeń		i	2	3	4	5	6	7	8	9	10
		Rektorat	Budynek A	Budynek B	Budynek C	Budynek D	Budynek E	Budynek F	Biblioteka	1 Akademik ]	Akademik źj
i	Rektorat	X	8	7	9	—	18	—	—	—	—
2	Budynek A	8	X	7	8	—	—	—	—	5	—
3	Budynek B	7	7	X	8	7	12	10	16	—	—
4	Budynek C	9	8	8	X	18	—	—	—	9	—
5	Budynek D	—	—	7	18	X	15	9	—	15	—
6	Budynek E	18	—	12	—	15	X	6	14	—	—
7	Budynek F	—	—	10	—	9	6	X	12	14	20
8	Biblioteka	_	—	16	—	—	14	12	X	5	—
9	Akademik 1	—	5	—	9	15	—	14	5	X	5
10	Akademik 2	—	—	—	—	-	—	20	—	5	X

Należy zaprojektować sieć powiązań światłowodowych minimalizujących koszty budowy tuneli i umożliwiających przesyłanie informacji między dowolnymi budynkami uczelni oraz znaleźć całkow-ity koszt budowy takiego systemu.

Rozwiązanie

Konstrukcja sieci

Zadanie można rozwiązać, korzystając z algorytmu minimalnego drzewa rozpinającego. Mamy 10 węzłów i 24 krawędzie. Numery węzłów' odpowiadają