MCSN Quiz

Comments on quiz #1

1) Technically a loop is either an edge (undirected) or an arc (directed). However I didn't downgrade you for treating a loop as a third category of graph of object (neither arc nor edge).

2) The degree of a vertex measures the number of incident lines (whether edges or arcs). Therefore an arc from A to B, plus an arc from B to A, counts for degree 2 on both A and B. Some people counted the two oppositely directed arcs between A and B as contributing only one degree to A (but two to B, for some reason). That's ok. It's possible to treat bidirectional arcs as edges (making A's degree 3 rather than 4), but you should treat A and B the same way. A sidenote: a loop is by convention considered to contribute degree 2 to its single vertex.

3) Some people forgot what a simple graph is. A simple undirected graph contains neither multiple edges nor loops; a simple digraph contains no multiple edges. Others forgot the definition of a connected graph. A connected graph is in one piece - any two vertices are connected by a path.

4, 5) Everyone got these!

6) Most people got something right here. But defining a term requires precision! A partition is a classification of each vertex in a network to exactly one class or cluster. If you want to add that the classes are represented by integers or discrete values that's fine too. Adding that these may represent attributes is also ok. But the key is the "assignment" of vertices to classes, such that every vertex is assigned to one class - no more, no less.