A tree is a graph connecting "N" vertices with "N-1" edges such that there is one and only one route between any two given vertices.

   In a rooted tree, travel along any of the edges is directed toward the "root". The root is customarily the top vertex in the tree. A family tree is an example of a rooted tree where a single individual in the present generation has a branching tree of ancestors (root will be at the bottom). Alternately, a family tree may show the many descendents that started from a single ancestor (or marriage).

  A non-rooted tree has a free form where no vertex has priority. A non-rooted tree can be twisted, deformed, contorted, etc. into many shapes without altering its structure.

   The chart above shows the 4 structurally different rooted trees (root is at the top) that can be constructed with 4 vertices. If we consider them as non-rooted trees, then there are only two different structures. Trees 1 and 2 have the same basic structure if there is no root. Similarly, trees 3 and 4 have the same non-rooted structure.

   The chart above shows the 9 structurally different rooted trees that are possible if we use 5 vertices. If we use them as "free" non-rooted trees, then there are only 3 structurally different patterns. Trees 1, 2, and 3 are structurally the same if there isn't a root. Similarly, trees 4, 5, 6, and 7 are all variations of the same structure if there isn't a root. Finally trees 8 and 9 have the same non-rooted structure.

   An interesting question arises. If you have any "N" number of vertices connected by "N-1" edges, how many structurally different trees are there of each type? We will present the results followed by a source that viewers can check if they want to know how to calculate the results.


                     Number of structurally different, rooted and non-rooted trees
                                        Computer Program by Bill Butler

Number of               Number of                    Number of
Vertices               Rooted Trees              Non-rooted trees
-----------------------------------------------------------------
   1                              1                             1
   2                              1                             1
   3                              2                             1
   4                              4                             2
   5                              9                             3
   6                             20                             6
   7                             48                            11
   8                            115                            23
   9                            286                            47
  10                            719                           106
  11                          1,842                           235
  12                          4,766                           551
  13                         12,486                         1,301
  14                         32,973                         3,159
  15                         87,811                         7,741
  16                        235,381                        19,320
  17                        634,847                        48,629
  18                      1,721,159                       123,867
  19                      4,688,676                       317,955
  20                     12,826,228                       823,065
  21                     35,221,832                     2,144,505
  22                     97,055,181                     5,623,756
  23                    268,282,855                    14,828,074
  24                    743,724,984                    39,299,897
  25                  2,067,174,645                   104,636,890
  26                  5,759,636,510                   279,793,450
  27                 16,083,734,329                   751,065,460
  28                 45,007,066,269                 2,023,443,032
  29                126,186,554,308                 5,469,566,585
  30                354,426,847,597                14,830,871,802
  31                997,171,512,998                40,330,829,030
  32              2,809,934,352,700               109,972,410,221
  33              7,929,819,784,355               300,628,862,480
  34             22,409,533,673,568               823,779,631,721
  35             63,411,730,258,053             2,262,366,343,746
  36            179,655,930,440,464             6,226,306,037,178
  37            509,588,049,810,620            17,169,677,490,714
  38          1,447,023,384,581,029            47,436,313,524,262
  39          4,113,254,119,923,150           131,290,543,779,126
  40                   1.170378E+16           363,990,257,783,342
               (Possible precision)
            (error on the last few)

   The above results are the output of a computer program that would require a significant amount of explanation. I originally wrote the program in response to "Exercise 3." on page 395, Vol. 1, Knuth's "The Art of Computer Programming" (Second Edition). The derivation of the algorithm is spread over several pages in the "Enumeration of Trees" section. (If you like generating functions, have fun - otherwise, good luck.)  Knuth's rating for the "Exercise" is "M40". Knuth's translation for this is: "Mathematically oriented" "Quite a difficult or lengthy problem, which is perhaps suitable for a term project in classroom situations." I will thus forgo trying to explain the algorithm although the computer code is surprisingly short. There are probably other sources that derive the algorithm. There will be other students that have to learn and understand the process. If you have the misfortune to find yourself in this position, you have my deepest sympathy.

Return to Durango Bill's Home Page


Web page generated via KompoZer