Hot answers tagged

3

An amalgam does not always exist. Consider the poset $S=\{a,b,c,d,e\}$ with the ordering $a<c$, $a<e$, $b<c$, and $b<d$. Note that $S_1=S\setminus\{a\}$ and $S_2=S\setminus\{b\}$ are both trees with respect to this ordering. Setting $T=S_1\cap S_2$, I claim that there does not exist any amalgam of $S_1$ and $S_2$ over $T$ (with $f_1$ and $f_2$ ...


3

The tree doesn't make any sense (assuming that it is an Abstract Syntax Tree). In ASTs, you recursively evaluate the children of a node, which doesn't make much sense here (you cannot say, "What is $ \times 5 $?"). Let me briefly explain why: In ASTs, the precedence is described in the tree structure, and not their nodes (that is, there is no parathesis ...


2

When you have a given binary search tree, the possible insertion sequences that will produce that tree is exactly every sequence where an internal node comes before all of its descendants in the tree. So in this case, the sequence must start with A E, F must come before G, and B, D, C occur in that order between themselves. But we're free to choose how we ...


1

From Varilly et. al.'s book and also see this paper http://cds.cern.ch/record/848107/files/cer-002531441.pdf


1

At every stage in your algorithm you need to choose which adjacent vertex you move to; I assume you are doing this in alphabetical order, however you should really specify this. You should also specify your starting vertex, which I assume is $a$, but again should be specified. Your DFS tree for (a) is correct. We add vertices in the order $a,b,c,d,e,f$ ...


1

Clearly the first key in the permutation must be $A$, since that determines the root of the derived tree. The second key will be a child of $A$, so it must be $E$. Similarly, the third key must be one of $B$ and $F$. Let’s take a closer look at the string consisting of the last five keys. It must begin with $B$ or $F$. $B$ must precede both $C$ and $D$. ...


1

We can remove the edge of weight $7$, since it could be replaced by the other edges of the rectangle, whose weights add to $6$. The resulting graph has $3$ cut vertices, and all minimal spanning trees in the $4$ components they separate can be arbitrarily combined. From left to right, there are $3$, $1$, $3$ and $2$ minimal spanning trees for the components, ...



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