patternMinor
There exists some number $x$ so in any run of BFS from vertex $w$, so the distance from $u$ to $v$ in BFS tree is always $x$
Viewed 0 times
fromnumberthevertexanybfsdistancealwayssomeexists
Problem
Studying for my finals and stuck on the following question:
Prove or disprove: Given an undirected and connected graph $G=(V,E)$ and three different vertices $u,v,w\in V$ then there exists some number $x$ so in any run of BFS from vertex $w$, the distance from $u$ to $v$ in BFS tree is always $x$.
I think it's not true but could not think about a good example to disprove it.
Prove or disprove: Given an undirected and connected graph $G=(V,E)$ and three different vertices $u,v,w\in V$ then there exists some number $x$ so in any run of BFS from vertex $w$, the distance from $u$ to $v$ in BFS tree is always $x$.
I think it's not true but could not think about a good example to disprove it.
Solution
The statement is false. Take a look at the following graph:
In one BFS run, you will get the following tree:
That has a distance of $1$ between $u$ and $v$, while in a different run, you could get another tree:
Which has a distance of $3$ between $u$ and $v$
In one BFS run, you will get the following tree:
That has a distance of $1$ between $u$ and $v$, while in a different run, you could get another tree:
Which has a distance of $3$ between $u$ and $v$
Context
StackExchange Computer Science Q#142569, answer score: 3
Revisions (0)
No revisions yet.