Tag Info

Hot answers tagged

2

If you remove one edge form a tree, it becomes disconnected. Hence a spanning connected subgraph must containt all egdes, hence the only spanning tree of a tree $T$ is $T$. The answer is 1, hence.


2

A connected graph with two vertices of degree one and the rest of degree two is called a path. If you want to distinguish between successor and predecessor vertices, you can direct the edges all the same direction and obtain a directed path.


2

Remember the "first theorem of graph theory:" $$\sum_{v \in V(G)} \deg v =2|E(G)|,$$ where $V(G)$ denotes the vertex set and $E(G)$ the edge set. If $\deg v$ is odd for each vertex, what does the above say about the parity (even or odd) of $|V(G)|$? Once you've figured this out, you still need to translate this into a statement about the size of the graph, ...


2

I'm assuming this means you have a graph $G$ on $n$ vertices with adjacency matrix $A$, and you want to count the number of spanning trees of $G$. Now, $G$ is a subgraph of $K_n$, and so any spanning tree of $G$ is certainly a spanning tree of $K_n$. But a spanning tree $T$ of $K_n$ is not necessarily a spanning tree of $G$. In particular, $T$ is not a ...


1

It seems that $A$ is the adjacency matrix of the complete graph. So $A_{i,j}=1$ whenever $i \neq j$ and $A_{i,i}=0$. So $$\sum_{T \text{ spanning tree of }K_n}\prod_{(i,j)\in T}A_{i,j}=\sum_{T \text{ spanning tree of }K_n}1$$ which is the number of spanning trees of $K_n$. Note: this would still work if $K_n$ were replaced by an arbitrary graph $G$, and ...


1

You are correct that the height of a heap is given by $\lfloor\log_2n\rfloor$. It is more than likely that the books you are looking at use $\lg n$ as shorthand for $\log_2 n$ rather than $\log_{10} n$.


1

In the context of data structures, $\log$ typically denotes the logarithm base $2$. In your example of a binary tree with $7$ nodes, we see that $\lfloor \log_2 (7) \rfloor = 2$. More generally, consider a full binary tree with height $h$, where the root is at height zero. Then it has $\sum_{n=0}^h 2^n = 2^{h+1} - 1$ total nodes. It's easy to see that ...


1

$\Longleftarrow$: Assume that (a) $x$ stands before $y$ in the pre-order traversal of $B$ and that (b) $x$ stands after $y$ in the post-order traversal of $B$. Now assume that (c) $x$ is not an ancestor of $y$ (a proof by contradiction will follow). There are two cases: $y$ is an ancestor of $x$: a node $u$ isn't visited by pre-order traversal until all ...


1

For the converse I would proceed by contrapositive with the following ideas. (1) Assume $x$ and $y$ are vertices for which neither is an ancestor of the other. (2) Argue that there is a lowest common ancestor (I am picturing the tree drawn with the root at the top and going downwards) of $x$ and $y$, say $a$. (3) Argue that one of $x$ and $y$, say $x$ is ...


1

This answer explores the ideas by @vonbrand, using a form of Lagrange inversion to extract coefficients. I would write the species equation slightly differently, namely as $$\mathcal{T} = \mathcal{ZY} + \mathcal{Z}\mathfrak{P}_{\ge 1}(\mathcal{T}).$$ This translates into the functional equation $$T(z) = zy + z(\exp T(z) - 1) = z(-1+y+\exp T(z)).$$ We ...


1

Recall that the $n$th triangular number is given by: $$ T_n = \frac{n(n + 1)}{2} $$ You appear to be asking for the inverse of this function. By taking the positive version of the above function's inverse, we obtain the following formula: $$ \frac{\sqrt{8n + 1} - 1}{2} $$ Indeed, for $n = 10$ nodes, we find that the number of levels is: $$ \frac{\sqrt{8(10) ...


1

As the calculation of this number/formula has not been posted I will try to outline it here. Start with the species equation $$\mathcal{T} = \mathcal{Z}\times \sum_{q=0}^{D-1} {D-1\choose q}\mathfrak{S}_{=q}(\mathcal{T}).$$ We can visualize this equation as there being $D-1$ slots at the lower side of every node, all subsets of size $q$ of which, ...



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