BFSの解析

Question

私はCormenから次のBFS機能を持っています。

頂点sから頂点vまでの任意のパスの最短辺数として、sからvまでの最短パス距離パス（s、v）の定義、またはsからvへのパスがない場合のA長経路の経路は、（S、v）はV秒からは、SからVへの最短経路であると言われている。

後は補題与えられる

G =（V、E）があるとする有向または無向グラフであり、sは任意の頂点であるVに属するとする。そして、任意のエッジ（u、v）に対して、

パス（s、v）< = path（s、u）+ 1。

私の質問は上記の式の中で< =を持っていなければならないということです。私は "="は大丈夫だと教えてくれますか？

レッツG =（V、E）有向または無向グラフであり、所与のソース頂点sが属するからBFSはG上で実行されると仮定する：以下

は

Leema 2 BFSアルゴリズムであります各頂点vがVに属するので、BFSによって計算された値d [v]は、d [v]> = path（s、v）を満たす。

証明：

我々は頂点が私たちの誘導の仮説は、dは[V]> =パス（S、V）は、すべてのVのためにVに属することであるキューQに配置された回数に誘導を使用

誘導の基礎は、sがBFSの8行目のQに置かれた直後の状況です。

すべてのvについて、d [s] = 0 = path（s、s​​）およびd [v] = path（s、v）がV - {s}に属するため、帰納仮説が成り立ちます。

私の質問は、「頂点がキューQに配置された回数に誘導を使用する」という意味です。帰納的仮説にどのように関連しているのか？

ありがとうございました！

BFS(G,s) 
1 for each vertex u V[G] - {s} 
2  do color[u] WHITE 
3   d[u] 
4   [u] NIL 
5 color[s] GRAY 
6 d[s] 0 
7 [s] NIL 
8 Q {s} 
9 while Q 
10  do u head[Q] 
11   for each v Adj[u] 
12    do if color[v] = WHITE 
13     then color[v] GRAY 
14      d[v] d[u] + 1 
15      [v] u 
16      ENQUEUE(Q,v) 
17   DEQUEUE(Q) 
18   color[u] BLACK 

Answer 1

最初の質問では、3つの頂点しかない完全なグラフを考えてみましょう。このグラフでは、path（s、v）= path（s、u）+ 1？