Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am trying to prove the following:

For any positive natural n, there exists an undirected graph of n nodes, positive natural edge widths, and nodes s and t such that a uniform-cost search from s examines all the nodes, whereas the optimal path from s to t consists of only a single edge.

share|improve this question
add comment

1 Answer 1

Here's a proof by induction. However, the case $n=1$ is a special case. Say node $s$ is also node $t$. Otherwise, if this is not allowed, then it cannot be proven.

Now the real base case is $n=2$. This is trivial. The graph that satisfies this case consists of two nodes $s$ and $t$, connected together. Note that the edge from $s$ to $t$ is visited last.

For the inductive case, consider that we have the graph of $n$ nodes, and the edge from $s$ to $t$ is visited last. Then we add another node, connect it to $s$ with a cost less than the cost from $s$ to $t$. Thus it will be visited before the edge between $s$ and $t$, so we have preserved that the edge from $s$ to $t$ will be visited last. Further, we have now shown an example for $n+1$, therefore this proves the inductive case. QED

share|improve this answer
1  
Is induction really necessary? Maybe I don't understand the problem, but it seems to me all you need is an edge from $s$ to $t$, and edges from $s$ to each $v_i$, $3\le i\le n$, and each $v_i$ to $t$, such that each $sv_i$ costs less than $st$ but each $v_it$ costs more than $st$ minus $sv_i$. –  Gerry Myerson May 1 '11 at 4:23
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.