CS 173: Skills list for fourth CBTF Test

The fourth CBTF test will have 5 questions on topics related to directed graphs, DAGs and Partial orders. The specific skills it will test are

• Directed Graph basics
  • Know that a graph is a set of vertices/nodes plus a set of edges.
  • Know that the edges in a digraph are a binary relation on the vertices.
  • Know how to name edges via their endpoints, e.g. (v,w).
  • Be able to specify a walk using an alternating sequence of vertices and edges.
• Directed Graph terminology and notation
  • Basics: in degree and out degree of a vertex
  • Walks: walk, closed walk, cycle, path. Know what each is and their differences
  • Distances: length of a path (number of edges in it), distance between two nodes.
  • Know the relationship between the sum of the out degrees of vertices, sum of the in degrees of vertices and the number of edges.
  • Know what the path accessibility relations G^+ and G^* are. Be able to identify whether a pair of vertices belong to one of these relations.
  • Know that G^* is reflexive, and transitive. Know that G^+ is transitive.
  • Know the adjacency matrix representation of a digraph.
  • Know the relationship between powers of an adjacency matrix and the number of walks between vertices in a directed graph.
• Directed Acyclic Graphs
  • Know what a DAG is.
  • Be able to identify whether a digraph is a DAG.
  • Know that G^+ for a DAG is irreflexive.
  • Know what a topological sorting of a graph is.
  • Know how to check if a listing of vertices is a topological sort of a graph or not.
  • Know that every DAG has a topological sorting.
  • Know how to compute the topological sort of a DAG.
• Partial orders
  • Know when a binary relation is a strict partial order or a (weak) partial order.
  • Know what reflexivity, symmetry, transitivity of a reaction means.
  • Know what irreflexivity, asymmetry, and anti-symmetry of a binary relation means.
  • Know the relationship between the walk relations of a DAG and strict/weak partial order.