CS 173: Skills list for Fourth Written Test

The fourth written test will have 3 questions, that require writing proofs, on topics related to directed graphs, DAGs, Partial orders, and undirected graphs. 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.
  • Know how to model a problem as a graph.
• 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 walk 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.
  • Be able to prove properties about walk relations G^+ and G^*.
  • Be able to read a new definition about graph concepts and prove simple facts about a new definition.
• 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.
  • Be able to prove simple properties about directed graphs.
• 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.
  • Be able to prove that a relation satisfies properties of a strict partial order or (weak) partial order.
  • Be able to prove that a relation is symmetric, asymmetric, anti-symmetric, transitive, reflexive, etc.
• Graph basics
  • Know that a graph is a set of vertices/nodes plus a set of edges.
  • Know that an edge is a subset if vertices of cardinality 2.
  • Know how to name edges via their endpoints as {v,w}.
  • Be able to specify a walk as an alternating sequence of vertices and edges that begins and ends with a vertex.
  • Be able to model problems as graphs.
• Graph terminology and notation
  • Basics: adjacent/neighboring vertices, endpoints of an edge, edge connecting (incident with) two vertices, degree of a vertex, subgraph
  • Special example graphs: K_n, C_n, W_n, K_n,m. Know shorthand, full names, structure, numbers of vertices and edges. Beware: W_n contains n+1 vertices.
  • Walks: walk, open walk, closed walk, cycle, path.
  • Connectivity: connected graph, connected component, acyclic.
  • Distances: length of a path (number of edges in it), distance between two nodes.
  • Other facts and concepts: Euler circuit, Handshaking theorem, bipartite graph
• Graph properties
  • Find the number of connected components in a graph
  • Know what a Euler tour of a graph is.
  • Determine if a graph has an Euler circuit (all vertices in the graph must have even degree).
  • Know what a Hamiltonian cycle in a graph is.
• Graph isomorphism
  • Prove that two graphs are isomorphic by giving a bijection between their vertices.
  • Prove that two graphs are not isomorphic by finding a feature that differs, e.g. different numbers of nodes/edges, different numbers of vertices with a specific degree k, small subgraph present in one graph but not in the other.
• Graph Coloring
  • Know the definition of coloring of a graph.
  • Know how to give a coloring for an example graph.
  • Know the definition of chromatic number of a graph.
  • Be able to argue that a graph has a certain chromatic number.
  • Know that a graph is bipartite if and only if its chromatic number is 2.