MATH61 Review

Review for Math 61 - Discreted Structures at UCLA

基础知识

1.1 集合 Sets

• Power set: P(x): the set of all subset
• Collection:
• Partition:

3.1 函数 Function

• 单射 injective, one-to-one
  • if f(x₁) = f(x₂) then x₁ = x₂
• 满射 surjective, onto
  • for each y ∈ Y, there exist some x ∈ X where f(x) = y
• 双射 bijective, one-to-one & onto
  • if f is bijective, f is invertible

2.2 证明 Proof

• 直接证明 Direct Proof: p true -> q true
• 反证法 Proof by Contradiction: opposite false
• Proof by contrapositive: opposite q -> opposite p
• 分类讨论 Proof by Cases: different situations

数学归纳法 Mathematical Induction

• Basis step:
  • S(n0) is true.
• Inductive step:
  • 假设S(n)成立，将公式带入S(n+1)，推出S(n+1)成立。
  • For each n >= n0, if S(n) is true, S(n+1) is true

序列与字符串 Sequence and Strings

• Properties：
  • 单调递增 increasing
  • 单调递减 decreasing
  • 非增 nonincreasing
  • 非减 nondecreasing
• Closed formula for S:
  • I = [i, j], {S_k}^j_k=i(j -> max)
• subsequence
• operation: 连加 ∑，连乘 Π
• string: finite sequence of char, length |a|, concatnation, substring (consective)

关系 Relations

• subset of X×Y, xRy

• reflective: if xRx

• symmetric: if xRy, then yRx

• antisymmetric:

  • if for all x, y ∈ X, if xRy and yRx, then x=y
  • 证明: if x!=y, then either (x, y) !∈ to R or (y, x) !∈ R

• transitive:

  • for all x, y, z ∈ X, if(x, y), (y, z) ∈ R, then (x, z) ∈ R

• partial order: 同时满足 Refelective, Antisymmetric, Transitive

• total order: if each (x, y) ∈ X are comparable

  • Inverse(R^-1) = {(y|x) | xRy } ⊆ Y×X

等价关系 Equivalence Relations

• 同时满足 Reflective, Symmetric, Transitive
• equivalence classes:
  • Partition of X: [a] = {x∈X | xRa} S = {[a] | a∈X}
  • |{equivalence}| = |{partitions}|
• Relation Matrix:
  • if has relationship = 1. otherwise = 0

Chapter 6. Counting method and Pigeonhole Principle

6.1 计数原理 Counting Principles

• Mutiplication Principle
• Prove if |x| = n, then |P(x) = 2ⁿ|
• Addition Principle:
• Inclusion-Exclusion Principle:

6.2 排列组合 Permutations & Combinations

• P(n, r) = n!/(n-r)!
• C(n, r) = P(n, r)/r! = n!/(n-r)!r!
• C_n = [1/(n+1)]*C(2n, n) -> catalan numbers
• k-elements selection from x (with t elements) allow repetition
  • C(k+t-1, t-1) = C(k+t-1, k)

6.7 二项式定理 Binomical Coefficient

• proof equations directly
  • (a + b)ⁿ = ∑C(n, k)a^n-kb^k
• Proof by cancelling
  • C(n+1, k) = C(n, k-1) + C(n, k)
• Compute coefficient: C(n, k)

6.8 鸽子洞定理 Pigeonhole Principle

• if f: X->Y where X, Y finite and |X| > |Y|, then f(x1) = f(x2) for some x1, x2 ∈ X where x1 != x2
• |X| = n and |Y| = m, let k = ⌈n/m⌉, then there are at least k distinct values a let f(a) are equal

Chapter 7 Recurence Relations

7.1 递推关系 Recurrence Relations

• String doesn’t contain the pattern “111”
• Tower of Honoi
• Find closed formula for a_n

常系数线性递推公式 Linear Homogeneous Recurrence Relations of Order with Constant Coefficients (LHRC)

• a_n = c₁a_n-1 + c₂a_n-2 + … + c_ka_n-k where c_k != 0

  • ex Fibonacci numbers fn = fn-1 + fn-2 is a LHRC of order 2
  • Sn = 2Sn - 1 is a LHRC of order 1

• How to solve LHRC?

  • t²-c₁t - c₂解出两个根r1和r2
  • a_n = br₁ⁿ+dr₂ⁿ， n >= 0
  • 带入b+d = c₀ and br₁ + dr₂ = c₁

• 如果是repeated root -> a_n = brⁿ+dnrⁿ, n >= 0

Chapter 8 图论 Graph Theory

8.1 图 Examples of Graphs

• 完全图 Complete grpah:
  • K_n
• 二分图 Bipartite graph
• 完全二分图 Complete bipartite graph:
  • K_n,m

8.2 路径与环 Path & Circle

• Connected: 所有的边在一起组成一个graph
• Component: 连接在一起的顶点和边的集合
• G is connected if G has only 1 component

欧拉环 Eulerian Cycle

• A cycle in G that includes each edge + vertex in G is called an Eulerian Cycle
• 一笔画问题
• 欧拉环的总度数是边的二倍
• G has a path with no repeated edges from v to w containing all vertices + edges <==> G is connected + v, w are the only vertices in G with odd degree
• If G contains a cycle from v to v, G contains a simple cycle from v to v

哈密顿环 Hamiltonian Cycles

• A cycle in G that contains each v exactly once is a Hamiltonian cycle
• Proof no Hamiltonian Cycles
  • compute |V(G)| = n, |E(G)| = m
  • find largest S ⊆ V(G) such that v1, v2 ∈ S => (v1, v2) !∈ E(G) + d(v) > 2 for v ∈ S
  • if m - ∑(d(v)-2)< n (# edges needed for H.cycle), then no H.cycle

Degree Sequence

• nonincreasing order
• 证明degree sequence无法构成G

Shortest-Path Algorithm

• Dijkstra算法:

dijkstra (w, a, z, L){
    L(a) = 0;
    for all vertices x != a:
        L(x) = max
    T: set of all vertices
    while(z ∈ T){
        choose v ∈ T with min L(v)
        T = T - {v}
        for each x ∈ T adjacent to v
            L(x) = min {L(x), L(v) + w(v, x)}
    }
}

图的表示方法 Representations of Graphs

• 邻接矩阵 adjacency matrices:
  • if two vertices have edge = 1. otherwise = 0
  • 矩阵的n次方等于以i, j为起点的长度为n的路径的数量

图的同构 Isomorphisms of Graphs

• 如果我们可以找到一组对应关系，使得两个图G与G’上的每个顶点与每条边一一对应，则G与G’是同构关系。
  • 同构是等价关系
• 两个图同构 <==> 调换顶点顺序，两个图的邻接矩阵相同
• 如何证明两个图不同构？
  • use invariants to detect when graphs are not isomorphic

平面图 Planar Graphs

• 可以画成边不交叉的图叫做平面图
• 面 Faces: 由平面图切割的区域叫做面
  • f = e - v + 2: 面数 = 边数 - 顶点数 + 2
  • 因此，如果G不满足此条件，则G不是平面图

Series Reduction

• 减去顶点v并减去其两条边，然后将连接的两个顶点相连接

图的同胚 Homeomorphic

• 通过series reduction进行减去顶点，如果能将两个图变为同构的，则二者同胚。
  • 同胚是等价关系

平面图判断 Kuratowski

• Planar Graph <==> G does not contain a subgraph homeomorhpic to K₅ or K_{3, 3}

树 Tree

• simple graph, 且两点之间只有一个simple path
• rooted tree
• 树高 height 从0开始算
• Every tree with 2 or more movertices has a vertex of degree 1
• Tree is a bipartite graph

More trees

• 树的属性:
  • parent
  • ancestors
  • child
  • descendant
  • siblings
  • terminal vertex/leaft
  • internal vertex
  • subtree of T rooted at x
• graph with no cycles is called acyclic
  • if T is a tree, T is acyclic + connected
• 下面四个关系是等价的：
  • T is a tree
  • T is connected & acyclic
  • T is connected & |E(T)| = n -1
  • T is acyclic & |E(T)| = n - 1

生成树 Spanning Trees

• subgraph T of G such that T is a tree where V(T) = V(G) is called a spanning tree of G
• G存在生成树 <==> G是连通图
• 如何找到生成树？
  • BFS
  • DFS
• 计算完全图的subgraph数量
  • 用组合C求出总量
  • 注意需要除以重复的环
  • 如果对称，需要除以2

最小生成树 Minimal Spanning Trees

• MST: 在weighted graph G中，最小生成树的边加权最小

prim (w, n, s):
    initialize all v(i) = 0, E = Ø
    update v(s) = 1
    for i = 1 to n - 1:
        min = max
        for j = 1 to n:
            if ( v(j) = 1 ):
                for k = 1 to n:
                    if v(k) = 0 and w(j, k) < min:
                        set k to be addable vertex
                        e = (j, k)
                        min = w(j, k)
                update v(addable vertex) = 1
                update E = E∪e
    return E

二叉树 Binary Trees

• 满二叉树 full binary tree
  • each vertex has 0 or 2 children
  • if a full binary tree T has i internal vertices, then T has i + 1 terminal vertices & 2i+1 total vertices
  • 证明：V(T) = 2i + 1
• 比赛场数可以用满二叉树计算：
  • 比赛场数（internal vertices）= 队伍总数（terminal vertices）- 1
  • 可组合的可能性：2^{# internal vertices}
  • 二叉树的树高为h，且有t个terminal vertices，则log₂t <= h

树的同构 Isomorphisms of Trees

• 普通树的同构：

  • 5个顶点的树有3种不同构的组合
  • Proof by cases，从可能的最高度数到最低度数，通过度数证明

• Rooted Tree的同构：

  • rooted trees如果同构，则两者的root必须相同
  • 4个顶点的rooted trees有4种不同构的组合

• 二叉树的同构：

  • 二叉树如果同构，则两者的左子节点与右子节点必须对应
  • 3个顶点的二叉树有5种不同的同构方式
  • 由n个节点组成的二叉树不同构的数量C_n
  • C_n = [1/(n+1)]*C(2n, n) -> catalan numbers

bin_tree_isom(r1, r2){
        if(r1 == null && r2 == null) return true
        if (r1 == null && r2 != null || r1 != null && r2 == null) return false
        lc_r1 = left child of r1
        lc_r2 = right child of r2
        rc_r1 = right child of r1
        rc_r2 = right child of r2
        if(bin_tree_isom(lc_r1, lc_r2) == True && bin_tree_isom(rc_r1, rc_r2) == True)
            return true
        else
            return false
 }