跳到主要内容

京都大学 情報学研究科 数理工学専攻 2019年8月実施 アルゴリズム基礎

标签：

Author​

祭音Myyura

Description​

日本語版​

を節点集合 ，枝集合 から成る連結な単純無向グラフとし， は隣接リストにより貯えられているとする． 二点 間の路の最短の長さを と記す． 以下の問いに答えよ．

(1) 任意の点 を選ぶ． を満たす枝 が存在すれば，枝 は長さ奇数の単純閉路に含まれることを証明せよ．

(2) が二部グラフであるかどうかを 時間で判定する方法を示せ．

(3) 異なる二点 に対して， 間の最短路が唯一であるかどうかを 時間で判定する方法を示せ．

English Version​

Let denote a simple connected undirected graph with a vertex set and an edge set . Assume that is stored in adjacency lists. For two vertices , let denote the shortest length of a path between them. Answer the following questions.

(1) Let be an arbitrary vertex. Prove that if there is an edge such that then edge is contained in a simple cycle of an odd length.

(2) Show how to test whether is a bipartite graph or not in time.

(3) Let be two distinct vertices. Show how to test whether has only one shortest path between and or not in .

Kai​

Let denote the length of a path .

(1)​

Let be a shortest path from to , and let be a shortest path from to .

Since both paths start at , they have at least one common vertex. Let be the last common vertex of and .

Denote by the subpath of from to , and by the subpath of from to . Since is the last common vertex of and , these two subpaths have no common vertices except .

Let

We show that .

Since and are shortest paths, by assumption,

Also,

and

Since every subpath of a shortest path is also a shortest path, both and are shortest paths from to . Therefore,

Combining these equalities, we obtain

Now consider the cycle formed by the path , the edge , and the reverse of the path .

Because is the last common vertex of and , the two paths and have no common vertices except . Therefore, the above closed walk is a simple cycle.

The length of this cycle is

Since , this length is

which is odd.

(2)​

The algorithm can be established from the following statement and (1):

  • A simple undirected graph is bipartite iff it contains no odd length cycle.

() When is bipartite, let denote the partition of .

Assume that there exists a cycle in of odd length.

W.l.o.g we assume that . Then we know that vertices are in vertex set , which implies that vertex is in vertex set , a contradiction.

Therefore, if is bipartite, there is no odd length cycle in .

() Run BFS from arbitrary . Color each vertex according to the parity of .

For every edge , if and have the same color, then since adjacent vertices in an unweighted graph have BFS distances differing by at most , they must satisfy .

By (1), this edge lies on an odd cycle, so G is not bipartite. If no such edge exists, all edges go between the two color classes, hence the graph is bipartite.

Algorithm​

Let be an arbitrary vertex. We use BFS to color vertices according to the parity of their distances from , and then check whether there exists an edge whose endpoints have the same color.

algorithm IsBipartite(G):
    for each v in V:
        color[v] <- null

    choose an arbitrary vertex s
    color[s] <- RED
    Q <- create an empty queue
    Q.enqueue(s)

    while Q is not empty:
        n1 <- Q.dequeue()
        for each n2 in n1.Adj():
            if color[n2] = null:
                if color[n1] = RED:
                    color[n2] <- BLUE
                else:
                    color[n2] <- RED
                Q.enqueue(n2)
            else:
                if color[n2] = color[n1]:
                    return "Graph is not bipartite"

    return "Graph is bipartite"

Since BFS scans each vertex and each edge a constant number of times, the running time is .

(3)​

Let be the distance from to , and let denote the number of shortest paths from to , truncated at . Thus, means that there are at least two shortest paths from to .

for each v in V:
    dist[v] = INF
    cnt[v] = 0

dist[s] = 0
cnt[s] = 1
Q.push(s)

while Q is not empty:
    u = Q.pop()
    for each v in Adj[u]:
        if dist[v] == INF:
            dist[v] = dist[u] + 1
            cnt[v] = cnt[u]
            Q.push(v)
        else if dist[v] == dist[u] + 1:
            cnt[v] = min(2, cnt[v] + cnt[u])

if cnt[t] == 1:
    return "unique"
else:
    return "not unique"
目录