京都大学 情報学研究科 数理工学専攻 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:

According to question (ii), there is no edge between and if and are both even or odd. Also, according to the statement of question (iii), no contains a pair of adjacent vertices. Hence no two vertices within the same set are adjacent, which implies that is a bipartite graph.

(iv)

We prove the statement by contradiction.

Assume that is bipartite. Suppose that there exists two adjacent vertices and in a .

Then there must exists two vertices adjacent to and , respectively. If , then a contradiction to the definition of bipartite graph. Hence we assume that . Repeat the above construction and finally we will be in the situation that , which leads to a contradiction.

Therefore, if some contains a pair of adjacent vertices then is not a bipartite graph.