A binary tree is a rooted tree where each vertex has zero, one or two children.

Let T1 be a binary tree with root r1 and let T2 be a binary tree with root r2. 

The binary trees T1 and T2 are isomorphic if there is one-to-one, onto function f from the vertex set of T1 to the vertex set of T2 satistying the following:

(a) T1 and T2 are isomorphic as rooted trees through an isomorphism f.

(b) v is a left (right) child of w in T1 if and only if f(v) is a left (right) child of f(w) in T2.

If a binary tree of height h has t terminal vertices, then

t<=2^h

A full binary tree is a binary tree in which each vertex has two or no children.

If T is a full binary tree with i internal vertices, then T has i+1 terminal vertices and 2i+1 total vertices.

A binary search tree is a binary tree T in which data are associated with the vertices. for each vertex v in T, each data item in the left subtree of v is less than the data item in v, and each data item in the right subtree of v is greater than the data item in v.

Decision Tree is a rooted tree If we begin at the root, answer each question, and follow the appropriate edge, so that we eventually arrive at a  deciding terminal vertex . 

when a problem has t number of all possible result , if the decision tree has n possible answering number per one vertex and h height, then   

t<=n^h

A tree T is a spannig tree of a graph G if T is a subgraph of G that contains all of the vertices of G.

Breadth-First search is a method to process all the vertices on a given level before moving to the next-higher level.

Depth-First search is a method to proceeds to successive levels in a tree at the earliest possible opportunity.

Let G be a weighted graph. A minimal spanning tree of G is a spanning tree of G with minimum weight.

Prim's Algorithm begins with a single vertex. Then at each iteration, it adds to the current tree a minimum-weight edge that does not complete a cycle.

Kruskal's algorithm find the edge in the graph with smallest weight that does not complete a cycle.

A (free) tree T is a simple graph such that for every pair of vertices v and w there is a unique path from v to w.

A rooted tree is a tree where one of its vertices is designated the root.

Let T1 be a rooted tree with root r1 and let T2 be a rooted tree with root r2. 

The rooted trees T1 and T2 are isomorphic if there is a one-to-one, onto function f from the vertex set of T1 to the vertex set of T2 satisfying the following:

(a) (vi, vj) ∈ T1 if and only if (f(vi), f(vj)) ∈ T2.

(b) f(r1) = r2.

The level of a vertex v is the length of the simple path from the root to v.

The height of a rooted tree is the maximum level number of its vertices.

Let T be a tree with root v0. Suppose that x, y and z are vertices in T and that (v0, v1, ..., vn) is a simple path in T, then

(a) the parent of v(n) is v(n-1).

(c) a child of v(n-1) is vn.

(b) ancestors of v(n) are v0, ..., v(n-1).

(d) descendants of v(n-2) are v(n-1), vn.

(e) x and y are siblings if x and y are children of z.

(f) a terminal vertex (or a leaf) is a vertex that has no children.

(g) an internal (or branch) vertex is a vertex that has at least one child. 

(h) a subtree T' of a tree T is a graph where

V(T') = { v0 and the descendants of v0 }

E(T') = { e | e is an edge on a simple path from v0 to some vertex in V(T') }

Let T be a graph with n vertices. The following are equivalent.

(a) T is a tree.

(b) T is connected and acyclic.

(c) T is connected and has n-1 edges. //vertex들을 연결할 수 있는 최소한의 구조

(d) T is acyclic and has n-1 edges.

Graphs G1 and G2 are isomorphic if there is a one-to-one, onto function f from the vertices of G1 to vertices of G2 and a one-to-one, onto function g from the edges of G1 to the edges of G2, so that e=(v,w) in G1 if and only if g(e)=(f(v), f(w)) in G2.

Graphs G1 and G2 are isomorphic if and only if for some ordering of their vertices, their adjacency matrices are equal.

Graphs G1 and G2 are homeomorphic if G1 and G2 can be reduced to isomorphic graphs by performing a sequence of series reductions

A graph is planar if it can be drawn in the plane without its edges crossing,

if G is a connected planar graph, then v-e+f=2 and 2e>=sf.

G is a planar graph if and only if G does not contain a subgraph homeomorphic to either K5 or K3,3.

Input:    A connected, weighted graph in which all weights are positive;

vertices a and z

Output:    L(z), the length of a shortest path from a to z

An Euler cycle in a graph G is a cycle that passes through every edge of G only once.

A graph G has an Euler cycle if and only if G is a connected graph and every vertex has even degree.

Hamiltonian cycle in a graph G is a cycle that visit every vertex of G only once by a simple cycle.

The n-cube, denoted I^n (n>=1), has 2^n vertices labeled 0, 1, 2, ..., 2^(n-1) , and edges connecting two vertices if the binary representation of their labels differ in exactly one bit.

 The n-Cube has a Hamiltonian cycle(n>=2).

A graph(or undirected graph) G consists of a set V of vertices(or nodes) and a set E of edges(or arcs) such that each edge e∈E is associated with an unordered pair of vertices.

G = (V , E)

A simple graph is a graph without loops or parallel edges.

Let G = (V, E) be a graph, we call (V', E') a subgraph of G if

(a) V'⊆V

(b) E'⊆E such that for every edge e'∈E', if e' is incident on v' and w', then v',w'∈V'.

The degree of a vertex v, denoted by δ(v), is the number of edges incident on v.

if G is a graph with n vertices and m edges, then

sum(δ(vi))[i=1~n] = 2m

A path from vo to vn of length n is an alternation sequence of n+1 vertices and n edges beginning with vertex vo and ending with vertex vn,

(vo, e1, v1, e2, v2, ..., vn-1, en, vn),

in which edge ei is incident on vertices vi-1 and vi for i = 1, ..., n

A simple path from v to w is a path from v to w with no repeated vertices.

A graph has a path with no repeated edges from v to w(v≠w) containing all the edges and all vertices if and only if it is connected and v and w are the only vertices having odd degrees.

A cycle(or circuit) is a path of nonzero length from v to v with no repeated edges.

A simple cycle is a cycle from v to v in which, except for the beginning and ending vertices that are both equal to v, there are no repeated vertices.

If a graph G contains a cycle from v to v, G contains a simple cycle from v to v

The connected graph is the graph in which for any vertices v and w in G, there is a path from v to w.

The complete graph on n vertices, denoted Kn, is the simple graph with n vertices in which there is an edge between every pair of distinct vertices.

The bipartite graph is the graph whose vertex set V is partitioned into sets V1 and V2 such that V1∩V2 = Φ, V1∪V2 = V, and each edge in E is incident on one vertex in V1 and one vertex in V2.

The complete bipartite graph on m and n vertices, denoted Km,n, is the simple graph whose vertex set is partitioned into sets V1 with m vertices and V2 with n vertices, and the edge set consists of all edges of the form (v1, v2) with v1∈V1, and v2∈V2. 

hypothesis를 true라 두고, conclusion을 유도.

-Mathematical Induction

N을 양의 자연수의 집합이라 하고, S(n)을 propositional function이라 하자.

(∀n)S(n)         D: N

를 증명하기 위해서는 이 proposition을 

∀n[ S(n) -> S(N+1) ]

로 바꾸어서 Direct proof를 보이면 된다.

conclusion을 false라 두고, hypothesis와의 contradiction을 보임.

A sentence that can be determined to be either true or false.

Hypothesis is the given proposition.

Conclusion is the proposition that follows from the hypothesis.

forming new compound proposition.

-conditional propositions: p->q

"If P, then q. " or "p only if q."

p: hypothesis , q: conclusion

-Biconditional proposition: p<->q

it equal (p->q) ^ (q->p)

"p if and only if q" of "p iff q"

- the order of evaluation is first ~, then ^, then v, last ->.

Two truth tables are identical, denoted P ≡ Q.

① p -> q ≡ ~p v q

② contrapositive 

p -> q ≡ ~q -> ~p

③ De Morgan's lows

~(p ^ q) ≡ ~p v ~q

~(p v q) ≡ ~p ^ ~q

④ a v ( b ^ c) ≡ (a v b) ^ (a v c) 

    a ^ ( b v c) ≡ (a ^ b) v (a ^ c) 

- ∀

The symbol ∀ means "for all".

Let P be a propositional function with domain of discourse D. The statement

for all x, P(x)

may be written 

(∀x)P(x).

it is true if for all x in D, P(x) is true.

-∃

The symbol ∃ means "there exists".

there exist x, P(x)

may be written 

(∃x)P(x).

it is true if for at least one x in D, P(x) is true.

~(∀x P(x)) ≡ (∃x)~P(x)

~(∃x P(x)) ≡ (∀x)~P(x)

A function f from a set X to a set Y(f : X->Y) is a subset of XxY such that for all x∈X, there is exactly one y∈Y with (x, y)∈f.

The floor of x, denoted └x┘, is the greatest integer less than or equal to x.

The ceiling of x, denoted ┌x┐, is the least integer greater than or equal to x.

- one-to-one                          for all x1, x2∈X, if(x1) = f(x2), then x1 = x2.

- onto                                   for all y∈Y, there exists x∈X such that y=f(x).

- bijection                              one-to-one, onto

- Binary operator on a set X       a function from X x X to X

- unary operator on X               a function from X to X

Let f be a bijection function from X to Y.

the inverse of f, denoted f^-1, is the funtion from Y to X defined by

f^-1 = { (y, x)| (x, y) ∈ f}

Let g be a function from X to Y and f be a funtion from Y to Z.

the composition of f with g, denoted f ∘ g, is the funtion from X to Z defined by

f ∘g(x) = f( g(x) )