Networks and Network Diagrams
Theory
A network is a set of vertices joined by edges. The degree of a vertex counts its edges, and the degrees always add to twice the number of edges. This Year 10A maths page covers drawing network diagrams for real situations, naming routes (walk, trail, path, circuit, cycle), connected networks, complete networks and which lists of degrees are possible.
A network or graph is a set of points called vertices (nodes) joined by lines called edges. It can model friendships, flights, roads, computer links and many other systems. The same network can be drawn in many ways: only which vertices are joined matters.
The degree of a vertex is the number of edges that meet at it. A loop adds \(2\). Two vertices are adjacent if an edge joins them.
A walk is any sequence of vertices joined by edges. A trail repeats no edge. A path repeats no vertex (so no edge either). A circuit is a trail that finishes where it started, and a cycle is a circuit with no repeated vertex except the start and finish.
A network is connected if there is a path between every pair of vertices; otherwise it splits into separate pieces. In a complete network every pair of vertices is joined by exactly one edge.
When you model a real situation, decide what the vertices stand for (people, places, computers, teams) and what the edges stand for (friendships, roads, cables, games). Networks are used again in the networks topics of the senior general mathematics courses.
| Route | Repeat an edge? | Repeat a vertex? | Finish at start? |
|---|---|---|---|
| walk | allowed | allowed | either |
| trail | no | allowed | no |
| path | no | no | no |
| circuit | no | allowed | yes |
| cycle | no | no (only start = finish) | yes |
Working with a network
- Draw it from a list or table: one vertex for each object, one edge for each link. Place busy vertices in the middle to avoid clutter.
- Degrees: count the edge ends at each vertex. Check that the total is \(2\times\) the number of edges.
- Unknown degree: if degrees are given in terms of \(x\), set their sum equal to \(2e\) and solve.
- Naming a route: check that each step is an edge, then check repeated edges, repeated vertices and whether it returns to the start (Example 1).
- Fewest edges between two vertices: work outwards from the start, listing the vertices one edge away, then two edges away, until you reach the end.
- Counting paths from one vertex to another: list them in order of the first edge used, and never revisit a vertex.
- Closing a vertex: remove it with all its edges, then check whether the remaining network is still connected (Example 2).
- Games and handshakes: a game between two teams or a handshake between two people is an edge. Count edges with \(\dfrac{\text{sum of degrees}}{2}\), or with the complete-network formula when everyone meets everyone.
- Possible or not? First check the sum is even. Then, in a network with no repeated edges, no degree can be more than the number of other vertices, and high-degree vertices force the degrees of the others (Example 4).
(i) E–A–C–D
(ii) A–B–C–A–D
(iii) A–E–B–A–D–C–A
(iv) B–C–D–A–B
(v) D–A–B–A–E.
For each route ask: is an edge repeated? Is a vertex repeated? Does it finish where it started?
(i) No repeats and it does not return: a path.
(ii) Edges \(AB, BC, CA, AD\) are all different, but \(A\) is visited twice: a trail, not a path.
(iii) Six different edges and it returns to \(A\), but \(A\) is also visited in the middle: a circuit, not a cycle.
(iv) Returns to \(B\) with no other vertex repeated: a cycle.
(v) Edge \(AB\) is used twice (\(A\)–\(B\)–\(A\)): only a walk.
(i) Draw a network.
(ii) Find the degree of each vertex and check the sum.
(iii) Which one place, if closed with its tracks, would cut Camp off from Hut?
(iv) What is the least number of tracks from Lake to Cave?
(i) One vertex for each place and one edge for each track:
(ii) Camp \(2\), Lake \(2\), Peak \(3\), Falls \(3\), Cave \(2\), Hut \(2\). The sum is \(14 = 2\times 7\) tracks.
(iii) Every route from Camp to Hut passes through Peak and then Falls. Closing Peak or closing Falls would cut Camp off from Hut. Closing Lake or Cave would not, because there is another way around.
(iv) Lake–Peak–Falls–Cave uses \(\mathbf{3}\) tracks. No shorter route exists, because Lake is not joined to Falls.
(i) How many edges does the complete network on \(9\) vertices have?
(ii) In a sports competition every team plays every other team once, and \(78\) games are played. How many teams are there?
With \(n\) vertices, each vertex has degree \(n - 1\). The degrees add to \(n(n-1)\), which counts every edge twice.
| \(e\) | \(=\) | \(\dfrac{n(n-1)}{2}\) |
(i)
| \(e\) | \(=\) | \(\dfrac{9\times 8}{2} = \mathbf{36}\) |
(ii) Teams are vertices and games are edges.
| \(\dfrac{n(n-1)}{2}\) | \(=\) | \(78\) |
| \(n^2 - n - 156\) | \(=\) | \(0\) |
| \((n - 13)(n + 12)\) | \(=\) | \(0\) |
| \(n\) | \(=\) | \(\mathbf{13}\quad (n \gt 0)\) |
Check: \(\dfrac{13\times 12}{2} = 78\).
(i) \(3, 3, 2, 2, 1\)
(ii) \(5, 2, 2, 1, 1, 1\)
(iii) \(3, 3, 3, 1\)?
(i) The sum is \(11\), which is odd. The sum of the degrees is always \(2e\), an even number, so this is impossible.
(ii) The sum is \(12\), so there would be \(6\) edges. With \(6\) vertices, the degree-\(5\) vertex is joined to all \(5\) others. That gives every other vertex \(1\) so far; one more edge between the two vertices that need degree \(2\) finishes it. Possible.
(iii) The sum is \(10\), which is even, but that is not enough. With only \(4\) vertices, a vertex of degree \(3\) is joined to all \(3\) others. Three such vertices are all joined to the fourth vertex, so its degree is at least \(3\), not \(1\). Impossible.
An even sum is needed, but it does not guarantee the network exists. Try to draw it.
Common pitfalls
Frequently asked questions
What is the degree of a vertex?
The degree of a vertex is the number of edges that meet at it. A loop that starts and finishes at the same vertex adds 2 to its degree.
Why is the sum of the degrees twice the number of edges?
Every edge has two ends, and each end adds 1 to the degree of a vertex. So adding all the degrees counts every edge exactly twice.
What is the difference between a trail and a path?
A trail never uses the same edge twice but may revisit a vertex. A path never revisits a vertex, so it cannot repeat an edge either.
What is the difference between a circuit and a cycle?
Both finish where they started without repeating an edge. A cycle also visits no vertex twice except the start and finish; a circuit is allowed to pass through a vertex more than once.
How many edges does a complete network have?
With \(n\) vertices, each vertex joins the other \(n - 1\), and each edge is shared by two vertices, so there are \(\dfrac{n(n-1)}{2}\) edges. For \(9\) vertices that is \(36\).