Tree (graph theory)

Imagine dots joined by lines.

In math, we call this a tree. A tree has no loops. You cannot go in a circle.

Every dot can reach every other dot. This is a special path. A forest is a group of trees.

Some trees have a root. The root is a starting dot. You can name the dots. This helps us keep track.

Math helps us see these patterns.

Imagine dots connected by lines. In math, we call this a tree.

A tree must follow two rules. First, all dots must be connected. You can reach any dot from any other dot. Second, there are no loops. You cannot travel in a circle. If you add one more line, you might make a loop. If you take one line away, the tree breaks apart.

Some trees have a special starting dot called a root. This is a rooted tree. We can name the other dots based on the root. A dot connected to the root is a child. The root is the parent.

In a rooted tree, we use words like leaf. A leaf is a dot with no children. It is at the very end of a path. An internal vertex is a dot that is not a leaf.

Groups of trees are called a forest. A mathematician named Arthur Cayley studied these in 1857. Computers also use trees to store data. They help keep information organized in a clear way.

In math, a tree is a special way to connect dots. These dots are called vertices, and the lines between them are called edges.

A tree must follow two main rules. First, every dot must be part of the same group. This means you can find a path from any dot to any other dot. Second, there can be no loops or circles. If you try to walk along the lines, you can never end up back where you started without turning around. If you add just one more line to a tree, you will create a loop. If you take one line away, the tree will break into separate pieces.

There are many different ways to look at these shapes. Sometimes, a group of trees is called a forest. This is just a collection of trees that are not connected to each other.

You can also have a directed tree. In these, the lines have arrows that show a specific direction. If all the arrows point away from a starting dot, it is called an arborescence. If they all point toward a starting dot, it is called an anti-arborescence. Some trees even have a special starting dot called a root. This makes it a rooted tree, which helps us organize information.

In a rooted tree, we use family words to describe the dots. The root is like the head of the family. The dots connected to the root are its children. Any dot that has its own children is called an internal vertex. A dot at the very end of a path with no children is called a leaf.

You can also talk about siblings, which are dots that share the same parent. We can even measure how tall a tree is by looking at the distance from the root to the furthest leaf. This distance is called the height of the tree.

Math lovers have studied these patterns for a long time. In 1847, a physicist named Gustav Kirchhoff used trees to study electrical circuits. He looked at how wires and junctions work together. Later, in 1857, a British mathematician named Arthur Cayley used the word "tree" to describe these shapes.

Cayley even found a famous formula to count how many different trees you can make with a certain number of labeled dots. His work helped people understand how these structures grow and change.

Trees are very useful in our modern world. Computer scientists use them as data structures to keep information organized. For example, a binary tree is a type of tree where each dot has at most two children.

This helps computers find information very quickly. You can see the idea of a tree in many places, from how a family tree shows ancestors to how a map might show paths. Even though they are simple shapes, they help us solve very hard problems.

In graph theory, a tree is a specific type of undirected graph. A graph is a collection of points, called vertices, connected by lines, called edges.

For a graph to be a tree, it must satisfy two essential conditions. First, it must be connected, meaning a path exists between every pair of distinct vertices. Second, it must be acyclic, which means it contains no cycles or loops. If you were to add a single edge to a tree, you would create a cycle. If you were to remove any single edge, the graph would become disconnected.

Mathematically, a tree can be defined through several equivalent properties. For a finite tree with $n$ vertices, the graph must have exactly $n - 1$ edges. Every tree is also a bipartite graph. This means its vertices can be divided into two groups such that no two vertices within the same group are connected. Additionally, any two vertices in a tree are connected by exactly one unique simple path. This uniqueness is a fundamental characteristic of the tree structure.

There are many variations of trees depending on how they are organized. A forest is an undirected acyclic graph. You can think of a forest as a disjoint union of several separate trees. If a tree has a specific vertex designated as the root, it is called a rooted tree. In these structures, we use hierarchical terms to describe relationships. A vertex connected to the root is a child, while the root itself has no parent. Vertices with no children are called leaves, also known as terminal or outer vertices. Vertices with at least two connections are called internal vertices.

Directionality adds another layer of complexity to these graphs. A directed tree, or polytree, is a directed acyclic graph (DAG) whose underlying undirected graph is a tree. In a rooted tree, edges can be oriented in specific ways. If all edges point away from the root, the structure is called an arborescence or an out-tree. If all edges point toward the root, it is called an anti-arborescence or an in-tree. Similarly, a directed forest is a DAG where the underlying graph is a forest. These structures are vital for representing hierarchies and flows.

The history of tree theory involves several important mathematicians. In 1847, the German physicist Gustav Kirchhoff used trees to investigate electrical circuits. He established a relationship between the number of wires, known as branches, and the number of junctions, known as vertices. He also considered the number of loops, or faces, in a circuit. Later, in 1857, the British mathematician Arthur Cayley coined the term "tree" in his work on analytical forms. Cayley also provided a famous formula to determine the number of possible trees that can be formed using $n$ labeled vertices, which is $n^{n-2}$.

Trees are highly significant in modern computer science. They serve as fundamental data structures for organizing and searching information. For instance, a $k$-ary tree is a rooted tree where each vertex has at most $k$ children. A common version is the binary tree, where $k$ is 2. Computer scientists use self-balancing trees, such as AVL trees, to manage data efficiently. In these systems, the depth of a vertex is the length of the path to the root, while the height of a vertex is the longest downward path to a leaf.

Beyond computing, trees possess unique geometric and structural properties. Every tree has a center, which consists of either one vertex or two adjacent vertices. This center represents the middle of every longest path in the tree. Trees also have a centroid, which is a vertex or edge that, when removed, splits the tree into smaller pieces that are no more than half the original size. Because trees are so strictly organized, they are used to find medians in graphs and to create spanning trees, which are subgraphs that connect all vertices of a larger graph using the minimum number of edges.