京都大学 情報学研究科 数理工学専攻 2022年8月実施 グラフ理論

Author

祭音Myyura

Description

日本語版

非負実数全体の集合を で表す． を点集合 枝集合 をもつ単純有向グラフ および容量関数 からなるネットワークとする． 点の部分集合 に対し， 内の点から 内の点へ向かう枝の集合を と記す． 指定された二点 に対し，次を満たす関数 を -フローと呼ぶ．

-フロー の流量 を

で定める．また を満たす点の部分集合 を -カットと呼び，その容量 を

で定める．以下の問いに答えよ．

(i) 任意の -フロー と -カット に対し以下が成り立つことを証明せよ．

(ii) 与えられた -フローf に対して定められる残余ネットワーク の作り方を説明せよ．

(iii) 残余ネットワーク が から へ至る有向路を持たないような -フロー に対し， を において から到達可能な点の集合とする．このとき において が成り立つことを証明せよ．

(iv) を において容量 を最小にする任意の -カットとする．このとき (iii) の残余ネットワーク において から のどの点へも到達できないことを証明せよ．

English Version

Let denote the set of nonnegative reals. Let be a network that consists of a simple directed graph with a vertex set and an edge set and a capacity function . For vertex subsets , let denote the set of edges that leave a vertex in and enter a vertex in . For two designated vertices , an -flow is defined to be a function which satisfies the following:

The flow value of an -flow f is defined to be

An -cut is defined to be a vertex subset such that and , and its capacity is defined to be

Answer the following questions.

(i) Prove that for any -flow and any -cut

holds.

(ii) For a given -flow , show how to construct its residual network .

(iii) For an -flow such that the residual network has no directed path from to , let denote the set of all vertices reachable from in . Prove that holds in .

(iv) Let be an -cut with the minimum capacity in . Prove that no vertex in is reachable from in the residual network in (iii).

Kai

(i)

We can rewrite the flow conservation law for any node as

then we have

Expanding the right-hand summation and regrouping terms yields

The two summations and are actually the same, since for all vertices , the term appears once in each summation. therefore

(ii)

We define the residual capacity by

and the edge set by

(iii)

To prove , we prove the following two conditions:

(a) All outgoing edges from the cut must be fully saturated.

(b) All incoming edges to the cut must have zero flow.

Assume that there exists an outgoing edge , , such that it is not saturated, i.e. . This implies that there exists an edge , , , therefore there exists a path from to , which is contradictory to the definition of . Hence, any outgoing edge is fully saturated.

Assume that there exists an incoming edge , , such that it carries some non-zero flow, i.e. . This implies that there exists an edge , , , therefore there exists a path from to , which is contradictory to the definition of . Hence, any incoming edge must have zero flow.

Finally, we have

(iv)

Prove by contradiction: W.l.o.g we assume that there exists only one vertex , i.e. .

From the flow conservation law we have

From (iii) we know that

and

Hence we have

Since is reachable from in , we know that either

(a) there exists an edge such that , i.e.,

or

(b) there exists an edge such that . i.e.,

Both cases imply that

Then we consider the capacity of cut

which is contradictory to the fact that is a minimum cut.