Question

. Provide a weighted directed graph G = (V, E, c) that includes three vertices a, b, and c, and for which the maximum-cost simple path P from a to b includes vertex c, but the subpath from a to c is not the maximum-cost path from a to c

Answer 1

the graph contains three vertices a,b,c.

Also it should satisfy two conditions according to the question. They are,

1. the maximum-cost simple path P from a to b includes vertex c.

2. the subpath from a to c is not the maximum-cost path from a to c.

Here the maximum cost simple path means, the path cost should be maximum and it should not have any repeating edges.

So lets assume a directed graph with given three vertices and let there exist four edges with certain costs as:

edge ac, with cost 2

edge ab with cost 1

edge bc with cost 4

edge cb with cost 3

so the graph look like this:

here all the given condtions are satisfied as:

condition 1. the maximum-cost simple path P from a to b includes vertex c.

so the found P is a------c--------b

the maximum cost path is found between a and b vertices and the maximum cost is:

cost of edge ac + cost of edge cb

=2 + 3 = 5

But this wont be the case when direct path from vertice a to b is chosen, we only get a cost less than 5, that is 1

so our maximum cost simple path always has vertex c included.

condition 2: the subpath from a to c is not the maximum-cost path from a to c.

this is also satisfied, because, the cost of subpath a to c is having the cost 2

while the path from a to c through b is a-----b------c

with cost, =

cost of edge ab + cost of edge bc = 1 +4 = 5 which is the maximum cost simple path.

So the maximum cost simple path is a-----b------c and NOT the subpath ac

Thus we obatined a weighted directed graph G = (V, E, c) that includes three vertices a, b, and c, and for which the maximum-cost simple path P from a to b includes vertex c, but the subpath from a to c is not the maximum-cost path from a to c.