Teoria Grafów w Sieciach

Graf jako model sieci

Sieć telekomunikacyjną można przedstawić jako zbiór punktów połączonych relacjami. Teoria grafów dostarcza formalnych pojęć i narzędzi do opisywania, analizowania oraz optymalizacji takich sieci. Reprezentacja grafowa pozwala stosować zasady matematyczne do problemów związanych z routingiem, niezawodnością i wydajnością.

Elementy grafu

Każdy graf sieciowy składa się z dwóch podstawowych komponentów:

Wierzchołek (ang. vertex lub node): Punkt w sieci. Może reprezentować komputer, router, przełącznik lub centralę telefoniczną.
Krawędź (ang. edge lub link): Połączenie między dwoma wierzchołkami. Reprezentuje fizyczne łącze komunikacyjne, takie jak kabel światłowodowy, przewód miedziany lub połączenie bezprzewodowe.

Grafy mogą być (jeśli ruch płynie tylko w jedną stronę) lub (jeśli ruch może płynąć w obu kierunkach).

Właściwości grafów i charakterystyka sieci

Analiza właściwości grafu opisuje strukturę i wybrane cechy reprezentowanej sieci.

Stopień grafu

W grafie nieskierowanym wierzchołka określa liczbę jego bezpośrednich połączeń. Minimalny ( $\delta(G)$ ) i maksymalny ( $\Delta(G)$ ) stopień wskazują odpowiednio na najsłabiej i najlepiej połączone węzły sieci. Wartości te pomagają wskazać potencjalne wąskie gardła oraz pojedyncze punkty awarii.

Specjalne typy grafów

Graf regularny: Graf, w którym każdy wierzchołek ma ten sam stopień. Reprezentuje sieć o zrównoważonej i przewidywalnej strukturze. Graf 3-regularny nazywany jest grafem kubicznym.
Graf pełny ( $K_n$ ): Graf, w którym każda para wierzchołków jest połączona krawędzią. Reprezentuje w pełni połączoną sieć o wysokiej redundancji. Liczba wymaganych krawędzi wynosi $\frac{n(n-1)}{2}$ , dlatego dla dużych $n$ takie połączenie jest kosztowne.
Graf planarny: Graf, który można narysować na płaszczyźnie bez przecinania się krawędzi. Pojęcie to ma znaczenie w projektowaniu fizycznego układu obwodów i niektórych diagramów sieciowych. Każdy graf pełny $K_n$ dla $n \ge 5$ jest nieplanarny.

Ścieżki i odporność sieci

Sieć potrzebuje ścieżek, którymi dane mogą dotrzeć od źródła do celu. Liczba i rodzaj dostępnych ścieżek wpływają na odporność sieci na awarie.

Ścieżki krawędziowo rozłączne: Są to co najmniej dwie ścieżki między tymi samymi węzłami początkowym i końcowym, które nie współdzielą krawędzi ani łączy. Dwie takie ścieżki pozwalają zachować połączenie między końcami po awarii pojedynczego łącza, na przykład po przecięciu kabla.
Ścieżki węzłowo rozłączne: Są to ścieżki, które współdzielą tylko węzeł początkowy i końcowy, bez wspólnych węzłów pośrednich ani łączy. Dwie takie ścieżki pozwalają zachować połączenie po awarii jednego węzła pośredniego, na przykład routera.
Spójność grafu: Jest to miara odporności sieci. ( $\kappa'(G)$ ) to minimalna liczba łączy, których usunięcie rozspójnia graf. ( $\kappa(G)$ ) to minimalna liczba węzłów, których usunięcie rozspójnia graf. Dla spójnego grafu nieskierowanego wartości te spełniają nierówność: $\kappa(G) \leq \kappa'(G) \leq \delta(G)$ .

Klasyczne problemy grafowe w sieciach

Wiele zadań projektowania sieci odpowiada problemom znanym z teorii grafów.

Minimalne drzewo rozpinające (MST): Celem jest znalezienie podzbioru krawędzi, który łączy wszystkie wierzchołki w spójnym , bez tworzenia cykli i z minimalną możliwą sumą wag krawędzi.
Ma to zastosowanie w projektowaniu sieci szkieletowej łączącej miasta lub centra danych przy najmniejszej sumie wag krawędzi. Do znajdowania MST stosuje się między innymi algorytmy Prima i Kruskala.
Problem komiwojażera (TSP) i cykl Hamiltona: TSP polega na znalezieniu najkrótszej trasy w grafie ważonym, która odwiedza każdy wierzchołek dokładnie raz i wraca do punktu początkowego. W projektowaniu sieci, zwłaszcza pierścieniowych i siatkowych, taka zamknięta trasa jest .
Problem ten pojawia się w projektowaniu topologii sieci, szczególnie w sieciach pierścieniowych, gdzie celem jest połączenie wszystkich węzłów w pętlę przy minimalnej całkowitej długości kabla.