Graph theory and trees
'Trees' are a type of structure within the mathematical theory of graphs.
Graphs consist of two things: nodes (other words for these, 'vertices', 'points') and links (other words for these, 'edges', 'lines', 'ties'). In applications, nodes typically model individual people, countries, businesses, web pages, genes, amino acids, etc. Links typically model friendships, web hyperlinks, telephone lines, communications, etc. For us, nodes are going to represent formulas and the links will show the decomposition, or transformation, of a formula into other formulas.
You can think of a node and being a dot or a point, and a link as being a line or an edge which runs from a node to a node. So here is a graph
The size of a graph is the number of nodes in it. This one is of size 7.
The degree of a node is the number of links that connect to it. So, for example, the node d has degree 2 and g degree 3.
How the links are drawn is irrelevant (you can draw them as curves or straight lines or locate them differently, and the links can cross each other without that meaning anything)-- all that matters is which nodes they connect. These two graphs are actually the same graph.
A walk is an alternating sequence of nodes and links, which starts and ends with a node. So, in the first example graph, a->d->e is a walk. A path is a walk with no repeated nodes. The length of a walk is the number of links included in it. Two nodes are adjacent if there is a link between them.
A graph has a cycle, or is cyclic, if there is a walk of non-zero length that starts and ends on the same node (otherwise the graph is said to be acyclic).
A graph is connected if there is a path between every two nodes in it. The first example graph is not connected (because the node b cannot be reached), and the second example graph is connected.
There are a couple of different ways of explaining or defining trees (and which is preferable depends a little on what is going to be done with the resulting trees).
A tree is a connected graph in which between every two nodes there is only one path (ie there are no 'cycles'). For example,
is a tree (you can walk from node to node (so it is connected) but you cannot walk around in a circle (so there are no cycles)).
With a tree, there are nodes which do not have other nodes below them. These are leaves. So, in the above tree, d is the root, and c, f and b are leaves. With any leaf, there is exactly one path from the root to it, such a path is a branch.
d-a-g-f is a branch in the above tree.