The word "graph" has many different meanings in math. This is common in English usage, but in math we try to avoid it. It's called overloading a symbol and the effort to stop doing it is about as old as computer science, which means in terms of math history, it's like it happened yesterday.
A graph can be a bar chart or a pie chart, a graphing calculator will draw sine waves and lines and parabolas and such, but when used in the phrase "graph theory", we are talking about the mathematical version of connect the dots, where the dots are called nodes (or sometimes vertices) and the lines connecting them are called edges. There have been several earlier posts in the Wednesday math series about graph theory, most recently about minimal spanning trees back in June of last year.
A graph can represent many different things. It could be a flowchart of a computer program or a transportation grid. In chemistry class, the representation of a molecule is a graph, where each atom is shown as a node and the bonds are the edges. We are going to look at directed trees, which means a minimally connected graph that has one special node designated as the root. Given that we use the words tree and root, it would be nice if we stayed consistent with the metaphor and put the root at the bottom, but it's very common to go the other way around and put the root node at the top, not unlike an org chart.
A binary tree means that every node has a maximum of two nodes directly below it. Some nodes have no nodes below them, and they are called leaves or external nodes. The nodes directly below are often called children, and the node above the parent, which extends the metaphor of tree to family tree.
When teaching divisibility, students now are taught to make factor trees. For example, if we want to find all the factors of 300, we find two numbers larger than 1 to multiply together to 300. In the example on the left, we use 30 and 10. On the right, the pair of numbers was 150 and 2. We continue to do this splitting function on any number that isn't a prime until all the leaves(represented as circles in this picture, to differentiate them from the internal nodes drawn as squares) are filled with prime numbers, which cannot be split into a product of two numbers greater than 1. The two trees are clearly different, but what they have in common is they have the same number of leaves and the same list of numbers inside those leaves, though possibly in a different order. Those numbers when multiplied together are called the prime factorization of 300, which is 2×2×3×5×5, or 2²×3×5².
Over the next few weeks, I'll be bringing up many problems very different from one another that use binary trees as their solutions.
