[discrete mathematics review series] VI. tree

1. What is a tree ？
Undirected tree ( Trees ): A connected undirected graph without loops
The forest : Every connected branch is a non connected undirected graph of a tree
Ordinary tree : Ordinary picture
Leaf : The degree in the tree is 1 The summit of
Branch point : The degree in the tree is greater than or equal to 2 The summit of , That is, the root node and the interior point

2. Related properties of trees
set up G=<V,E>,|V|=n,|E|=m, Then the following propositions are equivalent :
(1)G Connected without loops ;
(2)G There is a unique path between each pair of vertices ; ‘
(3)G Is connected and m=n-1;
(4)G There is no circuit in and m=n-1;
(5)G No circuit in , But add an edge between any two nonadjacent vertices , It forms the only primary circuit ;
(6)G Is connected and each edge is a bridge .

3. Related theorems of trees
n There are at least 2 A leaf
prove : Extraordinary tree , The degree of each vertex is greater than or equal to 1,
Equipped with k A leaf ,m=n-1
According to the handshake Theorem 2m>=k*1+(n-k)*2k>=2
4. Make trees
(1) Make trees : set up G=<V,E> Is an undirected connected graph ,T yes G And is a tree , said T yes G The spanning tree
G stay T The edge in is called T Branch , be not in T The edge in is called T Chord .
T The derived subgraph of the set of all strings of is called T Residual tree of （ The remaining trees are not necessarily trees , Not necessarily connected ）
(2) set up n Connected undirected graphs of order have m side , Then its spanning tree has n One 1 side , Yu Shuyou m-n Ten 1 side .

5. The properties of spanning trees
(1) Any undirected connected graph has a spanning tree , As long as a connected graph has a tree
(2) inference : set up n Order undirected connected graph G Yes m side , be m>=n-1.（ Before breaking the circle ）

6. The loop of a string
Basic circuit : set up T It's a connected graph G=<V,E> A spanning tree of , For each string e, There is a unique chord e and T A primary circuit made up of branches Ce, call Ce Is corresponding to the string e The basic circuit of .
The basic loop system : The set of all basic circuits is the corresponding spanning tree T The number of basic circuits is equal to m-n+1（ Is the number of sides of the remainder ）

7. Minimum spanning tree
(1) set up T Is an undirected connected weighted graph G=<V,E,W> The spanning tree ,T The sum of the weights of all edges in is called T The right to , Write it down as W(T).
(2) Minimum spanning tree : Spanning tree with minimum weight of weighted graph
(3) The minimum spanning tree problem is ： Find the minimum spanning tree of any given undirected connected graph with weight :
The algorithm for finding the minimum spanning tree ：
Ring breaking method ： Remove the edge with the largest weight in each loop in the undirected connected graph
Circle avoidance method (Kruskal Cusk algorithm ) — The algorithm for finding the minimum spanning tree
1) Arrange each edge from small to large according to the weight
2) Select from small to large , If a ring is formed, the currently selected edge is rounded off , Until selected n-1 side

8. Directed trees
Directed trees : A directed graph whose base graph is an undirected tree
Root tree : There's a vertex with a degree of penetration of 0, The rest are 1 Of
An extraordinary directed tree
The root : The degree of penetration in the directed tree is 0 The summit of
Leaf : The degree of penetration in the directed tree is 1, The degree of 0 The summit of
Inside point : The degree of penetration in the directed tree is 1, The exodus is greater than 0 The summit of
Branch point : The exodus is greater than 1 The point of , The general name of tree root and interior point
The vertices v The number of layers : From the roots to v Path length of （ The root of the tree is 0 layer ）
Tree height : The maximum number of layers of vertices in a directed tree

9. Family tree :
(1) If the summit a Adjacent to the vertex b, said b yes a Son , a yes b Father ;
(2) if b and c Son of the same vertex , said b and c It's brother ;
(3) if a≠b And a Can be up to b, said a yes b The ancestors of the , b yes a The offspring of .
(4) A father can also be an ancestor of a son

10. Root tree : set up v Is a vertex of the root tree and is not the root of the tree , call v And all the derived subgraphs of its descendants v A root subtree of roots .

11. Ordered trees : Specify the order of vertices on the same layer of the root tree
r Fork tree : Each branch of the root tree has at most r A son
r Cross regular tree : Each branch of the root tree has exactly r A son
r Cross completely regular tree : Leaves with the same number of layers r Cross regular tree
r Cross ordered tree : Orderly r Fork tree
r Fork regular ordered tree : Orderly r Cross regular tree
r Fork completely regular ordered tree : Orderly r Cross completely regular tree

12. The best binary tree
set up 2 Fork tree T Yes t A leaf v1, v2, …, vt, The rights of leaves are w1, w2, …, wt, be called T The right to , among
l(vi) yes vi The number of layers . In the ownership of w1, w2, …, wt Of t Of a leaf 2 In the fork tree , The least powerful 2 A fork tree is called optimal 2 Fork tree .

The total weight of the optimal binary tree = Is the sum of the product of the weight of each vertex and the number of layers
Seek the best 2 Fork tree algorithm
Huffman（ Huffman ） Algorithm :
Given a real number w1, w2, …, wt ,
① do t A leaf , Respectively by w1, w2, …, wt Right .
② In all degrees of penetration 0 The summit of ( Not necessarily leaves ) Select the two vertices with the least weight , Add a new branch point , With this 2 The highest point is the son , Its power is equal to this 2 The sum of the rights of two sons .
③ repeat ②, Until only 1 The degree of entry is 0 To the top of .
W(T) be equal to ：
1. The sum of the weights of all branching points
or 2. The weight of leaves is multiplied by the sum of layers

13. set up a =α1α2…αn-1αn It's a length of n String of symbols
α The prefix of : α1α2…αk , k=1,2,…,n-1,n
Prefix code : {β1, β2, …, βm}, among β1, β2, …, βm Is a non empty string , And any two are not prefixes to each other
2 Meta prefix code : There are only two symbols ( Such as 0 And 1) The prefix code of xβα
{0,10,110, 1111}, {10,01,001,110} yes 2 Meta prefix code {0,10,010, 1010} Not a prefix code
A tree 2 The fork tree generates a binary prefix code :
For each branch point , If associated 2 side , Mark on the left 0, Right label 1; If only 1 side , It can be marked with 0( Look to the left ), You can also mark 1( Look on the right ). The string composed of the numbers marked on the path from the tree root to each leaf is recorded at the leaf , The resulting string forms a prefix code .

Insert picture description here
The best 2 Meta prefix code : Suppose that the message to be transmitted contains t Characters , character ai The frequency of occurrence is pi , The length of its code Degree is li , that n The expected encoding length of a message of characters is

Insert picture description here

Call the code with the minimum expected length 2 The meta prefix code is the best 2 Meta prefix code .