Tag Info

2

Let $P$ be the number of degree 1 vertices. Then $$-2=\sum(\deg(v)-2)=\sum_{\deg(v)=1}(-1)+\sum_{\deg(v)=2}0+\sum_{\deg(v)\ge3}=-P+\sum_{\deg(v)\ge3}$$ and we're done.

2

This is correct. A tree has no cycles, so no closed regions, so there is only one face-the outer region.

2

The map $\pi$ assigns to each node of the tree $T$ its level. In the specific case of the binary tree of intervals used in the construction of the middle-thirds Cantor set, $\pi([0,1])=0$, $$\pi([0,1/3])=\pi([2/3,1])=1\;,$$ and so on: if $\pi(I)=n$, and $I_0$ and $I_1$ are the two children of $I$, then $\pi(I_0)=\pi(I_1)=n+1$. The map $\sigma^*$ takes ...

1

If you first draw the complete tree from the matrix then using Prim's algorithm you just add the egde with the lowest value to the minimum spanning tree and continue doing so until all vertices are connected to the minimum spanning tree (of course you should'nt add any edge if it doesn't add another vertice to the tree). I personally think that it is a lot ...

1

To stick with your notation: $(a,d)\ \{a,d\}$ $(d,f)\ \{a,d,f\}$ $(a,b)\ \{a,b,d,f\}$ $(b,e)\ \{a,b,d,e,f\}$ $(c,e)\ \{a,b,c,d,e,f\}$ $(e,g)\ \{a,b,c,d,e,f,g\}$ Making the total cost $5+6+7+7+5+9=39$. You went wrong in the third step, where you added $(f,e)$ instead of $(a,b)$. NB: Draw it yourself, check that you understand each step and verify that ...

1

Your statement seems wrong. The good property is : if $X$ is not contained in any spanning tree, then $X$ contains a cycle. Notice that if $X$ contains a cycle, $X$ isn't contained in any spanning tree (since a spanning tree is cycle-free), so that we couldn't prove any stronger property. You can prove the property by contradiction : First notice that ...

1

Each leaf in a tree can be reached by exactly one path from the root node. If there are $N$ leaves, there are $N$ paths from the root to a leaf node. If there were more, there would be a leaf node with two paths to it. This contradicts Statement 1. If there were fewer, there would be a leaf node with no paths to it, meaning it is not a leaf of the tree. ...

1

Your answer to the first question is not correct. Consider the tree on three nodes with root $R$, and children $V_1$ and $V_2$. This tree only has two levels, but one of $V_1$ or $V_2$ is still the 3rd smallest element. As for the second question, a heap need not be completely balanced, and the maximal element of the heap need not be in the last row.

1

A spanning tree of a connected graph $G$ by definition is a tree whose vertex set is all of $V(G)$. All trees $T$ satisfy the equation $E(T) = V(T) -1$. Let $V(G) =n$. Therefore, if $T$ is spanning tree of $G$, $T$ has $E(T) = V(T) -1 = V(G) -1 = n-1$.

1

You just need to make an argument that if $H$ is not a tree then $H$ contains a cycle, therefore there is an edge that can be removed without disconnecting $H$. This contradicts the assumption that $H$ has minimal edge weight.

1

Suppose $|V| \ge 2$. Recall that the sum of the degrees of all vertices is $2|E|$. Since The graph is connected there cannot be a vertex of degree $0$. Thus as $2|V|> 2|E|$ there is a vertex of degree one. Removing that vertex and the adjacent edge does not change that the graph is connected. And if the graph after removal is a tree, so is the graph ...

1

An empty graph on $n$ vertices has $n$ connected components, Suppose you have a graph and add an edge, then the number of connected components is reduced by at most one ( since this edge touches at most two connected components). Therefore a connected graph on $n$ vertices has at least $n-1$ edges). Suppose a connected graph on $n$ vertices has $n-1$ ...

1

To show that one of the statements is not true it suffices to give an example for which the statement is false. In the following example graphs the DFS is always started at node $s$ and the orientation of the edges indicates the search direction. Edges that are not oriented are not traversed during the search. For statements 1. and 3. consider the following ...

1

While the postorder traversal is correct, it is not a BST. For example, $9$ is to the left of $4$. The idea here is to take the last number as the root, partition the keys less than the root into the left subtree and the keys greater than the root into the right subtree, and recurse. So you should get:

1

In the simple case where there is at most one direct connection between any two segments of the network, suppose the network topology is not already tree, and that a spanning tree has been selected. There will be some link that is not in the spanning tree ... and the shortest path between the two ends of that link would certainly be to use that link (for a ...

1

Consider the trees shown below: 1 1 / / 2 2 / \ 3 3 Both have preorder $123$, and both have postorder $321$, but they’re not the same binary tree. ...

1

I would suggest it goes like this: Let us first count the degrees of the nodes in the Prüfer Code, ie. count how many times they appear: $$\begin{array}{c|c} \text{node}&6&2&5&10&9\\ \hline \text{degree}&2&3&1&1&2 \end{array}$$ Thus $6$ has to have appeared twice as a neighbor of a removed vertex before it could ...

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