WitCH 77: Road to Nowhere

If nothing else, people can enjoy a great song.

This one puzzled us when we gave the 2021 Further Mathematics Exams a three-minute scan, but we didn’t bother then to think, um, further. Now, however, since graph theory is likely a mandatory part of Specialist 1&2, and thus also, at least technically, a mandatory part of Specialist 3&4, we have thought a little harder. So, after discussions with John Friend and with a colleague who we shall refer to as Professor Combo, here we are.

The following question appeared in the Network module on the 2021 Further Mathematics Exam 1. Have fun.

59 Replies to “WitCH 77: Road to Nowhere”

  1. So… if we use the accepted definition of a graph being a collection of vertices and edges, this diagram is not a graph.

    Or a “network.”

    I’m guessing the intended answer was D since there are no “1-step paths” from any building back to itself and likewise none from J to M, K to N or M to N, each counting twice in the matrix for a total of 11 zeros.

    1. Here is my interpretation (I’m no expert so I’m receptive to counter-arguments and debate):

      The diagram is a MAP, not a graph or a network. The map shows how the pathways connect to the buildings and can be used to draw a graph. There’s a loop at K (because there is a direct route that leads back to K), a double edge joining K and L, and a double edge joining J and K (because there are two different direct routes to these pair of buildings). Note that there is direct route between L and J. I’ve attached my graph and the adjacency matrix. Each different route is an edge.

      A couple of notes:
      1) The pathways are NOT edges. Each different route is an edge.

      2) Any confusion comes from thinking of the pathways as if they are edges.

      3) Maths Quest SM1/2 has a similar example and question and makes the distinction between pathways and routes clear. The distinction is unclear in Nelson SM12. Cambridge SM12 has no similar example or question. But Cambridge FM34 does – Ex 14C Q8 and makes the distinction between pathway and route clear (one of the parts says to “Draw this map as a graph by representing towns as vertices and and each different route between towns as an edge.”)

      I believe there are two mistakes in the question:

      1) It should have been worded something like
      “The \displaystyle map below shows …. An adjacency matrix for the graph that represents this map is formed. …”
      VCAA’s use of the word network falsely suggests -I think – that the diagram is a graph. It is not.
      The above understanding leads to Option C as the answer.

      2) Another possible interpretation is that you can add a vertex where the pathways intersect, then the map becomes a graph … This does not lead to any correct option. So another error in the question is that there are two different and reasonable models that can be used – one leads to Option C and the other leads to no option. Perhaps – one might argue – VCAA intended only the model leading to an option. The model I’ve used is the model given in the textbooks. They don’t mention adding vertices where the pathways intersect.

      NB: This post is mainly to try and get my own thoughts straight on this question, so all feedback is welcome.

      1. Hi John!

        I took a quick look through the comments and didn’t see this, but my first model graph did have loops at each vertex. I mean, in the real world, I can go from M to M without issue, I just stand still. That graph has an adjacency matrix with not enough zeros.

        I don’t think this is the best way to interpret the map they have given, and if I were to do the question I’d have to go with another interpretation that resulted in an answer from those given. I’d pick C or D. Problem is, if we can’t stand still and make a loop, then also we aren’t allowed to walk down a path and turn around and make a loop. So are we allowed to do the turns at K and make a loop? Are we allowed to turn almost 180 to make the J -> L path? These things are not clear to me.

        Another question that is too ambiguous. Reminds me of a comment I just read suggesting that we could do with a few more pedants in the world…

      2. My adjacency matrix had a ‘typo’ (no-one took the chance to have a free hit! And don’t say you were just being nice! Better to say you didn’t care!!) Attached is a correct copy (correction in red).

    2. Yep… missed the loop at K.

      Which makes 10 zeros and answer C.

      I’ve always understood a network and a graph to be interchangeable in VCAA-speak.

      But that doesn’t mean anything.

    1. The term is ambiguous, and is context-dependent, because there is the idea of a flow network (A digraph with a source and a sink) along with a capacity function, but in a variety of contexts, it can just mean a graph/directed graph with certain attributes. For instance, a network of connected devices, or a website and its connections to other web pages. You’ll have to take that up with the study design, because flow networks (and applications such as min-cut/max flow + matching) are in the module.

          1. FM3/4 is above my pay grade. I think the Graph Theory in SM3/4 will be very different to what it is in FM3/4 – more theoretical (‘pure’) and more focussed on proof (including existence and non-existence proofs).

      1. Thanks, Sai, although the fact that “flow network” is a thing doesn’t imply that “network” is a thing.

        The real question is, is “network” a synonym for “graph”, or is it simply a vague term for any real world scenario that might be modelled by a graph? If the former, how does one answer the above exam question? On the other hand, if the latter, how does one answer the above exam question?

        1. My understanding of the definition of a network is that it’s a simple, weighted, directed graph G satisfying:
          a) There is exactly one vertex in G, called the source, having no incoming edges,
          b) There is exactly one vertex in G, called the sink, having no outgoing edges,
          c) The weight \displaystyle c_{ij} of the directed edge (i, j), called the capacity of (i, j), is a non-negative number,
          d) The undirected graph obtained from G by ignoring the directions of the edges is connected.

          So the diagram given in the question is definitely NOT a network. It is a MAP. VCAA screwed up.

          So Marty, to answer the question, you have to realise that VCAA screwed up and meant MAP, not network, and assume the wording I suggested earlier. Then again, maybe VCAA has its own definition of a network that’s peculiar to FM3/4. It wouldn’t be the first time VCAA had made up its own definition …

          1. John, your understanding of “network” is neither here nor there. It is a question of what the word means, if anything, in (Further and, now, Specialist) VCE texts and in (ha ha) the VCE study design.

            The issue for the exam question above is does the word “network” imply anything substance, or is it just a vague scenario word? In either case, what are students expected to do, and what is the justification for that expectation?

  2. My thoughts on this weird map:

    This initially seems to resemble a multigraph (where parallel edges are permitted), but it’s downright impossible to discern what edge goes to what, as I initially perceived that there were two edges connecting K and J. The same issue occurs for J and L, it is hard to tell if there is an edge between J and L. In practice, it’s very reasonable to just insert an intermediate vertex there, or use a multigraph but not leave it as something not easy to interpret. For both reasons, it definitely isn’t a graph!

    1. Thanks, Sai. It obviously isn’t a graph, even noting that “graph” in this context permits multiple edges between the same two vertices.

      The question is, does the word “network”, or anything, somehow guide the student on how they are supposed to make a precise object? Does the diagram, in any mathematical or VCE-conventional sense, have a unique adjacency matrix?

      I assume the answer is no, but given I don’t know the lingo or the subject, I figure it’s worth asking.

      1. Cambridge General Mathematics Units 1&2 on page 454 uses the phrase “Graph or Network” which to me implies that the two words are interchangeable in the eyes of the author and publisher and therefore in the eyes of many teachers who use this text as their source of knowledge.

        That does not make it correct of course.

        On page 457 of the same textbook… “…a weighted graph is often called a network.”

        So maybe the author changed their mind or is also confused about the difference.

      2. There’s nothing that says the graph has to be ‘simple’, so multiple edges and loops is perfectly fine. What I drew is a perfectly fine graph that represents the routes between buildings shown on the given MAP. The adjacency matrix is unique, provided:
        a) you exclude isomorphisms of the graph, and
        b) you don’t insert extra vertices at the intersection points.

        The Cambridge FM3/4 textbook, for example, simply defines a network as “a weighted graph where the weights represent physical quantities such as time, distance or cost.” VCAA have made very sloppy use of the word ‘network’. Marty, I’ll bet that VCAA have used the word ‘network’ exactly as you said above: “just a vague scenario word”.

        As for “what are students expected to do, and what is the justification for that expectation?” …

        1) Students have to interpret VCAA’s intent. As always. And it’s part of the job of the poor schmuck that teaches them to teach students that they will need to do this and how to do this.
        2) There’s no justification. It shouldn’t be expected because it shouldn’t be necessary. There should be an expectation that VCAA can deliver an exam that does not have sloppy errors. Because there should be an expectation that the exam writers and vettors are competent.

        btw the definition I gave for ‘network’ is the standard definition. If the word ‘network’ is used in any mathematical context, the definition I gave is its meaning. You’ll find this definition in any standard textbook on discrete mathematics.

        Now, what are the chances that the new Stupid Design has a glossary of terms where things like graph, network etc. are clearly defined …? This question is symptomatic of many underlying VCAA problems.

    2. Re: “The same issue occurs for J and L, it is hard to tell if there is an edge between J and L.”

      Yes, it’s a bit tricky to see. But a careful inspection the MAP shows that there is a direct route between J and L and therefore an edge ‘obviously’ connects J and L in the graph representation.

  3. 2020 Exam 1 Module 2 Question 8 – Incorrect usage of the word ‘network’.

    2019 Exam 1 Module 2 Question 6 – Correct wording.

    2015 Exam 1 Module 5 Question 6 – Correct wording. This is how the 2021 question should have been worded!!

    So VCAA \displaystyle can get it right – but unfortunately the writer(s) and vettor(s) of 2020 and 2021 Module 2 lacked an understanding of the word ‘network’. Not an ideal quality when writing questions for a module called … \displaystyle Networks and Decision Making.

  4. From the back cover of “Introduction to Stochastic Networks” by R. F. Serfozo (Springer, 1999): “In a stochastic network, such as those in computer/telecommunications and manufacturing, discrete units move among a network of stations where they are processed.” The term “network” itself is not explained or defined in that monograph. The preface starts with the sentence, “The term stochastic network has several meanings.” (And it goes on to say which meaning the book adopts.)

    In view of this, I am inclined to go with Marty’s offered second alternative to describe “network” (in his words) as “a vague term for any real world scenario that might be modelled by a graph”. It would seem strange to me that a stochastic network may exhibit, as per a reasonable definition such as in the above book, all kinds of weird set-ups while a network could not. (Perhaps I am too much under the sway of the idea that “stochastic X”, where “X” stands for anything, should be a version of “X” just with probabilities thrown in.)

    1. Hi Christian. I’m going to put my head on the chopping block here (I’m no expert) and maintain that the word ‘network’ has a well-defined mathematical meaning – the one I gave above. This definition makes it clear that a network IS a graph, a graph with specific properties. The picture in the VCAA question is NOT a network in the mathematical sense of the word and should NOT be called a network. VCAA should have said something like:

      “The MAP below …” or “The diagram below …” and it could have referred to “the system of pathways” or “the arrangement of pathways”. VCAA’s use of the word ‘network’ in this question was lazy, sloppy and ignorant.

      I do not accept that in the world of discrete mathematics, network is simply “a vague term for any real world scenario that might be modelled by a graph”, as Marty puts it.

      Re: Serfozo. A common definition for stochastic network that I’ve come across is:
      “Stochastic networks are networks that vary over time with non-binary vertices that represent a probability for a link between two nodes.”

      Does the word ‘network’ as used in network theory’, ‘communication network’ etc. lose it’s precise and nuanced mathematical meaning? Changing to something more along the lines of what Marty offered?

      Regardless of this, in a \displaystyle mathematics Module called \displaystyle Networks and Decision Making that is clearly an introduction to Graph Theory, one should and must expect much better than the word ‘network’ only having some vague meaning. Mathematics is based on precise definitions and language. This is something that VCAA and its \displaystyle network of goons consistently fails on.

      1. John, I think you’re pushing weirdly and way too hard for a single “correct” usage of the term “network”. I agree, obviously, that the VCE use of the term is vague and sloppy and inconsistent. But any word that is used in the real-world and the applied-world and the pure-world is going to have a variety of different and less-or-more defined and equally legitimate usages.

        I’ll try to summarise the VCE usage in a later comment or update, but to return to the exam question, I don’t want to lose sight of the key point. The key point is, if “network” is somehow a formal mathematical object, enough to have an adjacency matrix, then the diagram/map/whatever included in the exam question is not a network.

        The key point is, whatever a “network” might be, the exam question is screwed.

  5. I’ll do this as a comment rather than a post update, since people are likely to have corrections and clarifications. Here is my summary of the use of “network” in materials for VCE that I have in hand.

    GENERAL MATHEMATICS 1&2 STUDY DESIGN

    a) The Matrices sub-topic (p 19) refers to “road networks” and “people in a network”, clearly colloquial usages.

    b) The Graphs and Networks sub-topic (p 20) refers to “weighted graphs and networks”. The “and” suggests that the two terms are not synonymous, but that suggestion may just be clumsy wording.

    SPECIALIST MATHEMATICS 1&2 STUDY DESIGN

    a) The topic Graph Theory (P 46) refers to “social networks”, with no suggestion of a formal definition.

    FURTHER MATHEMATICS 3&4 STUDY DESIGN (pretty much what Sai was indicating)

    a) The introduction to the module Networks and Decision Mathematics (p 61) refers to “the use of networks to model and solve problems involving travel, connection, flow, matching, allocation and scheduling”

    b) Various applications of “networks” are then suggested, without pointing to a clear definition.

    c) In the sub-topic Shortest Path Problems, the SD refers to “the shortest path between a given vertex and each of the other vertices in a weighted graph or network”. Possibly this is intended to mean “weighted graph” and “network” are synonymous, but that is unclear.

    CAMBRIDGE FURTHER TEXT

    a) Chapter 14 is titled Graphs, Networks and Trees

    b) Section 14A is titled Graphs and Networks but the word “network” does not appear in the text or the exercises.

    c) The first use of “network” in the text is in 14D, titled Weighted Graphs and Networks. The text seems to use “network” exactly as a synonym for “weighted graph”, i.e. a graph with numbers on the edges.

    d) The usage in 14D is reinforced in the Key Ideas summary of the chapter.

    CAMBRIDGE SPECIALIST 1&2 TEXT (via GO only, because Cambridge are being dicks)

    a) Chapter 27 is titled Graph Theory. The word “network” does not appear.

    MATHS QUEST SPECIALIST 1&2 TEXT

    a) Chapter 5 is titled Graphs and Networks. The term “network” is used often but is never defined. It appears to be used mostly in a colloquial sense, but occasionally also as a synonym for (unweighted) “graph”.

    1. My (non-expert) five cents:

      Re: “GENERAL MATHEMATICS 1&2 STUDY DESIGN …
      b) The Graphs and Networks sub-topic (p 20) refers to “weighted graphs and networks”. The “and” suggests that the two terms are not synonymous, but that suggestion may just be clumsy wording.”

      The standard definition for a network includes is “a simple, weighted, \displaystyle directed graph G satisfying: …”

      The word ‘directed is very important’. So a ‘weighted graph’ without any further qualification is definitely not synonymous with a network. It would make sense to introduce weighted graphs first and then add conditions to define a network.

      So the text in Cambridge FM3/4 seeming “to use “network” exactly as a synonym for “weighted graph”, i.e. a graph with numbers on the edges.” is incorrect on the part of the text.

      I can also add that Nelson SM1/2 does not mention networks. But it is actually very clear about the difference between maps and graphs. Its chapter summary includes the following (and I quote):

      Road maps and graphs
      To draw a road map as a graph
      * list the vertices: these may be towns or other landmarks
      * list the edges: these are all the possible paths between the vertices.
      A path from vertex A to vertex A is drawn as a loop.
      * use the two lists to draw a graph

      PS – Apparently a digital copy of Nelson SM1/2 does not exist.

        1. Marty, are you saying that there’s no standard definition of ‘network’ within VCAA? If so, I completely agree – I’ve looked at all the questions in the Network and Decision Making Module for all of the available VCAA Further Maths exams. VCAA’s consistent inconsistent use of the word ‘network’ over the past 15 years is astounding.

          But … if you’re saying that there’s no standard definition of ‘network’ in textbooks on Discrete Mathematics, then I disagree. The Discrete Maths textbooks I’ve looked at have been consistent. But I’ll happily admit I’m wrong if two conflicting definitions are cited.

          I think the definition is relevant. The meaning of a word and how that word is used is important.

          If the meaning of ‘network’ and VCAA’s use of the word is not the issue here, I don’t see what is. For me the major issue is VCAA calling the map a network when it’s not. It’s not a network, it’s not a graph. I think we can all agree on that. But you \displaystyle can draw a graph from the diagram given in the question.

          I’ll also agree that there’s a second issue in that the map can be modelled in two standard ways (leading to two different answers):
          1) the way I did it, and
          2) adding vertices to the forks in the pathways.

          What is the problem that you see with the question?

          1. John, the word “network” in the exam question is probably an error but it is not the main issue. The main issue is that what is pictured is not anything that has an adjacency matrix. Moreover, as you indicate, there are two natural ways to model the diagram with a graph that *does* have an adjacency matrix, leading to two different answers.

            That’s the real problem: the exam question is stuffed, entirely independent of the vague or incorrect language. The language issue, the meaning of the word “network”, is very secondary.

            On the language issue, there are two separate aspects:

            a) The use of the term in VCE materials

            b) The use of the term more generally

            I have stated clearly my view of both (a) and (b). In particular on (b), I wrote:

            “But any word that is used in the real-world and the applied-world and the pure-world is going to have a variety of different and less-or-more defined and equally legitimate usages.”

            Stop being a pedant.

  6. So, if I was trying to get into the head of the person who wrote this question (which I’m not…) I would guess that their intention was:

    1. Draw a picture which has some key points named.

    2. Suggest that you can produce a graph (I’ll stay away from the N-word for the moment) from the information provided.

    3. Believe that said graph will have an adjacency matrix.

    4. Ask a question about said adjacency matrix.

    If you read the question as a FM student trying to do well on an exam (and, for better or worse, that is the reason I’m engaging with the discussion…) then you can see how Answer C might make sense.

    The other options do not make sense, so select Answer C and move on with your life.

    (Your teachers’ won’t, but you can)

        1. Just teasing. I agree with your comment, and 2 was very funny. The only question is, is there, in VCE, a standard method of turning such non-graphs into graphs? I assume not.

          1. The textbook writers write/vet the exams, and the exam writers/vet write the textbook.

            This Circle of Stupidity means that, in the fantasy world of VCAA, there IS “a standard method of turning such non-graphs into graphs”. And that method is to do what is written in those textbooks.

            Marty, we will disagree on this (but it might come back to bite you) – words, definitions, grammar etc \displaystyle are important. It’s not being pedantic.

            Marty says John is a pedant.
            However, with a couple of well-placed commas … (Boom boom)

              1. If there were a few more pedants on the vetting committee (does such a thing really exist?) we would not have the problems we do now.

                But this goes well beyond teachers, schools and textbook writers.

                We’ve all (I assume, from reading this blog and the comments) gone down that rabbit-hole often enough to know the hole is very, very deep.

          2. I worry a bit about this, because the last time I taught 3+4 Further (2004, for those playing “guess who” at home…) such a question (here is a picture, produce a graph) was really common on SACs.

            But, I learned this from the teachers I worked with and so perhaps, in my own little bubble I worked under the assumption that everyone else teaching VCE thought the same.

            When I took a holiday to teach IB, there was a standard glossary of terms for each subject. Maybe VCE could…

            …yeah, OK… nevermind.

            1. VCAB * did!

              (See part of the 1988 Course Description Booklet for Mathematics here: https://mathematicalcrap.com/2022/01/18/specialist-mathematics-12-note-sharing-and-idea-sharing/#comment-13535 )

              What we have seen over the last 40 years is an erosion of quality, exponentially accelerated by VCAA. (The erosion actually began once the VUSEB was replaced, but VCAB did OK).
              VCAA’s Stupid Design is not fit to lick the boots of the VCAB Course Description Booklet. If VCAA truly wanted to give teachers a fit-for-purpose Course Description Booklet for Mathematics, as opposed to the Stupid Design that gets thrown at us, all it has to do is look to the past. But this won’t happen for at least the next 5 years, because some numbnuts at the VRQA
              ( https://www.vrqa.vic.gov.au/Pages/default.aspx )
              elephant stamped VCAA’s piece of shit (nearly 3 months ago, but for some reason VCAA won’t make it available until we’re all back at school and won’t have time to dissect it) that we all have to live with. These bastards all scratch each other’s backs.

              * VUSEB –> VCAB –> VBOS –> BOS –> VCAA.

            2. “here is a picture, produce a graph” is all part of the VCAA ‘give questions a real life context no matter how stupid it might be’ imperative. (Which is why we get stunt cars … that have an infinite initial acceleration: https://mathematicalcrap.com/2021/11/11/witch-75-car-crash/ )

              From the Daft Stupid Design (SM1/2):
              “• examples of graphs from a range of contexts such as molecular structure, electrical circuits, social networks, utility connections…”
              To which must clearly be added ‘road and pathway \displaystyle networks, especially roads and pathways with forks in them.

              Which, I have to say, is still better than a stunt car.

      1. Some people who come from a non-English speaking background have a better understanding of grammar that those from an English speaking background. I could tell a good story about this – but not here.

    1. So, if “a graph is what math people talk about” and a network is what “non-math people talk about”, does that mean this exam question had (at least) two authors?

      Might explain a few things!

      1. Indeed. And the mathematical competencies of the writers and vettors are in parallel, not series.

          1. Not quite … two False inputs would give a True output.

            I’m making an analogy to the equivalent resistance of several resistors all connected in parallel …: \displaystyle \frac{1}{R_{total}} = \frac{1}{R_{1}} + \frac{1}{R_{2}} + ....

            1. I feel a SAC question coming along…

              “The resistance of the examiners to change is independent of any other examiner…”

  7. I have taught students in General Mathematics about graphs/networks, published a couple of papers on graph theory, and come to the following conclusion.

    Graph theory, as it is presented in VCE mathematics, is a litany of definitions and superficial applications. In a sense this is a characteristic of the early stages of graph theory. You need to spend a lot of time (say a semester) to get to something substantial. I have suggested elsewhere that graph theory should be deleted from the curriculum.

    1. Terry, I completely agree with you. And I would add ‘proofs’ to your litany list, if the implicit inclusion of graph theory in SM3/4 is taken into account.

      And yet, the Daft Stupid Design explicitly states that SM1/2 Graph Theory topic includes:

      “examples of graphs from a range of contexts such as molecular structure, electrical circuits, social networks, utility connections and their use to discuss types of problems in graph theory including existence problems, construction problems, counting problems and optimisation problems”

      What it means by “optimisation problems” is anyone’s guess since weighted graphs and networks are not part of the sillibus, despite the use of the word ‘network’ in “social networks” And what’s meant to be \displaystyle done with all these examples is anyone’s guess. But there’s no mention of pathways (with forks) linking buildings or roads linking towns …

      The inclusion of graph theory is farcical. I don’t how it gets taught in Further (if chosen from the optional modules), where there seems to be a lot more content.

      1. Look at how it is exmamined in Further 3&4…

        80 to 90% of the marks on any given exam are really easy.

        Sure, there is usually one quite challenging question at the end, but for a lot of students, the middle-level-difficulty questions in this module are, relatively speaking, easier than other modules.

  8. In graph theory, a network is a directed graph in which weights (which need not be integers) are assigned to the edges. The main reason for talking about them at all in school seems to be to arrive at the max.-flow min.-cut theorem which is a key theorem in the study of networks. An excellent text on graph theory is: R. J. Wilson, Introduction to graph theory. Curriculum designers could do worse than use the definitions in Wilson. Here is a link to the 4th edition.

    Click to access wilsongraph.pdf

    Wilson’s book shows that there is a lot of material than can be studied before you ever need the concept of a network.

  9. A few times I worked in Hungary where they have special summer schools in mathematics for enthusiastic high school students. I was told that they don’t invite Erdos to these schools anymore because he turns the students into graph theorists rather than mathematicians.

  10. This might be a bit pedantic, but given Marty’s recent string of grammar lessons, I feel empowered to suggest another issue with the question:

    An adjacency matrix is formed. Not The adjacency matrix is formed.

    Does this not suggest that there are multiple possibilities for said matrix?

    Based on that logic, no answer is possible, because the question setter does not indicate that they know which adjacency matrix was formed…

    1. Aha. In the interests of demonstrating that my loathing and detestation of VCAA is based on the mathematics and is nothing personal, I will defend VCAA on this particular score. If you go right back to the top of the blog, you’ll see that the adjacency matrix I constructed is based on the columns (and rows) being labelled in the order J K L M N. There’s nothing special about this order except convenience. Use a different order and you get a different adjacency matrix (that is ‘equivalent’ to mine). However, regardless of the order, the structure of the graph is (obviously) maintained and so there will still be the same number of zeros.

      So it does make sense to ask for \displaystyle an adjacency matrix rather than \displaystyle the adjacency matrix.

Leave a Reply

Your email address will not be published.

The maximum upload file size: 128 MB. You can upload: image, audio, video, document, spreadsheet, interactive, text, archive, code, other. Links to YouTube, Facebook, Twitter and other services inserted in the comment text will be automatically embedded. Drop file here

This site uses Akismet to reduce spam. Learn how your comment data is processed.