# Tag Info

## Hot answers tagged trees

5

The counter example does not exist. Let $v_1$ be a vertex of $G$ with degree $1$. Then, let $v_2$ be its neighbor. Because the degree of $v_2$ is more than $1$, $v_2$ has a neighbor that is not $v_1$. Let that neighbor be $v_3$. Now, $v_3$ has a neighbor that is not $v_2$ (because the degree of $v_3$ is at least $2$) and is not $v_1$ (because $v_1$ has ...

4

I will assume that you meant a connected tree. Also, I am using maximal to mean "of maximal length," which may not be what you meant. A path in a tree is a sequence of vertices, with no repeats, where successive vertices in the sequence are adjacent. If a path $P$ is at least as long as any other path, then that path is maximal. It is possible for there to ...

3

Would you be ok with an answer like, i(n) = (2*n+2)*Psi(n+1)+(2*gamma-4)*n+2*gamma; where Psi is the digamma function as defined here? I got that by issuing following in Maple 2015, rsolve( {(it(n+1) - n/(n+1)*it(n) - n + n^2/(n+1) - n/(n+1))*(n+1)/2 = it(n), it(0)=0}, it(n) );

2

It depends what you mean by maximal. Usually maximal is different from maximum in the following sense: a maximal path can mean a path that cannot be made any longer; in other words, at each end there is a vertex all of whose neighbours are already on the path. Note that under this definition, a maximal path is not necessarily a path of maximum length. Here ...

2

Let $\phi_T : \mathbb{N}\times\mathbb{N} \to \mathbb{B}$ be defined as $$\phi_T(n,k) \iff \text{in tree } T \text{ there are at least } n \text{ nodes }\text{with at least } k \text{ children each},$$ and define $\Phi_S : \mathbb{N}\times\mathbb{N} \to \mathbb{B}$ \begin{align}\Phi_S(n,k) \iff & \phi_T(n,k) \text{ is true for infinitely many trees ...

2

You seem to have two output classes and given the hint, the inputs must be equally likely since 2 of 10 inputs lead to class 1, the rest class zero, corresponding to 0.2 and 0.8 respectively. The definition of entropy is $$-\sum_{x} p_x \log_2(p_x)$$ which will give the numerical value of $$-0.2 \times (-2.3) -0.8 \times (-0.3)$$as the entropy.

1

Number of edges in a complete bipartite graph $K_{m,n}$ is $mn$. Number of edges in a tree with $v$ vertices is $v-1$. Hence, if we want $K_{a,b}$ to be a tree, we need $$ab = a+b-1 \implies ab-a-b+1 = 0\implies (a-1)(b-1) = 0 \implies a = 1 \text{ or }b=1$$

1

Yes and no. A spanning tree of minimal total weight must have minimal "heaviest edge" too, but the opposite is not necessarily the case. Suppose that $A$ and $B$ are both spanning trees in the same graph, but that $A$ has an edge that is heavier than every edge in $B$. Then $A$ cannot have minimal total weight. To wit, let $(v_1,v_2)$ be the heavy edge in ...

1

If I understand correctly, this diagram represents both players playing optimally. Every value inside the node(rectangle/circle) is the highest possible value the first play can obtain if both players play optimally. After the first step of the first player, there are two possible states {2,10,3} and {1,2,10}. In {1,2,10} it is the second player's turn and ...

1

It seems the solver is not able to handle the summation statement. Trying now to avoid the summation: \begin{align} i(n) &= n - 1 + \frac{2}{n} \sum_{k=0}^{n-1}i(k) \\ i(n+1) &= n + \frac{2}{n+1} \sum_{k=0}^ni(k) \\ &= \frac{2}{n+1}i(n) + n + \frac{2}{n+1} \sum_{k=0}^{n-1} i(k) \\ &= \frac{2}{n+1}i(n) + n + \frac{n}{n+1} \left( i(n) - n + 1 ...

1

I’ll get you started. Start at the bottom: the leaves have empty subtrees, so the value of each leaf is simply the integer stored in it. Now go up a level and work on the four max nodes just above the leaves. each of them is the root of a small tree with $3$ nodes. For the first one, for instance, we have this tree: 0 / \ ...

1

From the pre-order sequence you know that the root is N. The in-order sequence then tells you that A, L, D, and Z are in the left subtree, and U, R, Y, B, and G are in the right subtree. Now go back to the pre-order sequence: it tells you that Z is the root of the left subtree. The in-order sequence then tells you that all three of the other nodes of the ...

Only top voted, non community-wiki answers of a minimum length are eligible