Graph connectivity: components और cuts
उद्देश्य, पूर्वज्ञान और प्रचलन
Connected components, bridges, articulation vertices, trees और spanning forests पर तर्क करना; directed graphs में weak तथा strong connectivity अलग करना; और छोटे edge/vertex cuts समझना सीखें। केवल degree से connectivity का निर्णय न करें। पूर्वज्ञान: graph terms, adjacency representations, सामान्य sets और counting। मौजूदा BFS/DFS पाठ traversal की विधि सिखाते हैं; यहाँ वही code traces दोहराने के बजाय structural तर्क हैं।
किसी section में directed न कहा हो तो graphs finite, simple और undirected हैं: loops या parallel edges नहीं। Vertices और edges labeled हैं। किसी vertex से स्वयं तक length-0 path स्वीकारते हैं और एक-vertex graph को connected मानते हैं। Practice में empty-graph conventions नहीं चाहिए। Component एक maximal connected vertex set है, graph का सबसे लंबा path नहीं।
1. Reachability से vertices का partition
Undirected graph connected है यदि हर pair of vertices के बीच path हो। Reachability reflexive है (length-0 path), symmetric है (path उलटें) और transitive है (walks जोड़कर दोहराए हिस्से हटाने से path मिलता है)। इसकी equivalence classes connected components हैं।
Isolated vertex, size-1 component बनाता है। अलग components के बीच कोई edge नहीं; edge होता तो उसके endpoints और components जुड़े होते। Graph में c components हों तो दो अलग components के बीच edge जोड़ने से count ठीक 1 घटता है। एक ही component के भीतर edge जोड़ने से count नहीं घटता।
इसलिए graph को connected बनाने के लिए कम-से-कम c−1 नई edges चाहिए और c−1 पर्याप्त हैं: हर component से एक representative चुनकर उन्हें tree की तरह जोड़ें। यह components के बीच उपलब्ध नई edges के बारे में है, यह दावा नहीं कि कोई भी c−1 edges जोड़ना काम करेगा। केवल अंदर की edges जोड़ते रहने से graph disconnected रह सकता है।
2. Bridges महत्वपूर्ण edges हैं
Bridge ऐसी edge है जिसे हटाने पर, सभी vertices रखते हुए, connected components की संख्या बढ़े। एक bridge हटाने से count ठीक 1 बढ़ता है। एक edge हटाने से उसका पुराना component दो से अधिक टुकड़ों में नहीं टूट सकता: उस edge से गुजरने वाला पुराना path एक endpoint तक और दूसरे endpoint से आगे के paths में बाँटा जा सकता है।
Edge तभी bridge है जब वह किसी cycle पर न हो। Cycle पर हो तो बाकी cycle उसके endpoints के बीच दूसरा रास्ता देती है; edge हटाने से उनका connection नहीं टूटता। उलटे, edge हटाने पर भी endpoints जुड़े रहें तो alternate simple path और हटाई edge मिलकर cycle बनाते हैं।
यह graph का गुण है, चित्र का नहीं। लंबी दिखने वाली line जरूरी नहीं bridge हो। चित्र में lines का crossing, जब तक बताया न जाए, vertex नहीं है। हर vertex की degree कम-से-कम 2 होने पर भी graph में bridge हो सकता है।
3. हल किया graph: एक edge से जुड़े दो triangles
V={a,b,c,d,e,f} और E={ab,bc,ca,cd,de,ef,fd} लें। ab,bc,ca एक triangle और de,ef,fd दूसरा triangle हैं। केवल cd दोनों को जोड़ती है।
Graph connected है; n=6 vertices,m=7 edges। केवल cd bridge है। हर दूसरी edge किसी triangle पर है, इसलिए उसे हटाने पर alternate route बचती है। cd हटाने पर components {a,b,c} और {d,e,f} मिलते हैं।
Articulation या cut vertex ऐसा vertex है जिसे उसकी सभी incident edges सहित हटाने पर component count बढ़े। यहाँ c,d articulation vertices हैं। c हटाने से {a,b} और {d,e,f}; d हटाने से {a,b,c} और {e,f} components मिलते हैं। a हटाने पर graph connected रहता है, क्योंकि b अभी c से जुड़ा है। बाकी non-cut vertices के लिए भी वैसा तर्क करें।
Degrees 2,2,3,3,2,2 हैं, इसलिए minimum degree δ=2। फिर भी एक edge या एक vertex हटाकर graph disconnect कर सकते हैं। Minimum degree 2 से हर single-edge या single-vertex failure को सहने की गारंटी नहीं मिलती।
4. Edge और vertex हटाने की जाँच अलग है
Bridge जाँचते समय सभी vertices रखें और केवल edge हटाएँ। Articulation vertex जाँचते समय vertex तथा उससे जुड़ी हर edge हटाकर components दोबारा गिनें। बड़ी degree अपने आप articulation सिद्ध नहीं करती; path में degree-2 vertex भी articulation हो सकता है।
Path 1−2−3−4 में हर edge bridge है, लेकिन केवल 2,3 articulation vertices हैं। Leaf 1 हटाने पर connected path 2−3−4 बचता है; component count 1 ही रहता है। एक edge वाले दो-vertex graph में edge bridge है, लेकिन कोई vertex articulation नहीं: किसी को हटाने पर एक connected vertex बचता है।
Disconnected graph में भी deletion से पहले और बाद के component counts compare करके परिभाषाएँ लागू होती हैं। किसी component का vertex उसे बाँटे तो articulation हो सकता है। Isolated vertex हटाने से component count घटता है, इसलिए इस परिभाषा में वह articulation नहीं।
5. Tree की कई समतुल्य पहचानें
Tree connected और cycle-विहीन graph है। n≥1 वाले simple undirected graph के लिए ये tree की समतुल्य पहचानें हैं:
- Connected हो और ठीक n−1 edges हों।
- Acyclic हो और ठीक n−1 edges हों।
- अलग vertices के हर pair के बीच ठीक एक simple path हो।
Tree connected है, इसलिए हर pair का path है। दो अलग simple paths हों तो जहाँ वे अलग होकर फिर मिलें, वहाँ cycle बनेगी, जो acyclicity के विरुद्ध है। उलटे, cycle पर दो vertices के बीच दो अलग simple paths मिलते हैं। इससे unique-path की पहचान सिद्ध होती है।
Finite tree में n−1 edges होती हैं। Leaf और उसकी incident edge बार-बार हटाकर एक vertex तक पहुँचने से यह दिखा सकते हैं। Connected graph का spanning tree होता है: cycle की edge हटाकर connectivity बनाए रखें, जब तक cycles न बचें। इसलिए connected graph में कम-से-कम n−1 edges हैं। Connected graph में पहले से ठीक n−1 edges हों तो उस tree के बाहर अतिरिक्त edge नहीं; graph स्वयं tree है।
केवल ठीक n−1 edges से tree सिद्ध नहीं। Triangle और isolated vertex में n=4,m=3=n−1, लेकिन graph disconnected और cyclic है। साथ की connectedness या acyclicity की शर्त जरूर पढ़ें।
6. Forests, component count और अतिरिक्त edges
Forest acyclic graph है, जो disconnected भी हो सकता है। उसमें n vertices और c components हों तो हर component tree है। इसलिए कुल edges Σ(nᵢ−1)=n−c। Isolated vertices भी इसमें आते हैं: एक vertex और zero edges का योगदान।
सामान्य undirected graph में n vertices,m edges,c components हों तो spanning forest में n−c edges होती हैं: हर component का एक spanning tree। इसलिए m≥n−c; equality तभी जब graph पहले से forest हो। चुने spanning forest के बाहर edges की संख्या m−n+c है।
हर extra edge, अपने endpoints के unique forest path के साथ एक fundamental cycle बनाती है। m−n+c cycle-space dimension है, सभी simple cycles की कुल संख्या नहीं। Cycles overlap करके combine हो सकती हैं। दो-triangle graph में m−n+c=7−6+1=2। हर triangle की एक edge हटाने पर 5-edge spanning tree बनता है; bridge cd हर spanning tree में रहनी होगी।
c components वाले पूरे vertex set का spanning tree बनाने से पहले components जोड़ने होंगे। Disconnected graph के भीतर spanning forest मौजूद है, लेकिन उसी पूरे disconnected graph का spanning tree नहीं।
7. छोटे cuts और connectivity parameters
Edge cut, edges का ऐसा set है जिसे हटाने पर connected graph disconnect हो। कम-से-कम दो vertices वाले connected graph की edge connectivity λ, ऐसे set का न्यूनतम आकार है। Bridge हो तो λ=1। Bridges न होने पर भी दो edges हटाने से graph disconnect हो सकता है।
Vertex connectivity κ, vertices की न्यूनतम संख्या है जिन्हें हटाने पर बचा graph disconnect हो जाए या केवल एक vertex बच जाए। Single-vertex विकल्प complete graphs संभालता है; इस convention में n≥2 पर κ(Kₙ)=n−1। उन्हीं graphs में λ(Kₙ)=n−1। Complete graphs पर formulas से पहले ये conventions स्पष्ट करें।
Cycle C₄ में λ=2: एक edge हटाने पर connected path बचता है; दो उचित edges हटाने पर disconnect होता है। κ=2 भी: एक vertex हटाने पर connected path, जबकि दो opposite vertices हटाने पर दो isolated vertices बचते हैं। दो-triangle graph में λ और κ दोनों 1 हैं, जबकि δ=2। Exact minimum cut size के लिए उतने आकार का cut दें और बताएँ कि उससे छोटा हर deletion disconnect क्यों नहीं करता। केवल एक cut देना upper bound ही देता है।
8. Directed graphs: weak और strong अलग
Directed graph में path को edge directions माननी होती हैं। Strong connectivity में हर vertex हर दूसरे तक directed path से पहुँचता है। Weak connectivity में directions हटाकर बना undirected graph connected होता है। Strong से weak मिलता है, लेकिन उलटी दिशा जरूरी नहीं।
a→b और b→c वाले graph में weak connectivity है, strong नहीं: c से a नहीं पहुँच सकते। Strongly connected components या SCCs हैं {a},{b},{c}। a→b,b→c,c→a हों तो तीनों एक SCC में हैं।
SCC, mutually reachable vertices का maximal set है। हर SCC को एक vertex में contract करें और internal edges छोड़ दें तो resulting directed graph में directed cycle नहीं होती। अलग SCCs के बीच cycle होती तो उनके vertices mutually reachable होते और वे एक ही SCC होने चाहिए थे। यह structural तथ्य किसी खास SCC algorithm पर निर्भर नहीं।
विश्वसनीय जाँच की विधि
Graph conventions और सारी edges स्पष्ट करें। Deletion से पहले components गिनें, ठीक माँगा deletion करें, फिर गिनें। Tree के दावे में edge count और साथ की structural शर्त दोनों जाँचें। Exact cut value में lower bound का प्रमाण और उतने आकार का cut दें। Directed प्रश्नों में direction तथा weak/strong शब्द स्पष्ट रखें। Matching, vertex colouring, Menger theorem और efficient cut-finding algorithms आगे के विषय हैं; यह पूरा graph theory नहीं।
मौलिक अभ्यास: छह single-correct MCQ
मौलिक प्रश्न हैं, पिछले वर्षों के नहीं। हर प्रश्न में ठीक एक विकल्प चुनें। दिए index, domain और graph conventions लागू रखें।
C01. V={a,b,c,d,e,f}, E={ab,bc,ca,cd,de,ef,fd} में bridges का पूरा set क्या है?
A. {ab,bc,ca} B. {cd} C. {de,ef,fd} D. हर edge
उत्तर: B
A: ये पहले triangle की edges हैं; हर एक के endpoints का alternate path है।
B: केवल cd triangles जोड़ती है; हटाने से दो components। बाकी हर edge cycle पर है।
C: ये दूसरे triangle की edges हैं, इसलिए कोई bridge नहीं।
D: Cycle edges bridges नहीं; केवल joining edge महत्वपूर्ण है।
C02. उसी दो-triangle graph में articulation vertices का पूरा set क्या है?
A. {a,b,e,f} B. {c} C. सभी छह vertices D. {c,d}
उत्तर: D
A: इनमें से किसी को हटाने पर उसके triangle के बाकी दो vertices शेष graph से जुड़े रहते हैं।
B: c के साथ d भी articulation vertex है।
C: बाकी चार deletions में graph connected रहता है।
D: c हटाने से {a,b} और {d,e,f}; d हटाने से {a,b,c} और {e,f} अलग। कोई दूसरा deletion disconnect नहीं करता।
C03. Forest में 7 vertices और 3 connected components हैं। कितनी edges हैं?
A. 4 B. 6 C. 3 D. 10
उत्तर: A
A: हर component tree है, इसलिए कुल edges n−c=7−3=4।
B: n−1=6 में एक connected tree माना है, तीन components नहीं।
C: Component count, edge count नहीं है।
D: n+c forest का नियम नहीं; इतनी edges से cycles होंगी।
C04. कौन-सा उदाहरण यह दावा गलत सिद्ध करता है कि n−1 edges वाला हर simple undirected graph tree है?
A. चार vertices का connected path B. एक triangle और एक isolated vertex C. Cycle-विहीन connected graph D. बिना edge का एक-vertex graph
उत्तर: B
A: यह tree है और दावा गलत सिद्ध नहीं करता।
B: n=4,m=3=n−1, लेकिन disconnected और cyclic; केवल edge count पर्याप्त नहीं।
C: यह tree की परिभाषा ही है।
D: दिए convention में n=1,m=0 वाला यह tree है।
C05. Cycle C₄ की दी गई परिभाषाओं के अनुसार क्रमशः vertex connectivity κ और edge connectivity λ क्या हैं?
A. 1, 1 B. 1, 2 C. 2, 2 D. 2, 1
उत्तर: C
A: एक edge या एक vertex हटाने से cycle का connected path बचता है; disconnect नहीं।
B: एक vertex हटाने पर path बचता है, इसलिए κ=1 नहीं।
C: हर single deletion में connectivity रहती है; दो opposite vertices या दो उचित edges disconnect करते हैं, इसलिए दोनों न्यूनतम 2।
D: Cycle में bridge नहीं, इसलिए λ=1 नहीं।
C06. Directed graph में केवल a→b और b→c edges हैं। कौन-सा कथन सही है?
A. Strongly connected है और एक SCC है। B. न weakly, न strongly connected। C. Weakly connected है और दो SCCs हैं। D. Weakly connected, strongly connected नहीं; तीन singleton SCCs हैं।
उत्तर: D
A: c से a का वापस path नहीं, इसलिए सभी vertices की mutual reachability नहीं।
B: Directions हटाने पर connected path a−b−c है; weak connectivity सही।
C: कोई अलग pair mutually reachable नहीं; दो-vertex SCC नहीं बन सकता।
D: Arrows हटाने पर connected path, लेकिन reverse reachability नहीं; SCCs {a},{b},{c} हैं।
स्रोत और दायरा
यह मौलिक पाठ आधिकारिक GATE 2027 CS syllabus के Section 1 में Discrete Mathematics के बताए विषय को विकसित करता है। इससे पूरा subject या syllabus समाप्त होने का दावा नहीं है। Syllabus प्रासंगिकता और संस्थागत course chapter आगे पढ़ने का स्रोत है। Worked examples, भाषा और अभ्यास मौलिक हैं।
स्रोत खोले और जाँचे गए: 2026-10-14।
प्रगति सहेजने के लिए साइन इन करें। साइन इन