Problem niezawodności sieci


Wyobraźmy sobie, że chcemy zaprojektować sieć komunikacyjną (np. telekomunikacyjną, drogową, komputerową). Składa sie ona z pewnej liczby punktów węzłowych (np. terminali komputerowych) i bezpośrednich połączen (linii) między niektórymi z nich.

Jak przedstawić sieć komunikacyjną przy pomocy grafu ? Sieć taką możemy przedstawić za pomocą grafu, którego wierzchołki odpowiadają punktom węzłowym a krawędź miedzy dwoma wierzchołkami oznacza bezpośrednie połaczenie linią danych dwóch punktów węzłowych. Oto przykładowa sieć składająca się z 6 punktów węzłowych oznaczonych literami A,B,C,D,E,F i pewnych krawędzi między nimi

Wiemy, że nic nie jest doskonałe i sieć narażona jest na awarie. Spójność wierzchołkowa takiego grafu jest równa minimalnej liczbie awarii w punktach węzłowych sieci, które spowodują awarię całej sieci (to znaczy między niektórymi węzłami zostanie zerwane połączenie). Natomiast spójność krawędziowa oznacza minimalną liczbę awarii łączy między węzłami, które spowodują awarię sieci. Przez niezawodność sieci możemy rozumieć maksymalną liczbę awarii, których wystąpienie nie spowoduje awarii całej sieci.

Im większa spójność grafu tym większa niezawodność sieci Jak skonstruować sieć by jej niezawodność byla możliwie największa? Oczywiście im więcej linii (krawędzi) tym niezawodność większa. Z drugiej jednak strony zbudowanie każdego połączenia kosztuje. Możemy założyć, że szukamy możliwie najtanszej sieci o z góry założonej niezawodności, bądź szukamy sieci o ustalonym koszcie i możliwie największej niezawodności. Jedno z możliwych sformułowan tego problemu wygląda następująco:

Sformułowanie problemu.
Załóżmy, że dana jest liczba punktów węzłowych oraz żądana niezawodność sieci k (liczba 'dopuszczalnych' awarii). Zbudowanie każdego bezpośredniego połączenia obarczone jest pewnym kosztem jednostkowym (jest to pewne uproszczenie - w rzeczywistości koszty budowy połączen są różne). Chcemy zaprojektować sieć o żądanej niezawodności, której koszt budowy będzie możliwie najmniejszy.Poszukujemy więc grafu o n wierzchołkach i możliwie najmniejszej liczbie krawędzi, którego
spójność wierzchołkowa lub spójność krawędziowa wynosi k.

[ Początek strony ] [ MiNIWykłady ]

Wszystkie prawa zastrzeżone © 2000 Wydział Matematyki i Nauk Informacyjnych Politechniki Warszawskiej