From CCE wiki archived
Jump to: navigation, search

Comments on quiz #1

1) Technically a loop is either an edge (undirected) or an arc (directed) - not that it makes all that much difference. However I didn't downgrade you for treating a loop as a third category of graph of object (neither arc nor edge), since it's often treated that way.

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. That's ok (but then you should also treat it as counting one degree to B). 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. A couple of you forgot what an undirected graph is - and drew directed rather than undirected graphs. In this case the notion of connectedness is a bit more complex - we have strong connectedness when every two vertices are connected by a path that respects arrow direction, and weak connectedness if every two vertices are connected by a path that feels free to take one-ways the wrong way. (But you weren't supposed to draw digraphs precisely to avoid such nuances!).

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.