Question

For any given positive integer n design a tree on n vertices with b(T) ≤ ⌈1.5⌈log n⌉+1/2⌉. (One can consider the reverse: given an integer, broadcast time t, and try to design a tree T with large number of vertices).

Answer 1

To design a tree with a maximum broadcast time of ⌈1.5⌈log n⌉+1/2⌉, a binary tree can be used where each vertex has 0, 1, or 2 children. Starting with a complete binary tree with 1 vertex, additional levels can be added to double the number of vertices until the desired number of vertices is reached.

Step-by-step explanation:

To design a tree with a maximum broadcast time of ⌈1.5⌈log n⌉+1/2⌉, we can start by considering a binary tree. In a binary tree, each vertex has either 0, 1, or 2 children. Since we want to maximize the number of vertices, we can start with a complete binary tree with 1 vertex and gradually add more levels until we reach the desired number of vertices. For each additional level, the number of vertices doubles.

As an example, let's say we want to design a tree with 10 vertices. We can start with a complete binary tree with 1 vertex. Adding the first level, we get 3 vertices. Adding the second level, we get 7 vertices. Adding the third level, we get 15 vertices. Adding the fourth level would exceed 10 vertices, so we stop at the third level. Thus, the tree with 10 vertices has a broadcast time of ⌈1.5⌈log 10⌉+1/2⌉ = ⌈1.5⌈1⌉+1/2⌉ = ⌈1.5+1/2⌉ = 3.