Podręcznik

1. Modele sieciowe

1.1. Podstawowe pojęcia

Graf skierowany

$G=(V,E)$ to zbiór wierzchołków

$V$ oraz zbiór łuków

$E$ , przy czym zbiór

$E=\{u,v\}, u,v \in V$ zawiera uporządkowane pary wierzchołków, a porządek wskazuje na kierunek łuku. Dla łuku

$\{u,v\}$ , wierzchołek

$u$ jest wierzchołkiem początkowym, a

$v$ jest wierzchołkiem końcowym.

Ścieżką nazywamy zbiór łuków łączących dwa zadane wierzchołki. Ścieżka z wierzchołka

$s$ do wierzchołka

$t$ jest zbiorem łuków

$(s,v_1), (v_1, v_2), \ldots, (v_{k-1},v_k), (v_k,t)$ . Wówczas

$s$ nazywamy źródłem, a

$t$ ujściem.

Cyklem nazywamy ścieżkę, której źródło jest jednocześnie ujściem.

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.

Siecią przepływową nazywamy ważony graf skierowany.

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}$ .