0
$\begingroup$

Given the following lemma first:

Lemma 1: Let $G=<V,E>$ be a directed or undirected graph, and let $s \in V$ be an arbitrary vertex. Then, for any edge $(u,v) \in E$,

$$\lambda(s,v) \le \lambda(s,u) + 1\tag{1}\label{1}$$

I would like to discuss the following proof the following lemma:

Lemma 2: Suppose that during the execution of BFS on a graph $G=<V,E>$, the queue $Q$ contains the vertices $\left< v_1, v_2, \cdots, v_r \right>$, where $v_1$ is the head of $Q$ and $v_r$ is the tail. Then,

$$d[v_r] \le d[v_1] +1 ~and~ d[v_i] \le d[v_{i+1}], i=(1,2, \cdots, r-1) \tag{2} \label{2}$$

Definitions:

  • $d[v]$ is the distance from source vertex $v$ to vertex $u$.
  • BFS is breadth first search algorithm of a graph.
  • $\lambda(s,u)$ is the shortest distance from $s$ to vertex $u$ as the minimum number of edges.

BFS Algorithm: (Courtesy to CLRS book):

enter image description here

Proof Lemma 2:

Basic step: By induction and for $s$ vertex only being in the queue, we can see that $d[s] \le d[s] +1 $ and $d[s] \le d[s]$ holds.

Inductive step: (Courtesy to CLRS book)For the inductive step, we must prove the lemma holds after both dequeuing and enqueuing a vertex. If the head $v_1$ of the queue is dequeued, the new head is $v_2$. (If the queue becomes empty, then the lemma holds vacuously.) But then we have $d[v_r] \le d[v_1] +1 \le d[v_2] + 1$, and the remaining inequalities are unaffected. Thus, the lemma follows with $v_2$ as the head. Enqueuing a vertex requires closer examination of the code. In line 16 of BFS, when the vertex $v$ is enqueued, thus becoming $v{r+1}$, the head $v_1$ of $Q$ is in fact the vertex $u$ whose adjacency list is currently being scanned. Thus, $d[v_{r+1}] = d[v] = d[u] + 1 = d[v_1] + 1$. We also have $d[v_r] \le d[v_1] + 1 = d[u] + 1 = d[v] = [v_{r+l}]$, and the remaining inequalities are unaffected. Thus, the lemma follows when $v$ is enqueued.

Problem2:

  1. We would like to prove that lemma 2 holds based on dequeuing and enqueuing of vertices to $Q$. If we don't remove any vertex from queue, then we would have complete list of vertices $\left< v_1, v_2, \cdots, v_r \right>$, so in this case and based on definition of distance $d[v]$, how we would have $d[v_r] \le d[v_1] +1$ in ref{2} please holds? I mean the distance to $d[v_r]$ is obviously as I see it can not be less than $d[v_1] +1$? $v_r$ is the last vertex added to queue and based on incrementing strategy in BFS, we would have $d[v_r] = d[u] + 1$, where $u$ is the precedence vertex as I see it, so I am not sure how this $d[v_r] \le d[v_1] +1$ hold please?
  2. Same reasoning to the previous problem applies to this statement in the proof please," Thus, the lemma 2 follows with $v_2$ as the head." Same thing, it says that if we remove $v_1$, then $d[v_r] \le d[v_2] + 1$ as $v_1$ is removed now, but why this is the case again please same to issue/problem 1 I stated?
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.