京都大学 情報学研究科 数理工学専攻 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 a -path and denote a shortest -path between two vertices and , respectively.

For a path we define a subpath of as .

Let denote the length of a path .

(1)

We first prove that for any common vertex of and , i.e. , we have .

Assume that for a vertex . Then the length of the path from to defined by edges is smaller than , which is contradictory to the fact that is a shortest path from to .

Then, let be the last common vertex of and , the length of cycle is

which is odd.

(2)

The idea 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 .

() Let be an arbitrary vertex. Let and be two subsets of .

Assume that there exists two vertices such that .

With similar statement in (1), let be the last common vertex of and , the length of cycle is odd, which is a contradiction.

Therefore, if contains no odd length cycle, then is bipartite.

Algorithm

Let be an arbitrary vertex. We use BFS to compute all the distances from to vertices and check whether there exists two vertices of same distances are adjacent.

algorithm IsBipartite(G(V, E), s):
    Q <- create an empty queue
    color[s] <- RED
    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'

(3)

• Use BFS to find a shortest -path in .
• Let denote an edge of . Use BFS to find a shortest -path in .
• If length of the two paths we found are same, then have two or more shortest paths between and .
• If length of the two paths we found are not same, then has only one shortest path between and .