Adjacency Matrices · applications

Applications: Adjacency Matrices

10 question types · Pre-University · each worked step by step with a figure that follows the steps

01

Signposts at the Junctions of a Country Park, Read Off the Park's Road Matrix

methodRead Each Row as the Roads at One Junction, Count a Loop Road at Both of Its Ends, and Halve Only the Entries Off the Diagonal

The roads of a country park join four junctions, P, Q, R and S, and the park's map records them in a matrix. The entry in row X and column Y is the number of roads joining junction X directly to junction Y. A loop road, which leaves a junction and comes back to it without passing any other junction, is entered once, as a 1 in that junction's own row and column. With rows and columns in the order P, Q, R, S, the matrix is 0210201111120120. At every junction, a signpost has one arm for each way a driver can leave the junction along a road. (a) How many arms does the signpost at junction R need? (b) How many roads are there in the park?

PQRSPQRSP0210Q2011R1112S0120Row R, column R: the loop, entered once
Each junction is a vertex and each road an edge. The two roads between P and Q and the two between R and S are the 2s; the loop at R is the 1 on the diagonal.
Model the park as a graph: a vertex for each junction and an edge for each road. The signpost at a junction needs one arm for each road end there, so the number of arms is the degree of the vertex. The matrix is symmetric, because a road joining X to Y also joins Y to X.
step 1 of 5

Draw the park as a graph with a vertex for each junction and an edge for each road. The arms of a signpost count the ends of roads at that junction, which is the degree of the vertex. An ordinary road has one end at each of its two junctions, and a loop road has both of its ends at the same junction.

  1. Model the park as a graph: a vertex for each junction and an edge for each road. The signpost at a junction needs one arm for each road end there, so the number of arms is the degree of the vertex. The matrix is symmetric, because a road joining X to Y also joins Y to X.
  2. Read row R, which is 1, 1, 1, 2. The entries off the diagonal say that R has 1 road to P, 1 road to Q and 2 roads to S, which gives 1 + 1 + 2 = 4 road ends. The 1 in column R is the loop road, and it has both of its ends at R.
  3. (a) The degree of R is 4 + 2 = 6, so the signpost at R needs 6 arms. Adding the row alone gives 5, one short, because the loop is entered once but a driver can leave along it in two directions.
  4. For the number of roads, add the entries off the diagonal, row by row: 3 + 4 + 4 + 3 = 14. Each road between two different junctions appears twice in this total, once in the row of each of its junctions, so there are 14 ÷ 2 = 7 such roads.
  5. (b) The diagonal holds one loop, entered once, so the park has 7 + 1 = 8 roads. Check: the degrees are 3, 4, 6 and 3, which add up to 16 = 2 × 8, as they must, since every road has two ends.

answer(a) 6 arms; (b) 8 roads

techniqueThe Adjacency Matrix

Common pitfalls

  • Taking the row total, 5, as the number of arms at R. The loop road is entered as a single 1, but a driver can set off along it in either direction, so it needs two arms.
  • Halving the total of every entry in the matrix, 15 ÷ 2, which is not a whole number. The loop is entered once, not twice, so it has to be counted on its own and not halved.
02

Who Follows Whom Among Five Friends on a Photo-Sharing App, Read From a Matrix of Follows

methodRead Across a Row for the Accounts One Person Follows and Down a Column for That Person's Followers, and Compare Each Entry With Its Mirror Across the Diagonal

Five friends, Ana, Ben, Cai, Dee and Eve, use a photo-sharing app on which one account can follow another without being followed back. Their follows are recorded in a matrix with rows and columns in the order Ana, Ben, Cai, Dee, Eve: the entry in row X and column Y is 1 when X follows Y, and 0 otherwise. The matrix is 0110110100000100110110100. (a) Which of the five has the most followers among the others, and how many? (b) How many pairs of the five follow each other?

ABCDEA Ana, B Ben, C Cai, D Dee, E EveABCDEA01101B10100C00010D01101E10100Row X: whom X follows. Column Y: who follows Y.
Each friend is a vertex, with an arc from X to Y when X follows Y. A line with two heads is a pair who follow each other.
Model the follows as a directed graph: a vertex for each friend and an arc from X to Y when X follows Y. Row X lists the accounts X follows, so a row total is an out-degree. Column Y lists the friends who follow Y, so a column total is an in-degree, the number of followers.
step 1 of 6

Draw the follows as a directed graph, with an arc from X to Y when X follows Y. A row of the matrix lists the accounts one friend follows, and a column lists the friends who follow one account. Two friends follow each other when the matrix has a 1 in both of the places that mirror each other across the main diagonal.

  1. Model the follows as a directed graph: a vertex for each friend and an arc from X to Y when X follows Y. Row X lists the accounts X follows, so a row total is an out-degree. Column Y lists the friends who follow Y, so a column total is an in-degree, the number of followers.
  2. Add each column: Ana 0 + 1 + 0 + 0 + 1 = 2, Ben 1 + 0 + 0 + 1 + 0 = 2, Cai 1 + 1 + 0 + 1 + 1 = 4, Dee 0 + 0 + 1 + 0 + 0 = 1 and Eve 1 + 0 + 0 + 1 + 0 = 2.
  3. (a) Cai has the most followers, 4: every other friend follows Cai. Cai's own row adds up to only 1, so Cai follows just one of them, Dee.
  4. X and Y follow each other when the entry in row X, column Y and the entry in row Y, column X are both 1. These two entries mirror each other across the main diagonal, so check each 1 above the diagonal against its mirror below it.
  5. Above the diagonal there are 1s for Ana and Ben, Ana and Cai, Ana and Eve, Ben and Cai, Cai and Dee, and Dee and Eve. Their mirrors are 1 for Ana and Ben, Ana and Eve, and Cai and Dee, and 0 for the other three.
  6. (b) 3 pairs follow each other: Ana and Ben, Ana and Eve, and Cai and Dee. Check: the diagonal of A2, where A is the matrix, counts for each friend the follows that are returned. It reads 2, 1, 1, 1, 1, which adds up to 6, twice the number of pairs.

answer(a) Cai, with 4 followers; (b) 3 pairs: Ana and Ben, Ana and Eve, and Cai and Dee

techniqueThe Adjacency Matrix · Counting Walks with Matrix Powers

Common pitfalls

  • Adding the rows instead of the columns. A row total counts whom a friend follows: Ana and Dee each follow 3, but the question asks for followers, and those are counted down a column.
  • Counting the 1s on both sides of the diagonal, which gives 6. Each pair that follows both ways shows up once above the diagonal and once below it, so it must be counted once.
03

A Ranger's Matrix of Hiking Trails Between Five Huts, With One Entry Typed Wrongly

methodCheck Each Entry Against Its Mirror Across the Diagonal, Let the Number of Trails on the Map Decide Which of the Two Entries Is Wrong, and Add the Corrected Rows

A park ranger types up the trails between five mountain huts, A, B, C, D and E, as a matrix. Every trail can be walked both ways and joins two different huts, and no two trails join the same pair. The entry in row X and column Y is 1 when a trail joins X and Y, and 0 otherwise. With rows and columns in the order A, B, C, D, E, the ranger's matrix is 0111010010100100110100010. Exactly one entry was typed wrongly, and the trail map shows 6 trails. (a) Which entry is wrong, and what should it be? (b) Which hut has the most trails, and how many?

ABCDEA01110B10010C10010D01101E00010Trails run both ways, so the matrix should be symmetric
The ranger's matrix. A trail joins its two huts both ways, so each entry should equal its mirror across the diagonal.
Every trail runs both ways, so a correct matrix is symmetric across its main diagonal. Compare each entry above the diagonal with its mirror below it.
step 1 of 5

A trail joins its two huts both ways, so the matrix of a trail network is symmetric: the entry in row X, column Y equals the entry in row Y, column X. A pair of mirrored entries that disagree holds the mistake, and the number of trails on the map shows which of the two is wrong.

  1. Every trail runs both ways, so a correct matrix is symmetric across its main diagonal. Compare each entry above the diagonal with its mirror below it.
  2. Every pair of mirrored entries matches except the pair for A and D: row A, column D holds 1, but row D, column A holds 0. So one of these two entries is the wrong one.
  3. Decide which with the number of trails. If A and D are joined, the trails are A–B, A–C, A–D, B–D, C–D and D–E, which makes 6. If they are not joined, there are only 5. The map shows 6, so the trail between A and D is there.
  4. (a) The wrong entry is in row D, column A: it should be 1, not 0. Check: the corrected matrix has entries adding up to 12 = 2 × 6, while the typed one adds up to 11, an odd number, which the matrix of a trail network can never have.
  5. (b) The corrected row totals are A 3, B 2, C 2, D 4 and E 1. Hut D has the most trails, 4, to A, B, C and E. The typed matrix gave D only 3, level with A.

answer(a) Row D, column A: it should be 1, not 0; (b) hut D, with 4 trails

techniqueThe Adjacency Matrix

Common pitfalls

  • Changing row A, column D to 0 because the 0 in row D looks like the entry that fits. Either of the two entries could be the slip; only the 6 trails on the map show which one it is.
  • Reading the degrees from the typed matrix, which puts A and D level on 3 trails. The wrong entry is in row D, so row D has to be corrected before its total means anything.
04

An Aircraft's Day of Flights Between Four Airports, Counted From the Route Matrix

methodWrite the Routes as an Adjacency Matrix, Square It for Days of Two Flights and Multiply Once More for Three, and Read the Entry for the Start and the Finish

A regional airline flies between four airports, K, L, M and N. There are direct routes between K and L, K and M, K and N, L and M, and M and N, each flown in both directions, and there is no direct route between L and N. An aircraft's day is a sequence of flights along these routes, each flight starting where the last one ended, and it may visit the same airport more than once. (a) An aircraft starts its day at L and must end it at N. How many different days of exactly two flights are possible? (b) Another aircraft starts at L and must end at K after exactly three flights. How many different days are possible?

KLNMA =0111101011011010Order K, L, M, N. There is no route between L and N.
Each airport is a vertex and each route an edge: A = 0111101011011010.
Write the routes as an adjacency matrix, with rows and columns in the order K, L, M, N: A = 0111101011011010. A day of n flights is a walk of length n, and the entry in row X, column Y of An counts the walks of length n from X to Y.
step 1 of 5

A day of n flights is a walk of length n in the route network. The entry in row X, column Y of the nth power of the adjacency matrix counts the walks of length n from X to Y, so each answer is one entry of a matrix power.

  1. Write the routes as an adjacency matrix, with rows and columns in the order K, L, M, N: A = 0111101011011010. A day of n flights is a walk of length n, and the entry in row X, column Y of An counts the walks of length n from X to Y.
  2. Square the matrix: A2 = 3121121221311212. For example, row L of A times column N of A is 1 × 1 + 0 × 0 + 1 × 1 + 0 × 0 = 2.
  3. (a) The entry in row L, column N of A2 is 2, so there are 2 days of two flights: L to K to N, and L to M to N.
  4. For three flights, multiply row L of A2 by column K of A: 1 × 0 + 2 × 1 + 1 × 1 + 2 × 1 = 5. This is the entry in row L, column K of A3 = A2 A.
  5. (b) There are 5 days of three flights from L to K. Check by listing them: L–K–L–K, L–K–M–K, L–K–N–K, L–M–L–K and L–M–N–K.

answer(a) 2 days; (b) 5 days

techniqueCounting Walks with Matrix Powers · The Adjacency Matrix

Common pitfalls

  • Reading the answer to (a) from A itself. Row L, column N of A is 0 because there is no direct route; the days of two flights are counted by A2.
  • Leaving out days that fly back and forth, such as L–K–L–K. The question allows an airport to be visited more than once, and the matrix power counts every such walk.
05

Loopback Tests on Four Radio Towers Joined by One-Way Links

methodWrite the Links as a Matrix, Find the Diagonal of Its Cube for the Relays That Come Home, and Divide the Diagonal's Total by the Number of Towers in Each Ring

Four radio towers, N, E, S and W, pass signals over one-way links: N can send to E and to S, E can send to S and to W, S can send to N and to W, and W can send to N. No tower sends to itself. In a loopback test, a tower sends out a signal that is passed along the links exactly three times in all and must arrive back at the tower that sent it. (a) How many different three-step relays start and end at tower E? (b) A ring is three different towers that can pass a signal round, each to the next and from the last back to the first; the same ring started from a different tower counts as the same ring. How many rings does the network have?

NESWA =0110001110011000Order N, E, S, W. A 1 means the row's tower can send to the column's.
Each tower is a vertex and each link an arc. N and S can send to each other; every other link works one way.
Write the links as a matrix, with rows and columns in the order N, E, S, W and a 1 in row X, column Y when X can send to Y: A = 0110001110011000. The matrix is not symmetric, because most links work one way only.
step 1 of 5

Write the links as a matrix A with 1 in row X, column Y when X can send to Y. The entry in row X, column Y of A3 counts the three-step relays from X to Y, so the relays that come home are counted on the diagonal of A3. With no tower sending to itself, each of them goes once round a ring.

  1. Write the links as a matrix, with rows and columns in the order N, E, S, W and a 1 in row X, column Y when X can send to Y: A = 0110001110011000. The matrix is not symmetric, because most links work one way only.
  2. Square it: A2 = 1012200111100110. The entry in row X, column Y counts the two-step relays from X to Y.
  3. (a) The relays from E back to E in three steps are the entry in row E, column E of A3: row E of A2, which is 2, 0, 0, 1, times column E of A, which is 1, 0, 0, 0, gives 2 × 1 = 2. The 2 relays are E–S–N–E and E–W–N–E.
  4. Find the rest of the diagonal of A3 the same way. For N: 1, 0, 1, 2 times 0, 0, 1, 1 gives 1 + 2 = 3. For S: 1, 1, 1, 0 times 1, 1, 0, 0 gives 2. For W: 0, 1, 1, 0 times 0, 1, 1, 0 gives 2.
  5. (b) The diagonal adds up to 3 + 2 + 2 + 2 = 9. No tower sends to itself, so a three-step relay that comes home passes through three different towers and goes once round a ring. Each ring is counted once from each of its three towers, so there are 9 ÷ 3 = 3 rings: N–E–S, N–E–W and N–S–W, each in that order.

answer(a) 2 relays; (b) 3 rings

techniqueCounting Walks with Matrix Powers · The Adjacency Matrix

Common pitfalls

  • Reading the diagonal of A2 for the relays. That counts relays of two steps, such as N to S and back to N; the test uses three steps, so the diagonal of A3 is needed.
  • Taking the total of the diagonal, 9, as the number of rings. Each ring is counted three times, once from each of its towers, so the total must be divided by 3.
06

A Board Game With One-Way Bridges Between Four Islands, and How Many Turns Let the Counter Reach Every Island

methodWrite the Bridges as a Matrix, Work Out Its Powers One at a Time, and Stop at the First Power With No Zero Entry

In a board game, a counter moves between four islands, A, B, C and D, over bridges, and on every turn it must cross exactly one bridge, in a direction the bridge allows. The bridges allow these crossings: A to B, A to C, A to D, B to C, B to D, C to B, C to D, and D to A. (a) What is the smallest number of turns k such that, wherever the counter starts, it can finish on any of the four islands, its starting island included, after exactly k turns? (b) After exactly that number of turns, which starting island and finishing island are joined by the most different sequences of crossings, and how many sequences are there?

ABCDA =0111001101011000Order A, B, C, D. Arrows at both ends: the bridge goes both ways.
Each island is a vertex and each allowed crossing an arc: A = 0111001101011000.
Write the crossings as a matrix, with rows and columns in the order A, B, C, D: A = 0111001101011000. The entry in row X, column Y of Ak counts the ways from X to Y in exactly k turns, so the question asks for the first power with no zero entry.
step 1 of 6

Write the crossings as a matrix A. The entry in row X, column Y of Ak counts the ways to go from X to Y in exactly k turns, so the question asks for the first power of A that has no zero entry. Work out the powers one at a time and stop there.

  1. Write the crossings as a matrix, with rows and columns in the order A, B, C, D: A = 0111001101011000. The entry in row X, column Y of Ak counts the ways from X to Y in exactly k turns, so the question asks for the first power with no zero entry.
  2. A itself has zeros, for example all down its diagonal: in one turn the counter cannot finish where it started. So k = 1 does not work.
  3. Square it: A2 = 1112110110110111. It still has zeros: in two turns the counter cannot go from B to C, from C to B, or from D to A. So k = 2 does not work.
  4. Multiply by A once more: A3 = A2 A = 2223112212121112. Every entry is at least 1.
  5. (a) k = 3: after exactly three turns the counter can finish on any island, from any start.
  6. (b) The largest entry of A3 is the 3 in row A, column D, and it is the only 3. So the counter can go from A to D in 3 different ways: A–B–C–D, A–C–B–D and A–D–A–D.

answer(a) k = 3 turns; (b) from A to D, in 3 different ways

techniqueCounting Walks with Matrix Powers · The Adjacency Matrix

Common pitfalls

  • Stopping at A2 because most of its entries are positive. The question needs every start and every finish, and A2 still has three zeros.
  • Adding A + A2 + A3, which counts the ways of up to three turns. The counter must cross a bridge on every turn, so only sequences of exactly k turns count.
07

Air-Freight Charges Between Five Cities, and the Cheapest Way to Send a Crate With One Stop or Two

methodRead Each Flight's Charge From the Table, Add the Charges Along Every Route Through One Stop and Take the Least, Then Do the Same for Every Route Through Two Stops

An air-freight company charges a fixed price per crate for each direct flight it runs between five cities, A, B, C, D and E. Its table of charges, in dollars, is A–B 40, A–C 25, A–D 55, B–C 20, B–D 30, B–E 45, C–D 25, C–E 70 and D–E 15. Every flight runs both ways at the same price, and there is no direct flight between A and E. A crate sent on a route with stops pays for every flight it takes. (a) What is the cheapest route from A to E with exactly one stop, and what does it cost? (b) What is the cheapest route from A to E with exactly two stops, and how much does it save on the route in (a)?

ABCDEA—402555—B40—203045C2520—2570D553025—15E—457015—Charges in dollars. A dash: no direct flight.
The table is a weighted graph: each charge is the weight of an edge. There is no edge between A and E.
Read the table as a weighted graph: a vertex for each city and an edge for each direct flight, weighted with its charge. A route costs the sum of the weights along it. There is no edge between A and E, so a crate has to stop at least once.
step 1 of 5

Read the table as a weighted graph: a vertex for each city and an edge for each direct flight, weighted with its charge. A route costs the sum of the weights along it, so try every route with the given number of stops and compare the totals.

  1. Read the table as a weighted graph: a vertex for each city and an edge for each direct flight, weighted with its charge. A route costs the sum of the weights along it. There is no edge between A and E, so a crate has to stop at least once.
  2. With one stop at X, the cost is the charge from A to X plus the charge from X to E. Through B it is 40 + 45 = 85. Through C it is 25 + 70 = 95. Through D it is 55 + 15 = 70.
  3. (a) The cheapest route with one stop is A–D–E, costing $70. It starts with the most expensive flight out of A, but the cheap flight from D to E more than makes up for it.
  4. With two stops, the route is A–X–Y–E, where X and Y are two different cities from B, C and D. The six routes cost: A–B–C–E 40 + 20 + 70 = 130, A–B–D–E 40 + 30 + 15 = 85, A–C–B–E 25 + 20 + 45 = 90, A–C–D–E 25 + 25 + 15 = 65, A–D–B–E 55 + 30 + 45 = 130 and A–D–C–E 55 + 25 + 70 = 150.
  5. (b) The cheapest route with two stops is A–C–D–E, costing $65, which saves 70 − 65 = $5 on the route in (a). The extra stop pays because going from A to D through C costs 25 + 25 = 50, less than the direct flight at $55.

answer(a) A–D–E, costing $70; (b) A–C–D–E, costing $65, which saves $5

techniqueThe Weighted Adjacency Table

Common pitfalls

  • Starting with the cheapest flight out of A, A–C at $25, and carrying on from C. The flight from C to E costs $70, so that route totals $95; every stop has to be tried.
  • Assuming that a route with more stops always costs more. Going from A to D through C costs $50, less than the direct flight at $55, so a route with two stops can beat the best route with one.
08

Driving Times on the Roads Between Five Towns, and Which Road No Fastest Trip Uses

methodCompare Each Road's Time With the Routes Round Through Other Towns, Then Build Up the Fastest Times Outward From the Start

Seven roads join five towns, A, B, C, D and E, and a table gives the driving time on each road, in minutes: A–B 12, A–C 20, B–C 6, B–D 12, C–D 7, C–E 15 and D–E 10. Every road can be driven both ways in the same time, and there are no other roads. (a) One of these roads is on no fastest route between any two of the towns. Which road is it? (b) What is the fastest driving time from A to E, and which route gives it?

ABCDE122061271510Driving times in minutes, the same both ways
Each town is a vertex and each road an edge, weighted with its driving time.
Read the table as a weighted graph, with a vertex for each town and each road weighted with its time. A road is on no fastest route when some other route between its two ends is quicker: any trip that uses the road could go round that way instead and arrive sooner.
step 1 of 6

Read the table as a weighted graph, with a vertex for each town and each road weighted with its driving time. A road is on no fastest route when another route between its own two ends is quicker, because any trip that uses the road could take that route instead. For the fastest time from A, build up the fastest time to each town in turn.

  1. Read the table as a weighted graph, with a vertex for each town and each road weighted with its time. A road is on no fastest route when some other route between its two ends is quicker: any trip that uses the road could go round that way instead and arrive sooner.
  2. Test the road A–C, which takes 20 minutes. The route A–B–C takes 12 + 6 = 18 minutes, which is quicker, so A–C is on no fastest route.
  3. Test the other roads the same way. B–D takes 12 against 6 + 7 = 13 for B–C–D, and C–E takes 15 against 7 + 10 = 17 for C–D–E. A–B, B–C, C–D and D–E are each quicker than every way round. So each of these six roads is the fastest route between its own two ends.
  4. (a) The road between A and C is the one on no fastest route: a trip between A and C is quicker through B.
  5. For the fastest time from A to E, build up the fastest time to each town from A. B takes 12. C takes 12 + 6 = 18 through B, quicker than 20 direct. D takes 12 + 12 = 24 through B, or 18 + 7 = 25 through C, so 24. E takes 18 + 15 = 33 through C, or 24 + 10 = 34 through D, so 33.
  6. (b) The fastest time from A to E is 33 minutes, on the route A–B–C–E. Check against the other routes: A–B–D–E takes 34, A–B–C–D–E takes 35, A–C–E takes 35 and A–C–D–E takes 37 minutes.

answer(a) The road between A and C; (b) 33 minutes, on the route A–B–C–E

techniqueThe Weighted Adjacency Table

Common pitfalls

  • Keeping A–C because it is the only road straight from A to C. A direct road is not always the quickest: A–B–C takes 18 minutes against its 20.
  • Taking the route with the fewest roads, A–C–E, as the fastest. It takes 35 minutes, 2 more than A–B–C–E.
09

A Road Atlas's Chart of Distances Between Five Towns, With One Entry Hidden by a Stain

methodApply the Triangle Rule Through Each Other Town for an Upper and a Lower Bound, and Read an Equality in the Rule as a Town on a Shortest Route

A road atlas has a chart of the shortest road distances, in miles, between five towns, A, B, C, D and E. A coffee stain hides the distance between A and B. The rest of the chart reads A–C 28, A–D 9, A–E 14, B–C 12, B–D 7, B–E 13, C–D 19, C–E 19 and D–E 10. (a) Find the hidden distance between A and B. (b) Which of the towns B, D and E can lie on a shortest road route from A to C?

ABCDEA—?28914B?—12713C2812—1919D9719—10E14131910—Shortest road distances in milesThe triangle rule: XZ is at most XY + YZ
The chart holds shortest distances, so every three towns obey the triangle rule. The stain hides AB.
The chart gives shortest road distances, so they obey the triangle rule: for any towns X, Y and Z, the distance from X to Z is at most the distance from X to Y plus the distance from Y to Z, because going through Y is one way to get from X to Z.
step 1 of 6

The chart gives shortest road distances, so every three towns obey the triangle rule: the distance between two of them is at most the sum of their distances to the third, because going through the third town is one way to make the trip. Through each other town the rule gives an upper bound or a lower bound for the hidden entry. When the rule holds with equality, the middle town lies on a shortest route.

  1. The chart gives shortest road distances, so they obey the triangle rule: for any towns X, Y and Z, the distance from X to Z is at most the distance from X to Y plus the distance from Y to Z, because going through Y is one way to get from X to Z.
  2. Upper bounds for the distance AB, going through each other town: through D, 9 + 7 = 16; through E, 14 + 13 = 27; through C, 28 + 12 = 40. So AB is at most 16.
  3. Lower bounds come from the triangles the other way round. A to C is at most A to B plus B to C, so 28 ≤ AB + 12, and AB is at least 28 − 12 = 16. The triangles through D and E give only 9 − 7 = 2 and 14 − 13 = 1.
  4. (a) AB is at most 16 and at least 16, so the hidden distance is 16 miles.
  5. A town X can lie on a shortest route from A to C exactly when the triangle rule is an equality, AX + XC = AC = 28. For B: 16 + 12 = 28. For D: 9 + 19 = 28. For E: 14 + 19 = 33, which is more than 28.
  6. (b) B and D can lie on a shortest route from A to C, and E cannot. Check: the route A–D–B–C is 9 + 7 + 12 = 28 miles long, the chart's distance, and it passes through both.

answer(a) 16 miles; (b) B and D can, and E cannot

techniqueThe Weighted Adjacency Table

Common pitfalls

  • Giving the smallest upper bound, 16, as the answer without a lower bound. An upper bound alone allows any distance up to 16; it is the triangle with C that rules out anything less.
  • Choosing towns for (b) by how close they look to A or to C. A town lies on a shortest route only when its two distances add up to exactly 28, and E's add up to 33.
10

Co-Authors in a Research Group, and Which Two Researchers the Leader Should Introduce

methodSquare the Adjacency Matrix, Read an Entry Off the Diagonal as the Number of Co-Authors Two Researchers Share, and Compare Only the Pairs Who Have Not Written Together

Five researchers in a group, Ada, Ben, Cho, Dev and Eli, record who has written a paper with whom. Ada has written with Ben, Cho and Eli; Ben with Ada, Cho and Dev; Cho with Ada, Ben and Eli; Dev with Ben only; and Eli with Ada and Cho. (a) How many co-authors do Cho and Dev have in common? (b) The group leader will introduce the two researchers who have not yet written together but have the most co-authors in common. Which two are they, and how many co-authors do they share?

ABCDEA Ada, B Ben, C Cho, D Dev, E EliA =0110110110110010100010100
Each researcher is a vertex, with an edge between two who have written a paper together.
Write the co-authorships as an adjacency matrix, with rows and columns in the order Ada, Ben, Cho, Dev, Eli: A = 0110110110110010100010100.
step 1 of 6

Draw the group as a graph with an edge between two researchers who have written together, and write its adjacency matrix A. A co-author shared by X and Y is a walk of length 2 from X to Y, so the entry in row X, column Y of A2 counts the co-authors they share.

  1. Write the co-authorships as an adjacency matrix, with rows and columns in the order Ada, Ben, Cho, Dev, Eli: A = 0110110110110010100010100.
  2. A co-author shared by X and Y gives a walk of length 2 from X to Y, through that co-author, so the entry in row X, column Y of A2 counts the shared co-authors. Row Cho times column Dev is 1 × 0 + 1 × 1 + 0 × 0 + 0 × 0 + 1 × 0 = 1.
  3. (a) Cho and Dev have 1 co-author in common: Ben.
  4. Square the whole matrix: A2 = 3121113102213111011012102. The pairs who have not written together are the 0s of A off the diagonal: Ada and Dev, Ben and Eli, Cho and Dev, and Dev and Eli.
  5. Read their entries in A2: Ada and Dev 1, Ben and Eli 2, Cho and Dev 1, and Dev and Eli 0.
  6. (b) The leader introduces Ben and Eli, who share 2 co-authors, Ada and Cho. Ada and Cho also have an entry of 2, but they have already written together, so they are not a candidate.

answer(a) 1 co-author, Ben; (b) Ben and Eli, who share 2 co-authors, Ada and Cho

techniqueCounting Walks with Matrix Powers · The Adjacency Matrix

Common pitfalls

  • Choosing the largest entry of A2 off the diagonal without checking A. Ada and Cho share 2 co-authors as well, but they have already written a paper together.
  • Reading the diagonal of A2 as shared co-authors. A diagonal entry counts the walks of length 2 from a researcher back to themselves, which is the number of their own co-authors.
Mr. Chalk Read the guide