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

Author

祭音Myyura

Description

日本語版

を節点集合 、 枝集合 から成る単純強連結有向グラフとし、 に属する節点の個数を 、に属する枝の本数を とする。 の各枝 に実数値重み を与えて得られるネッタワークを とする。 節点 から節点 への有向枝は と書き、その枝重みは とも書く。 節点 をこの順に訪ねる路 について、枝の本数を 、枝重みの和を と書く。

節点 が与えられたものとする。各節点 について、 から への路 で を満たすものにおける のうち、最小値を と定める。 また から への単純路 における のうち、最小値を と定める。 を満たす閉路 を負閉路と呼ぶ。以下の問いに答えよ。

(i) に負閉路が存在しないとき、かつその時に限り、

が成り立つことを示せ。

(ii) に負閉路が存在するかどうかを判定し、もし存在しない場合には全ての に対して を出力する、 時間のアルゴリズムを与えよ。

English Version

Let denote a simple, strongly connected digraph with a vertex set and an edge set , let denote the number of vertices in , and let denote the number of edges in . Let denote a network obtained from by assigning a real value to each edge as its weight. A directed edge from a vertex to a vertex is denoted by and its weight is written as . When a path visits vertices in this order, let denote the number of edges in and let denote the summation of weights of edges in

Suppose that a vertex is given. For each vertex , we define to be the minimum of among all paths from to such that . We define to be the minimum of among all simple paths from to . A cycle is called a negative cycle if . Answer the following questions.

(i) Prove that there is no negative cycle in if and only if

(ii) Show an -time algorithm that determines whether or not there exists a negative cycle in and that outputs for all if no negative cycle exists.

Kai

(i)

(a) (If there is no negative cycle, then )

Prove by contradiction: Assume that there exists an edge such that .

Let denote a path from to of weights and denote a path from to of weights .

Let . Since , by the definition of we know that , i.e., is not a simple path.

W.l.o.g we assume that only contains sub-cycle .

Assume that , let denote the path obtained by remove the sub-cycle of , we have

and , which is contradictory to the definition of .

Hence , which is contradictory to the condition "there is no negative cycle".

Therefore, if there is no negative cycle, then .

---

(b) (If , then there is no negative cycle)

Prove by contradiction: Assume that there exists a negative cycle

From the condition we know that ,

Hence

sum over all the equations,

which is contradictory to the fact that

Therefore, if , then there is no negative cycle.

(ii)

Bellman-Ford algorithm (Wiki)

function BellmanFord(list vertices, list edges, vertex source) is

    // This implementation takes in a graph, represented as
    // lists of vertices (represented as integers [0..n-1]) and edges,
    // and fills two arrays (distance and predecessor) holding
    // the shortest path from the source to each vertex

    distance := list of size n
    predecessor := list of size n

    // Step 1: initialize graph
    for each vertex v in vertices do
        // Initialize the distance to all vertices to infinity
        distance[v] := inf
        // And having a null predecessor
        predecessor[v] := null
    
    // The distance from the source to itself is, of course, zero
    distance[source] := 0

    // Step 2: relax edges repeatedly
    repeat |V|−1 times:
        for each edge (u, v) with weight w in edges do
            if distance[u] + w < distance[v] then
                distance[v] := distance[u] + w
                predecessor[v] := u

    // Step 3: check for negative-weight cycles
    for each edge (u, v) with weight w in edges do
        if distance[u] + w < distance[v] then
            predecessor[v] := u
            // A negative cycle exists; find a vertex on the cycle 
            visited := list of size n initialized with false
            visited[v] := true
            while not visited[u] do
                visited[u] := true
                u := predecessor[u]
            // u is a vertex in a negative cycle, find the cycle itself
            ncycle := [u]
            v := predecessor[u]
            while v != u do
                ncycle := concatenate([v], ncycle)
                v := predecessor[v]
            error "Graph contains a negative-weight cycle", ncycle
    return distance, predecessor