Graph and PRIM and DIJKSTRA Problems?

 

We are given an Undirected, Weighted and Connected Graph G, (without negative weight and all weights are distinct) that shortest path between any two vertexes on this graph is on minimum spanning tree. Then:

I) Graph G is a Tree.

II) weight of each {u,v} edge, is at least equal to heaviest edge in shortest path from u to v.

III) shortest path between any two vertex u, v is unique.

IV) suppose start from vertex s , Prime (for calculating MST) and Dijkstra (for calculating shortest path), process and add the vertexes into a Tree, with the same order. (two algorithm works with same order in processing and adding node)

Please explain, why just two of these claims is TRUE? I am confusing with the definition, Proposed by OUR TA.

Let G=(V,E,w) be a weighted graph with the following properties.

  • w(e)>=0 for each e in E and w(e1) != w(e2) for each e1,e2 in E with e1 != e2 .

  • 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 .

    • Note that property 2 is not stated totally clearly in the requirement, but to my understanding, this is what is meant by the OP, since other interpretations don't actually make sense: if for any pair of vertices a and b , there are two shortest paths p1 and p2 between them, they cannot be contained in the same minimum spanning tree, as they would form a cycle. Likewise, given a shortest path p between a and b , there does not necessarily exist a minimum spanning tree which contains p .

    Then, statements I) and IV) are not necessarily true, but statements II) and III) are true.

    For statement I), consider the following counterexample. Let G:=(V,E,w) with V:={1,2,3} , E:={{1,2},{1,3},{2,3}} and 

    w({1,2}):=1,
w({1,3}):=2,
w({2,3}):=4.

    Note that all edge weights are positive and distinct, hence property 1 from above is satisfied. Furthermore, the edges {1,2} and {1,3} constitute the only minimum spanning tree T for G . Finally, the only shortest path from 1 to 2 is {1,2} , the only shortest path from 1 to 3 is {1,3} , and the only shortest path from 2 to 3 is {2,1}{1,3} . All of these paths are included in T . However, G contains the cycle {1,2},{2,3},{3,1} , hence it is not a tree.

    For statement II), let u,v in V . Let p be a shortest path from u to v in G . Assume that w({u,v}) is smaller than an edge of maximum weight in p . Then {u,v} is a path from u to v in G with weight smaller than the total weight of p , which must be larger than w({u,v}) as all edge weights are positive. This means that p is not a shortest path from u to v in G , a contradiction.

    For statement III), note that the minimum spanning tree is uniquely determined; this follows from the workings of the algorithm of Prim, as the distinct edge weights from property 1 from above make the choice of the lightest edge deterministic. Alternatively, this can be seen inductively by arguing that each spanning tree must contain an edge of minimum weight of G . In total, as the minimum spanning tree T is uniquely determined, there can be only one shortest path from u to v in G for each u,v in V , as each shortest path must be contained in T . If two such paths existed, T had a cycle, which is not the case.

    For statement IV), consider the following counterexample. Let G:=(V,E,w) where V:={1,2,3,4} , E:={{1,2},{1,3},{2,3},{2,4},{3,4}} and 

    w({1,2}):=01,
w({1,3}):=04,
w({2,3}):=10,
w({2,4}):=03,
w({3,4}):=09.

    Suppose Prim and Dijkstra start at node 1 . Then, the edges {1,2},{2,3},{3,4} consitute the uniquely determined minimum spanning tree T , which is generated by Prim in the sequence 1,2,4,3 .

    The path {1,2} is the only shortest path from 1 to 2 , {1,3} is the only shortest path from 1 to 3 ; {1,2}{2,4} is the only shortest path from 1 to 4 and {4,2}{2,1}{1,3} is the only shortest path from 4 to 3 . Furthermore, {2,3} is the only shortest path from 2 to 3 and {2,1}{1,4} is the only shortest path from 2 to 4 . In total, G has properties 1 and 2 from above.

    The choices of Dijkstra can be done as follows, where ++ denotes infinity. 

    Node                1  2  3  4
tentative distance 00 01 04 ++
discovered          y  n  n  n
=> select node 2

Node                1  2  3  4
tentative distance 00 01 04 04
discovered          y  y  n  n
=> select node 3 (could also select 4, as Prim, but selects 3)

Node                1  2  3  4
tentative distance 00 01 04 04
discovered          y  y  y  n
=> select node 4

    In total, the sequence of selected nodes is 1,2,3,4 , which differs from the sequence generated by Prim.

    I agree with Codor that Statement I is not necessarily true and Statement II is true. Codor's proof for Statements I and II are correct. However, I think that Statement III and not necessarily true and Statement IV is true.

    For Statement III, there is a counter example: There are 3 vertices A, B and C. There are 3 edges (A, B), (B, C) and (A, C) whose weights are 1, 2 and 3 respectively. The minimum spanning tree includes the edges (A, B) and (B, C). However, shortest path between A and C is not unique: either (i) (A, B), (B, C), or (ii) (A, C)

    Statement IV is correct. This could be proved by mathematical induction.

    链接地址: http://www.djcxy.com/p/35222.html

    上一篇: 最小化有向图中树路径的成本

    下一篇: 图表和PRIM和DIJKSTRA问题？