Podręcznik

 Graf jest spójny jeżeli dla dowolnej pary wierzchołów grafu istnieje ścieżka je łącząca (z pominięciem skierowania łuków).

 Graf ważony jest to graf, a którym do łuków zostały przypisane pewne wagi $w_e, e \in E$.

Powyższe wagi mogą mieć charakter kosztu związanego z przepływem daną krawędzią, przy czym koszt należy rozumieć tu w sposób ogólny: może to być koszt finansowy, ale również czas lub odległość. Wagi mogą przyjmować również znaczenie przepustowości, a więc ograniczenia maksymalnego przepływu daną krawędzią. Generalnie graf może zawierać wiele wag dla pojedynczej krawędzi, ale typowymi parametrami sieci przepływowej są koszty i przepustowości krawędzi.

 Przepływem na łuku nazywamy przypisaną do łuku liczbę reprezentującą wielkość przesyłanego towaru.

 Wierzchołek $p$ nazywamy poprzednikiem wierzchołka $v$ jeżeli w grafie istnieje łuk $p,v)$. Zbiór wszystkich poprzedników wierzchołka $v$ oznaczmy przez $P_v$.

 Wierzchołek $s$ nazywamy następnikiem wierzchołka $v$ jeżeli w grafie istnieje łuk $v,s)$. Zbiór wszystkich następników wierzchołka $v$ oznaczmy przez $S_v$.

Dywergencją $b_v$ wierzchołka $v$ nazywamy $b_v=\sum_{s \in P_v} f_{sv} - \sum_{p \in P_v} f_{vp}$. Jeżeli $b_v> 0$ to wierzchołek $v$ jest źródłem. Jeżeli $b_v$ to wierzchołek $v$ jest ujściem.

Graf $H$ jest podgrafem grafu $G$ jeżeli zbiory wierzchołów i krawędzi $H$ są podzbiorami odpowiednio zbiorów wierzchołków i krawędzi $G$.

 Drzewem rozpinającym grafu $G$ nazywamy spójny podgraf, taki, że zawiera wszystkie wierzchołki z grafu $G$ oraz zawiera $n-1$ krawędzie, gdzie $n$ jest liczbą wierzchołów $G$.

Skojarzeniem nazywamy podzbiór krawędzi grafu $G$ taki, że krawędzie nie mają wspólnych wierzchołków. Maksymalne skojarzenie, to skojarzenie zawierające maksymalną liczbę krawędzi.

Pokryciem jest podzbiór wierzchołów takich, że wszystkie krawędzie są przylegające do co najmniej jednego wierzchołka z tego zbioru. Z minimalnym pokryciem mamy do czynienia, jeżeli liczba wierzchołków jest najmniejsza.

Graf jest dwudzielnym jeżeli możemy podzielić zbiór wierzchołków na dwa rozłączne podzbiory, takie że w każdym z tych podzbiorów nie ma krawędzi łączących wierzchołki w obrębie zbioru.

 Istnieje wiele sposobów reprezentacji sieci przepływowych. Macierz sąsiedztwa jest macierzą kwadratową w której kolumny i wiersze odpowiadają wierzchołkom grafu. Wartość 1 w wierszu $i$ i kolumnie $j$ oznacza krawędź skierowaną $(i,j)$. Innym sposobem reprezentacji jest przechowywanie dla każdego wierzchołka listy łuków wychodzących z tego wierzchołka. W programowaniu liniowym najczęściej wykorzystuje się macierz incydencji. Jej wiersze odpowiadają wierzchołkom, a kolumny odpowiadają łukom. Wartość 1 w wierszu $i$ oraz kolumnie $j$ oznacza początek łuku $j$ w wierzchołku $i$, zaś wartość -1 oznacza, że łuk $j$  kończy się w wierzchołku $i$. Jeżeli w sieci przepływowej wyróżnimy wierzchołek źródłowy $s$ oraz wierzchołek ujściowy $t$, to ograniczenia modelujące przepływ w sieci mogą przyjąć następującą postać:

$\sum_{z\in V} f_{v,z} - \sum_{u\in V} f_{u,v} = \left\{\begin{array}{rl} F& \textit{dla } v=s \\ 0&\textit{dla } v\in V\setminus\{s,t\}\\ -F&\textit{dla } v=t \end{array} \right.$

gdzie $F$ jest wielkością przepływu z $s$ do $t$, a $f_{u,v}\leq c_{uv}$ jest przepływem  po krawędzi $(u,v)$ ograniczonym przepustowością łuku $c_{uv}$.