Outline
- Counting
- Relation
- Graphs
- Tree
- P, NP and NPC Problems
Chapter 11 - Counting
Basic Counting Rules： the Product Rule & the Sum Rule
Pigeonhole Principle：
If there are more objects than bins then there is at least one bin with more than one object.
Generalized Pigeonhole Principle：
If $N$ objects are placed into $k$ bins, then there is at least one bin containing at least $⌈N/k⌉$ objects.
Inclusion-Exclusion Principle：
$|A\cup B|=|A|+|B|-|A\cap B|$
$|\bigcup\limits_{i=1}^{n}E_i|=\sum\limits_{k=1}^{n}(-1)^{k+1}\sum\limits_{1\le i_1<i_2<\cdots<i_k\le n}|E_{i_1}\cap E_{i_2}\cap\cdots \cap E_{i_k}|$
Permutations：
$P(n,k)=\frac{n!}{(n-k)!}$
Binomial Coefficient：
$\left(\begin{array}{c}
n \\
k
\end{array}\right)=C(n, k)=\frac{n!}{k!(n-k)!}$
Some Properties of Binomial Coefficients：
$\left(\begin{array}{c}
n \\
k
\end{array}\right)=\left(\begin{array}{c}
n \\
n-k
\end{array}\right)$
$\sum\limits_{i=0}^{n}\left(\begin{array}{c}
n \\
i
\end{array}\right)=2^n$
Pascal identity：
$\left(\begin{array}{c}
n \\
k
\end{array}\right)=\left(\begin{array}{c}
n-1 \\
k-1
\end{array}\right)+\left(\begin{array}{c}
n-1 \\
k
\end{array}\right)$
Pascal’s Triangle：
$\begin{array}{l}
1 \\
1 \quad 1 \\
\begin{array}{lll}
1 & 2 & 1
\end{array} \\
\begin{array}{llll}
1 & 3 & 3 & 1
\end{array} \\
\begin{array}{lllll}
1 & 4 & 6 & 4 & 1
\end{array} \\
\begin{array}{llllll}
1 & 5 & 10 & 10 & 5 & 1
\end{array} \\
\begin{array}{lllllll}
1 & 6 & 15 & 20 & 15 & 6 & 1
\end{array} \\
\end{array}$
The Binomial Theorem：
$(x+y)^n=\sum\limits_{i=0}^{n}\left(\begin{array}{c}
n \\
i
\end{array}\right)x^{n-i}y^i$.
Trinomial Coefficients：
When $k_1+k_2+k_3=n$
$\left(\begin{array}{ccc}
& n & \\
k_{1} & k_{2} & k_{3}
\end{array}\right)=\frac{n!}{k_1!k_2!k_3!}$
The Polynomial Theorem：
$(a_1+a_2+\cdots+a_m)^n=\sum\limits_{x_1+x_2+\cdots+x_m=n}\frac{n!}{x_1!x_2!\cdots x_m!}a_1^{x_1}a_2^{x_2}\cdots a_m^{x_m}$
Solving Linear Recurrence Relations of degree 2：
$a_n=c_1a_{n-1}+c_2a_{n-2}$
characteristic equation: $r^2-c_1r-c_2=0$
If CE has 2 distinct roots $r_1\ne r_2$, the solution: $a_n=\alpha_1r_1^n+\alpha_2r_2^n$
Solving Linear Recurrence Relations of degree k：
$a_n=\sum\limits_{i=1}^kc_ia_{n-i}$
CE: $r^k-\sum\limits_{i=1}^k c_ir^{k-i}=0$
If CE has $k$ distinct roots $r_i$, then the solution: $a_n=\sum\limits_{i=1}^k \alpha_ir_i^n$
The Case of Degenerate Roots in General：
Suppose there are $t$ roots $r_1,\cdots, r_t$ with multiplicities $m_1,\cdots,m_t$. Then the solution:
Linear Nonhomogeneous Recurrence Relations：
$a_n=F(n)+\sum\limits_{i=1}^kc_ia_{n-i}$
- Solve $a_n=\sum\limits_{i=1}^kc_ia_{n-i}$ and get $a_n=h(n)$
- Solve particular solution $p(n)$
- $a_n=p(n)+h(n)$
Generating Functions：
$G(x)=a_0+a_1x+\cdots+a_kx^k+\cdots=\sum\limits_{k=0}^{\infty}a_kx^k$
Examples of Generating Functions：
$G(x)=1/(1-x)$ for $|x|<1$
$1,1,1,1,1,\cdots$
$G(x)=1/(1-ax)$ for $|ax|<1$
$1,a,a^2,a^3,a^4,\cdots$
$G(x)=1/(1-x)^2$ for $|x|<1$
$1,2,3,4,5,\cdots$
$G(x)=1/(1-ax)^2$ for $|ax|<1$
$1,2a,3a^2,4a^3,5a^4,\cdots$
Operations of Generating Functions：
Let $f(x)=\sum\limits_{k=0}^{\infty}a_kx^k$, and $g(x)=\sum\limits_{k=0}^{\infty}b_kx^k$
Then
Convolution Rule：
Let $A(x)$ be the generating function for selecting items from a set $A$, and let $B(x)$ be the generating function for selecting items from a set $B$ disjoint from $A$. Then the generating function for selecting items from the union $A ∪ B$ is the product $A(x) \cdot B(x)$.
e.g. Number of ways to select $n$ balls with $k$ colors.
$D(x)=1/(1-x)^k$, $d_n=[x^n] (1/(1-x)^k)=\left(\begin{array}{c}n+k-1 \\n\end{array}\right)$
Useful Generating Functions：
$\begin{aligned}
(1+x)^{n} & = \sum_{k=0}^{n} C(n, k) x^{k} \\
(1+a x)^{n} & = \sum\limits_{k=0}^{n} C(n, k) a^{k} x^{k} \\
\left(1+x^{r}\right)^{n} & = \sum\limits_{k=0}^{n} C(n, k) x^{r k} \\
\frac{1-x^{n+1}}{1-x} & = \sum\limits_{k=0}^{n} x^{k} = 1+x+x^{2}+\cdots+x^{n} \\
\frac{1}{1-x} & = \sum\limits_{k=0}^{\infty} x^{k} = 1+x+x^{2}+\cdots \\
\frac{1}{1-a x} & = \sum\limits_{k=0}^{\infty} a^{k} x^{k} = 1+a x+a^{2} x^{2}+\cdots \\
\frac{1}{1-x^{r}} & = \sum\limits_{k=0}^{\infty} x^{r k} = 1+x^{r}+x^{2 r}+\cdots \\
\frac{1}{(1-x)^{2}} & = \sum\limits_{k=0}^{\infty}(k+1) x^{k} = 1+2 x+3 x^{2}+\cdots \\
\frac{1}{(1-x)^{n}} & = \sum\limits_{k=0}^{\infty} C(n+k-1, k) x^{k} \\
\frac{1}{(1+x)^{n}} & = \sum\limits_{k=0}^{\infty} C(n+k-1, k)(-1)^{k} x^{k} \\
\frac{1}{(1-a x)^{n}} & = \sum\limits_{k=0}^{\infty} C(n+k-1, k) a^{k} x^{k} \\
e^{x} & = \sum\limits_{k=0}^{\infty} \frac{x^{k}}{k !} = 1+x+\frac{x^{2}}{2 !}+\frac{x^{3}}{3 !}+\cdots \\
\ln (1+x) & = \sum\limits_{k=0}^{\infty} \frac{(-1)^{k+1} x^{k}}{k} = x-\frac{x^{2}}{2}+\frac{x^{3}}{3}-\frac{x^{4}}{4}+\cdots
\end{aligned}$
r-Combinations from a Set：
An n-combination with repetition allowed, or a multiset of size $n$, chosen from a set of $k$ elements, is an unordered selection of elements with repetition allowed.
number of n-combinations: $C(n+k-1,n)$
Chapter 12 - Relation
Properties of Relations：
Reflexive Relation：$\forall a\in A$, $(a,a)\in R$
Irreflexive Relation：$\forall a\in A$, $(a,a)\notin R$
- Symmetric Relation：$\forall a,b\in A$, $(a,b)\in R→(b,a)\in R$
Antisymmetric Relation：$\forall a,b\in A$, $(a,b)\in R\wedge (b,a)\in R→a=b$
Transitive Relation：$\forall a,b,c\in A$, $(a,b)\in R\wedge (b,c)\in R→(a,c)\in R$
Combining Relations：
Using set operations.
Composite of Relations：
$(a,b)\in R$, $(b,c)\in S$, then $(a,c)\in S\circ R$
The powers $R^n$, for $n=1,2,3,\cdots$, is defined inductively by
$R^1=R$ and $R^{n+1}=R^n\circ R$
The relation $R$ on a set $A$ is transitive IFF $R^n\subseteq R$ for $n=1,2,3,\cdots$
Number of Reflexive Relations：
The number of reflexive relations on a set $A$ with $|A|=n$ is $2^{n(n-1)}$
Proof: $n$ diagonal elements fixed, the other $n(n-1)$ elements are free to choose.
Representing Relations：
explicit list/table, function $f:D→\{T,F\}$, 01 matrix, directed graph…
Closures of Relations：
Let $R$ be a relation on a set $A$. A relation $S$ on $A$ with property $P$ is called the closure of $R$ with respect to $P$ if $S$ is subset of every relation $Q$ ($S\subseteq Q$) with property $P$ that contains $R$ ($R\subseteq Q$).
$S$ is the minimal set containing $R$ satisfying the property $P$.
- reflexive closures
- symmetric closures
- transitive closures
Path Length：
Let $R$ be relation on a set $A$. There is a path of length $n$ from $a$ to $b$ IFF $(a,b)\in R^n$.
Proof by induction.
Let $A$ be a set with $n$ elements, and $R$ a relation on $A$. If there exists a path from $a$ to $b$ with $a\ne b$, then there exists a path of length $\le n-1$.
Connectivity Relation：
Let $R$ be a relation on a set $A$. The connectivity relation $R^\star$ consists of all pairs $(a,b)$ such that there is a path (of any length) between $a$ and $b$ in $R$.
The transitive closure of a relation $R$ equals the connectivity relation $R^\star$.
Proof:
$R^\star$ is transitive.
$(a,b)\in R^\star$ and $(b,c)\in R^\star$, then there are paths from $a$ to $b$ and from $b$ to $c$ in $R$. Thus, there is a path from $a$ to $c$ in $R$. This means that $(a,c)\in R^\star$.
$R^\star\subseteq S$ whenever $S$ is a transitive relation containing $R$.
Suppose that $S$ is a transitive relation containing $R$.
Then $S^n$ is also transitive and $S^n\subseteq S$.
We have $S^\star\subseteq S$. Thus $R^\star\subseteq S^\star\subseteq S$.
Transitive Closure Algorithm：
Roy-Warshall Algorithm ($\Theta(n^3)$)
1 | // computes R* ith zero-one matrices |
n-ary Relations & Relational Databases：
domains, degree, functional, primary key, composite key, selection, projection, join…
Equivalence Relation：
A relation $R$ on a set $A$ is called an equivalence relation if it is reflexive, symmetric and transitive.
Equivalence Class：
Let $R$ be an equivalence relation on a set $A$. The set of all elements that are related to an element $a$ of $A$ is called the equivalence class of $a$, denoted by $[a]_R$. When only on relation is considered, we use the notation $[a]$.
Let $R$ be an equivalence relation on a set $A$. The following statements are equivalent:
- $a\ R\ b$
- $[a]=[b]$
- $[a]\cap[b]\ne0$
Proof:
1→2: Prove $[a]\subseteq[b]$ and $[b]\subseteq[a]$
2→3: $[a]$ is not empty ($R$ reflexive)
3→1: $\exists c$ s.t. $c\in[a]$ and $c\in [b]$
Partition of a set：
Let $S$ be a set. A collection of nonempty subsets of $S$ $A_1,A_2,\cdots,A_k$ is called a partition of $S$ is
$A_i\cap A_j=\emptyset$, $i\ne j$ and $S=\bigcup\limits_{i=1}^{k}A_i$
Equivalence Classes and Partitions：
Let $R$ be an equivalence relation on a set $A$. Then union of all th equivalence classes of $R$ is $A$:
The equivalence classes form a partition of $A$.
Let $\{A_1,A_2,\cdots,A_i,\cdots\}$ be a partition of $S$. Then there is an equivalence relation $R$ on $S$, that has the sets $A_i$ as its equivalence classes.
Partial Ordering：
A relation $R$ on a set $S$ is called a partial ordering, if it is reflexive, antisymmetric and transitive. A set $S$ together with a partial ordering $R$ is called a poset, denoted by $(S,R)$. Members of $S$ are called elements of the poset.
Comparability：
The elements $a$ and $b$ of a poset $(S,≼)$ are comparable if either $a≼b$ or $b≼a$. Otherwise, $a$ and $b$ are called incomparable.
Total Ordering：
If $(S,≼)$ is a poset and every two elements of $S$ are comparable, $S$ is called a totally ordered or linearly ordered set, and $≼$ is called a total order or a linear order. A totally ordered set is also called a chain.
Lexicographic Ordering：
Given two posets $(A_1,≼_1)$ and $(A_2,≼_2)$, the lexicographic ordering on $A_1\times A_2$ is defined by specifying that $(a_1,a_2)$ is less than $(b_1,b_2)$, i.e., $(a_1,a_2)≼(b_1,b_2)$, either if $a_1≺_1b_1$ or if $a_1=b_1$ then $a_2≼_2b_2$.
Hasse Diagram：
……
Maximal and Minimal Elements：
$a$ is a maximal (resp. minimal) element in poset $(S, ≼)$ is there is no $b\in S$ such that $a ≺ b$ (resp. $b ≺ a$).
Greatest and Least Elements：
$a$ is the greatest (resp. least) element of the poset $(S, ≼)$ if $b ≼ a$ (resp. $a ≼ b$) for all $b\in S$.
Upper Bound and Lower Bound：
$u\in S$ is called an upper bound (resp. lower bound) of $A$ if $a ≼ u$ (resp. $u ≼ a$) for all $a\in A$.
$x\in S$ is called the least upper bound (resp. greatest lower bound) of $A$ if $x$ is an upper bound (resp. lower bound) that is less than any other upper bound (resp. greater than any other lower bound) of $A$.
Well-Ordered Set：
$(S, ≼)$ is a well-ordered set if it is a poset such that $≼$ is a total ordering and every non empty subset of $S$ has a least element.
The Principle of Well-Ordered Induction：
Suppose that $S$ is a well-ordered set. Then $P(x)$ is true for all $x\in S$, if
Inductive Step: For every $y\in S$, if $P(x)$ is true for all $x\in S$ with $x ≺ y$, then $P(y)$ is true.
The reason for no base step: For the least element $x_0$, the precedent “P(x) is true for all $x\in S$ with $x ≺ x_0$” is itself false, by vacuous proof, $P(x_0)$ is true.
Lattices：
A poset in which every pair of elements has both a least upper bound and a greatest lower bound is called a lattice.
Topological Sorting：
Given a partial ordering $R$, find a total ordering $≼$ such that $a≼b$ whenever $a\ R\ b$. $≼$ is said compatible with $R$.
Chapter 13 - Graph
Definition of a Graph：
A graph $G=(V,E)$ consists of a nonempty set $V$ of vertices and a set $R$ of edges. Each edge has either one or two vertices associated with it, called its endpoints. An edge is said to be incident to its endpoints.
Simple graph：
A graph in which at most one edge joins each pair of distinct vertices and no edge joins a vertex to itself.
multigraph：
Graphs that may have multiple edges connecting the same vertices.
pseudograph：
Graphs that may include loops, and possibly multiple edges connecting the same pair of vertices or a vertex to itself.
Undirected Graphs：
adjacent(neighbors), neighborhood, degree…
Handshaking Theorem: If $G=(V,E)$ is an undirected graph with $m$ edges, then $2m=\sum\limits_{v\in V}deg(v)$.
An undirected graph has an even number of vertices of odd degree.
Directed Graphs：
adjacent from, adjacent to, in-degree $deg^-(v)$, out-degree $deg^+(v)$
$|E|=\sum\limits_{v\in V}deg^-(v)=\sum\limits_{v\in V}deg^+(v)$
Complete Graphs：
A complete graph on $n$ vertices, denoted by $K_n$, is the simple graph that contains exactly one edge between each pair of distinct vertices.
Cycles：
A cycle $C_n$ for $n \ge 3$ consists of $n$ vertices $v_1, v_2,\cdots, v_n$, and edges $\{v_1,v_2\},\{v_2,v_3\},\cdots,\{v_{n-1},v_n\},\{v_n,v_1\}$.
Wheels：
A wheel $W_n$ is obtained by adding an additional vertex to a cycle $C_n$.
N-dimensional Hypercube：
An n-cube $Q_n$ is a graph with $2^n$ vertices representing all bit strings of length $n$, where there is an edge between two vertices that differ in exactly one bit position.
Bipartite Graphs：
A simple graph $G$ is bipartite if $V$ can be partitioned into two disjoint subsets $V_1$ and $V_2$ such that every edge connects a vertex in $V_1$ and a vertex in $V_2$.
Complete Bipartite Graphs：
A complete bipartite graph $K_{m,n}$ is a graph that has its vertex set partitioned into two subsets $V_1$ of size $m$ and $V_2$ of size $n$ such that there is an edge from every vertex in $V_1$ to every vertex in $V_2$.
Bipartite Graphs and Matchings：
A matching is a subset of $E$ such that no two edges are incident with the same vertex.
A maximum matching is a matching with the largest number of edges.
A matching $M$ in a bipartite graph $G=(V,E)$ wth bipartition $(V_1,V_2)$ is a complete matching from $V_1$ to $V_2$ if every vertex in $V_1$ is the endpoint of an edge in the matching, i.e., $|M|=|V_1|$.
Hall’s Marriage Theorem：
The bipartite graph $G=(V,E)$ with bipartition $(V_1,V_2)$ has a complete matching from $V_1$ to $V_2$ IFF $|N(A)|\ge |A|$ for all subsets $A$ of $V_1$.
“only if”: For every vertex $v\in A$, there is an edge in $M$ connecting $v$ to a vertex in $V_2$. Thus, for all subsets $A$ of $V_1$, there are at least as many vertices in $V_2$ that are neigbors of vertices in $A$ as there are vertices in $A$, $|N(A)|\ge |A|$.
“if”: Use strong induction.
Base step: $|V_1|=1$
Inductive hypothesis: Let $k$ be a positive integer. If $G=(V,E)$ is a bipartite graph ith bipartition $(V_1,V_2)$, and $|V_1|=j\le k$, then there is a complete matching $M$ from $V_1$ to $V_2$ whenever the condition that $|N(A)|\ge |A|$ for all $A\subseteq V_1$ is met.
Inductive step: suppose that $H=(W,F)$ is a bipartite graph with bipartition $(W_1,W_2)$ and $|W_1|=k+1$
Case (Ⅰ): For all integers $j$ with $1\le j\le k$, the vertices in every set of $j$ elements from $W_1$ are adjacent to at least $j+1$ elements of $W_2$.
Find a complete matching from $W_1-\{v\}$ to $W_2-\{w\}$, then match $v$ to $w$.
Case (Ⅱ): For some integer $j$ with $1\le j\le k$, there is a subset $W_1’$ of $j$ vertices such that there are exactly $j$ neighbors of these vertices in $W_2$.
Let $W_2’$ be the set of these neighbors. Then by i.h., there is a complete matching from $W_1’$ to $W_2’$. Now consider the graph $K=(W_1-W_1’,W_2-W_2’)$. We will show that the condition $|N(A)|\ge |A|$ is met for all subsets $A$ of $W_1-W_1’$.
If not, there is a subset $B$ of $t$ vertices with $1\le t\le k+1-j$ such that $|N(B)|<|B|$, contradiction.
Then there is a complete matching for $K$, and thus a complete matching for $G$.
Subgraphs：
A subgraph of a graph $G=(V,E)$ is a graph $(W,F)$, where $W\subseteq V$ and $F\subseteq E$. A subgraph $H$ of $G$ is a proper subgraph of $G$ if $H\ne G$.
Union of Simple Graphs：
Simple graph: $G_1\cup G_2=(V_1\cup V_2, E_1\cup E_2)$
Representation of Graphs：
adjacency lists, adjacency matrices, and incidence matrices.
Isomorphism of Graphs：
The simple graphs $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$ are isomorphic if there is a bijection from $V_1$ to $V_2$ with the property that $a$ and $b$ are adjacent in $G_1$ IFF $f(a)$ and $f(b)$ are adjacent in $G_2$, for all $a$ and $b$ in $V_1$. Such a function is called an isomorphism.
Useful graph invariants: the number of vertices, number of edges, degree sequence, etc.
Path：
Let $n$ be a nonnegative integer and $G$ an undirected graph. A path of length $n$ from $u$ to $v$ in $G$ is a sequence of $n$ edges $e_1,e_2,\cdots,e_n$ of $G$ for which there exists a sequence $x_0=u,x_1,\cdots,x_{n-1},x_n=v$ of vertices such that $e_i$ has the endpoints $x_{i-1}$ and $x_i$ for $i=1,\cdots,n$.
A path is simple if it does not contain the same edge more than once.
Circuit：
The path is a circuit if it begins and ends at the same vertex, i.e., if $u=v$ and has the length greater than $0$.
Simple Path Existence Lemma：
If there is a path between two distinct vertices $x$ and $y$ in graph $G$, then there is a simple path between $x$ and $y$ in $G$. (Just delete cycles/loops.)
Connected Components：
A connected component of a graph $G$ is a connected subgraph of $G$ that is not a proper subgraph of another connected subgraph of $G$.
Connectedness in Directed Graphs：
A directed graph is strongly connected if there is a path from $a$ to $b$ and a path from $b$ to $a$ whenever $a$ and $b$ are vertices in the graph.
A directed graph is weakly connected if there is a path between every two vertices in the underlying undirected graph.
Cut Vertices and Cut Edges：
……
A set of edges $E’$ is called an edge cut of $G$ if the subgraph $G-E’$ is disconnected. The edge connectivity $\lambda(G)$ is the minimum number of edges in an edge cut of $G$.
Paths and Isomorphism：
The existence of a simple circuit of length $k$ is isomorphic invariant. In addition, paths can be used to construct mappings that may be isomorphisms.
Counting Paths between Vertices：
Let $G$ be a graph with adjacency matrix $A$ with respect to the ordering $v_1, v_2,\cdots, v_n$ of vertices. The number of different paths of length r from $v_i$ to $v_j$ , where $r > 0$ is positive, equals the $(i, j)$-th entry of $A^r$.
Proof by induction:
$A^{r+1}=A^rA$, the $(i,j)$-th entry of $A^{r+1}$ equals $b_{i1}a_{1j}+b_{i2}a_{2j}+\cdots+b_{in}a_{nj}$, where $b_{ik}$ is the $(i,k)$-th entry of $A^r$.
Euler Paths and Circuits：
An Euler circuit in a graph $G$ is a simple circuit containing every edge of $G$.
A connected multigraph with at least two vertices has an Euler circuit IFF each of its vertices has even degree.
An Euler path in $G$ is a simple path containing every edge of $G$.
A connected multigraph has an Euler path but not an Euler circuit IFF it has exactly two vertices of odd degree.
Hamilton Paths and Circuits：
A simple path in a graph $G$ that passes through every vertex exactly once is called a Hamilton path.
A simple circuit in a graph $G$ that passes through every vertex exactly once is called a Hamilton circuit.
Sufficient Conditions for Hamilton Circuits：
Dirac’s Theorem： If $G$ is a simple graph with $n\ge 3$ vertices such that the degree of every vertex in $G$ is $\ge n/2$, then $G$ has a Hamilton circuit.
Ore’s Theorem： If $G$ is a simple graph with $n\ge 3$ vertices such that $deg(u)+deg(v)\ge n$ for every pair of nonadjacent vertices, then $G$ has a Hamilton circuit.
Shortest Path Problems：
Dijkstra-$O(v^2)$, Fredman & Tarjan-$O(e+v\log v)$, Bellman-Ford-$O(ev)$…
Planar Graphs：
A graph is called planar if it can be drawn in the plane without any edge crossing. Such a drawing is called a planar representation of the graph.
Euler’s Formula：
Let $G$ be a connected planar simple graph with $e$ edges and $v$ vertices. Let $r$ be the number of regions ina planar representation of $G$. Then $r=e-v+2$.
Proof by induction.
The Degree of Regions：
The degree of a region is defined to be the number of edges on the boundary of this region. When an edge occurs twice on the boundary, it contributes two to the degree.
Corollaries of Planar Graphs：
Corollary 1： If $G$ is a connected planar simple graph with $e$ edges and $v$ vertices, where $v\ge3$, then $e\le 3v-6$.
The degree of every region is at least 3.
The sum of the degrees of the regions is exactly twice the number of edges in the graph.
Corollary 2：If $G$ is a connected planar simple graph, then $G$ has a vertex of degree not exceeding 5.
- Proof by contradiction using Corollary 1 and Handshaking Theorem.
Corollary 3：In a connected planar simple graph has $e$ edges and $v$ vertices with $v\ge3$ and no circuits of length 3, then $e\le2v-4$.
- The degree of every region is at least 4. (no circuit of length 3)
Kuratowski’s Theorem：
If a graph is planar, so will be any graph obtained by removing an edge $\{u, v\}$ and adding a new vertex $w$ together with edges $\{u,w\}$ and $\{w, v\}$. Such an operation is called an elementary subdivision.
The graphs $G_1 = (V_1, E_1 )$ and $G_2 = (V_2, E_2 )$ are called homomorphic if they can be obtained from the same graph by a sequence of elementary subdivisions.
A graph is nonplanar IFF it contains a subgraph homomorphic to $K_{3,3}$ or $K_5$.
Graph Coloring：
A coloring of a simple graph is the assignment of a color to each vertex of the graph so that no two adjacent vertices are assigned the same color.
The chromatic number of a graph is the least number of colors needed for a coloring of this graph, denoted by $\chi(G)$.
Four-color theorem：
The chromatic number of a planar graph is no greater than 4.
Six Color Theorem：
The chromatic number of a planar graph is no greater than 6.
Proof by induction. (w.l.o.g., assume that the graph is connected)
Basic step: For a single vertex, pick an arbitrary color.
Inductive hypothesis: Assume that every planar graph with $k\ge1$ or fewer vertices can be 6-colored.
Inductive step: Consider a planar graph with $k+1$ vertices. Using Corollary 2 (the graph has a vertex of degree 5 or fewer). Remove this vertex, by i.h., we can color the remaining graph with 6 colors. Put the vertex back in. Since there are at most 5 colors adjacent, so we have at least one color left.
Five Color Theorem：
The chromatic number of a planar graph is no greater than 5.
Proof by induction. (w.l.o.g., assume that the graph is connected)
Basic step: For a single vertex, pick an arbitrary color.
Inductive hypothesis: Assume that every planar graph with $k\ge1$ or fewer vertices can be 5-colored.
Inductive step: Consider a planar graph with k + 1 vertices. Using Corollary 2 (the graph has a vertex of degree 5 or fewer). Remove this vertex, by i.h., we can color the remaining graph with 5 colors. Put the vertex back in.
Case (Ⅰ): If the vertex has degree less than 5, or if it has degree 5 and only $\le 4$ colors are used for vertices connected to it, we can pick an available color for it.
Case (Ⅱ): We make a subgraph out of all the vertices colored 1 or 3. If the adjacent vertex colored 1 and the adjacent vertex colored 3 are not connected by a path in the subgraph.
On the other hand, if the vertices colored 1 and 3 are connected via a path in the subgraph, we do the the same for the vertices colored 2 and 4. Note that this will be a disconnected pair of subgraphs, separated by a path connecting the vertices colored 1 and 3.
Chapter 14 - Tree
Tree：
A tree is a connected undirected graph with no simple circuits.
An undirected graph is a tree IFF there is a unique simple path between any two of its vertices.
A rooted tree is a tree in which one vertex has been designated as the root and every edge is directed away from the root.
parent, child, sibling, ancestor, descendant, leaf, internal vertex, subtree…
m-Ary Trees：
A rooted tree is called an m-ary tree if every internal vertex has no more than $m$ children.
The tree is called a full m-ary tree if every internal vertex has exactly $m$ children.
In particular, an m-ary tree with $m = 2$ is called a binary tree.
A binary tree is an ordered rooted tree where the children of each internal vertex are ordered.
In a binary tree, the first child is called the left child, and the second child is called the right child.
left subtree, right subtree
Counting Vertices in a Full m-Ary Trees：
A full m-ary tree with $i$ internal vertices has $n = mi + 1$ vertices. Leaves number $ℓ=n-i$.
Level and Height：
The level of a vertex $v$ in a rooted tree is the length of the unique path from the root to this vertex.
The height of a rooted tree is the maximum of the levels of the vertices.
A rooted m-ary tree of height $h$ is balanced if all leaves are at levels $h$ or $h − 1$. (differ no greater than 1)
The Number of Leaves：
There are at most $m^h$ leaves in an m-ary tree of height $h$.
If an m-ary tree of height $h$ has ℓ leaves, then $h \ge ⌈\log_m ℓ⌉$. If the m-ary tree is full and balanced, then h = $⌈\log_mℓ⌉$.
Tree Traversal：
preorder traversal, inorder traversal, postorder traversal.
expression trees, prefix notation, infix notation, postfix notation.
Catalan Numbers：
$C_0=C_1=1$
$C_n=\sum\limits_{i=0}^{n-1}C_iC_{n-i-1}=\frac{1}{n+1}\left(\begin{array}{c}2n \\n\end{array}\right)=\left(\begin{array}{c}2n \\n\end{array}\right)-\left(\begin{array}{c}2n \\n-1\end{array}\right)$
The number of 01 sequences using $n$ ones and $n$ zeros such that the number of ones is no less than the number of zeros in any prefix subsequence.
The number of full binary trees with $2n+1$ vertices.
The number of binary trees with $n$ vertices.
Spanning Trees：
Let $G$ be a simple graph. A spanning tree of $G$ is a subgraph of $G$ that is a tree containing every vertex of $G$.
A simple graph is connected IFF it has a spanning tree.
DFS, BFS：
……
Minimum Spanning Trees：
Prim’s Algorithm($O(e\log v)$), Kruskal’s Algorithm($O(e\log e)$).
Chapter 15 - P, NP and NPC Problems
Class NP vs. Class P：
P： decision problems solvable in polynomial time
NP： decision problems with certificates verifiable in polynomial time (polynomial time verification)
Satisfiability Problem(NP)：
To determine whether a Boolean formula is satisfiable or not.
2SAT Problem(P)：
To determine whether a 2-CNF formula is satisfiable or not.
Using path searching (polynomial-time decidable), construct edges using “→”.
A 2-CNF formula is unsatisfiable IFF there exists a variable $x$ such that:
- there is a path from $x$ to $\neg x$ in the graph $G$
- there is a path from $\neg x$ to $x$ in the graph $G$
Polynomial-Time Reduction & The Class NP-Complete：
see Chapter 6.
Cook’s Theorem：
SAT $\in$ NPC.
3SAT $\le_P$ DCLIQUE $\le_P$ DVC
Clique：
A clique is a complete subgraph of $G$.
The Problem CLIQUE
Find a clique of maximum size in a graph $G$.
The Problem DCLIQUE
Given an undirected graph G and an integer $k$, determine whether $G$ has a clique of size $k$.
DCLIQUE $\in$ NP： certificate $O(|V^2|)$
3SAT $\le_{P}$ DCLIQUE：
For the $k$ clauses input to 3SAT, draw literals as vertices, and all edges between vertices such that:
- across clauses only
- not between $x$ and $\neg x$
The reduction takes polynomial time: A satisfiable assignment $⇌$ a clique of size $k$
Vertex Cover：
A vertex cover of $G$ is a set of vertices such that every edge in $G$ is incident at at least one of these vertices.
The Vertex Cover Problem (VC)
Given a graph $G$, find a vertex cover of $G$ of minimum size.
The Problem DVC
Given a graph $G$ and an integer $k$, determine whether $G$ has a vertex cover of with $k$ vertices.
DVC $\in$ NP： certificate $O(ke)=O((n+e)^2)$
DCLIQUE $\le_{P}$ DVC：
Start with the graph $G=(V,E)$ input of the DCLIQUE problem.
Construct the complement graph $\bar G=(V,\bar E)$ by only considering the missing edges from $E$.
The reduction takes polynomial time: A clique of size $k$ in $G$ $⇌$ a vertex cover of size $|V|-k$ in $\bar G$
Approximate Vertex Cover：
Approx-Vertex-Cover is a 2-approximation algorithm, i.e., $\frac{|C|}{|C^\star|}\le 2$.
Proof:
The set of edges picked by this algorithm is a maximal-maching $M$: no two edges touch each other.
The potimal vertex cover $C^\star$ must cover every edge in $M$, so $|C^\star|\ge |M|$. The algorithm returns a vertex set of size $2|M|$. Therefore, we have
.
