Networks and network terminology

What a network is

• A network (also called a graph) is a set of points joined by lines. It is a model of anything made of connections.
• The two parts:
  • Nodes (also called vertices) — the dots. They stand for places or objects: towns, buildings, computers, intersections.
  • Arcs (also called edges) — the lines. They stand for connections: roads, cables, pipes, flights.
• A network records what is connected to what. It does not record position, direction on the page, or scale.
• This is the single most important idea in the topic. Two drawings that look completely different are the same network if the same nodes are joined by the same arcs. Where you place the dots is your choice.

Weights

• A weight is a number attached to an arc. It measures the "cost" of using that connection.
• The weight can be anything the context measures:
  • Distance — kilometres of road
  • Time — minutes of travel
  • Money — dollars to lay a cable
  • Capacity — litres per second in a pipe
• A network with weights is a weighted network. All three methods in this standard use the weights.
• Read the units off the question and keep them. A shortest path of "18" is meaningless; "18 km" or "18 minutes" is an answer.

The degree of a node

• The degree of a node is the number of arcs meeting at it.
• Count arc-ends, not neighbours. If two separate arcs both run to the same node, the degree still goes up by 2.
• A node is odd or even according to its degree. This matters enormously for traversability later.
• The handshake check — the degrees of all the nodes always add to twice the number of arcs:

$$\sum \text{degrees} = 2 \times (\text{number of arcs})$$

• Each arc has two ends, and each end contributes 1 to somebody's degree. So the total is always even, and a network always has an even number of odd nodes.
• Use this as a check every time you write down a degree table. If your degrees do not add to twice the arcs, you have miscounted.

Walks, paths and cycles

• A walk is any sequence of arcs travelled one after another.
• A path is a walk that does not repeat a node. This is what "route" usually means in a question.
• A cycle (or circuit) is a path that starts and finishes at the same node.
• A trail is a walk that does not repeat an arc, but may repeat a node. Traversability is about trails.
• The distinction matters. "Every arc once" (a trail) and "every node once" (a path) are different problems with different answers — and only the first is in this standard.

Connected networks and components

• A network is connected if you can get from every node to every other node by some route.
• If not, it splits into components — separate pieces with no arc between them.
• A network must be connected before a spanning tree exists. If the map shows an island with no bridge, no amount of algorithm will connect it — say so.

Trees

• A tree is a connected network with no cycles.
• Two facts follow, and both are worth memorising:
  • A tree on $n$ nodes has exactly $n - 1$ arcs.
  • There is exactly one route between any two nodes in a tree.
• A tree is the cheapest kind of connected network, because every arc is essential — remove one and the network falls into two pieces.

Directed networks

• In a directed network (a digraph) the arcs have arrows and can only be travelled one way.
• One-way streets, uphill/downhill travel times and pumped flows are all modelled this way.
• Directions change the answer: the shortest path from A to F need not be the reverse of the shortest path from F to A.
• Unless a question shows arrows, treat every arc as two-way.

Reading a network out of a context

• Internal tasks usually give you a table of distances, a map, or a paragraph of description — not a finished network.
• Turn it into a network first, in three steps:
  • Identify the nodes — what are the places or objects being connected?
  • Identify the arcs — which pairs are directly joined? A blank cell in a table means no direct connection, not distance zero.
  • Label every arc with its weight, and state the units.
• Redraw for clarity. Spread the nodes out so arcs cross as little as possible. Crossing lines cause more errors in this standard than the arithmetic does.