Have you ever tried counting trees? Perhaps you tried counting those kinds of trees in science with the leaves, trunks and branches. But this one is a different kind of tree.
Well, counting trees could be tedious especially when trees tend to be disorganized. But before that, let us give a background on trees and the field of Graph Theory since they are our main topic for today. Graph Theory has applications such as network analysis, computing shortest paths and computer science since it deals with many algorithms. Even in biology, Graph Theory can also be utilized! Some examples would be the structure of molecules and the structure of the DNA. With this, Graph Theory has a lot of concepts that will fascinate even non-mathematics majors for having terms such as trees, circuits, forests and even loops. But the aforementioned words will be taken in a different context since this is still a field under mathematics. But let us first define the tree. According to Bondy and Murty, a tree is a connected acyclic graph and an acyclic graph (also known as forest) is a graph that has no cycles. Cycles can also be referred to as circuits. In addition, a tree with n vertices has n-1 edges. Thus, each component of a forest is a tree and any tree is a connected forest. In short, trees are just straight paths with origin and terminus. Counting trees is a tedious task especially in Graph Theory. In Graph Theory, determining the number of trees in a graph is not simply by looking at the graph and telling that the graph contains trees. Some graph may contain at least one tree, more than one tree or if possible, no trees at all. The authors sensed the need of providing an algorithm on how to count trees with the use of mathematical equations. With this, developing an algorithm in order to count trees is a need especially in this field because some unsolved problems will involve graph labeling and determining the gracefulness of said trees. A paper submitted on August 2016 by Dhruv Mubayi and Jacques Verstraete entitled "Counting Trees in Graphs" explained the methods on how to obtain the number of trees using algorithms. It used some concepts in algebra, combinatorics in order to formulate the algorithm needed to simply count the trees in a systematic manner. By the definition of trees of n vertices and n-1 edges, it can create cliques of different orders. With the degree sequences of bipartite graphs, the trees were evaluated using an approximate form of Jensen's inequality. Jensen's inequality proved to be of great help in maintaining the systematics of counting trees. Of course, there are proofs to be established and bounds are needed to be set in order to obtain results in counting trees. In conclusion, their theorem can be improved if structural information on the graph is given and their results are tightly based on regular graphs. With their peer-review system in improving their paper, the authors had obtained the necessary parameters in making the algorithm for counting trees and they thanked those who helped them in revising their process. Counting trees may be tedious using those equations but they sure helped a lot in the trial-and-error method and using your vision in checking whether the graphs have trees or not. Algorithms can help especially when there are so many graphs with trees to consider. This information would certainly help those who would pursue further studies in Graph Theory. References:
1 Comment
|
AuthorCzarina Atienza is a student of the University of the Philippines Los Baños. You may get in touch with her at [email protected] ArchivesCategories |