Past exam of the Probability, statistics and options II course of the University of Oxford / 2007 / S

Take a shortest allowed simple graph path. If it does not use $k$ as an intermediate vertex, its length is at least $u_{ij}^{(k-1)}$. If it does, simplicity makes $k$ occur only once. Splitting there gives an $i$--$k$ path and a $k$--$j$ path whose intermediate vertices are in $\{1,\dots ,k-1\}$. Their lengths are at least the respective two minima. In either case,For identical endpoints use the usual empty path of length zero.

An old shortest graph path is still allowed at stage $k$, so $u_{ij}^{(k)}\le u_{ij}^{(k-1)}$. Concatenating shortest $i$--$k$ and $k$--$j$ paths gives a walk of length $u_{ik}^{(k-1)}+u_{kj}^{(k-1)}$, but it may repeat vertices. Every repeated section is a closed walk. In the absence of negative-length cycles in a graph, each such closed walk has nonnegative length: decompose it into simple cycles. Removing these sections therefore produces an allowed simple graph path of no greater length. This proves the other upper bound. Together with part (a),

Initialize an $n\times n$ array $d$ with $d_{ii}=0$ and $d_{ij}=a_{ij}$ for $i\ne j$. For $k=1,\dots ,n$, replace every entry in place byThis is the Floyd-Warshall algorithm. At the start of stage $k$, the induction hypothesis is $d_{ij}=u_{ij}^{(k-1)}$. During that stage, row $k$ and column $k$ do not change: $d_{kk}=0$ and no negative cycle can lower it. Hence the operands $d_{ik},d_{kj}$ remain the stage-start values even with in-place updates. Part (b) proves that after the stage every entry is $u_{ij}^{(k)}$. Induction gives all shortest path lengths after stage $n$. The algorithm uses $n^2$ stored lengths and $O(n^3)$ arithmetic operations, with only a fixed number of loop counters beyond the array.

Use four vertices, with lengths $a_{12}=a_{24}=0$, $a_{23}=a_{32}=-1$, and every other non-loop arc of length $100$. The two arcs between $2$ and $3$ form a negative-length cycle in a graph. For $i=1$, $j=4$, $k=3$,The recurrence would give $-2$, by concatenating $1\to 2\to 3$ and $3\to 2\to 4$. That walk repeats $2$, so it is not a simple graph path. Every simple graph path from $1$ to $4$ still has length at least zero, attained by $1\to 2\to 4$. Thusa strict inequality in part (a).

For every perfect matching $M$, each vertex occurs exactly once, so the feasibility inequalities giveIf a perfect matching $M^{\ast }$ uses only tight edges, equality holds. It therefore attains a lower bound valid for every perfect matching, proving minimum cost. In a bipartite graph this is the weak duality and complementary slackness certificate for the assignment problem. The Hungarian algorithm maintains feasible row and column potentials and seeks a perfect matching among tight edges.

Begin with $u=v=0$ and the printed matching $\{(1,1),(3,2),(5,3)\}$. Grow an alternating tree from unmatched row two. Its tight edge reaches column two, whose matched row is three. Thus the reached row set is $S=\{2,3\}$ and the reached column set is $T=\{2\}$. Among unreached columns the reduced costs are $(6,5,4,4)$ from row two and $(3,4,2,3)$ from row three, so their minimum is two.

Increase $u_2,u_3$ by two and decrease $v_2$ by two. The new tight edge $(3,4)$ reaches an unmatched column. Augment along $2\to 2\to 3\to 4$, replacing $(3,2)$ by $(2,2),(3,4)$. The matching becomes $\{(1,1),(2,2),(3,4),(5,3)\}$.

Now grow from unmatched row four. Edge $(4,1)$ reaches matched row one, and edge $(1,5)$ reaches unmatched column five. Augment along $4\to 1\to 1\to 5$, replacing $(1,1)$ by $(4,1),(1,5)$. This yieldsNo further potential update is needed. The final potentials are $u=(0,2,2,0,0)$ and $v=(0,-2,0,0,0)$. Their reduced-cost matrix isEvery entry is nonnegative and every chosen entry is zero. The dual sum is $\sum u_i+\sum v_j=2$, so part (a) certifies optimality.

Before a potential update, let $S$ be the reached rows and $T$ the reached columns in an alternating forest grown from unmatched rows. Every reached column is matched, or an augmentation would already have occurred, and its matched row is reached. Each tree has one more reached row than reached column, so $|S|-|T|>0$.

The update amount is the smallest slack across $S\times T^c$. It is strictly positive because all zero-slack edges have already been explored, and the complete assignment problem guarantees that the set is nonempty before a perfect matching is found. Increasing $u_i$ for $i\in S$ and decreasing $v_j$ for $j\in T$ therefore increases the dual sum byAll feasibility inequalities remain valid by the definition of the minimum slack.