21-01-2013, 10:15 AM
Trees
1Trees.docx (Size: 66.34 KB / Downloads: 25)
An acyclic graph (also known as a forest) is a graph with no cycles. A tree is a connected acyclic graph. Thus each component of a forest is tree, and any tree is a connected forest.
Theorem The following are equivalent in a graph G with n vertices.
i. G is a tree.
ii. There is a unique path between every pair of vertices in G.
iii. G is connected, and every edge in G is a bridge.
iv. G is connected, and it has (n - 1) edges.
v. G is acyclic, and it has (n - 1) edges.
vi. G is acyclic, and whenever any two arbitrary nonadjacent vertices in G are joined by and edge, the resulting enlarged graph G' has a unique cycle.
vii. G is connected, and whenever any two arbitrary nonadjacent vertices in G are joined by an edge, the resulting enlarged graph has a unique cycle.
Theorem
Let T be a graph with n vertices. Then the following statements are equivalent.
a. T is connected and contains no cycles.
b. T is connected and has n-1 edges.
c. T has n-1 edges and contains no cycles.
d. T is connected and each edge is abridge.
e. Any two vertices of T are connected by exactly one path.
f. T contains no cycles, but the addition of any new edge creates exactly one cycles.
Centers and Bicenters
It is convenient to start building up the tree at the middle of a tree and move outwards. This was the approach used by Arthur Cayley when he counted the number of chemical molecules by building them step by step. But what do we mean by the "middle" of a tree?
Tree Searching
There are two well-known search methods. They are brown as depth-first search( DFS) and breadth-first search (BFS). Each of these methods lists the vertices as they are encountered, and indicates the direction in which each edge is first traversed. The methods differ only in the way in which the vertex-lists are constructed.