{%hackmd @RintarouTW/About %}

# Tree

:::info
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

:::info
$$
\cases{
V:Vertices, |V|=n\\
E:Edges\\
G=(V,E)\text{ with no self-loops}\\
}\\
\Downarrow\\
G\text{ is a tree.}\\
\Updownarrow\\
G\text{ is connected}\land |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$, exists a unique simple path between them.}
$$
:::

## Spanning Tree

:::info
$G$ is a connected undirected graph.
A **Spanning Tree** is the **[spanning subgraph](/@RintarouTW/Graph_Theory#Subgraph)** (remove unrequired edges only) of $G$ that is a tree.
:::

:::info
Minimal Spanning Tree
$G=(V,E,w)$ is the spanning tree with weight of each edge.
Minimal Spanning Tree $\iff \sum_\limits{e\in E} w(e) = \text{minimal}$
:::

### Prim's Algorithm

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

:::info
Bridge
$G=(V,E)$ is a connected undirected graph. $\{L,R\}$ is a partition of $V$,
$e$ is a bridge $\iff e\in E$ is an edge that connect a vertex in $L$ and a vertex in $R$.
:::

:::info
$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$.
:::

:::info
Prim's Algorithm
- $L=V-\{v_0\}, R=\{v_0\}, E'=\varnothing$
- Find the least weighted bridge($e=(v_L,v_R)$) between $L,R$,
$E'=E'+\{e\}$ $\tag{step 2}$
- $L=L-\{v_L\}, R=R+\{v_L\}$, if $L\ne\varnothing$, goto step 2.
- $E'$ is the minimal spanning tree of $G$.
:::

### Minimum Diameter Spanning Tree (MDST)

:::info
Given a connected undirected graph $G = (V,E)$, find a spanning tree $T = (V,E′)$ of $G$ such that the longest path in $T$ is as short as possible.
:::

## Rooted Trees

graph {
graph [bgcolor=transparent];
node[fontcolor="#888888";color="#888888"];
edge [color="#888800"];
rankdir=TB;
"A (Root)"--B,C,D
B--E,F,G
C--H,I,J
D--K--L,M
}

:::info
- 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 ≥ 1$, be disjoint rooted trees with roots $v1, v2,\ldots, 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, \ldots, vr$. We call $T1,T2,\ldots,Tr$ subtrees of the larger tree.
:::

### Kruskal’s Algorithm

Alternative waty to find the minimal spanning tree (MST)

:::info
$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($\implies G$ is not connected).
:::

## Binary Trees

:::info
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

graph {
graph [bgcolor=transparent];
node[fontcolor="#888888";color="#888888"];
edge [color="#888800"];
rankdir=TB;
1--2,3,4
}

graph {
graph [bgcolor=transparent];
node[fontcolor="#888888";color="#888888"];
edge [color="#888800"];
rankdir=TB;
1--2,4,3
}

:::

:::info
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.
<img src="https://i.imgur.com/UBUevY2.png" style="filter:invert(.9)"/>

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

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

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

graph {
graph [bgcolor=transparent];
node[fontcolor="#888888";color="#888888"];
edge [color="#888800"];
rankdir=TB;
25--17,33
17--9,20
9--" ",13
33--"  ",30
}

:::

### Expression Trees

:::info
$x=a*b-c/d+e$
<img src="https://i.imgur.com/vBDd7FP.png" style="filter:invert(.9)">

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

:::info
Let $B(n)$ be the number of different binary trees of size $n$ ($n$ vertices), $n ≥ 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 +
$$\vdots$$
left subtree with $n$ vertices * right subtree with $0$ vertex.
$$
\begin{array}l
\therefore B(n+1) &= B(0)B(n) + B(1)B(n-1) + \cdots + B(n)B(0)\\
&= \sum_\limits{k=0}^n B(k)B(n-k)
\end{array}
$$
:::

###### tags: `math`