TAOCP 2.3.4.1: Free Trees

Section 2.3.4.1 exercises: 13/13 solved.

13 items

Section 2.3.4.1. Free Trees

Exercises from TAOCP Volume 1 Section 2.3.4.1: 13/13 solved.

#	Rating	Status	Time
1	[**]	verified	1m24s
2	[**]	verified	43s
3	[**]	solved	2m22s
4	[**]	verified	37s
5	[**]	solved	2m38s
6	[**]	verified	37s
7	[**]	verified	38s
8	[**]	solved	25s
9	[**]	solved	3m15s
10	[**]	verified	1m24s
11	[**]	verified	42s
12	[**]	solved	2m11s
13	[**]	verified	41s

Practice › Mathematics › TAOCP › TAOCP Vol 1: Fundamental Algorithms › TAOCP 2.3.4.1: Free Trees ›

TAOCP 2.3.4.1 Exercise 1

We reconstruct the solution by systematically enumerating all simple cycles that start and end at $B$, using the adjacency information from Fig.

Practice › Mathematics › TAOCP › TAOCP Vol 1: Fundamental Algorithms › TAOCP 2.3.4.1: Free Trees ›

TAOCP 2.3.4.1 Exercise 2

Let $(V_0,V_1,\ldots,V_n)$ be a walk from $V = V_0$ to $V' = V_n$.

Practice › Mathematics › TAOCP › TAOCP Vol 1: Fundamental Algorithms › TAOCP 2.3.4.1: Free Trees ›

TAOCP 2.3.4.1 Exercise 3

The reviewer's objections are decisive.

Practice › Mathematics › TAOCP › TAOCP Vol 1: Fundamental Algorithms › TAOCP 2.3.4.1: Free Trees ›

TAOCP 2.3.4.1 Exercise 4

Since $G'$ is a finite free tree with at least one edge, the auxiliary result in Section 2.

Practice › Mathematics › TAOCP › TAOCP Vol 1: Fundamental Algorithms › TAOCP 2.3.4.1: Free Trees ›

TAOCP 2.3.4.1 Exercise 5

**Corrected Solution to Exercise 2.

Practice › Mathematics › TAOCP › TAOCP Vol 1: Fundamental Algorithms › TAOCP 2.3.4.1: Free Trees ›

TAOCP 2.3.4.1 Exercise 6

Process the edges one at a time, maintaining a set of connected components of the vertices already joined by the selected edges.

Practice › Mathematics › TAOCP › TAOCP Vol 1: Fundamental Algorithms › TAOCP 2.3.4.1: Free Trees ›

TAOCP 2.3.4.1 Exercise 7

Let the graph of the flow chart have vertices corresponding to the boxes, and let the free subtree be $G'$ with edges $e_1,e_2,e_3,e_4,e_9$.

Practice › Mathematics › TAOCP › TAOCP Vol 1: Fundamental Algorithms › TAOCP 2.3.4.1: Free Trees ›

TAOCP 2.3.4.1 Exercise 8

Let a reduced flow chart be obtained from an original flow chart by combining a set of vertices into a supervertex and summing the corresponding edge flows.

Practice › Mathematics › TAOCP › TAOCP Vol 1: Fundamental Algorithms › TAOCP 2.3.4.1: Free Trees ›

TAOCP 2.3.4.1 Exercise 9

The splitting of edges $e_{13}$ and $e_{19}$ was introduced solely to satisfy the formal definition of a graph in which no two edges may join the same pair of vertices.

Practice › Mathematics › TAOCP › TAOCP Vol 1: Fundamental Algorithms › TAOCP 2.3.4.1: Free Trees ›

TAOCP 2.3.4.1 Exercise 10

Let the terminals $T_1,\ldots,T_n$ be the vertices of a graph $G$, and let each wire correspond to an edge.

Practice › Mathematics › TAOCP › TAOCP Vol 1: Fundamental Algorithms › TAOCP 2.3.4.1: Free Trees ›

TAOCP 2.3.4.1 Exercise 11

Let $S$ be any nonempty proper subset of the terminals, and let $\bar S$ be its complement.

Practice › Mathematics › TAOCP › TAOCP Vol 1: Fundamental Algorithms › TAOCP 2.3.4.1: Free Trees ›

TAOCP 2.3.4.1 Exercise 12

A direct implementation is obtained by maintaining, for each terminal not yet in the growing tree, the cheapest known connection from that terminal to any terminal already in the tree.

Practice › Mathematics › TAOCP › TAOCP Vol 1: Fundamental Algorithms › TAOCP 2.3.4.1: Free Trees ›

TAOCP 2.3.4.1 Exercise 13

Assume first that the graph is connected.