學海無涯，思境無維；數乃六藝，理之始也。
或有一得足矣 愚千慮

$$$$

Tree

Cycle : A cycle is a circuit whose edge list contains no duplicates. It is customary to use

$C_n$ to denote a cycle with

$n$ edges.

A Tree contains no cycle or self-loops.

A forest is an undirected graph whose components are all trees.

Conditions for a graph to be a tree

$$\begin{gathered} \{\begin{array}{l}V:Vertices,|V|=n\\ E:Edges\\ G=(V,E)\text{ with no self-loops}\end{array} \\ \Downarrow \\ G\text{ is a tree.} \\ \Updownarrow \\ G\text{ is connected}\wedge |E|=n-1 \\ \Updownarrow \\ G\text{ is connected, if }e\in E,(V,E-\{e\})\text{ is disconnected.} \\ \Updownarrow \\ G\text{ contains no cycle, by adding a new edge, yout created a new cycle.} \\ \Updownarrow \\ \text{For two distinct vertices in }V\text{, exists a unique simple path between them.} \end{gathered}$$

Spanning Tree

$G$ is a connected undirected graph.
A Spanning Tree is the spanning subgraph (remove unrequired edges only) of

$G$ that is a tree.

Minimal Spanning Tree

$G=(V,E,w)$ is the spanning tree with weight of each edge.
Minimal Spanning Tree

$⟺\sum _{e\in E}w(e)=\text{minimal}$

Prim's Algorithm

Find the minimal spanning tree of a connected, undirected, weighted graph.

Bridge

$G=(V,E)$ is a connected undirected graph.

$\{L,R\}$ is a partition of

$V$,

$e$ is a bridge

$⟺e\in E$ is an edge that connect a vertex in

$L$ and a vertex in

$R$.

$G=(V,E,w)$ is a weighted undirected connected graph.

$\{L,R\}$ is a partition of

$V$, if

$e$ is the least weighted bridge between

$L,R$, then exists a minimal spanning tree of

$G$ that include

$e$.

Prim's Algorithm

• $L=V-\{v_0\},R=\{v_0\},E^{\prime }=\varnothing$
• Find the least weighted bridge(
  $e=(v_L,v_R)$) between
  $L,R$,
  
  $E^{\prime }=E^{\prime }+\{e\}$
  $$
• $L=L-\{v_L\},R=R+\{v_L\}$, if
  $L\ne \varnothing$, goto step 2.
• $E^{\prime }$ is the minimal spanning tree of
  $G$.

Minimum Diameter Spanning Tree (MDST)

Given a connected undirected graph

$G=(V,E)$, find a spanning tree

$T=(V,E\prime )$ of

$G$ such that the longest path in

$T$ is as short as possible.

Rooted Trees

• Basis: A tree with no vertices is a rooted tree (the empty tree).
• A single vertex with no children is a rooted tree.
• Recursion: Let
  $T1,T2,...,Tr,r\ge 1$, be disjoint rooted trees with roots
  $v1,v2,\dots ,vr$ respectively, and let
  $v0$ be a vertex that does not belong to any of these trees. Then a rooted tree, rooted at
  $v0$, is obtained by making
  $v0$ the parent of the vertices
  $v1,v2,\dots ,vr$. We call
  $T1,T2,\dots ,Tr$ subtrees of the larger tree.

Kruskal’s Algorithm

Alternative waty to find the minimal spanning tree (MST)

$G=(V,E,w),|V|=m,|E|=n$

• sort edge list by weight. lighter first.
• pick the the edge in the edge list in order and that won't cause the cycle into the set
  $S$. (this approach makes sure lighter edge get picked first)
• until
  $|S|=m-1$ or the end of the edge list(
  $⟹G$ is not connected).

Binary Trees

An ordered rooted tree is a rooted tree whose subtrees are put into a definite order and are, themselves, ordered rooted trees. An empty tree and a single vertex with no descendants (no subtrees) are ordered rooted trees.

Two Different Ordered Rooted Trees

Binary Tree
(1) A tree consisting of no vertices (the empty tree) is a binary tree
(2) A vertex together with two subtrees that are both binary trees is a binary tree. The subtrees are called the left and right subtrees of the binary tree.

A vertex of a binary tree with two empty subtrees is called a leaf.
All other vertices are called internal vertices.

A full binary tree is a tree for which each vertex has either zero or two empty subtrees.

Traversals of Binary Trees

• Preorder Traversal
• Inorder Traversal
• Postorder Traversal

Binary Sort Tree Creation

Binary Sort Tree + Inorder Traversal would create a sorted ascending list.

Binary Sort Tree for 25, 17, 9, 20, 33, 13, and 30.

Expression Trees

$x=a\ast b-c/d+e$

Expression Tree removed the parenthese.

• Prefix form: +ab (Preorder Traversal of the Expression Tree = + -*ab/cde)
• Infix form: a+b (Inorder Traversal = a*b-c/d+e)
• Postfix form: ab+ (Postorder Traversal of the Expression Tree = ab*cd/-e+ )

Counting Binary Trees

Let

$B(n)$ be the number of different binary trees of size

$n$ (

$n$ vertices),

$n\ge 0$.

$B(0)=1$

$B(n+1)$ =
left subtree with

$0$ vertex * right subtree with

$n$ vertices +
left subtree with

$1$ vertex * right subtree with

$n-1$ vertices +

$$⋮$$
left subtree with

$n$ vertices * right subtree with

$0$ vertex.

$$\begin{array}{ll}\therefore B(n+1)& =B(0)B(n)+B(1)B(n-1)+\cdots +B(n)B(0)\\ & =\sum _{k=0}^{n}B(k)B(n-k)\end{array}$$

tags: math