CS 173: Skills list for Examlet 4
- Graph basics
- Know that a graph is a set of vertices/nodes plus a set of edges.
- Know what a loop and a multi-edge are, that a "simple graph" has neither,
and that graphs in this class are simple unless we specify otherwise.
- Know how to name edges via their endpoints, e.g. vw or {v,w}.
- Be able to specify a walk using an edge sequence and/or node sequence.
- 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:
Kn, Cn, Wn,
Kn,m. Know shorthand, full names, structure, numbers of vertices and edges.
Beware: Wn contains n+1 vertices.
- Walks: walk, open walk, closed walk, cycle, path.
- Connectivity: connected graph, connected component, cut edge, acyclic.
- Distances: length of a path (number of edges in it), distance between two nodes, diameter of a graph.
- Other facts and concepts: Euler circuit, Handshaking theorem, bipartite graph
- Graph properties
- Find the number of connected components in a graph
- Determine if a graph has an Euler circuit
(all vertices in the graph must have even degree).
- Count the number of paths between two fixed nodes
- Graph isomorphism
- Prove that two graphs are isomorphic by giving a bijection between their vertices.
- Count the number of isomorphisms between two graphs.
- 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 that a (vertex) coloring of a graph is labelling of each
vertex with a color, such that adjacent vertices always have different
colors.
- Know that the chromatic number of a graph is the minimum number
of colors required to color it.
- Know the shorthand notation χ(G).
- Know that graph coloring is useful for (among other things) register allocation
in compilers for programming languages like C and Java.
- Know that if D is the maximum degree of any vertex in a graph G,
then G can be colored with D+1 colors.
- Know that the "greedy" coloring algorithm often
produces pretty good colorings fast, but is not guaranteed to produce
the best solution.
- Two-way bounding
- Understand the difference between an exact result, an upper bound, and a
lower bound.
- Prove an equality by establishing upper and lower bounds. E.g.
prove that the chromatic number of a graph G is n.
- Prove a set equality by proving inclusion in both directions.
- Summations
- Know how to read summation notation, i.e. convert between it
and a list of terms with ellipsis (...). Same for product notation.
- Extract the first or last term in a sum or product.
- Rewrite a sum or product so that its index variable starts
at a different number.
- Know the closed form for the sum of the first n integers.
- Know the closed form for a geometric series, especially
two special cases: sum
of (1/2)k and sum of 2k.
- Know how to adjust a closed form for changes in the start/end index values.
- (Easy) Induction
- Given a claim, identify/state the key parts of an inductive proof:
the induction variable, the claim
P(n), base case, inductive step, inductive hypothesis, conclusion of the inductive step.
- Be able to state a (strong) inductive hypothesis. (We always use strong hypotheses
in this class, but some of you may have used weak hypotheses in other classes.)
- Use induction to prove a formula (equality or inequality)
is correct for all integers starting at some base case.
- Use induction to prove that a non-formula claim (e.g. a divisibility relation)
holds for all integers starting at some base case.
- Any proofs for this examlet will have very simple structure.
In particular, the truth of the claim at n=k depends only on the claim being true at n=k-1,
with only one base case required.