Unit 3 – Introduction to Trees | Discrete Mathematics SPPU

Introduction to Trees and Their Properties

In Discrete Mathematics and Graph Theory, a tree is a highly structured, hierarchical data model. Unlike physical trees that grow upwards from the ground, data structure trees grow downwards from a single starting point. Mathematically, a tree is defined as a connected, undirected, and acyclic graph.

To break this definition down:

• Connected: There is a continuous path between any two points (nodes) in the structure. There are no disconnected or isolated parts.

• Undirected: The connections (edges) between the points do not have strict one-way directions in the fundamental graph theory definition (though in computer science, we often traverse them top-down).

• Acyclic: There are no closed loops or cycles. You cannot start at one point, travel through a sequence of connections, and return to the same starting point without retracing your steps.

Hinglish Explanation: Graph theory mein "Tree" ek aisa network ya structure hai jisme sabhi points ek dusre se jude hote hain (connected), par koi bhi closed loop ya chakkr (acyclic) nahi banta. Agar aap ek point se chalna shuru karein, toh ghoom kar wapas usi point par aane ka koi rasta nahi hota bina piche mude.

Essential Terminologies of a Tree

To understand tree structures, one must be familiar with the following basic terms:

1. Node (or Vertex): The fundamental unit of a tree that contains data or information.

2. Edge: The connecting link between two nodes.

3. Root: The topmost node of the tree. It is the only node that does not have a parent.

4. Leaf (or Terminal Node): A node at the very bottom of the tree that has no children.

5. Internal Node: Any node that has at least one child.

6. Parent and Child: If an edge connects node A downwards to node B, A is the parent, and B is the child.

7. Depth: The depth of a node is the number of edges from the root to that specific node.

8. Height: The height of a tree is the total number of edges on the longest path from the root to the furthest leaf.

Fundamental Properties of Trees

Any graph that is classified as a tree must satisfy specific mathematical properties:

• Edge Count: A tree with n vertices (nodes) will always have exactly n - 1 edges. If you have 10 nodes, you will have exactly 9 connecting edges.

• Unique Paths: There is one, and only one, unique path between any pair of nodes in a tree.

• Cycle Creation: Adding even a single new edge between any two existing nodes in a tree will instantly create a cycle, meaning it will no longer be a tree.

• Disconnection: Removing even a single edge from a tree will divide it into two disconnected components (this is known as creating a "forest").

Decision Trees

A decision tree is a specific type of tree used to model a sequence of decisions and their possible outcomes. It is a visual and analytical tool where each internal node represents a "test" or a "condition" on an attribute, each branch represents the outcome of that test, and each leaf node represents a final decision, classification, or result.

Working Mechanism of a Decision Tree

Imagine you are deciding whether to play tennis outside. The decision tree would look like this:

1. Root Node (Condition): Is it raining?

2. Branches (Outcomes): Yes / No.

3. Next Internal Node (If Yes): Is the wind strong?

4. Leaf Node (Final Decision): If the wind is strong, the leaf says "Do not play." If the wind is weak, the leaf says "Play."

Decision trees are highly intuitive because they mimic human decision-making logic.

Decision Trees and their Applications in Machine Learning

In the field of Artificial Intelligence and Machine Learning, Decision Trees are powerful predictive modeling algorithms. They belong to the category of Supervised Learning and are primarily used for Classification (predicting categories, like "Spam" or "Not Spam") and Regression (predicting numerical values, like house prices).

How Machine Learning Uses Decision Trees

When a machine learning algorithm builds a decision tree from a dataset, it does not do it randomly. It uses complex mathematical metrics to decide which attribute should be the root node and how to split the data at every subsequent node.

The two most common metrics used are:

1. Entropy: A mathematical measure of randomness, impurity, or uncertainty in a dataset. A dataset with 50% spam emails and 50% normal emails has high entropy (high confusion). A dataset with 100% normal emails has zero entropy (pure). The goal of a decision tree is to reduce entropy.

2. Information Gain: This measures how much the entropy is reduced when the data is split using a specific attribute. The algorithm calculates the Information Gain for every possible condition and chooses the one that gives the highest gain (the most clarity) to form the next node.

Hinglish Explanation: Machine learning mein Decision Tree ek flowchart ki tarah kaam karta hai. Data ko dekh kar algorithm khud decide karta hai ki kaunsa question sabse pehle poochna chahiye jisse data jaldi se sahi category (jaise Spam ya Normal) mein divide ho jaye. Is logic ko mathematically calculate karne ke liye hum Entropy (confusion) aur Information Gain (clarity) ka use karte hain.

Advantages of Decision Trees in Machine Learning

• Interpretability: They are transparent. A human can trace the branches and understand exactly why the algorithm made a specific prediction.

• Minimal Data Preparation: Unlike other algorithms, decision trees do not require heavy data normalization or scaling. They can handle both categorical (text) and numerical data effortlessly.

Prefix Codes and Huffman Coding

What are Prefix Codes?

When transmitting data over a network, characters (like A, B, C) are converted into binary codes (0s and 1s). A major problem in data transmission is decoding a continuous stream of binary data without confusion.

A Prefix Code (also known as a prefix-free code) is a coding system where the code assigned to one character is never the prefix (the starting sequence) of the code assigned to another character.

For example, if the letter 'A' is assigned the code 0, no other letter can have a code that starts with 0 (like 01 or 011). This ensures that when the computer reads the binary stream, it knows exactly where one character ends and the next begins, completely avoiding ambiguity.

Huffman Coding

Huffman Coding is a highly famous and efficient algorithm used for lossless data compression. It was developed by David A. Huffman.

Traditional encoding (like ASCII) assigns a fixed length of bits (usually 8 bits) to every character, regardless of how often that character appears in a file. Huffman coding changes this by using variable-length prefix codes.

• Characters that appear very frequently (like the letter 'E' in English) are assigned very short binary codes.

• Characters that appear rarely (like the letter 'Z') are assigned longer binary codes.

This drastically reduces the overall size of the file.

Step-by-Step Huffman Coding Algorithm

1. Calculate Frequencies: Count how many times each character appears in the data.

2. Sort: Arrange the characters in ascending order based on their frequencies.

3. Build the Tree (Bottom-Up):

   • Take the two characters with the lowest frequencies.

   • Combine them to create a new internal node (a parent). The frequency of this parent node is the sum of the frequencies of the two children.

   • Place this new node back into the sorted list and remove the two children from the list.

   • Repeat this process until only one single node remains. This final node becomes the Root of the Huffman Tree.

4. Assign Codes: Traverse the tree from the root to the leaves. Assign a 0 to every left branch and a 1 to every right branch. The path from the root to a character leaf generates its unique prefix code.

Hinglish Explanation: Huffman coding data compress (size chhota) karne ka ek smart tareeka hai. Jo letters text mein sabse zyada baar aate hain, unko sabse chhote binary codes diye jaate hain, aur jo kam aate hain unko bade codes. Tree ke left side jane par '0' aur right side jane par '1' likha jata hai, jisse har letter ka ek unique code ban jata hai jise computer bina confusion ke read kar sakta hai.

Applications of Trees in File Systems

One of the most universal applications of tree data structures is the File System inside every computer Operating System (Windows, macOS, Linux).

Hierarchical Structure

Operating systems organize data hierarchically.

• Root Directory: At the very top of the hierarchy is the Root Directory (represented as C:\ in Windows or / in Linux). This is the root node of the tree.

• Sub-directories (Folders): Inside the root, you create folders. These folders can contain more folders. These act as the internal nodes of the tree.

• Files: The actual files (like a .txt or .jpg file) cannot contain other files or folders. Therefore, files act as the leaf nodes of the tree.

Important Note on Pathnames

Because a tree guarantees a unique path between the root and any node, file systems use this property to create file paths.

• Absolute Path: Traces the exact route from the root node to the file. Example: C:\Users\Admin\Documents\report.pdf.

• Relative Path: Traces the route starting from the current directory (internal node) you are working in.

By using a tree structure, operating systems can search for, organize, and manage millions of files efficiently without scanning the entire hard drive sequentially.

Cut Sets in Graph Theory

In graph theory and network analysis, it is crucial to understand the vulnerabilities of a network. This introduces the concept of a Cut Set.

Definition of a Cut Set

In a connected graph, a Cut Set is a specific set of edges that, if completely removed from the graph, will disconnect the graph into exactly two separate components.

However, a Cut Set must satisfy a strict condition called the Minimal Property:

• If you remove the entire cut set, the graph disconnects.

• But, if you put back even one single edge from that cut set into the graph, the graph will reconnect.

This means a cut set contains only the absolute minimum number of edges required to cause a disconnection. It contains no extra, unnecessary edges.

Importance of Cut Sets

Cut sets are fundamentally used to analyze network reliability. In a computer network or a power grid, engineers need to identify the cut sets to understand the weakest points of the network. If the edges in a cut set fail (like cables breaking), the entire network gets divided, and communication stops.

Hinglish Explanation: Cut set un edges (taaro ya raasto) ka ek group hai jinko agar hum system se nikal de, toh poora network do alag-alag hisso mein toot jayega. Par isme ek shart hai: ye strictly utni hi edges ka group hona chahiye jinki wajah se network toot raha hai. Agar hum us group me se ek bhi edge wapas laga de, toh network wapas jud jana chahiye.

The Max Flow - Min Cut Theorem in Transport Networks

This theorem is one of the most important concepts in optimization, operations research, and network theory. To understand it, we must first define a transport network.

What is a Transport Network?

A transport network is a directed graph where edges represent pipes, roads, or communication links. It has three main components:

1. Source Node (S): The starting point where the material (water, data, traffic) originates.

2. Sink Node (T): The final destination where the material is collected.

3. Capacity (C): Every edge has a maximum capacity. For example, a water pipe can only carry a maximum of 50 liters per minute. It cannot exceed this capacity constraint.

Flow Conservation Rule: For every internal node (nodes other than the Source and Sink), the amount of material entering the node must be exactly equal to the amount of material leaving the node. Nodes cannot store or consume material.

Max Flow and Min Cut

• Max Flow: The maximum possible amount of material that can be successfully transported from the Source to the Sink without violating any edge capacities.

• Min Cut: Imagine trying to sabotage this network by cutting pipes to stop the flow completely. A "cut" separates the Source from the Sink. Every cut has a "Capacity", which is the sum of the capacities of the edges you cut. The Min Cut is the cut that has the smallest possible capacity in the entire network.

The Theorem Statement

The Max Flow - Min Cut Theorem states mathematically that:

The Maximum Flow from the Source to the Sink is exactly equal to the Capacity of the Minimum Cut of the network.

Real-Life Analogy

Imagine a highway system connecting City A (Source) to City B (Sink). There are multiple routes, consisting of 4-lane highways, 2-lane roads, and single-lane bridges.

No matter how wide the highways are at the beginning, the total amount of traffic that can reach City B is strictly limited by the narrowest combination of roads (the bottlenecks) that divide the two cities. The total capacity of these worst bottlenecks represents the Min Cut. The maximum traffic that can flow through the system (the Max Flow) will exactly equal the capacity of this bottleneck.

Hinglish Explanation: Max Flow Min Cut theorem ka logic bohot simple hai. Agar aap paani ki pipes ka ek network banate hain, toh paani ka maximum flow utna hi ho sakta hai jitni network ki sabse patli pipe (bottleneck) allow karegi. Aap piche se kitna bhi paani chhod de, system ki limit uske sabse weak point (Min Cut) par nirbhar karti hai. Isiliye Max Flow humesha Min Cut ke barabar hota hai.

Comparison Table: Trees vs. General Graphs

To clarify the concepts further, here is a quick comparison between a Tree and a standard Graph:

Summary and Key Takeaways

• A Tree is a connected, undirected, acyclic graph where n nodes are connected by n - 1 edges.

• Decision Trees map conditions to outcomes and are extensively used in Machine Learning for classification tasks based on Entropy and Information Gain.

• Prefix Codes ensure that no binary code is the start of another, preventing data translation errors.

• Huffman Coding utilizes binary trees to assign variable-length prefix codes based on character frequency, achieving excellent data compression.

• Operating systems use trees to build File System hierarchies, relying on unique paths (Absolute and Relative) for fast data retrieval.

• A Cut Set is the minimal set of edges required to disconnect a graph into two components.

• The Max Flow - Min Cut Theorem proves that the maximum throughput of a transport network is determined entirely by its most restrictive bottleneck (the minimum cut).

SEO Keywords Section

Search keywords related to this topic:

Discrete Mathematics Trees and Properties, Graph Theory tree definition, Decision Trees in Machine Learning, Entropy and Information Gain simple explanation, Prefix codes and Huffman coding algorithm step by step, Data compression using Huffman tree, Applications of Trees in File Systems, Absolute and relative path in OS, Cut sets in graph theory minimal property, Transport network source and sink, Max flow min cut theorem explained, Max flow min cut theorem real life example, Bottleneck in transport networks, Computer Engineering discrete math notes, Tree terminologies root node leaf edge.