Unit IV: Trees
Course: Discrete Mathematics
Code: CADSC102
Basic Concepts of Tree
In discrete mathematics, a tree is a connected graph that contains no circuits (cycles). It is one of the most important structures used to represent hierarchical relationships.
[Image of a basic tree graph structure]
- Connectedness: There is a path between every pair of vertices.
- Acyclic: There are no loops or closed paths in the structure.
Properties of Trees
Trees have several mathematical properties that distinguish them from other types of graphs:
- Edge-Vertex Relationship: A tree with n vertices always has exactly n - 1 edges.
- Unique Path: There is exactly one unique path between any two vertices in a tree.
- Minimally Connected: Removing any edge from a tree results in a disconnected graph (it becomes a "forest").
Pendant Vertices and Centre of a Tree
Special vertices in a tree help define its structure and shape.
Pendant Vertices
A pendant vertex (also known as a leaf) is a vertex of degree 1. Every tree with more than one vertex has at least two pendant vertices.
Centre of a Tree
The centre of a tree consists of one or two vertices that have the minimum maximum distance to all other vertices in the tree. This is found by repeatedly removing all pendant vertices until only one or two remain.
Rooted Binary Trees
A rooted tree is a tree in which one specific vertex is designated as the root.
Rooted Binary Tree
A binary tree is a rooted tree where every internal vertex has at most two children. Each child is typically designated as either a "left child" or a "right child".
Complete and Extended Binary Trees
Depending on how the nodes are filled, binary trees are categorized into specific types:
- Complete Binary Tree: A binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
- Extended Binary Tree: Also known as a 2-tree, it is a binary tree where every node has either zero or two children. Empty spots are often represented by special "external nodes".
Exam Focus & Tips
- Exam Tip: Remember the formula Edges = V - 1. If a question asks for edges in a tree with 15 vertices, the answer is 14.
- Common Mistake: Confusing a general tree with a binary tree. A general tree can have any number of children per node, whereas a binary tree is limited to two.
- Mnemonic: "No Cycles, No Problems" - A tree must never have a loop.
Frequently Asked Questions
Q: What is a pendant vertex?
A: A vertex with a degree of 1, effectively a "leaf" of the tree.
Q: How many roots does a rooted tree have?
A: Exactly one.