2
$\begingroup$

Given undirected and connected graph $G = (V,E)$. Prove for any DFS run: for any $u,v \in V$ if $u.d>v.d$ then $u.d − v.d ≥ δ(u,v)$

$δ(u,v)$-distance of a shortest path (not necessarily unique) in G

$u.d,v.d$-time, when each vertex was discovered in DFS for the first time.

I know that DFS not necessarily returns the shortest path.And I know that if $u.d>v.d$ then $u$ discovered after $v$, $v≠u$ and there is path is DFS between vertices, because G is connected.

I have tried to assume by contradiction that $u.d-v.d<δ(u,v)$

Given that G is connected and $v.d<u.d$. Then v discovered before $u$ and $u≠v$. According to the “parenthesis property” theorem: either $u$ is a descendant of $v$, or $u$ and $v$ do not exhibit an ancestor-descendant relation if $G_π$.

In the first case, $u$ is a descendant of $v$.

Let’s assume by contradiction that $u.d-v.d<δ(u,v)$ $u.d-v.d$ sets distance of simple path $(u,v)$ from $u$ to $v$ in $G_π$. Because $u$ is a descendant of $v$, the path $(u,v)$ also appears in $G$. By our assumption this distance is smaller then $δ(u,v)$ and that is in contradiction to the fact that $δ(u,v)$ is a distance of a shortest path (not necessarily unique) in $G$.

In the second case, $u$ and $v$ do not exhibit an ancestor-descendant relation if $G_π$.

Hence, $u$ was not discovered from $v$. It means that there is $w≠v∈V$ such that: $w.d<v.d<v.f<u.d<u.f<w.f$ $(w≠v)$

$w.d<u.d$ then $u.d-w.d≥δ(u,w)$ (proof of the first case) $w.d<v.d$ then $v.d-w.d≥δ(v,w)$

And I have no idea how to continue from here..

$\endgroup$
  • $\begingroup$ It can be pretty tricky writing down a proof unless you are very precise about 1) your dfs implementation 2) what words like "time", "discovered", "visited" mean $\endgroup$ – Matthew C Dec 3 '19 at 17:14
  • $\begingroup$ Basically you have two cases: $v$ is discovered as a descendant of $u$ (easy), or not. In the latter case, if your DFS is implemented using a stack, this is like saying that $v$ is a descendant of some $w$, where $w$ was beneath $u$ in the stack $\endgroup$ – Matthew C Dec 3 '19 at 17:16
  • $\begingroup$ @user111398 I cant prove the state in the latter case.. Do you have any clue? $\endgroup$ – sasha Dec 8 '19 at 15:22

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.