An undirected, weighted, connected graph $G$, (with no negative weights and with all weights distinct) is given. We know that, in this graph, the shortest path between any two vertices is on the minimum spanning tree (MST). Verify the following: 1) shortest path between any two vertices $u$, $v$ is unique.
My question is, is this statement (1) is false or True? Other details is not mentioned in the old exam question, But I think: 1) if this means that for any pair of vertices and for any shortest path between them, it lies on MST So this statement is False. for example Let’s assume that we have a graph with two vertices ${1, 2}$ and one edge between them with zero weight. There are infinitely many shortest paths between the first and the second vertex ($[1, 2]$, $[1, 2, 1, 2]$, …) 2) if this means For each $a,bin V$, for each shortest path $P$ from $a$ to $b$ in $G$ there exists a minimum spanning tree $T$ of $G$ such that $p$ is contained in $T$. this statement is True.
Asked By : Anjela Minoeu
Answered By : superuseroi
- be undirected
- be weighted
- be connected
- with no negative weights
- with all weights distinct
- in this graph, the shortest path between any two vertices is on the minimum spanning tree (MST)
I believe the key point here is the article used in point 6, as pointed out by David Richerby comment From the wikipedia page: Article (grammar): Definite Article
A definite article indicates that its noun is a particular one (or ones) identifiable to the listener. It may be something that the speaker has already mentioned, or it may be something uniquely specified. The definite article in English, for both singular and plural nouns, is the.
Indefinite article
An indefinite article indicates that its noun is not a particular one (or ones) identifiable to the listener. It may be something that the speaker is mentioning for the first time, or its precise identity may be irrelevant or hypothetical, or the speaker may be making a general statement about any such thing.
So point 6 lends to some ambiguity:
- It could be that the shortest path is implied to be unique. (In this case I must say the hypothesis and the question are sort of misleading)
- Or it could be that the shortest path is only one of the possible shortest paths between any two vertices
So if we interpret the hypothesis as per point 1 (i.e. the shortest path means there is a unique shortest path) then the hypothesis is also the answer. If we interpret the hypothesis as per point 2 then we could consider the following undirected graph:
A--5--B | / 2 3 | / C
There is no unique shortest path between A and B
Since we could have both:
AB (cost 5)
AC + CB (cost 2+3 = 5) So if we interpret the hypothesis not meaning the shortest path is unique and asks you to verify this, then we have demonstrated that there is such graph with no unique shortest path that satisfies all other conditions.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/41185 Ask a Question Download Related Notes/Documents
