91Ó°ÊÓ

Which complete bipartite graphs \(K_{m, n},\) where \(m\) and \(n\) are positive integers, are trees?

How many edges does a tree with \(10,000\) vertices have?

Show that there is a unique minimum spanning tree in a connected weighted graph if the weights of the edges are all different.

Given the coding scheme a: 001, b: 0001, e: 1, r: 0000, s: 0100, t: 011, x: 01010, find the word represented by $$ \begin{array}{ll}{\text { a) } 0110100011 .} & {\text { b) } 0001110000} \\\ {\text { c) } 0100101010} & {\text { d) } 01100101010}\end{array} $$

A chain letter starts when a person sends a letter to five others. Each person who receives the letter either sends it to five other people who have never received it or does not send it to anyone. Suppose that \(10,000\) people send out the letter before the chain ends and that no one receives more than one letter. How many people receive the letter, and how many do not send it out?

Use Huffman coding to encode these symbols with given frequencies: a: 0.20, b: 0.10, c: 0.15, d: 0.25, e: 0.30. What is the average number of bits required to encode a character?

A chain letter starts with a person sending a letter out to 10 others. Each person is asked to send the letter out to 10 others, and each letter contains a list of the previous six people in the chain. Unless there are fewer than six names in the list, each person sends one dollar to the first person in this list, removes the name of this person from the list, moves up each of the other five names one position, and inserts his or her name at the end of this list. If no person breaks the chain and no one receives more than one letter, how much money will a person in the chain ultimately receive?

a) Use Huffman coding to encode these symbols with frequencies a: 0.4, b: 0.2, c: 0.2, d: 0.1, e: 0.1 in two different ways by breaking ties in the algorithm differently. First, among the trees of minimum weight select two trees with the largest number of vertices to combine at each stage of the algorithm. Second, among the trees of minimum weight select two trees with the smallest number of vertices at each stage. b) Compute the average number of bits required to encode a symbol with each code and compute the variances of this number of bits for each code. Which tie-breaking procedure produced the smaller variance in the number of bits required to encode a symbol?

Show that an ordered rooted tree is uniquely determined when a list of vertices generated by a preorder traversal of the tree and the number of children of each vertex are specified.

A complete \(m\) -ary tree is a full \(m\) -ary tree in which every leaf is at the same level. Construct a complete binary tree of height 4 and a complete 3 -ary tree of height 3 .