3.5.1
Intuition 30-second pictureEk graph bas dots connected by lines hota hai. Dots ko vertices (ya nodes ) kehte hain, lines ko edges . Baaki sab — direction, weight, "simple vs multi" — sirf yeh rules hain ki woh lines kya kar sakti hain . Pehle dots-and-lines wala mental model pakad lo; vocabulary toh bas variations ko label karti hai.
Ek graph ek pair G = ( V , E )
V vertices (nodes) ka ek set hai.E edges ka ek set hai, jahan har edge vertices ki ek pair ko connect karti hai.
Hum usually n = ∣ V ∣ m = ∣ E ∣
YEH abstraction KYO? Kyunki relationships har jagah hain: social network pe dost, roads se jude sheher, hyperlinks se jude web pages, aur tasks jo doosre tasks pe depend karte hain. Ek graph specifics hata deta hai aur sirf "kaun kis se connected hai" rakhta hai — toh ek hi set of algorithms (BFS, Dijkstra, ...) hazaaron alag-alag real problems solve kar deta hai.
Ek graph type ko char on/off switches ki tarah socho. Yeh independent hain — inhe freely mix kar sakte ho (jaise ek directed weighted multigraph).
Definition Directed / Undirected
Undirected edge : ek unordered pair { u , v } dono taraf jaata hai. Agar u v v u Directed edge (ek arc ): ek ordered pair ( u , v ) sirf u v point karta hai. ( u , v ) ( v , u )
YEH KYO maayane rakhta hai: Facebook friendship mutual hoti hai → undirected. Twitter "follow" ek-taraf hota hai → directed. Ek directed graph pe aap A → B B → A nahin bhi ho sakta.
Intuition Direction = arrowsUndirected = plain line —. Directed = arrow →. Woh akela arrowhead change kar deta hai ki kaunse algorithms use karne padenge (jaise topological sort sirf directed graphs ke liye exist karta hai).
Definition Weighted / Unweighted
Unweighted : har edge identical hoti hai; edge ya toh exist karti hai ya nahin.Weighted : har edge ek number w ( u , v ) weight (cost, distance, time, capacity...).
KYO: "Mere dost tak kitne hops?" weight ignore karta hai (unweighted, BFS). "Sabse sasta flight route?" weight chahiye (Dijkstra). Ek unweighted graph ko weighted treat karna theek hai — bas har weight = 1
Ek self-loop ek vertex se khud apne aap tak jaane wali edge hoti hai: ( v , v )
Definition Simple graph vs Multigraph
Ek simple graph mein no self-loops aur no parallel edges hote hain. Kisi bhi do vertices ke beech zyada se zyada ek edge hoti hai.
Ek multigraph parallel edges (aur usually self-loops) allow karta hai .
Multigraph KYO? Do sheher ke beech genuinely do alag roads ho sakti hain, har ek ki apni length ke saath. Ek simple graph tumhe sirf ek rakhne par majboor karega — information kho jaayegi.
Scratch se derive karo — KYO:
Ek edge distinct vertices ka ek unordered pair hoti hai (no self-loops → distinct; simple → zyada se zyada ek).
Toh max edges count karna = n 2 vertices choose karne ke tarike count karna.
Pehli vertex pick karne ke tarike: n n − 1 n ( n − 1 )
Lekin { u , v } { v , u } same undirected edge hain → hum double-count kar rahe the. 2 se divide karo.
Result: 2 n ( n − 1 )
KYO: ab ( u , v ) = ( v , u ) divide nahin karte. n n − 1 n ( n − 1 )
Ek vertex ka degree deg ( v ) + 2 in-degree = andar aane wale arrows, out-degree = bahar jaane wale arrows.
Derive karo — KYO: jab tum sabhi vertices ke degrees add karte ho, har edge { u , v } — ek baar u v
Worked example Example 1 — Graph classify karoV = { A , B , C } A − B B − C A − B
Undirected? Haan (lines, koi arrows nahin). Kyo? Koi ordered pairs nahin diye gaye.
Simple? Nahin — A − B multigraph . Yeh step kyo: "simple" duplicates forbid karta hai.
m = 3 ∑ deg = 2 ( 3 ) = 6 deg ( A ) = 2 , deg ( B ) = 3 , deg ( C ) = 1 ⇒ 6
Worked example Example 3 — Weighted directed (real)Flights: ( N Y C → L O N , ... ) ,
Directed: haan, dono arcs ke alag costs hain. Kyo: ek direction book karna ≠ doosra.
Weighted: haan, weight = price. Yahan shortest-path = sabse sasta trip → Dijkstra (non-negative weights).
Common mistake Steel-man: "Ek undirected edge do directed edges ke barabar hai."Kyo sahi lagta hai: "dono taraf" sunne mein do one-way arrows lagte hain, aur indeed tum undirected { u , v } ( u , v ) aur ( v , u ) model kar sakte ho.
Fix / subtlety: modelling trick kaam karta hai, lekin conceptually yeh alag objects hain, aur edge count alag hota hai : ek undirected edge do directed arcs ban jaati hai. Toh m m 2 m
Common mistake Steel-man: "Simple graph matlab easy / kam edges wala."Kyo sahi lagta hai: "simple" sunne mein "chhota" lagta hai. Fix: simple ek structural rule hai (no self-loops, no parallel edges), size ka claim nahin. Ek simple graph mein phir bhi 2 n ( n − 1 ) complete graph K n
Common mistake Steel-man: "Unweighted graphs shortest-path algorithms use nahin kar sakte."Kyo sahi lagta hai: Dijkstra weights ke saath padhaaya jaata hai. Fix: ek unweighted graph bas ek weighted graph hai jisme sabhi weights = 1 BFS wahan shortest paths dhundhta hai — aur Dijkstra se fast hai kyunki har edge ka cost same hai.
Recall Feynman: ek 12-saal ke bachche ko samjhaoSocho dots tumhare dost hain, aur jab bhi do log ek doosre ko jaante hain tum ek line kheenchte ho. Woh poori drawing ek graph hai.
Agar "jaanna" dono taraf jaata hai (dosti), ek plain line kheeencho — undirected .
Agar yeh ek-taraf hai ("main usse follow karti hoon, woh mujhe nahin"), ek arrow kheeencho — directed .
Agar kuch dostiyaan zyada mazboot hain, line pe ek number likho — weighted .
Simple matlab: koi dost khud apna dost nahin (no self-loop), aur tum kabhi ek hi pair ke beech do lines nahin kheenchte. Agar tum do lines kheenchte ho (shayad do sheher ke beech do alag roads), toh yeh multigraph hai.
Bas itna hai — "graph theory" ka baaki hissa sirf inhi lines pe chal ke chalne ke clever tarike hain.
Mnemonic 4 switches yaad karo:"DWSP" → D irection (arrow?), W eight (number?), S elf-loop (allowed?), P arallel edges (allowed?). Aakhiri do milke decide karte hain Simple vs Multi .
Aur max edges ke liye: undirected 2 se divide karta hai ("ek handshake ke liye do log chahiye lekin yeh ek handshake hai").
What two sets define a graph G = ( V , E ) V E
Difference between a directed and an undirected edge? Directed = ordered pair ( u , v ) { u , v }
What is a weighted graph? Ek graph jahan har edge ek number carry karti hai (cost/distance/time); unweighted mein sabhi edges equal hoti hain (weight 1).
Define a self-loop. Ek vertex se khud apne aap tak jaane wali edge, ( v , v )
What are parallel edges? Do ya zyada edges jo same pair of vertices ko connect karti hain.
Define a simple graph. Ek graph jisme no self-loops aur no parallel edges hain (kisi bhi pair ke beech ≤ 1 edge).
Define a multigraph. Ek graph jo parallel edges (aur usually self-loops) allow karta hai.
Max edges in a simple undirected graph on n ( 2 n ) = 2 n ( n − 1 )
Why divide by 2 for undirected max edges? Kyunki { u , v } = { v , u } n ( n − 1 )
Max edges in a simple directed graph (no self-loops)? n ( n − 1 ) ( u , v ) = ( v , u )
State the Handshaking Lemma. ∑ v deg ( v ) = 2 m
Corollary of the handshake lemma about odd degrees? Odd degree wale vertices ki sankhya hamesha even hoti hai.
How do you model one undirected edge with directed edges? Do arcs ( u , v ) ( v , u )
What is K n Complete graph: ek simple graph jahan vertices ka har pair connected hota hai; iske 2 n ( n − 1 )
For directed graphs, what replaces degree? In-degree (incoming arcs) aur out-degree (outgoing arcs).
Graph representations — adjacency list vs matrix (yeh definitions store kaise hoti hain)BFS — breadth first search (unweighted graphs pe shortest path)Dijkstra's algorithm (weighted , non-negative graphs pe shortest path)Topological sort (sirf directed acyclic graphs pe)Complete graph $K_n$ and dense vs sparse graphs Handshaking lemma and degree sequences Trees as special graphs (connected, acyclic, m = n − 1
arc is ordered pair enables
n = size of V and m = size of E
Four independent switches
