Graph Exercise

in Posts

This is an exercise I usually do in class. We’ll do it individually as “homework”. You must turn it in. We will grade it for “effort” (check/no check, and maybe a notation for something exceptional).

You must draw out all of the parts. Draw it by hand - do not use software to do it (that defeats the purpose). Turn in a PDF or image file with your pictures. Graph Exercise (due Mon, Nov 23)

One caveat: once you see “the answer” everything else is obvious. Try not to cheat.

Here is a simple graph.

  • 9 nodes (A,B,C,D,E,F,G,H,I)
  • 12 edges (C,H), (F,A), (H,A), (E,G), (I,C), (E,I), (A,G), (E,B), (B,I), (D,C), (F,G), (H,D)

  1. Draw a quick node link diagram (or two)

  2. Draw a representation that is not a node-link diagram that helps expose the structure, which will help you in step 3

  3. Draw a “better” node-link diagram (that exposes the structure of the graph)

So, your page should have (at least) 3 pictues on it. Please turn in a single PDF or image file.

Discussion

An unfortunate problem with doing this as an online assignment is that we cannot discuss it in between phases.

One of the things that is interesting is that there is a “right answer” - something that many people come up with, and the consensus in class is that it is the best node link diagram for showing the structure in this graph. It is interesting to think about why people like the “right answer” so much. It’s not like there is a ground truth, but there is a consensus.

Grading

We’ll grade this check/no check and count it as part of your participation grade.