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

Author

祭音Myyura

Description

日本語版

を節点集合 , 枝集合 から成る単純有向グラフとし， を の各枝 に実数値の容量 を与えて得られるネットワークとする． 節点の部分集合 に対し， 内の点から 内の点へ向かう枝の集合を と記す． 非負実数全体の集合を で表す． 指定された二点 に対し，流量保存則 および容量制約 を満たす関数 を フローと呼び，その流量 を

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

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

(i) 任意の フロー と カット に対し，等式

が成り立つことを証明せよ．

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

(iii) 残余ネットワーク において， から への有向路が存在するとき，そのひとつを とする． 上の枝の における容量の最小値を とするとき， には流量が である フローが存在することを証明せよ．

(iv) 残余ネットワーク が から への有向路をもたないとき， において から到達可能な節点の集合を とする．このとき， である任意の集合 に対し が成り立つことを証明せよ．

English Version

Let be a simple directed graph with a vertex set and an edge set , and let be a network obtained from by assigning a real value to each edge as its capacity. For vertex subsets , let denote the set of edges that leave a vertex in and enter a vertex in . Let denote the set of nonnegative reals. For two designated vertices , an -flow is defined to be a mapping which satisfies (flow conservation law) and (capacity constraint), and its flow value 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 in , assume that there is a directed path from to in the residual network . Let denote the minimum capacity of an edge in in . Prove that has an -flow whose flow value is .

(iv) For an -flow in , assume that there is no directed path from to in the residual network . Let denote the set of vertices that are reachable from in . Prove that holds for any set with .

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)

Let be defined as follows:

We prove that is a flow and

First we verify that obeys that capacity constraint.

For an edge , we have

For an edge , we have

Hence the capacity constraint holds.

Next we prove the flow conservation constraint. For a vertex , obviously the flow conservation constraint holds if . Hence we focus on the case that .

For a vertex , since is a simple path, there are exactly two edges and in that adjacent to .

if and , then we have

if and , then we have

Similarly for the case and the case . Hence the flow conservation constraint holds.

Finlly, we compute the value . Same as the proof of flow conservation constraint, there are two cases for the edge in corresponds to the edge adjacent to in of .

It is easy to compute that in both cases we have

Therefore, has an -flow whose flow value is .

(iv)

By 京都大学 大学院 情報学研究科 数理工学専攻 2022年実施 グラフ理論 (i) and (iii) we know that is actually a minimum -cut.

Hence for any any set with , we have .