3
$\begingroup$

I stuck in one challenging question, I read on my notes.

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,b\in 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.

Improve this question
$\endgroup$
14
  • $\begingroup$ Usually, "path" means "simple path", i.e., a sequence $v_1\dots v_\ell$ of distinct vertices such that $v_1v_2, \dots, v_{\ell-1}v_{\ell}$ are edges. By that definition, $1212$ isn't a path so your example with a zero-weight edge only has one shortest path between the vertices. (Also, zero-weight edges are often implicitly forbidden by a convention that assigns weight zero to the absence of an edge.) $\endgroup$
    – David Richerby
    Apr 9, 2015 at 20:41
  • 1
    $\begingroup$ 1. Is your question "what is the definition of path"? If so, (a) where have you looked to find the definition of path? (it's often listed in textbooks); (b) if it wasn't listed in your textbook, that might be a better question (more likely to be useful to others in the future) than this very specific question. 2. I think you need to define "shortest path" carefully, if you want to make the question precise. It looks like your notes aren't very precise about this (for instance, writing "the shortest path" is strictly speaking problematic, as the shortest path might not be unique). $\endgroup$
    – D.W. ♦
    Apr 9, 2015 at 20:43
  • $\begingroup$ You means my example is not correct, ok, under my interpretation (1), again is it false? @DavidRicherby $\endgroup$
    – Anjela Minoeu
    Apr 9, 2015 at 20:44
  • $\begingroup$ thanks @D.W. we dont want to play with words :) path is path. e consider simple path and path. just two case, we can overcome to these. $\endgroup$
    – Anjela Minoeu
    Apr 9, 2015 at 20:46
  • $\begingroup$ Your observation that a shortest path should lie on the MST is false. $\endgroup$
    – Hendrik Jan
    Apr 9, 2015 at 21:08

1 Answer 1

Reset to default
0
$\begingroup$

Let's consider the hypothesis of the question to try clarify every aspect:

Our Graph G should:

  1. be undirected
  2. be weighted
  3. be connected
  4. with no negative weights
  5. with all weights distinct
  6. 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:

  1. 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)
  2. 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.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ Talking about "the shortest path" rather than "a shortest path" implies uniqueness, to me. But, if "the" does imply uniqueness, the question is saying "Suppose we have a graph with unique shortest paths. Is it true that shortest paths are unique?" $\endgroup$
    – David Richerby
    Apr 9, 2015 at 22:53
  • $\begingroup$ Thank you @DavidRicherby you do have a point. then maybe we should work toward an example rather than a counter example. I will keep this answer for now until we hear back, or would you suggest I edit it? $\endgroup$
    – superuseroi
    Apr 9, 2015 at 23:01
  • $\begingroup$ I'd leave it for now. You've written a good answer to one of the things the question could mean. $\endgroup$
    – David Richerby
    Apr 9, 2015 at 23:07
  • $\begingroup$ if we consider Any shortest path must be on MST The statement is True, if consider there exists a shortest path on MST this is false. am I right? I means consider two case. $\endgroup$
    – Anjela Minoeu
    Apr 10, 2015 at 7:17
  • $\begingroup$ @AnjelaMinoeu I have added further details to my answer. I suggest you edit your question if you have further details $\endgroup$
    – superuseroi
    Apr 10, 2015 at 13:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.