Discrete_Mathematics_part2

离散数学 Discrete Mathematics

part 3 Number Theory 数论

basic knowledge 基础知识

Let $Z$ be the set of integers. Let $a,b\in Z$ and $a\neq 0$
- a devides b (整除): there is an integer $c\in Z$ such that $b=ac$
  - a is a divisor（因子）of b;b is mutiple of a
  - $a \mid b$: a divides b ;$a\nmid b$: a does not divide b
- $n \in {2,3,\ldots}$is a prime if the only positive divisors of n are 1 and n.
- if n is not a prime , n is a composite（合数）（不讨论0,1）
- 素数无穷多构造。N=最大素数以下所有数字素数只和加一，和所有已知素数互质，矛盾。
The Well-Ordering Property良序公理：

every non-empty subset of $N(Z^+)$ has a least element .$//\forall S\in p(N) \backslash {\emptyset},\exists s_0\in S$ such that $s_0\leqslant s$ for all $s \in S$.
Division Algorithm带余除法:

let $a,b\in Z$and b>0.Then there are unique integers q,r such that $0\leqslant r<b$ and $a=bq+r$.

prove:
- existence:
```
let $S=\{a-bx:x\in Z \ and\ a-bx\geqslant0\}.$Then$S\neq \emptyset \ and\ S \subseteq N$,$S$ has a least element , say $r=a-bq\geqslant0$
```
  if $r\geqslant b$,then $r-b=a-b(q+1)\in S$ and $r-b<r$.The contradiction shows that $0\leqslant r<b.$
- uniqueness:Suppose that $q’,r’\in Z，0\leqslant r’<b$ and $a=bq’+r’$
  
  Recall that $a=bq+r,0\leqslant r<b$.Then $b(q-q’)=r’-r\in (-b,b)$. It must be the case that $q=q’$ and thus $r=r’$.
mod: a mod b is defined as r(let $a,b\in Z$and b>0.Then there are unique integers q,r such that $0\leqslant r<b$ and $a=bq+r$.)
$\lfloor \alpha \rfloor$:floor of $\alpha$,$\leqslant \alpha$
$\lceil \alpha \rceil$:ceil of $\alpha$,$\geqslant \alpha$
Greatest Common Divisor(GCD):
- common divisor 公因子： a integer d such that $d|a,d|b$
- greatest common divisor 最大公因子（GCD）,gcd(a,b) : the largest common divisor of a,b
- relatively prime 互素：gcd(a,b)=1
- $\exists s,t\in Z,st\ gcd(a,b)=as+bt.$
- $d=gcd(a,b)=gcd(a/d,b/d)=1$
- 计算gcd，辗转相除法，
- properties :
  
  or 可兼有的或 \lor
theorem(Congruence): Let $n\in Z^+$. For any $a\in Z$, there is a unique integer $r$, such that $0\leqslant r< n$ and $a\equiv r \pmod n$.

prove:
- Existence: by division algorithm,$\exists q,r\in Z$ such that $0\leqslant r<n,a=qn+r$
  
  $a\equiv r\pmod n$
- Uniqueness:Suppose that $0\leqslant r’ <n$ and $a\equiv r’\pmod n$
  
  $|r-r’|<n$ and $r\equiv r’\pmod n$
  
  $|r-r’|<n$ and $n|(r-r’)$
  
  $r=r’$
加减乘除法时间复杂度
Prime Number Theorem : for $x\in R^+,\pi(x)=\sum_{p\leqslant x }1$:the number of primes $\leqslant x$
- Fundamental Theorem of Arithmetic （算术学的基本定理）
theorem: every intr=eger n>1 can be uniquely written as $n=p_1^{e_1}\cdots p_r^{e_r}$,where $p_1,\dots,p_r$ are distinct primes ,$p_1<\cdots <p_r$ and $e_1,\ldots,e_r \geqslant 1$.
prove: 第二类数学归纳法 mathematical induction
- existence:
  - 显然n=2,3,4,5满足
  - 假设n$\leqslant$k满足, Induction hypothesis: suppose true for integers $2\leqslant n \leqslant k$
  - Prove the statement for n=k+1
    - if(n=k+1 is a prime） $n=(k+1)^1$ QED
    - else n=k+1 is composite ,$n=n_1n_2$,by introduction hypothesis，
      
      $n1=p_1^{\alpha_1 }\cdots p_r^{\alpha_r},n2=q_1^{\beta_1 }\cdots q_s^{\beta_s}$
      
      $n=n_1n_2=p_1^{\alpha_1 }\cdots p_r^{\alpha_r}\cdot q_1^{\beta_1 }\cdots q_s^{\beta_s}$has the expected form.
- uniqueness:
  - Suppose that $n=p_1\cdots p_r=q_1\cdots q_s$,where $p_i,q_i$ are all primes.
  - $p_1|n \Rightarrow p_1|q_1\cdots q_s \Rightarrow p_1|q_j$ for some $j\Rightarrow p_1=q_j$
  - Without loss of generality, we suppose that j=1
  - Then $p_2\cdots p_r=q_2\cdots q_s$
  - The theorem is true by induction

Ideal 理想

Definion:Let $\emptyset \neq I \subseteq Z$.I is called an ideal of Z if
- $a,b\in I\Rightarrow a+b\in I$;and
- $a\in I,r\in Z \Rightarrow ra\in I$
example:$kZ={\ldots , -2k,-k,0,k,2k,\ldots}$is an ideal of Z for every $k\in Z$
- theorem:Let I be an ideal of Z. Then $\exists d \in Z$ such that $I=dZ$
  - prove:
Definion:Let $I_1,I_2$ be ideals of Z. Then the sum of $I_1$ and $I_2$ is define as $I_1+I_2={x+y:x\in I_1 ,y\in I_2}$
theorem:$I_1+I_2$ is an ideal of Z
- $$\forall a,b\in I_1+I_2,a+b\in I_1+I_2$$
  - $\exists x_1,x_2\in I_1,y_1,y_2\in I_2$ such that $a=x_1+y_1;b=x_2+y_2$
  - $$a+b=(x_1+x_2)+(y_1+y_2)\in I_1+I_2$$
- $$\forall a \in I_1+I_2 ,r\in Z ,ra\in I_1+I_2 $$
  - $\exists x\in I_1,y\in I_2$ such that $a=x+y$
  - $ra=(rx)+(ry)\in I_1+I_2$
example:$3Z+5Z=Z;4Z+6Z=2Z$
$aZ+bZ=gcd(a,b)Z$

prove:

PS: w.l.o.g.:without loss of generality (不失一般性)

二元关系指，R是A$\times$B 的子集，具体我感觉怪怪的，不是很明白。

Congruence

definition: Let $a\in Z ,n\in Z^+$

$[a]_n=a+nZ={a+nx:x\in Z}$ is called the residue class 剩余类of $a$ mod $n$

any element in this class is called a representative代表元.
example: n=6,$[0]_6={\ldots,-12,-6,0,6,12,\ldots};[1]_6={\ldots,-11,-5,1,7,13,\ldots}$

$Z_n,Z_n^*$

$Z_n$:
- Define: Letn be any positive integer. $Z_n$ is defined as the set of all residue classes modulo n.
- $Z_n={[0]_n,[1]_n,\ldots,[n-1]_n}={[1]_n,[2]_n,\ldots,[n-1]_n,[n]_n}=\cdots$
- - addition: $[a]_n+[b]_n=[a+b]_n$
  - subtraction:$[a]_n-[b]_n=[a-b]_n$
  - multiplication:$[a]_n\cdot [b]_n=[a\cdot b]_n$
- Remark(well-defined):if $a\equiv a’\pmod n$ and $b\equiv b’\pmod n$,then$a\pm b\equiv a’\pm b’\pmod n$ and $ab=a’b’\pmod n$.
- Hence,$[a]_n\pm [b]_n=[a’]_n+[b’]_n;[a]_n\cdot [b]_n=[a’]_n\cdot [b’]_n$
- - $$
    a\equiv a’\pmod n\Rightarrow n|(a-a’) \Rightarrow \exists x \ such\ that\ a-a’=nx\
    b\equiv b’\pmod n\Rightarrow n|(b-b’) \Rightarrow \exists x \ such\ that\ b-b’=ny\
    (a+b)-(a’+b’)=nx+ny\
    (a-b)-(a’-b’)=nx-ny\
    ab-a’b’=a(b-b’)+b’(a-a’)=any+b’nx
    $$
$Z_n^*$:
- inverse:Let $n\in Z^+$ and let $[a]_n \in Z_n$.$[s]_n\in Z_n$ is called an inverse of $[a]_n$ if $[a]_n[s]_n=[1]_n$.
- division:if $[a]_n$ has an inverse $[s]_n$,define $\frac{[b]_n}{[a]_n}=[b]_n\cdot [s]_n$
- theorem: Let $n\in Z^+$.$[a]_n\in Z_n$ has an inverse if and only if $gcd(a,n)=1$
  - Only if: $\exists s\ s.t.[a]_n[s]_n\equiv [1];\exists t,as-1=nt;gcd(a,n)=1$
  - if:$\exists s,t\ s.t.as+nt=1;as\equiv 1\pmod n$
- Let $n\in Z^+$.Define $Z_n^*={[a]_n\in Z_n:gcd(a,n)=1}$
  - if n is prime ,then $Z_n^*={1,2,\ldots,n-1}$
  - if n is composite ,then $Z_n^*\subset Z_n$
  - example:$Z_5^*={1,2,3,4};Z_6^*={1,5}$
    Euler’s Phi Function ($\phi (n)$)
$\phi(n)=|Z_n^*|$ for every $n\in Z^+$ ($\phi (n)$ is the number of intergers $a\in [n]$ such that $gcd(a,n)=1$)
property:
- if p is a prime, then $\phi(p^e)=p^{e-1}(p-1)$ for any $e\in Z^+$
  - prove:let $x\in [p^e]$. Then $gcd(x,p^e)\neq 1$ iff$p|x$ iff$x=p,2p,\ldots,p^{e-1}\cdot p$
  - $\phi(p^e)=p^e-p^{e-1}=p^{e-1}(p-1)$
- if n=pq for two different primes p and q ,then $\phi(n)=(p-1)(q-1)$.
  - prove容斥: $A={1,2,\ldots,pq},A_p={x\in A:p|x},A_q={x\in A:q|x}$
  - $Z_n^*=A-A_p\cup A_q$
  - $|Z_n^*|=|A-A_p\cup A_q|=|A|-|A_p\cup A_q|=|A|-|A_p|-|A_q|+|A_p\cap A_q|=(p-1)(q-1)$
Euler’s Theorem:Let $n\geqslant1$ and $\alpha \in Z_n^*$. Then$\alpha^{\phi(n)}\equiv 1 \pmod n$
Fermat’s Little Theorem:if p is a prime and $\alpha \in Z_p$. Then $\alpha^p \equiv \alpha \pmod p$.
• This is a corollary of Euler’s theorem for $n=p$

Cryptography_rsa

1. 凭空产生两个质数$p,q$
2. 设$N=p \times q$
3. 根据欧拉函数$r=\phi(N)=(p-1)(q-1)$
4. 凭空产生一个小于r的整数$e$使得$e$和$r$互质
5. 求$d$使得$ed\equiv1\pmod r$
6. 销毁$p,q$,没有人知道$p,q$是多少
  得出$(N,e)$是公钥,$(N,d)$是私钥
  参考链接
Alice得到公钥和私钥，Alice把公钥告诉Bob，自己把私钥藏起来不告诉任何人。Bob给Alice发消息。
- 加密：
  假设Bob的消息是$n$,密码是$c$,手上有公钥$(N,e)$
  $$
  c\equiv n^e \pmod N
  $$
  Bob将加密后的$c$发给Alice
- 解密：
  
  Alice得到密码$c$,根据私钥$(N,d)$
  $$
  n \equiv c^d \pmod N
  $$
  解码得到$n$
- 原理：
  $$
  c\equiv n^e \pmod N \
  c^d \equiv n^{e\cdot d} \pmod N
  $$
  因为$e\cdot d \equiv 1 \pmod r$,即$e\cdot d \equiv h \cdot r +1 \pmod N$,其中$h$是自然数
  $$
  c^d\equiv n^{h\cdot r+1}\pmod N\
  c^d\equiv n^{h\cdot \phi(n)+1}\pmod N\
  c^d\equiv n\cdot n^{h\cdot \phi(n)}\pmod N\
  c^d\equiv n\cdot (n^{\phi(n)})^h\pmod N\
  $$
  根据欧拉定理$a^{\phi(n)}\equiv 1 \pmod n$
  $$
  c^d \equiv n\times 1^h \pmod N\
  c^d \equiv n \pmod N
  $$
快速幂，取模Modulo Exponentiation（Square-and-Multiply Algorithm）
Euclidean Algorithm (EA)辗转相除算gcd
Extended Euclidean Algorithm (EEA) 算as+bt的s和t

#gcd
def gcd(a,b):
    if(b==0):
        return a
    return gcd(b,a%b)
#exgcd gcd(a,b)=as+bt
def EEA(a,b):
    if b==0:
        return (1,0)
    (s,t)=EEA(b,a%b)
    return (t,s-a//b*t)
#b=a^{-1} (mod n)
def inverse(a,n):
    b = EEA(a,n)[0]
    if(b<0):
        b+=n
    return b
#a^e mod n
def multiply_and_square(a,e,n):
    if(e==0):
        return 1
    res = multiply_and_square(a,e//2,n)
    if(e%2==1):
        return (res*res*a)%n
    else:
        return (res*res)%n
#rsa_enc
def RSA_enc(p,q,e,m):
    c = multiply_and_square(m,e,p*q)
    return c
#rsa_dec
def RSA_dec_given_pq(p,q,e,c):
    m = multiply_and_square(c,inverse(e,(p-1)*(q-1)),p*q)
    return m

图论 Graph

basis knowledge

graph图 $G=(V,E)$ is defined by a non empty set V of vertices and aset of E of edges.
vertices顶点 $|V|$ is called the order(阶数) of G.
edges边
endpoint端点
Infinite Graph 无限图 $|V|=\infty$ or$|E|=\infty$
Finite Graph 有限图 $|V|< \infty$ or $|E| < \infty$
Types of Graphs
- are edges of G directed ?
  - directed graph 有向图
  - undirected graph 无向图
- multiple edges
  - simple graph 简单图
  - multigraph 多重图
- loops自环
  - pseudograph伪图
Special Simple Graph:
- complete graph完全图:
  - $K_n:V={v_1,\ldots,v_n};E=\Large{$${v_i,v_j}$ $:i\neq j\leq n$ $\Large}$
- cycle环，圈：
  - $C_n:V={v_1,\ldots,v_n};E=\Large{$${v_1,v_2},{v_2,v_3},\ldots,{v_n,v_1}$$\Large}$
- wheel轮：
  - $W_n:V={v_0,v_1,v_2,\ldots,v_n};E=$$\Large{$${v_1,v_2},\ldots,{v_n,v_1}$$\Large}$$\bigcup$$\Large{$${v_0,v_1},\ldots,{v_0,v_n}$$\Large}$
- n-Cubes方体：
  - $Q_n:V={0,1}^n;E={$${u,v}:d(u,v)=1}$即u，v二进制只有一位不一样
  - $d(u,v)=|{i\in [n] :u_i \neq v_i}|$即u，v二进制有几位不一样
Adjacency List邻接表：
Let $G = (V, E)$ be a graph with no multiple edges. The adjacency list of $G$ is a list the vertices of the graph and all adjacent vertices
$v_i,v_j \in V$ are adjacent if ${v_i,v_j}$ or $(v_i,v_j)$ is an edge
adjacency matrix邻接矩阵 :

let $G=(V={v_1,\dots,v_n},E)$ be a simple graph. The adjacency matrix of $G$ is an $n\times n$ matrix $A=(a_{ij})$, where
$$
a_{ij}=\left{ \begin{array}\ 1 & {v_i,v_j}\in E \ 0 & {v_i,v_j}\notin E\end{array}\right.
$$
multiplicity重数:
let $G=(V={v_1,\dots,v_n},E)$ be an undirected graph. The adjacency matrix of $G$ is an $n\times n$ matrix $A=(a_{ij})$, where:
- $a_{ij}=$ multiplicity of ${v_i,v_j}$ when $i \neq j$
- $a_{ii}=$ the number of loops from $v_i$ to itself.
remark: the adjacentcy matrix of a simple graph is always symmetric.
incidence matrix关联矩阵:
let $G=(V={v_1,\dots,v_n},E={e_1,\ldots,e_m})$ be undirected.THe incidence matrix of $G$ is an $n\times m$ matrix $B=(b_{ij})$,where
$$
b_{ij}=\left{ \begin{array}\ 1 & if\ e_j\ is\ incident\ with\ v_i\ 0 & otherwise\end{array}\right.
$$
subgraph:

edge or vertex operation
remove/add an edge or vertex
- edge：
- vertex:
edge contyractions
union
complement graph补图：

$G\cup \overline{G}$ is a complete graph($K_n$).

degree and connection

degree:
- two vertices u and v in an undirected graph G are called adjacent (or neighbors) in G if u and v are endpoints of an edge e of G. Such an edge e is called incident with the vertices u and v and e is said to connect u and v.
- Neighbor:
  
  the set of adjacent vertices.
- degree:
  
  the number of neighbors.
- isolated: $degree = 0$
- pendant: $degree = 1$
- 对上面的图片，⑤ is pendant;⑥ is isolated
Handshaking Theorem:
- Let $G=(V,E)$ be an undirected graph with m edges. Then
  $$
  2m=\sum_{v \in V}deg(v)
  $$
  (Note: all undirected graph including simple graph,multigraph(multiple edges),pseudograph(loops))
- An undirected graph has an even number of vertices of odd degree.
  sketch of pf:Let $V_1$ and $V_2$ be the set of vertices of even degree and theset of vertices of odd degree,respectively,in an undirected graph $G=(V,E)$ with m edges.Then
  $$2m=\sum_{v \in V}deg(v)=\sum_{v \in V_1}deg(v)+\sum_{v \in V_2}deg(v)$$
degree for directed graph:
Let $G=(V,E)$ be a directed graph. If $(u,v)\in E$, we say that $u$ is adjacent to $v$ and $v$ is adjacent from $u$.
- $u$ is the initial vertex of $(u,v)$; $v$ is the terminal vertex of $(u,v)$.
- in-degree
- out-degree
Handshaking Theorem for directed graph:
- Let $G=(V,E)$ be a directed graph. Then
  $$
  \sum_{v \in V}deg^-(v)=\sum_{v \in V}deg^+(v)=|E|
  $$

Isomorphism

Definition:The simple graphs $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$ are isomorphic同构 if there is a bijection $\sigma :V_1\rightarrow V_2$ such that ${u,v}\in E_1 \Leftrightarrow {\sigma(u),\sigma(v)}\in E_2$
• $\sigma$ is called an isomorphism同构映射
• nonisomorphic: not isomorphic

Determine whether two graphs are isomorphic:
Definition: Graph invariants are properties preserved by graph isomorphism. For example,
• The number of vertices
• The number of edges
• The number of vertices of each number of degrees
REAMRKS: The graph invariants can be used to determine if two graphs are isomorphic or not.

Bipartite Graph and Match

Bipartite Graph二分图、二部图
- V can be devided to two disjoint part,such that there are not any edges in each part and all edges are connect two parts.
- Definition: $G=(V,E)$ is a bipartitie graph if $V$ has a partition ${V_1,V_2}$ such that $E\subseteq {$${u_1,u_2}:u_1\in V_1,u_2\in V_2}$.
  - $(V_1,V_2)$ is a bipartition of the vertex set $V$.
Complete Bipartite Graph完全二部图:
- A complete bipartite graph is a graph $K_{m,n}=(V,E)$ with $V={x_1,\ldots,x_m}\cup {y_1,\ldots,y_n}$ and $E={$${x_i,y_j}:i\in [m],j\in [n]}$
Matching
- Definition:
  A matching in a simple graph $G=(V,E)$ is a subset $M\subset E$ such that no two edges in M are incident with the same vertex.
  A maximum matching is a matching with the largestnumber of edges.
  A matching in a bipartite graph with $V=V_1\cup 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.
- Hall’s Marriage Theorem:
  A bipartitie graph $G=(X\cup Y,E)$ has a complete matching from $X$ to $Y$ iff $|N(A)|\geqslant |A|$ for any $A\subseteq X$

详细证明略去，这次不考

Path,connected, disconnected

Path
- Definition:
- for directed path:
Connectivity
- Definition:
  An undirected graph $G$ is said to be connected if there is a path between any pair of distinct vertices.
  • Graph of order 1 is connected; the complete graph $K_n$ is connected
  • disconnected非连通的: not connected
  • disconnect G: remove vertices or edges to produce a disconnected subgraph
- Theorem:Let $G=(V,E)$ be a connected undirected graph. Then there is a simple path between any pair of distinct vertices.
  证明同上略。
- Connected Component：
- • $v\in V$ is a cut vertex割点if $G-v$ has more connected components than G
  • $e\in E$ is a cut edge割边、bridge桥if $G-e$ has more connected components than G
Find cut vertices and cut edge(s)
- Vertex Connectivity
  - Definition:A connected undirected graph $G=(V,E)$ is said to be nonseparable不可分的if $G$ has no cut vertex.(one point)
  - Let $G=(V,E)$ be a connected simple graph.
    • vertex cut点割集: A subset $V’\subseteq V$ such that $G-V’$ is disconnected
    • vertex connectivity点连通度$\kappa(G)$ : the minimum number of vertices whose
    removal disconnect $G$ or results in $K_1$; equivalently,
    • if $G$ is disconnected, $\kappa(G)=0$; //additional definition
    • if $G=K_n$,$\kappa(G)=n-1$ //$K_n$ has no vertex cut
    • else,$\kappa(G)$ is the minimum size of a vertex cut of $G$
- Theorem:
- Property：
- Edge connectivity
  - Definition:Let $G=(V,E)$ be a connected simple graph. $E’\subseteq E$ is an edge cut边割集of $G$ if $G-E’$ is disconnected.
  - Let $G=(V,E)$ be a connected simple graph.
    The edge connectivity边连通度($\lambda(G)$) of $G$ is defined as below:
    • $G$ disconnected: $\lambda(G)$ = 0
    • $G$ connected:
    • $|V|=1$: $\lambda(G)$ = 0
    • $|V|>1$: $\lambda(G)$ is the minimum size of edge cuts of $G$.
- Theorem:
- Let $G=(V,E)$ be a simple graph. Then $\kappa(G)\leqslant\lambda(G)\leqslant\delta(G)$,where $\delta(G)=min_{v\in V} deg(v)$ is the least degree of $G’s$ vertices.
  prove(homework)
Connected Directed Graphs
路径同构不变性

Euler circuit, Euler path, Hamilton Circuits, Hamilton path
Counting Paths Between Vertices

证明详细分析见后，期末1/5

Euler circuit and Euler path
- Necessary and sufficient condition for Euler circuit
  证明后面详细分析，期末2/5
- 欧拉循环算法
- 欧拉路径
Hamilton Paths and Circuits
- Definition: Let $G=(V,E)$ be a graph.
  • Hamilton Path: A simple path that passes through every vertex
  exactly once.
  • Hamilton Circuit: A simple circuit that passes through every
  vertex exactly once.
- Determine if there is a Hamilton circuit in a given graph 0?
  • This problem is NP-Complete. //that means very difficult
- Necessary conditions on Hamilton circuit.
  • If 0 has a Hamilton circuit, then G doesn’t have a vertex of degree 1
  • If 0 has a Hamilton circuit and a vertex of degree 2, then a Hamilton circuit of 0 traverses both edges.
- Sufficient conditions for existence