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

标签：

• Kyoto-University
• Shortest-Path-Problem

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.

By the contrapositive of Question (2), since there is no negative cycle, for every edge

Hence

Any path from to must go through an edge from to . Hence, let denote a shortest simple path from to . Let be the first edge on that crosses from to and let and denote the subpaths of . Then,

Therefore,