Chapter 11: Trees

How many different isomers do these saturated hydrocarbons have?

\(\begin{array}{l}{\bf{a)}}{{\bf{C}}_{\bf{3}}}{{\bf{H}}_{\bf{8}}}\\{\bf{b)}}{{\bf{C}}_{\bf{5}}}{{\bf{H}}_{{\bf{12}}}}\\{\bf{c)}}{{\bf{C}}_{\bf{6}}}{{\bf{H}}_{{\bf{14}}}}\end{array}\)

Draw a game tree for him if the starting position consists of two piles with two and three stones, respectively. When drawing the tree represent by the same vertex symmetric positions that result from the same move. Find the valueof each vertex of the game tree. Who wins the game if both players follow an optimal strategy?

Give six examples of well-formed formulae with three or more operators in postfix notation over the set of symbols \(\left\{ {{\bf{x,y,z}}} \right\}\) and the set of operators \(\left\{ {{\bf{ + , \ast ,}} \circ } \right\}\).

Show that if \(G\) is a weighted graph with distinct edgeweights, then for every simple circuit of \(G\), the edge of maximum weight in this circuit does not belong to anyminimum spanning tree of \(G\).

How many edges must be removed to produce the spanning forest of a graph with n vertices, m edges, and c connected components?

In Exercises 31-33 find a degree-constrained spanning tree of the given graph where each vertex has degree less than or equal to 3, or show that such a spanning tree does not exist.

Let G be a connected graph. Show that if T is a spanning tree of G constructed using breadth-first search, then an edge of G not in T must connect vertices at the same level or at levels that differ by 1 in this spanning tree.

Extend the definition of well-formed formulae in prefix notation to sets of symbols and operators where the operators may not be binary.

When Kruskal invented the algorithm that finds minimumspanning trees by adding edges in order of increasing weightas long as they do not form a simple circuit, he also inventedanother algorithm sometimes called the reverse-delete algorithm. This algorithm proceeds by successively deletingedges of maximum weight from a connected graph as long asdoing so does not disconnect the graph.

Express the reverse-delete algorithm in pseudocode.

Draw a game tree for him if the starting position consists of three piles with one, two, and three stones, respectively. When drawing the tree represent by the same vertex symmetric positions that result from the same move. Find the value of each vertex of the game tree. Who wins the game if both players follow an optimal strategy?