跳到主要内容

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

标签：

Author​

祭音Myyura

Description​

連結単純無向グラフ と節点 が与えられたとき、 を始点とする幅優先探索により得られる の全域木を とし、 上で からの距離 である節点の集合を と記す。 以下の問いに答えよ。

(i) を始点として の全域木 を構築する幅優先探索の記述を与えよ。

(ii) である と の間には枝が存在しないことを証明せよ。

(iii) どの も隣接する２節点の対を含まないとき、 は二部グラフであることを証明せよ。

(iv) ある が隣接する２節点の対を含むとき、 は奇数長の閉路を持つことを証明せよ。

Kai​

(i)​

BFS-Tree(G, s):
    V_T = {s}
    E_T = {}
    Q = {}
    ENQUEUE(Q, s)

    while Q is not empty do
        u = DEQUEUE(Q)
        for each v in Adj[u] do
            if v is not in V_T then
                V_T = V_T + {v}
                E_T = E_T + {(u, v)}
                ENQUEUE(Q, v)   

    return (V_T, E_T)

(ii)​

If there exits an edge between and such that , w.l.o.g assume that and , then the distance from to is at most

which contradicts .

(iii)​

Consider the following sets:

We show that there is no edge between two vertices both in , and also no edge between two vertices both in .

First, consider two different layers and with the same parity. If , then

according to the result of question (ii), there is no edge between and .

Next, by the assumption, no contains a pair of adjacent vertices. Hence no two vertices within the same set are adjacent, which implies that all edges of go between and , i.e., is a bipartite graph.

(iv)​

We prove the statement by contradiction.

Suppose that some contains a pair of adjacent vertices . Since , the paths from to and from to in the BFS tree both have length .

Let be the unique path from to in , and let be the unique path from to in . Let be the last common vertex of these two paths. Suppose that . Then the path from to in has length

and the path from to in also has length

Moreover, these two paths have no common vertices except . Therefore, by taking the path from to , then the edge , and then the path from back to , we obtain a cycle.

The length of this cycle is

which is an odd number.

目录