7.02p–7.02r - Networks, matrices and modelling
Translate a connection problem into a graph or weighted network, then store and use its information in a matrix. In you will choose vertices, arcs, directions and weights; in you will construct adjacency and weighted matrices; in you will solve small problems and interpret the answers in context.
Choosing a network model
A direct trip takes minutes, but two successive links take and minutes. Can a route with more arcs take less time? Yes: counting connections and adding their costs answer different questions. We will use a small network to find the quickest route, then see what a one-way restriction changes.
You already know
Vertices represent objects and arcs their connections. In a digraph an arrow specifies a direction. Matrices have labelled rows and columns, and corresponding entries refer to corresponding positions.
A graph can model whether places are connected. To decide which journey is quicker, attach the travel time to each arc. In this model a vertex is a place where a route can start, finish or change links. An unmarked crossing of two roads need not be a junction.
Network
A network is a weighted graph: each arc has a weight representing a stated quantity, such as distance, time or cost. Graphs and networks may be directed or undirected. An undirected arc permits travel both ways; a directed arc permits only its stated direction. This terminology is not supplied in the formula booklet.
Choose the model deliberately. For a road journey, state what each vertex represents, what each arc means and the units of its weight. A two-way link of the same cost in either direction can be undirected. Different costs in the two directions require directed arcs, even if both directions are available.
A route's total time is the sum of its arc times when the model assumes fixed travel times and no extra waiting at vertices. If delays at a junction matter, they must also enter the model. A weight labelled capacity has a different interpretation from a weight labelled time; do not add weights without asking what they mean.
Key idea
The story determines the vertices, connections, directions, weights and assumptions. The drawing records that chosen model.
For example, , so an indirect journey can beat a direct one even though it uses more arcs.
Adjacency matrices
A matrix records a graph without depending on a particular drawing. Fix the vertex order first: changing it permutes the rows and columns, even though the underlying graph is unchanged.
Adjacency matrix
For an ordered vertex list, the adjacency matrix records the number of arcs from the row vertex to the column vertex . In an undirected graph each ordinary arc is recorded in both symmetric positions. A loop is recorded once in its diagonal entry. A simple graph has only zeros and ones, with a zero diagonal. This convention is not supplied in the formula booklet.
For a digraph, row sums give outdegrees and column sums give indegrees, including loops once in each. These degree-sum matrix rules are not supplied in the formula booklet. For an undirected graph with no loops, row sums give degrees. With loops, add the diagonal entry once more to count each loop twice. A symmetric adjacency matrix is consistent with undirected connections, but can also describe a digraph with matching opposite arcs; the stated model decides which interpretation is intended.
[DIAGRAM: asset_name: A graph and its adjacency matrix; asset_slug: h245_7_02_adjacency_matrix; caption: Entry in row A and column C is one because A and C are adjacent; description: The undirected graph has arcs AB AC BC CD, alongside its labelled four-by-four adjacency matrix in order A B C D, rows 0110, 1010, 1101, 0010. Symmetric entries A C and C A are accented.]
Worked example 1: an undirected adjacency matrix
Question. A graph has vertices and arcs . Write its adjacency matrix in that vertex order.
Plan. Enter one for each listed connection in both directions, with zero elsewhere.
Why this step? Fixing one vertex per row makes every connection checkable and avoids counting a crossing as an adjacency.
Answer.
Check. It is symmetric; row sums total , twice the four arcs.
The second example changes only direction: the same four links become arrows .
Worked example 2: a directed adjacency matrix
Question. Write the adjacency matrix of that digraph in order .
Plan. Keep rows as “from” and columns as “to”; do not add reverse entries.
Why this step? The reverse of an available directed connection need not exist.
Answer.
Check. Row sums total four outgoing arcs, and column sums total four incoming arcs.
To reconstruct a drawing from a matrix, draw its labelled vertices and add exactly the arcs specified by its entries. The entries determine the connections, not where the vertices should sit.
Watch out
Wrong: “A in an adjacency matrix is an arc of weight two.” An adjacency entry counts arcs; a means two arcs. Weights belong in a weighted matrix.
The next digraph includes both a repeated arc and a loop, so keep the count interpretation.
Weighted matrices
The adjacency matrix tells you whether a link exists and how many copies there are. A weighted matrix records the numerical value attached to a direct link instead.
Weighted matrix
A weighted matrix records direct-arc weights with a stated row and column order. For directed networks, rows mean “from” and columns mean “to”. Use a clearly defined symbol for an absent arc. In this lesson, a dash means “no direct arc”, including the diagonal when there is no loop; a numerical zero would mean an actual zero-weight arc. These conventions are not supplied in the formula booklet.
Continue this lesson.
You’re previewing NovaLearn without an account. Create a free account to read the rest.
Create free account