Three checks classify a network: are there arrows, are there numbers on the edges, and are there loops or repeated edges. Each check is separate, so one graph can be more than one type.
This lesson follows representing a real network as a graph in the SPM Mathematics networks chapter.
What are the three checks?
| Feature | Check | Name |
|---|---|---|
| Arrows on edges | Do edges have a direction? | Directed |
| Numbers on edges | Does each edge carry a value? | Weighted |
| Loops or repeated edges | Is any edge from a vertex to itself, or are two edges between the same pair? | Not simple |
A graph with no loops and no repeated edges passes the simple test. It can pass and still be directed or weighted.
Worked example: three situations
Situation 1. Four towns are joined by roads, and every road can be driven both ways. No road loops back, and no pair has two roads. The graph is simple and undirected.
Situation 2. The same towns, but the roads are labelled 12 km, 8 km, 15 km and 6 km. The graph is weighted, and it is still simple.
Situation 3. In a canteen, one-way arrows lead from the counter to each table. Table 2 has two arrows from the counter, one for each route. The graph is directed, and it is not simple because one pair has two edges.
The mistake that costs marks
The common slip is to read the number on an edge as the degree of a vertex, or the reverse. A weight is written beside an edge. A degree is counted at a vertex.
| Weight | Degree | |
|---|---|---|
| Belongs to | An edge | A vertex |
| Where you find it | Written on the graph | Counted from the graph |
| Example | 12 km on the road AB | 3 roads meet at A |
If a question asks for “the degree of A”, count edges at A. Do not add the weights.
Check yourself
A network has vertices P, Q and R. Edges: P to Q with weight 5, Q to R with weight 3, and a loop at R. All edges are two-way. Classify it.
Answer
Arrows: none, so the graph is undirected.
Numbers: P to Q and Q to R carry weights, so the graph is weighted. The loop has no weight given, so the labelling is incomplete.
Loop: there is a loop at R, so the graph is not simple.
What to study next
The weights are what make route finding possible. Continue with finding efficient routes in a small weighted network. Compare drawings with the graph evidence and fair-comparison lab, and log slips in the mistake log and paper-error review.
If you want a teacher to test your classification on new networks, see online one-to-one Mathematics tuition.