View Question
 Question
 Subject: TREES AND GRAPHS Category: Computers > Algorithms Asked by: dan1976-ga List Price: \$3.00 Posted: 25 Apr 2005 22:07 PDT Expires: 25 May 2005 22:07 PDT Question ID: 514258
 ```1) If a forest F consists of m trees and has n vertices, how many edges does F have.?``` Clarification of Question by dan1976-ga on 25 Apr 2005 22:08 PDT `F is simpe graph with no cycles`
 There is no answer at this time.

 `If you try a few examples, you should be able to see a pattern pretty easily.`
 ```What a great handle, "quadraticresidue-ga"! Yes, start with a single tree. If it had n vertices, it would have n-1 edges. Now a forest is a collection of trees. In each tree there is one fewer edge than the number of vertices in that tree. So, how many edges does a forest F require with m trees and n vertices (total)? regards, mathtalk-ga```
 ```Sorry for my broken English! > If a forest F consists of m trees and has n vertices, how many edges does F have.? > F is simpe graph with no cycles For all trees Ti from the forest F (1 <= i <= m): V(Ti) = Vi - a quantity of vertices, 1 <= i <= m. E(Ti) = Ei - a quantity of edges, 1 <= i <= m. Ei = Vi - 1 - this is a simple feature of tree. E(F) = E1 + E2 + ... + Em = (V1 - 1) + (V2 - 1) + ... + (Vm - 1) = (V1 + V2 + ... + Vm) - m. But V1 + V2 + ... + Vm = V(F) = n. Then E(F) = n - m. Thanx.```
 ```Forest if collection of disjoint trees. Step 1: Start from a single tree with n vertices. This will have n-1 edges. Step 2: Remove an edge from this tree. Now there are 2 trees and number of edges = n-2. Step 3: Recursively going the Step 2 m-1 times will leave us with m trees and number of edges = n-m.```