Reprezentacja sieci w formie graficznej ma swoje matematyczne podstawy w teorii grafów. W teorii grafów terminami określającymi węzeł jest wierzchołek, a łącze jest łukiem (rys. 1). Topologia sieci jest, więc zbiorem łączy, które łączą węzły (elementy sieciowe).

Rys. 1 Model sieci według teorii grafów.

Drzewo jest specyficznym przykładem grafu sieciowego. Jest ono grafem bez żadnych cykli, który ma dokładnie N-1 łączy, gdzie N jest liczbą węzłów w grafie. Drzewo grafu jest wykorzystywane w protokole Spanning Tree (rys. 2), w sieciach Ethernet. Mówimy, że graf jest drzewem, jeśli zawiera zbiór węzłów i łączy, które spełniają następujące warunki:

- jeden węzeł jest desygnowany jako korzeń (ang. root),

- pozostałe węzły mogą być podzielone na pewną liczbę rozłącznych zbiorów grafów poddrzew, a każde takie poddrzewo jest połączone dokładnie jednym łączem z korzeniem (ang. root).

Rys. 2 Spanning Tree dla grafu z rysunku 1.

Drzewo jest więc pozbawione wszelkich cykli i ma unikalną ścieżkę od roota do każdego węzła. Na rys. 2 węzeł N1 jest korzeniem, węzły N5, N6, N7 są liśćmi, a węzły N3, N4 gałęziami.

Teoria grafów jest szeroko wykorzystywana do określania najkrótszych ścieżek w sieci od węzła początkowego do końcowego. Takim przykładem są protokoły routingu oparte o algorytm Shortest Path First. Największym problemem w implementacjach algorytmów opartych o najkrótszą ścieżkę jest wybór miejsca, gdzie ma być skalkulowana ta ścieżka oraz czy ma być to implementacja scentralizowana czy rozproszona. Algorytmy scentralizowane są łatwiejsze do analizowania, gdyż podstawową przesłanką do ich działania jest to, że znana jest ogólna dostępność topologii sieci i jej stanu. W algorytmach rozproszonych wydajność jest wtedy optymalna, gdy jej scentralizowane odpowiedniki są w stanie stabilnym. Główną zaś różnicą jest podejście do problemu, jak różne algorytmy rozproszone reagują na zmiany w topologii sieci.