y.d是δ(s,v)的上界 河题8： Lemma 22.2 你能的作是怎么刂纳的吗？ Let G =(V,E)be a directed or undirected graph,and suppose that BFS is run on G from a given source vertex s e V.Then upon termination,for each ver- tex vV,the value v.d computed by BFS satisfies v.d >8(s,v). Proof We use induction on the number of ENQUEUE operations.Our inductive hypothesis is that v.d≥8(s,v)for all v∈V. The basis of the induction is the situation immediately after enqueuing s in line 9 of BFS.The inductive hypothesis holds here,because s.d =0=8(s,s)and v.d=oo≥8(s,v)for allv∈V-{s. For the inductive step,consider a white vertex v that is discovered during the search from a vertex u.The inductive hypothesis implies that u.d >(s,u).From the assignment performed by line 15 and from Lemma 22.1,we obtain v.d =,/.d+1 8s,w)+1 为什么？ 8(s,). Vertex v is then enqueued,and it is never enqueued again because it is also grayed and the then clause of lines 14-17 is executed only for white vertices.Thus,the value of v.d never changes again,and the inductive hypothesis is maintained.v.d 是δ(s,v)的上界 为什么？