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

Author

祭音Myyura

Description

日本語版

を節点集合 、枝集合 から成る単純強連結有向グラフ、 を の各枝 に実数値の重み を与えて得られるネットワークとする。 節点 から節点 への有向枝は と書き、その枝重みは とも書く。 節点 から節点 への距離 を における から への単純路上の枝重みの和の最小値と定める。 枝重み和が負である有向閉路を負閉路と呼ぶ。以下の問いに答えよ。

(i) 次の条件を満たす節点の実数値重み , が存在するとき、 に負閉路が存在しないことを証明せよ。

(ii) 次を満たす節点 と枝 の組が存在するとき、 に負閉路が存在することを証明せよ。

(iii) 各枝の重みが非負であると仮定する。 ある部分集合 と節点 に対して、 から へ向かう枝 の中で の値が最小とする枝を とする。 このとき、 が成り立つことを証明せよ。

English Version

Let denote a simple, strongly connected digraph with a vertex set and an edge set , and let denote a network obtained from by assigning a real value ot each edge as its weight. A directed edge from a vertex to a vertex is denoted by and its weight is writen as . Define the distance from a vertex to a vertex to be the minimum summation of weights of edges in a simple path from to in . A directed cycle is called a negative cycle if the sum of edge weights in the cycle is negative. Answer the following questions.

(i) Prove that has no negative cycle if there is a set of real weights such that

(ii) Prove that has a negative cycle if there is a pair of a vertex and an edge such that

(iii) Assume that the weight of each edge is non-negative. For a subset and a vertex , let be an edge that minimizes among all edges directed from to . Prove that .

Kai

(i)

Please refer to 京都大学 情報学研究科 数理工学専攻 2023年8月実施 グラフ理論.

(ii)

Let denote a simple path from to of distance . Let denote the path by concatenating and edge .

If , then by the definition of "distance" we know that is not a simple path otherwise .

Since is a simple path but is not, we have . Hence there exists a cycle in which can be written as .

Let denote the subpath of ends at (note that is also a simple path). If is not a negative cycle, i.e., , then we have

which contradicts the definition of . Therefore, is a negative cycle.

(iii)

(Note: this question is actually asking a proof of correctness of Dijkstra's algorithm)

Since the weight of each edge is non-negative, there does not exist negative cycle. Hence by the definition of and question (2) we know that

Any path from to must go through an edge from to . Hence, let denote a shortest simple path from to . W.l.o.g. we assume that and let and denote the subpaths of . Then,

Therefore,