AGT Questions Solution

Question 3

Part (a) [7 Marks]

Given initial adjacency matrix $A^0$:

$$A^0=\left(\begin{array}{cccc}0& 3& \infty & 7\\ 8& 0& 2& \infty \\ 5& \infty & 0& 1\\ 2& \infty & \infty & 0\end{array}\right)$$

Iteration 1 (k=1):

$A_{ij}^1=\min (A_{ij}^0,A_{i1}^0+A_{1j}^0)$

$$A^1=\left(\begin{array}{cccc}\min (0,0+0)& \min (3,0+3)& \min (\infty ,0+\infty )& \min (7,0+7)\\ \min (8,8+0)& \min (0,8+3)& \min (2,8+\infty )& \min (\infty ,8+7)\\ \min (5,5+0)& \min (\infty ,5+3)& \min (0,5+\infty )& \min (1,5+7)\\ \min (2,2+0)& \min (\infty ,2+3)& \min (\infty ,2+\infty )& \min (0,2+7)\end{array}\right)=\left(\begin{array}{cccc}0& 3& \infty & 7\\ 8& 0& 2& 15\\ 5& 8& 0& 1\\ 2& 5& \infty & 0\end{array}\right)$$

Iteration 2 (k=2):

$A_{ij}^2=\min (A_{ij}^1,A_{i2}^1+A_{2j}^1)$

$$A^2=\left(\begin{array}{cccc}\min (0,3+8)& \min (3,3+0)& \min (\infty ,3+2)& \min (7,3+15)\\ \min (8,0+8)& \min (0,0+0)& \min (2,0+2)& \min (15,0+15)\\ \min (5,8+8)& \min (8,8+0)& \min (0,8+2)& \min (1,8+15)\\ \min (2,5+8)& \min (5,5+0)& \min (\infty ,5+2)& \min (0,5+15)\end{array}\right)=\left(\begin{array}{cccc}0& 3& 5& 7\\ 8& 0& 2& 15\\ 5& 8& 0& 1\\ 2& 5& 7& 0\end{array}\right)$$

Iteration 3 (k=3):

$A_{ij}^3=\min (A_{ij}^2,A_{i3}^2+A_{3j}^2)$

$$A^3=\left(\begin{array}{cccc}\min (0,5+5)& \min (3,5+8)& \min (5,5+0)& \min (7,5+1)\\ \min (8,2+5)& \min (0,2+8)& \min (2,2+0)& \min (15,2+1)\\ \min (5,0+5)& \min (8,0+8)& \min (0,0+0)& \min (1,0+1)\\ \min (2,7+5)& \min (5,7+8)& \min (7,7+0)& \min (0,7+1)\end{array}\right)=\left(\begin{array}{cccc}0& 3& 5& 6\\ 7& 0& 2& 3\\ 5& 8& 0& 1\\ 2& 5& 7& 0\end{array}\right)$$

Iteration 4 (k=4):

$A_{ij}^4=\min (A_{ij}^3,A_{i4}^3+A_{4j}^3)$

$$A^4=\left(\begin{array}{cccc}\min (0,6+2)& \min (3,6+5)& \min (5,6+7)& \min (6,6+0)\\ \min (7,3+2)& \min (0,3+5)& \min (2,3+7)& \min (3,3+0)\\ \min (5,1+2)& \min (8,1+5)& \min (0,1+7)& \min (1,1+0)\\ \min (2,0+2)& \min (5,0+5)& \min (7,0+7)& \min (0,0+0)\end{array}\right)=\left(\begin{array}{cccc}0& 3& 5& 6\\ 5& 0& 2& 3\\ 3& 6& 0& 1\\ 2& 5& 7& 0\end{array}\right)$$

Final Answer:

The shortest path matrix is:

$A^4=\left(\begin{array}{cccc}0& 3& 5& 6\\ 5& 0& 2& 3\\ 3& 6& 0& 1\\ 2& 5& 7& 0\end{array}\right)$

Part B Prove that every planar graph has a dual.

Proof

1. Planar Embedding: A planar graph, G, by definition, has a planar embedding (a drawing in the plane with no edge crossings).

2. Faces: This embedding divides the plane into faces (regions bounded by edges, including the unbounded outer face).

3. Dual Graph Construction: We construct the dual graph, $G^{\ast }$, as follows:

   • For each face f in the planar embedding of G, create a vertex $v_f$ in $G^{\ast }$.
   • For each edge e in G, if e is on the boundary of two faces, $f_1$ and $f_2$, draw an edge $e^{\ast }$ in $G^{\ast }$ connecting $v_{f_1}$ and $v_{f_2}$. If e is only on one face, draw a loop on the corresponding vertex.

4. Dual is a Graph: The result of this construction, $G^{\ast }$, is a graph (possibly with multiple edges or loops). This is because each edge in the dual corresponds to a unique edge in the original graph, and each vertex in the dual corresponds to a unique face in the original graph’s planar embedding.

Conclusion: Therefore, given any planar graph G, we can always construct its dual graph, $G^{\ast }$, based on its planar embedding. This proves that every planar graph has a dual.