Graph Theory & Trees - Visual Learning

🎯 What is a Graph? (Super Simple!)

Imagine you have some cities and roads connecting them. That's a graph!

🌍 Real Life Example - WhatsApp Groups

You and your friends are vertices (points)

When you message someone, that's an edge (connection)

The whole group chat is a graph!

Simple Graph Example: You | Friend1 ——— Friend2 | | Friend3 ——— Friend4 Points = Vertices = People Lines = Edges = Connections

🎓 Basic Terms (Yaad Karo!):

Vertex (V): Ek point/dot (jaise city on map)
Edge (E): Line connecting two points (jaise road between cities)
Degree: Kitne edges ek vertex se connected hain

💡 Example - Facebook Network

Alice ——— Bob | | Carol ——— David Alice's Degree = 2 (connected to Bob and Carol) Bob's Degree = 2 (connected to Alice and David) Total Vertices = 4 Total Edges = 4

🔄 Types of Graphs (With Examples)

1️⃣ Undirected Graph (Two-Way Connection)

Jaise Facebook friendship - agar tum kisi ke friend ho, toh wo bhi tumhara friend hai!

Undirected Graph: A ——— B | | C ——— D A to B = YES B to A = YES (Both ways!)

Real Example:

🤝 Facebook Friends

👫 Marriage

🏠 Neighbors

2️⃣ Directed Graph (One-Way Connection)

Jaise Instagram follow - tum kisi ko follow karo, zaroori nahi wo tumhe follow kare!

Directed Graph: A ——→ B ↑ ↓ C ←—— D A to B = YES B to A = NO (One way only!)

Real Example:

📱 Instagram Follow

🚦 One-way Streets

➡️ Twitter Follow

3️⃣ Weighted Graph (Roads with Distance)

Jab edges pe values likhi ho - jaise cities ke beech ki distance!

🗺️ Example - Cities with Distance (km)

Delhi / \ 5/ \8 / \ Mumbai———Kolkata 12 Delhi to Mumbai = 5 km Delhi to Kolkata = 8 km Mumbai to Kolkata = 12 km

Use: Google Maps shortest route find karne ke liye!

4️⃣ Isomorphic Graphs (Same but Different Looking)

Do graphs jo dikhte different hain but actually same hain!

💡 Think of it like: Ek kamre mein furniture rearrange karna - room same hai, sirf arrangement different hai!

Graph 1: A — B | | C — D

Graph 2: 1 — 2 \ / X / \ 4 — 3

Both are SAME! Just drawn differently 🎨

🛣️ Paths and Circuits (Simple Explanation)

What is a Path?

Ek route jo ek point se doosre point tak jaata hai WITHOUT repeating any point!

🚶 Example - Walking Route

Home → Park → School → Market Path = Home → Park → School → Market (No place visited twice!)

✅ Valid Path: A → B → C → D

❌ NOT Valid: A → B → A → C (A repeated!)

What is a Circuit/Cycle?

Ek path jo START aur END same point pe ho!

🔄 Example - Round Trip

A / \ B C \ / D Circuit: A → B → D → C → A (Started at A, Ended at A!)

Real Life: Ghar se nikle, ghumke wapas ghar aaye = Circuit! 🏠

Shortest Path (Finding Fastest Route)

🚗 Example - Which Road is Shorter?

Home / \ 5/ \10 / \ School — Office 8 Route 1: Home → School → Office = 5 + 8 = 13 km Route 2: Home → Office = 10 km ✅ SHORTEST!

🎯 Algorithm Used: Dijkstra's Algorithm

Google Maps isi se shortest route find karta hai! 📍

🌟 Special Paths (Eulerian & Hamiltonian)

Eulerian Path (Har Road Ek Baar)

Simple Matlab: Har ROAD/EDGE ko exactly ek baar use karo!

📮 Real Life - Postman Problem

Ek postman ko har street pe exactly ek baar jaana hai letters deliver karne ke liye!

A ——— B | | C ——— D Eulerian Path: A → B → D → C → A → (back to start) (Har edge ek baar use hua!)

📝 Rule: Graph mein 0 ya 2 odd-degree vertices hone chahiye

Hamiltonian Path (Har City Ek Baar)

Simple Matlab: Har VERTEX/POINT ko exactly ek baar visit karo!

🚚 Real Life - Delivery Guy Problem

Ek delivery guy ko har city mein exactly ek baar jaana hai!

A ——— B | × | C ——— D Hamiltonian Path: A → C → D → B (Har vertex ek baar visit hua!)

Eulerian

✅ Har EDGE ek baar

🛣️ Roads important hain

📮 Postman delivering letters

Hamiltonian

✅ Har VERTEX ek baar

🏙️ Cities important hain

🚚 Salesman visiting cities

Planar Graphs (Drawing Without Crossing)

Ek graph jo paper pe bina lines cross kiye draw ho sake!

✏️ Try Yourself!

Triangle (Planar): A / \ B—— C Can draw without crossing! ✅

Complete Graph K₅ (Not Planar): All 5 points connected to each other Cannot draw without crossing! ❌

🔢 Euler's Formula (Super Important!)

V - E + F = 2 V = Vertices (points) E = Edges (lines) F = Faces (regions including outside) Example Triangle: V = 3, E = 3, F = 2 3 - 3 + 2 = 2 ✓

Graph Coloring (Rangon Se Bharna)

Simple Matlab: Har vertex ko color do lekin jo connected hain unka color different hona chahiye!

🎨 Real Life - Exam Schedule

Different subjects ko different time slots dena jisme koi conflict na ho!

Math —— Science | | History — English Math = Red Science = Blue History = Blue (can be same as Science!) English = Red (can be same as Math!) Minimum Colors = 2 (Chromatic Number = 2)

🎯 Four Color Theorem: Koi bhi map ko maximum 4 colors se color kar sakte ho!

🌳 Trees (Super Simple Explanation)

What is a Tree?

Ek special graph jisme NO LOOPS hain! Bilkul family tree ki tarah!

👨‍👩‍👧‍👦 Real Life - Family Tree

Grandpa | Father / \ You Sister No loops/cycles! Everyone connected!

🎯 Tree Ki Properties:

✅ NO cycles (koi loop nahi)
✅ Sab connected (sab points reach ho sakte hain)
✅ N vertices = N-1 edges (ALWAYS!)
✅ Do points ke beech exactly EK path

Graph vs Tree (Difference Samjho!)

Feature	Graph	Tree
Cycles	✅ Ho sakte hain	❌ Bilkul nahi
Edges	Koi bhi number	N-1 (fixed!)
Root	Koi root nahi	Ek root hota hai
Paths	Multiple paths	Sirf ek path
Example	Social Network	Family Tree

Rooted Tree (Ek Boss Hota Hai!)

🏢 Real Life - Company Structure

📖 Important Terms:

Root: Top wala vertex (CEO)
Parent: Upar wala (Manager)
Child: Neeche wala (Employee)
Leaf: Jiske neeche koi nahi (Last employee)
Height: Root se leaf tak kitne levels

Spanning Tree (Sab Connect Karo Minimum Edges Se)

Simple Matlab: Graph ke sab vertices ko connect karo but minimum edges use karo!

🔌 Real Life - Computer Network

Sare computers connect karne hain minimum wires use karke!

Original: A—B—C | | | D—E—F (9 edges)

Spanning Tree: A—B—C | | D—E—F (5 edges only!)

🎯 Minimum Spanning Tree (MST) - Step by Step

Simple Matlab: Sab cities connect karo MINIMUM cost/distance mein!

💡 Real Problem:

4 cities hain. Har city ko electricity supply karni hai wires se.

Wires ki cost alag-alag hai. MINIMUM cost mein sab connect karo!

🗺️ Example Problem

Cities with Wire Costs: A /|\ 2/ | \4 / | \ B |3 C \ | / 5\ | /1 \|/ D Cost between cities: A-B = 2, A-D = 3, A-C = 4 B-D = 5, C-D = 1

Algorithm 1: Kruskal's Algorithm (Easy to Understand!)

1 Step 1: Sare edges ko cost ke order mein arrange karo (smallest pehle)

Sorted Edges: C-D = 1 ✅ A-B = 2 ✅ A-D = 3 ✅ A-C = 4 ❌ (creates cycle!) B-D = 5 ❌ (not needed)

2 Step 2: Smallest edge select karo (C-D = 1)

3 Step 3: Next smallest (A-B = 2), agar cycle na bane to add karo

4 Step 4: Continue until N-1 edges (4 cities = 3 edges)

✅ Final MST:

A /| 2/ |3 / | B D | |1 | C Total Cost = 1 + 2 + 3 = 6 (Minimum possible!)

Algorithm 2: Prim's Algorithm (Another Way)

1 Step 1: Kisi bhi vertex se start karo (A se start karte hain)

2 Step 2: A se connected minimum edge choose karo (A-B = 2)

3 Step 3: Ab A or B dono se minimum edge (A-D = 3)

4 Step 4: Continue until sab vertices included (D-C = 1)

Kruskal's

✅ Sort all edges first

✅ Pick smallest edges

✅ Avoid cycles

Prim's

✅ Start from one vertex

✅ Grow tree gradually

✅ Add closest vertex

🌲 Binary Trees & Traversals (Visual Guide)

What is Binary Tree?

Simple Rule: Har node ke maximum 2 children ho sakte hain - Left aur Right!

👨‍👩‍👧 Real Life - Family with Max 2 Kids

Grandpa (Root) / \ Father Uncle / \ / You Sis Cousin Each person has max 2 children!

Tree Traversals (Tree Ko Padhne Ke Tarike)

Tree ko 3 different ways mein read kar sakte hain!

🌳 Example Tree

10 / \ 5 15 / \ / 3 7 12

1️⃣ Inorder (Left-Root-Right)

📖 Order: Pehle LEFT child → Phir ROOT → Phir RIGHT child

Step by Step: 1. Go LEFT till end: 3 2. Print ROOT of that: 5 3. Go RIGHT: 7 4. Back to main ROOT: 10 5. Go LEFT of right side: 12 6. Print RIGHT root: 15 Result: 3, 5, 7, 10, 12, 15 (Numbers in SORTED order! ✅)

2️⃣ Preorder (Root-Left-Right)

📖 Order: Pehle ROOT → Phir LEFT → Phir RIGHT

Step by Step: 1. Print ROOT first: 10 2. Go LEFT and print: 5 3. Print LEFT of 5: 3 4. Print RIGHT of 5: 7 5. Back to main, go RIGHT: 15 6. Print LEFT of 15: 12 Result: 10, 5, 3, 7, 15, 12 (ROOT pehle aata hai! ✅)

3️⃣ Postorder (Left-Right-Root)

📖 Order: Pehle LEFT → Phir RIGHT → Last mein ROOT

Step by Step: 1. Go LEFT till end: 3 2. Then RIGHT of that: 7 3. Print ROOT last: 5 4. Right side LEFT: 12 5. Print RIGHT root: 15 6. Main ROOT last: 10 Result: 3, 7, 5, 12, 15, 10 (ROOT last mein aata hai! ✅)

🎯 Easy Trick to Remember:

Traversal	Root Position	Easy Remember
Inorder	Middle (IN middle)	L-Root-R
Preorder	First (PRE = before)	Root-L-R
Postorder	Last (POST = after)	L-R-Root

🎯 Where Used?

Inorder: Binary Search Tree mein sorted order chahiye

Preorder: Tree copy karna ho (root pehle chahiye)

Postorder: Tree delete karna ho (children pehle delete)

💡 Exam Tips & Quick Revision

🎯 Most Important Formulas (Yaad Karo!)

1. Tree: N vertices = N-1 edges 2. Euler's Formula: V - E + F = 2 3. Chromatic Number: Minimum colors needed 4. Degree Sum: Σ(degrees) = 2 × edges

⚡ Last Minute Revision (Quick Recap!)

📊 GRAPHS - 2 Minute Recap

✓ Graph = Vertices + Edges ✓ Undirected = Two way (Facebook friends) ✓ Directed = One way (Instagram follow) ✓ Weighted = Values on edges (distances) ✓ Isomorphic = Same structure, different look

🛣️ PATHS - 2 Minute Recap

✓ Path = Start to end (no repeat) ✓ Circuit = Starts & ends at same point ✓ Eulerian = Visit all EDGES once → Condition: 0 or 2 odd degree vertices ✓ Hamiltonian = Visit all VERTICES once ✓ Shortest Path = Dijkstra's Algorithm

🎨 SPECIAL TOPICS - 2 Minute Recap

✓ Planar = Draw without crossing edges ✓ Euler's Formula: V - E + F = 2 ✓ Graph Coloring = Adjacent vertices ≠ same color ✓ Chromatic Number = Minimum colors needed ✓ Four Color Theorem = Max 4 colors for maps

🌳 TREES - 2 Minute Recap

✓ Tree = No cycles, all connected ✓ N vertices = N-1 edges (ALWAYS!) ✓ Spanning Tree = All vertices, minimum edges ✓ MST = Spanning tree with minimum weight ✓ Kruskal = Sort edges, pick smallest ✓ Prim = Start vertex, grow tree

🌲 BINARY TREES - 2 Minute Recap

✓ Binary Tree = Max 2 children per node ✓ Inorder = Left → Root → Right (sorted) ✓ Preorder = Root → Left → Right (copy) ✓ Postorder = Left → Right → Root (delete) Memory Trick: IN = Root IN middle PRE = Root BEFORE (first) POST = Root AFTER (last)

🔥 Day Before Exam - Quick Practice

1. Draw: Ek graph banao aur uska spanning tree nikalo (5 min)

2. Calculate: MST nikalo Kruskal se (5 min)

3. Traverse: Ek binary tree ka teeno traversal likho (5 min)

4. Check: Euler's formula verify karo kisi planar graph pe (3 min)

Total Time: Just 18 minutes! 💪

🎓 Pro Tips from Toppers

🎨 Colorful Diagrams: Exams mein colors use karo - examiner ko dikhta hai!
📝 Clear Steps: Algorithms mein numbered steps likho
🔢 Show Calculations: MST mein total cost clearly likho
✨ Examples De Do: Definitions ke saath ek chhota example add karo
⚡ Time Management: Easy questions pehle solve karo