$(10$ points$)$ A$-$Z Flows and Planar Graphs. Suppose a Network is a planar

graph and $a($the left$-$most vertex$)$ and $z($the right$-$most vertex$)$ are both on

the unbounded region surrounding the network. Construct the Dual Network

as follows: first add edges $($rays$)$ connecting vertex $a$ to infinity to the left

and vertex $z$ to infinity to the right. Give each ray infinite capacity $($weight$).$

Now form the dual graph by placing a vertex in the center of every face and

connecting the centers of faces which share an edge by a new edge which passes

through the midpoint of the old edge. Assign a weight to each dual edge that

is equal to the weight of the edge it crosses.

$($a$)$ Show that a shortest path from the center of the upper unbounded face in

the dual network to the lower unbounded face corresponds to a minimal

$a-z$ cut in the original network. This will require you to show that paths in

the dual correspond to cuts in the original, AND that this correspondence

sends shorter paths to lower$-$capacity cuts.

$($b$)$ Draw the dual network for the network shown above $($right$),$ and find the

shortest path, using the algorithm from Problem $1,$ from the vertex cor$-$

responding to the upper unbounded face to that of the lower unbounded

face. Give a minimal $a-z$ cut for $N.$