9.1. ネットワークとフローの定義

ネットワーク (network) は次の要素から構成される:

• 多重グラフ \(D=\left( V,A,\psi\right) \)

• 入口 (source) と呼ばれる頂点 \(s \in V\)

• 出口 (sink) と呼ばれる \(s\) と異なる頂点 \(t \in V\)

• 容量関数 (capacity function) と呼ばれる関数 \(c\colon A\rightarrow\mathbb{N}\)

多重有向グラフ \(D=\left( V,A,\psi\right) \)、入口 \(s \in V\)、出口 \(t \in V\)、容量関数 \(c\colon A\rightarrow\mathbb{N}\) から構成されるネットワークを \(N\) とする。このとき:

1. 任意の弧 \(a \in A\) に対して、値 \(c\left( a\right) \in\mathbb{N}\) を弧 \(a\) の容量 (capacity) と呼ぶ。

2. \(V\) の任意の部分集合 \(S\) に対して、\(V\) の部分集合 \(V\setminus S\) を \(\overline{S}\) と表記する。

3. \(V\) の任意の部分集合 \(P\), \(Q\) に対して、\(P\) に属する始点と \(Q\) に属する終点を持つ辺全体の集合を \(\left[ P,Q\right] \) と表記する。つまり、次のように定める:

   \[ \left[ P,Q\right] \colonequals \left\{ a\in A\mid \psi\left( a\right) \in P\times Q\right\} \]

4. \(V\) の任意の部分集合 \(P\), \(Q\) と任意の関数 \(d\colon A\rightarrow\mathbb{N}\) に対して、値 \(d\left( P,Q\right) \in\mathbb{N}\) を次のように定義する:

   \[ d\left( P,Q\right) \colonequals \sum_{a\in\left[ P,Q\right] }d\left( a\right) \]

   [特に、この定義で \(d=c\) とすれば \(c\left( P,Q\right) =\sum\limits_{a\in\left[ P,Q\right] }c\left( a\right) \) を得る。]

多重有向グラフ \(D=\left( V,A,\psi\right) \)、入口 \(s \in V\)、出口 \(t \in V\)、容量関数 \(c\colon A\rightarrow\mathbb{N}\) から構成されるネットワークを \(N\) とする。

ネットワーク \(N\) 上のフロー (flow) とは、次の条件を満たす関数 \(f\colon A\rightarrow \mathbb{N}\) を意味する:

• 任意の弧 \(a \in A\) で \(0\leq f\left( a\right) \leq c\left( a\right) \) が成り立つ。この条件は容量制約 (capacity constraints) と呼ばれる (弧 \(a \in A\) ごとに制約があるので、複数形を用いる)。

• 任意の頂点 \(v\in V\setminus\left\{ s,t\right\} \) が次の等式を満たす:

  \[ f^{-}\left( v\right) = f^{+}\left( v\right) \]

  ここで \(f^{-}\) と \(f^{+}\) は次のように定義される:

  \[ f^{-}\left( v\right) \colonequals \hspace{-8pt} \sum_{\substack{a\in A;\\[2pt] a \text{ の終点は } v}} \hspace{-10pt} f\left( a\right) \qquad \quad f^{+}\left( v\right) \colonequals \hspace{-8pt} \sum_{\substack{a\in A;\\[2pt] a \text{ の始点は } v}} \hspace{-10pt} f\left( a\right) \]

  この条件は保存制約 (conservation constraints) と呼ばれる。

フロー \(f\colon A\rightarrow\mathbb{N}\) と弧 \(a \in A\) に対して、値 \(f\left( a\right) \) を \(a\) における \(f\) の弧流量 (arc flow) と呼ぶ。

多重有向グラフ \(D=\left( V,A,\psi\right) \)、入口 \(s \in V\)、出口 \(t \in V\)、容量関数 \(c\colon A\rightarrow\mathbb{N}\) から構成されるネットワークを \(N\) とする。\(f\colon A\rightarrow\mathbb{N}\) を任意の写像 (例えば \(N\) 上のフロー) とする。このとき:

1. 任意の頂点 \(v \in V\) に対して、\(f^{-}\left( v\right)\) と \(f^{+}\left( v\right)\) を次のように定める:

   \[ f^{-}\left( v\right) \colonequals \hspace{-8pt} \sum_{\substack{a\in A;\\[2pt] a \text{ の終点は } v}} \hspace{-10pt} f\left( a\right) \qquad \quad f^{+}\left( v\right) \colonequals \hspace{-8pt} \sum_{\substack{a\in A;\\[2pt] a \text{ の始点は } v}} \hspace{-10pt} f\left( a\right) \]

   \(f^{-}\left( v\right) \) を \(f\) における \(v\) への入流量 (inflow) と呼び、\(f^{+}\left( v\right) \) を \(f\) における \(v\) からの出流量 (outflow) と呼ぶ。

2. 値 \(f^{+}\left( s\right) -f^{-}\left( s\right) \) を写像 \(f\) の値 (value) と定義し、\(\left\vert f\right\vert \) と表記する。