Extensions

An overview of problems that might elicit extended abstract thinking

This is a brainstormed list of possible problems that require a bit of extra thought - some extended abstract thinking. This kind of thinking needs to be shown to get "Achieved with Excellence", typically in two places in an assessment.

This list is by no means comprehensive or complete.

Traversability

After determining whether a network is traversable (possibly from a specified node), what if it's not. In a real world context, a simple "No" doesn't really answer the question. If I can't run along every trail in a network of running trails, what can I compromise? Depending on the problem or task (which should be read carefully) this might require using some edges more than once, or not using some edges, or adding an entirely new edge into the network.

Extra conditions might be placed on a search for an Euler path; for instance, what the Euler path had to visit all of the nodes once before repeating any? Or had to start with the shortest path from Auckland to Gisborne?

Minimum Spanning Tree

It is possible that there is more than one minimum spanning tree (a choice could be made as to which of two edges with the same weight should be added to the tree). If it looks like this is the case, discuss both, and see if there's a way to decide to pick one over the other.

What if the minimum spanning tree had some edges that couldn't be used (the ground is too hard to lay electrical cables beneath between two buildings)? If these edges can no longer be in the MST, then the answer will be a slightly larger spanning tree.

On the flip side, what if some of the edges in the spanning tree were free (or at a reduced cost in some way). This might also affect the final design of the spanning tree.

If travel is only possible on the minimum spanning tree, is it difficult to travel between some nodes? If the task was to make some roads safe for travel, is travel in the MST reasonable, or are some nodes very far apart?

Finally, what if some edges were specified in the spanning tree? If there were some edges that were required, what would change?

All of these changed trees should be compared to the original tree, to see what extra cost (possibly a cost in extra distance) the constraints are adding.

Shortest Path

If there is more than one shortest path between the start and end nodes, give them both; and perhaps choose one, especially if a good reason can be given for one over the other.

It might be that the shortest path needs to be found that avoids a certain edge or node, or the shortest path must use a certain edge or node. Sometimes, this is asked in terms of a return trip (travel from Perth to Sydney and then return to Perth via Darwin).

All of these changed paths should be compared to the shortest path, to see what extra cost the extra constraints are adding.

Chinese Postman Problem

The Chinese Postman Problem is an extension of Euler paths. It asks for an Euler Path in a network, but also requires that the tour ends at the start node. This requires a shortest path to be found between the two odd nodes (or, if particularly difficult, between carefully chosen pairs of odd nodes).

Main Trunk Line

Suppose we wanted a network of train lines in the South Island, that included the shortest path from Picton to Dunedin and then as few other rail tracks as possible. The shortest path from Picton to Dunedin is the "Main Trunk Line", and then Dijkstra's algorithm can be used to add short edges to this until a spanning tree is formed.

There are no checkpoint questions, exercises or investigations for this topic. However, the tasks (100 Acre Wood, Sherwood Forest and The Shire) require extended abstract thinking in some places.

Google Sites

Report abuse