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<0\) 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}\).