A full network investigation

Investigate a network

A network investigation combines counts, parity, route comparisons and a minimum spanning tree. Each calculation answers a different question, so state the object being measured before using a number

1. Include the outer face For a connected planar graph, Euler's formula counts the infinite outer face as well as the enclosed regions \(\displaystyle v+f=e+2\)
2. Use the degree sum The sum of all vertex degrees is twice the number of edges \(\displaystyle \sum\deg(v)=2e\)
3. Use odd vertices for Euler routes In a connected graph, zero odd vertices allows a circuit and two odd vertices give the endpoints of an open trail \(\displaystyle o=0\Rightarrow\text{circuit},\quad o=2\Rightarrow\text{open trail}\)
4. Keep optimisations separate A shortest path joins two specified vertices, while a minimum spanning tree reaches every vertex \(\displaystyle \text{shortest path}:A\to D,\quad \text{MST}:V(G)\)

Worked example

A connected planar network has vertices A, B, C, D, E and F. The edge weights are given below in kilometres. Find its face count, number of odd-degree vertices, shortest-path length from A to D and minimum spanning-tree total

1. \(\displaystyle f=e+2-v=8+2-6=4\)Euler's formula gives four faces for the connected planar graph
2. \(\displaystyle (\deg A,\deg B,\deg C,\deg D,\deg E,\deg F)=(4,2,3,3,2,2)\Rightarrow o=2\)Only C and D have odd degree, so there are two odd-degree vertices
3. \(\displaystyle A\!-\!D:6,\quad A\!-\!C\!-\!D:5+3=8,\quad A\!-\!B\!-\!C\!-\!D:2+9+3=14,\quad A\!-\!F\!-\!E\!-\!D:7+4+8=19\)Comparing the sensible route totals shows that A-D is shortest, with length 6 kilometres
4. \(\displaystyle 2+3+4+5+7=21\text{ km}\)Prim’s algorithm from A selects AB (2), AC (5), CD (3), AF (7), FE (4). Each is the lightest edge from the reached set to an unreached vertex, giving total 21 kilometres

Common mistakes

Difficulty levels

Questions about this topic

In this chapter