Minimum spanning trees: cuts, cycles, Prim और Kruskal
Contract और संबंध
मौजूदा graph-representation, BFS/DFS और heap पाठ आधार हैं। यहाँ finite undirected weighted graph है, self-loops नहीं। Parallel edges अलग candidates हो सकते हैं। Connected graph का spanning tree सभी vertices जोड़ता है, cycle नहीं रखता, अतः V−1 edges। MST total edge weight minimum करता है, source से distances नहीं। Negative, zero और tied weights मान्य हैं।
1. Cut और safe edges
Cut vertices को nonempty S और V\S में बाँटता है। Opposite sides जोड़ने वाला edge crossing है। Partial forest F किसी MST में contained हो और उसका कोई edge cut cross न करे तो cut, F को respect करता है। Minimum crossing edge e safe है: कोई MST, F और e दोनों रख सकता है।
Proof: F वाला MST T लें। e नहीं हो तो उसे जोड़ें; एक cycle बनेगा। Endpoints के बीच path cut cross करेगा, अतः cycle में दूसरा crossing edge f है। Cut, F को respect करता है इसलिए f, F में नहीं। e lightest है, अतः w(e)<=w(f)। f हटाने पर spanning tree T से भारी नहीं, इसलिए MST ही है और F,e रखता है। Ties में अलग MST हो सकते हैं; हर lightest edge हर MST में जरूरी नहीं। Unique minimum crossing edge हर MST में आता है, क्योंकि उसे छोड़ने पर exchange strict improvement देता।
2. Cycle property और ties
Cycle का uniquely heaviest edge किसी MST में नहीं होता: उसे रखने वाले tree को वैकल्पिक edge से strict improve कर सकते हैं। कई edges maximum पर tied हों तो किसी चुने maximum को कुछ MST से बाहर रखा जा सकता है; सभी maximum edges को हर MST से बाहर कहना गलत। All-1 triangle में कोई दो edges MST, weight 2 हैं। Tied weights से multiple MST अनिवार्य नहीं: graph स्वयं tree हो तो एक ही spanning tree है, भले weights बराबर हों।
3. Kruskal forest बढ़ाता है
Edges nondecreasing weight में sort करें। शुरू में हर vertex अलग component। Edge (u,v) तभी accept करें जब endpoints अलग current components में हों, फिर union करें। DSU component tests करता है; यह directed reachability test नहीं। Accepted edges cycle नहीं बनाते। उचित component cut पर edge safe है, इसलिए forest MST में extend हो सकता है।
उदाहरण AB=1, BC=2, AC=3, CD=4, BD=5। AB,BC accept; AC triangle ABC बनाता है इसलिए reject; CD accept। Total 7; चार vertices के लिए तीन edges। Comparison sorting O(E log(E+1)); path compression और union by rank वाले DSU का initialization तथा operations O(V+E α(V)), जहाँ α inverse Ackermann function है। Disconnected graphs में isolated vertices के लिए V initialization term बचाएँ। Connected simple graphs पर सामान्य simplification O(E log V) है।
4. Prim एक tree बढ़ाता है
किसी r से शुरू करें। बाहर के vertex v के लिए key[v]=tree से जोड़ने वाला सबसे हल्का edge weight और parent रखें। key[r]=0, बाकी ∞। Minimum-key vertex निकालें, उसका parent edge हो तो लें, और बाहर के neighbors के लिए सस्ता connecting edge मिले तो update करें। यह current tree cut का minimum edge चुनता है। Dijkstra से अलग update w(u,v) है, cumulative distance नहीं।
उदाहरण में A से AB=1, फिर BC=2, फिर CD=4, total 7। Adjacency matrix तथा linear extract-min में O(V²); adjacency lists और indexed binary heap में O((V+E) log V), connected V>=2 में अक्सर O(E log V)। Representation स्पष्ट करें।
5. Disconnected graph और गलतियाँ
Disconnected graph में सभी vertices वाला spanning tree नहीं। Kruskal minimum spanning forest देता है। Prim एक root से केवल उसका component लेता है; remaining minimum key ∞ हो तो उस component को रोकें, फिर unvisited root का key 0 रखकर restart करें और forest पाएँ। c components पर V−c edges, isolated vertices भी components हैं। दोनों MST algorithms में negative weights मान्य। Dijkstra की nonnegative condition MST पर न लगाएँ। Shortest-path tree और minimum-total-weight tree अलग objectives हैं।
मौलिक अभ्यास: छह single-correct MCQ
ये मौलिक शिक्षण प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। ठीक एक उत्तर चुनें।
P01. 8 vertices के connected graph में spanning-tree edges?
A. 6 B. 7 C. 8 D. 28
उत्तर: B
A: सभी आठ tree में नहीं जुड़ेंगे।
B: V−1=7।
C: Connected में आठ cycle बनाएँगे।
D: 28 सभी possible simple edges हैं।
P02. Cut का unique minimum crossing edge कहाँ आता है?
A. किसी MST में नहीं B. हर MST में C. केवल positive-weight graphs में D. हर possible spanning tree में
उत्तर: B
A: Cut exchange inclusion देता है।
B: छोड़ने पर strict cheaper exchange है।
C: Negative weights proof नहीं तोड़ते।
D: Nonminimum spanning tree उसे छोड़ सकता है।
P03. All-1 triangle में हर MST कितने edges लेता है?
A. 0 B. 1 C. 2 D. 3
उत्तर: C
A: Vertices नहीं जुड़ेंगे।
B: एक vertex अलग बचेगा।
C: कोई दो बिना cycle सब जोड़ते हैं।
D: तीनों cycle हैं।
P04. AB=1,BC=2,AC=3,CD=4,BD=5 पर Kruskal MST weight:
A. 6 B. 7 C. 8 D. 15
उत्तर: B
A: तीन lightest cycle बनाते, D छूटता है।
B: AB+BC+CD=1+2+4=7।
C: भारी valid tree optimum नहीं।
D: यह सभी edges का sum है।
P05. Prim key[v] किससे update करता है?
A. key[u]+w(u,v) B. सस्ता connecting w(u,v) C. Visited vertices की संख्या D. केवल BFS level
उत्तर: B
A: यह cumulative-distance विचार है, Prim नहीं।
B: Key current tree से cheapest edge है।
C: Vertex count edge cost नहीं।
D: Weighted MST में edge weights चाहिए।
P06. V=9,c=3 components के spanning forest में edges?
A. 3 B. 6 C. 8 D. 9
उत्तर: B
A: यह component count है।
B: V−c=6।
C: V−1 केवल connected पर।
D: यहाँ forest में इतने edges नहीं।
स्रोत और दायरा
यह 2026 course के बताए भाग का पाठ है, पूरे Algorithms syllabus की समाप्ति नहीं। सभी गणनात्मक उदाहरण और प्रश्न मौलिक हैं। 2027 की पूर्णता का दावा नहीं।
प्रगति सहेजने के लिए साइन इन करें। साइन इन