MATH239 Study Guide - Planar Graph, Flow Network, Graph Theory
29 Oct 2015
School
Department
Course
Professor
Document Summary
Enumeration and recurrence relations: binomial theorem (1 + x) =p, combinatorial proofs, generating functions, sum and product lemmas k 0 (cid:0) k (cid:1)xk. Application 2: (uniquely created) sets of binary strings, decomposition theorems: recurrence relations generating functions, solving recurrence relations explicitly. P deg(v) = 2q: basic de nitions: isomorphism, walks, paths, connectedness, cuts, cycles, bridges. Corollary: the number of vertices of odd degree is even. If there"s a walk from u to v, there"s a path from u to v. G connected every proper nonempty x v (g) induces a nonempty cut. An edge is a bridge it"s not in a cycle. E = {x, y} a bridge x, y in di erent components of g e. Two distinct paths from u to v = g contains a cycle: trees. At least two leaves (vertices of degree 1: spanning trees, bfsts, girth. Primary property of bfsts: adjacent vertices are at most 1 level apart.
