本文由Hobee原创，并仅在本站发表，仅供各位小伙伴学习交流使用。
为避免不必要的纠纷，本文禁止以任何形式转载，谢谢配合。
如有问题请通过评论区或邮件联系作者。
本文封面源于网络，侵删。
写在前面
众所周之，hobee在数学的学习方面就宛如一只菜鸡，只好通过不断复习和整理的途径来巩固自己辣鸡的数学成绩。主要是我真的什么也不会了啊（哭哭脸…那就从这里开始吧！
因为考核是候题目是英文的，所以我的整理也就用英文来叭（我也不想啊…
中英术语对照表
为了防止之后我自己都看不明白，在梳理知识点之前我先写一份中英术语对照表好了。
Key Terms
| English | Chinese | English | Chinese | English | Chinese |
|---|---|---|---|---|---|
| Graph | 图 | vertex/node | 顶点 | edge | 边 |
| Directed graph | 有向图 | directed edge/arc | 有向边 | multiple edges | 多重边 |
| loop | 环 | simple graph | 简单图 | multigraph | 多重图 |
| pseudograph | 伪图 | directed multigraph | 多重有向图 | mixed graph | 混合图 |
| adjacent | 邻接 | incident | 关联 | degree | 度 |
| in-degree deg- | 入度 | out-degree deg+ | 出度 | complete graph $K_N$ | 完全图 |
| Bipartite graph | 二分图 | complete bipartite graph | 完全二分图 | Subgraph | 子图 |
| union of two graphs | 两图的并 | adjacency matrix | 邻接矩阵 | incidence matrix | 关联矩阵 |
| graph isomorphism | 图的同构 | graph invariant | 图的同构不变量 | simple path | 简单路径 |
| simple circuit | 简单环 | connected graph | 连通图 | connected component | 连通分量 |
| vertex connectivity | 顶点联通性 | edge connectivity | 边联通性 | strongly/weakly connected directed graph | 强/弱连通有向图 |
| strongly/weakly connected component of a directed graph | 有向图的强/弱连通分量 | polish notation | 波兰式 | reverse polish notation | 逆波兰式 |
| tree | 树 | forest | 森林 | rooted tree | 根树 |
| subtree | 子树 | parent of $v$ | $v$的双亲 | child of $v$ | $v$的孩子 |
| sibling of $v$ | $v$的兄弟姐妹 | ancestor of $v$ | $v$的祖先 | descendant of $v$ | $v$的后代 |
| internal vertex | 内顶点 | leaf | 叶子节点 | level of a vertex | 节点的层次 |
| height of a tree | 树的高度 | m-ary tree | m叉树 | full m-ary tree | 完全m叉树 |
| binary tree | 二叉树 | ordered tree | 排序树 | balanced tree | 平衡树 |
| binary search tree | 二叉搜索树 | decision tree | 决策树 | tree traversal | 树的遍历 |
| preorder traversal | 前序遍历 | inorder traversal | 中序遍历 | postorder traversal | 后序遍历 |
| infix notation | 中序表达式 | prefix notation | 前序表达式 | postfix notation | 后序表达式 |
Results
Graphs and Trees
Graphs
Graphs and Graph Models
Graph Terminology and Special Types of Graphs
Representing Graphs and Graph Isomorphism
Adjacency Matrices
Incidence Matrices
Adjacency Lists
Isomorphism of Graphs
Connectivity
Tree
Introduction to Trees
A tree is a connected undirected graph with no simple circuits.
A forest is a graph that has no simple circuit, but is not connected.
Each of the connected components in a forest is a tree.
Theorem: An undirected graph is a tree iff there is a unique simple path between any two of its vertices.
Rooted Trees
A rooted tree is a tree in which one vertex has been designated as the root and every edge is directed away from the root.
An unrooted tree is converted into different rooted trees when different vertices are chosen as the root.
Terminology
parent, child, siblings
ancestors, descendants
leaf, internal vertices
subtree
M-ary rooted trees
A rooted tree is called an m-ary tree if every internal vertex has no more than m children.
The tree is called a full m-ary tree if every internal vertex has exactly m children.
An m-ary tree with m = 2 is called a binary tree
Ordered rooted trees
An ordered rooted tree is a rooted tree where the children of each internal vertex are ordered.
A binary tree is an ordered rooted where each internal vertex has at most two children, the first is called the left child and the second is called the right child.
Properties of trees
- A tree with n vertices has n-1 edges.
- A full m-ary tree with $i$ internal vertices has $n = mi + 1$ vertices.
- There all at most $m^h$ leaves in an m-ary tree of height $h$
- if an m-ary tree of height $h$ has $l$ leaves , then $h \ge \text{ceil}(\log_ml)$ , if the m-ary tree is full and balanced, then $h = \text{ceil}(\log_ml)$ .
- A full m-ary tree with
- $n$ vertices has $i = \frac{n-1}{m}$ internal vertices and $l = \frac{(m-1)n+1}{m}$ leaves
- $i$ internal vertices has $n = mi + 1$ vertices and $l = (m-1)i+1$ leaves.
- $l$ leaves has $n = \frac{ml-1}{m-1}$ vertices and $i = \frac{l-1}{m-1}$ internal vertices.
Level of vertices
The level of a vertex $v$ in a rooted tree is the length of the unique path from the root to this vertex.
The height of a rooted tree is the maximum of the levels of the vertices.
Balanced M-ary Trees
A rooted m-ary tree of height $h$ is balabced if all leaves are at levels $h$ or $h-1$ .
Applications of Trees
Binary Search Trees
Decision Trees
Prefix Codes - Huffman Coding
Game Tree - Tic-tac-toe
Tree Traversal
Universal Address Systems
Chapters of the book
Traversal Algorithms
preorder
root -> left -> right
inorder
left -> root -> right
postorder
left -> right -> root
Notation
prefix notation
preorder
postfix notation
postorder
