ग्राफ़ सिद्धांत: चरण-दर-चरण हल सहित अभ्यास प्रश्न

Q: ग्राफ़ सिद्धांत क्या है?

एक ग्राफ़ शीर्षों (बिंदुओं) और कोरों (दो शीर्षों के बीच रेखाओं) से बनता है। सरल ग्राफ़ में कोई लूप और दोहरी कोर नहीं होती। किसी शीर्ष की घात उससे मिलने वाली कोरों की संख्या है। हर कोर के दो सिरे होते हैं, इसलिए वह हर सिरे की घात में 1 जोड़ती है। इससे हैंडशेक लेमा मिलता है:

Q: ग्राफ़ सिद्धांत के अभ्यास में क्या शामिल है?

आसान: घात और कोरें मध्यम: यूलर पथ और वृक्ष कठिन: सबसे छोटे पथ और स्पैनिंग ट्री हर प्रश्न में नए मान होते हैं, इसलिए आप उत्तर नहीं बल्कि विधि सीखते हैं। अटक गए? पहले एक छोटा संकेत खोलें, और पूरी व्याख्या तभी जब ज़रूरत हो।

आरेखों, संकेतों और पूर्ण हल के साथ मुफ़्त ग्राफ़ सिद्धांत अभ्यास प्रश्न। हर बार नए मान, तीन स्तरों पर: घात और कोरें, यूलर पथ और वृक्ष, सबसे छोटे पथ और स्पैनिंग ट्री।

मुफ़्त अभ्यास प्रश्नआसान

एक वृक्ष में 12 शीर्ष हैं। उसमें कितनी कोरें |E| हैं?

|V| = 12

सटीक उत्तर: एक पूर्ण संख्या, बिना पूर्णांकन के।

अगला प्रश्न →

ग्राफ़ सिद्धांत का मुफ़्त अभ्यास करें अभी ग्राफ़ सिद्धांत का अभ्यास करेंहर दिन 5 मुफ़्त प्रश्न। कार्ड की ज़रूरत नहीं।

आप क्या अभ्यास करेंगे

आसानघात और कोरें
मध्यमयूलर पथ और वृक्ष
कठिनसबसे छोटे पथ और स्पैनिंग ट्री

ग्राफ़ सिद्धांत के प्रश्न कैसे हल करें

हर शीर्ष की घात लिखें; घातों का योग कोरों की संख्या का दोगुना होता है।
यूलर के प्रश्नों में जाँचें कि ग्राफ़ संबद्ध है और विषम घात वाले शीर्षों को गिनें।
वृक्षों के लिए n − 1 कोरों और हैंडशेक लेमा का उपयोग करें।
डाइक्स्ट्रा के लिए अस्थायी दूरियों की सारणी रखें और हर चक्र में सबसे छोटी दूरी वाले अनिर्धारित शीर्ष को निर्धारित करें।
न्यूनतम स्पैनिंग ट्री के लिए कोरों को भार के अनुसार क्रमबद्ध करें और चक्र बनाने वाली हर कोर छोड़ दें (क्रुस्कल), या किसी प्रारंभिक शीर्ष से एक वृक्ष बढ़ाएँ (प्रिम)।

सामान्य गलतियाँ

घातों के योग को 2 से भाग देना भूल जाना।
संबद्धता जाँचे बिना ग्राफ़ को यूलरीय कह देना।
डाइक्स्ट्रा में किसी शीर्ष की दूरी सबसे छोटी होने से पहले उसे निर्धारित कर देना।
चक्र की जाँच किए बिना सबसे हल्की कोरें ले लेना।
K_n के हैमिल्टन परिपथों की संख्या (n − 1)!/2 की जगह n! गिनना।

मुख्य सूत्र

हैंडशेक लेमा: Σ deg(v) = 2|E|
पूर्ण ग्राफ़: |E(K_n)| = n(n − 1)/2, |E(K_m,n)| = m·n
नियमित ग्राफ़: |E| = n·k/2
वृक्ष और वन: |E| = n − 1, |E| = n − c
वृक्ष के पत्ते: L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
यूलर: परिपथ: सभी घात सम; पथ: ठीक 2 घात विषम
K_n में हैमिल्टन परिपथ: (n − 1)!/2
डाइक्स्ट्रा अद्यतन: d(v) = min(d(v), d(u) + w(u, v))
लंबाई L की वॉक: (Mᴸ)_ij

ग्राफ़ सिद्धांत शुरू से सीखें

इससे पहले: समुच्चय, संबंध और फलन

1शीर्ष, कोरें और घात

एक ग्राफ़ शीर्षों (बिंदुओं) और कोरों (दो शीर्षों के बीच रेखाओं) से बनता है। सरल ग्राफ़ में कोई लूप और दोहरी कोर नहीं होती।

किसी शीर्ष की घात उससे मिलने वाली कोरों की संख्या है। हर कोर के दो सिरे होते हैं, इसलिए वह हर सिरे की घात में 1 जोड़ती है। इससे हैंडशेक लेमा मिलता है:

Σ deg(v) = 2·|E|

दो परिणाम: घातों का योग हमेशा सम होता है, और विषम घात वाले शीर्षों की संख्या भी सम होती है।

पूर्ण ग्राफ़ K_n हर जोड़े को जोड़ता है: n(n − 1)/2 कोरें।
पूर्ण द्विभाजित ग्राफ़ K_m,n एक ओर के हर शीर्ष को दूसरी ओर के हर शीर्ष से जोड़ता है: m·n कोरें।
n शीर्षों पर k-नियमित ग्राफ़ में n·k/2 कोरें होती हैं।

संलग्नता आव्यूह में (i, j) पर 1 होता है जब i और j जुड़े हों। अदिशित ग्राफ़ के लिए यह सममित होता है, पंक्ति योग घात होता है, और Mᴸ की प्रविष्टि (i, j) i से j तक लंबाई L की वॉक गिनती है।

स्व-जाँच एक ग्राफ़ की घातें 3, 3, 2, 2, 2 हैं। उसमें कितनी कोरें हैं?

उत्तर: 6. घातों का योग 12 है, और हर कोर दो बार गिनी जाती है, इसलिए 12/2 = 6 कोरें हैं। 5 शीर्षों की संख्या है।

2यूलर और हैमिल्टन

यूलर परिपथ हर कोर का ठीक एक बार उपयोग करता है और शुरुआत पर लौटता है। यूलर पथ हर कोर का एक बार उपयोग करता है पर कहीं और समाप्त हो सकता है। संबद्ध ग्राफ़ के लिए:

सभी घात सम: यूलर परिपथ मौजूद है;
ठीक दो घात विषम: यूलर पथ मौजूद है, एक विषम शीर्ष से दूसरे तक;
दो से अधिक घात विषम: दोनों में से कुछ नहीं।

हैमिल्टन परिपथ हर शीर्ष पर ठीक एक बार जाता है। इसके लिए कोई सरल घात-परीक्षण नहीं है। K_n में (n − 1)!/2 अलग हैमिल्टन परिपथ होते हैं: प्रारंभ तय करें, बाकी n − 1 शीर्षों को क्रमबद्ध करें, और दो दिशाओं के लिए 2 से भाग दें।

स्व-जाँच एक संबद्ध ग्राफ़ की घातें 2, 3, 4, 3, 2 हैं। उसमें क्या है?

एक यूलर पथ, पर यूलर परिपथ नहीं
एक यूलर परिपथ
दोनों में से कुछ नहीं
यूलर परिपथ और ऐसा यूलर पथ दोनों जो परिपथ नहीं है

उत्तर: एक यूलर पथ, पर यूलर परिपथ नहीं. ठीक दो शीर्षों की घात विषम है (दो 3), इसलिए उनके बीच यूलर पथ है, पर परिपथ नहीं।

3वृक्ष

वृक्ष चक्र-रहित संबद्ध ग्राफ़ है। n शीर्षों वाले हर वृक्ष में ठीक n − 1 कोरें होती हैं। कोई भी कोर जोड़ने से चक्र बनता है; कोई भी कोर हटाने से वह असंबद्ध हो जाता है।

n शीर्षों पर c वृक्षों वाले वन में n − c कोरें होती हैं। m कोरों वाला संबद्ध ग्राफ़ m − n + 1 कोरें हटाने के बाद एक स्पैनिंग ट्री रखता है।

हैंडशेक लेमा पत्तों को गिनता है: Σ deg = 2(n − 1)। संक्षिप्त रूप L = 2 + Σ (d − 2) है, घात d ≥ 3 वाले शीर्षों पर। घात 3 के दो शीर्षों और बाकी पत्तों वाले वृक्ष में 2 + 1 + 1 = 4 पत्ते होते हैं।

4डाइक्स्ट्रा और न्यूनतम स्पैनिंग ट्री

डाइक्स्ट्रा का एल्गोरिथ्म अऋणात्मक भारों वाले ग्राफ़ में प्रारंभिक शीर्ष से सबसे छोटी दूरियाँ खोजता है।

प्रारंभिक दूरी 0 दें और हर दूसरे शीर्ष को ∞।
सबसे छोटी दूरी वाले अनिर्धारित शीर्ष को निर्धारित करें; उसकी दूरी अब अंतिम है।
हर पड़ोसी v के लिए d(v) = min(d(v), d(u) + w(u, v)) अद्यतन करें।
तब तक दोहराएँ जब तक लक्ष्य निर्धारित न हो जाए।

न्यूनतम स्पैनिंग ट्री सभी शीर्षों को सबसे कम कुल भार से जोड़ता है। क्रुस्कल कोरों को हल्की से भारी की ओर क्रमबद्ध करता है और हर कोर को तब तक लेता है जब तक वह चक्र न बनाए। प्रिम प्रारंभिक शीर्ष से एक वृक्ष बढ़ाता है और हमेशा उससे बाहर जाने वाली सबसे हल्की कोर जोड़ता है। दोनों n − 1 कोरों के बाद रुक जाते हैं।

हल किया गया उदाहरण

नीचे के ग्राफ़ में A से E तक की सबसे छोटी दूरी ज्ञात करें।

प्रारंभ

d(A) = 0। इसके पड़ोसियों को d(B) = 4 और d(C) = 1 मिलता है।

C को निर्धारित करें (1)

C के रास्ते: d(B) = min(4, 1 + 2) = 3 और d(E) = 1 + 8 = 9।

B को निर्धारित करें (3)

B के रास्ते: d(D) = 3 + 5 = 8।

D को निर्धारित करें (8)

D के रास्ते: d(E) = min(9, 8 + 1) = 9। कोई सुधार नहीं, बराबरी।

E को निर्धारित करें (9)

E निर्धारित हो गया: उसकी दूरी अंतिम है।

उत्तर

सबसे छोटी दूरी d(E) = 9 है, मार्ग A → C → E से। मार्ग A → C → B → D → E की लंबाई भी वही है, 1 + 2 + 5 + 1 = 9।

स्व-जाँच क्रुस्कल के एल्गोरिथ्म ने भार 1, 2 और 3 की कोरें ले ली हैं। अगली सबसे हल्की कोर, भार 4, दो ऐसे शीर्षों को जोड़ती है जो पहले से जुड़े हैं। क्या होगा?

उसके बजाय भार 3 की कोर हटा दी जाती है
उसे छोड़ दिया जाता है क्योंकि वह चक्र बना देगी
उसे ले लिया जाता है क्योंकि वह बची हुई सबसे हल्की कोर है
एल्गोरिथ्म रुक जाता है

उत्तर: उसे छोड़ दिया जाता है क्योंकि वह चक्र बना देगी. क्रुस्कल कभी चक्र नहीं बनाता: एक ही घटक के दो शीर्षों के बीच की कोर छोड़ दी जाती है, और एल्गोरिथ्म अगली कोर पर चला जाता है।

5सामान्य गलतियाँ

कोरों की संख्या पाने के लिए घातों के योग को 2 से भाग देना भूल जाना।
ग्राफ़ संबद्ध है या नहीं, यह जाँचे बिना यूलर परिपथ की जाँच करना।
डाइक्स्ट्रा में किसी शीर्ष को उसकी अस्थायी दूरी सबसे छोटी होने से पहले निर्धारित कर देना।
चक्र जाँचे बिना n − 1 सबसे हल्की कोरें ले लेना।
K_n के हैमिल्टन परिपथों को (n − 1)!/2 की जगह n! गिनना।

6परीक्षा प्रश्न कैसे दिखते हैं

आसान: घात और कोरें। आप हैंडशेक लेमा का उपयोग करते हैं, K_n, K_m,n, नियमित ग्राफ़ों और वृक्षों की कोरें गिनते हैं, संलग्नता आव्यूह पढ़ते हैं, या दी गई घात वाले शीर्ष पर क्लिक करते हैं।
मध्यम: यूलर पथ और वृक्ष। आप तय करते हैं कि ग्राफ़ में यूलर परिपथ या पथ है या नहीं, वृक्ष के पत्ते गिनते हैं, स्पैनिंग ट्री के लिए हटाई जाने वाली कोरें गिनते हैं, या K_n में हैमिल्टन परिपथ गिनते हैं।
कठिन: सबसे छोटे पथ और स्पैनिंग ट्री। आप डाइक्स्ट्रा का एल्गोरिथ्म चलाते हैं, किसी दिए गए चक्र में निर्धारित शीर्ष खोजते हैं, न्यूनतम स्पैनिंग ट्री का भार निकालते हैं, क्रुस्कल या प्रिम द्वारा अगली जोड़ी जाने वाली कोर पर क्लिक करते हैं, या संलग्नता आव्यूह से वॉक गिनते हैं।

ऐप में इसे चरण-दर-चरण सीखें ऐप में इसे चरण-दर-चरण सीखें

हल किए गए उदाहरण

उदाहरण 1आसान

एक सरल अदिशित ग्राफ़ का संलग्नता आव्यूह दिखाया गया है। ग्राफ़ में कितनी कोरें |E| हैं?

ज्ञात करें: |E|

संकेत दिखाएँ

प्रविष्टि (i, j) 1 होती है जब शीर्ष i और j किसी कोर से जुड़े हों।
हर कोर {i, j} दो 1 देती है: एक (i, j) पर और एक (j, i) पर।
आव्यूह में 8 एक हैं।

उत्तर और चरण-दर-चरण हल दिखाएँ

घात: किसी शीर्ष की घात उससे मिलने वाली कोरों की संख्या है। हर कोर के दो सिरे होते हैं, इसलिए घातों का योग कोरों की संख्या का दोगुना होता है: Σ deg(v) = 2|E| (हैंडशेक लेमा)। अतः विषम घात वाले शीर्षों की संख्या सम होती है। K_n में n(n − 1)/2 कोरें होती हैं, n शीर्षों पर k-नियमित ग्राफ़ में nk/2, और n शीर्षों वाले वृक्ष में n − 1 कोरें।

एक-बिट गिनें

पंक्ति योग: 1 + 1 + 2 + 1 + 3 = 8

|E| = 8/2 = 4

उत्तर

|E| = 4

उदाहरण 2मध्यम

क्या संबद्ध ग्राफ़ में यूलर परिपथ है, परिपथ न होने वाला यूलर पथ है, या दोनों में से कुछ नहीं? अपना उत्तर क्लिक करें।

|V| = 7|E| = 10

1यूलर परिपथ
2यूलर पथ, परिपथ नहीं
3दोनों में से कुछ नहीं

संकेत दिखाएँ

यूलर के प्रमेय को केवल शीर्षों की घात चाहिए (ग्राफ़ संबद्ध है)।
सभी घात सम: यूलर परिपथ। ठीक दो घात विषम: उनके बीच यूलर पथ। इससे अधिक: दोनों में से कुछ नहीं।
विषम घात वाले शीर्षों को गिनें।

उत्तर और व्याख्या दिखाएँ

यूलर, हैमिल्टन और वृक्ष: संबद्ध ग्राफ़ में यूलर परिपथ (हर कोर एक बार, शुरुआत पर वापसी) तब होता है जब हर शीर्ष की घात सम हो, और परिपथ न होने वाला यूलर पथ तब जब ठीक दो शीर्षों की घात विषम हो; तब पथ एक विषम शीर्ष से दूसरे तक चलता है। हैमिल्टन परिपथ हर शीर्ष पर एक बार जाता है; K_n में ऐसे (n − 1)!/2 होते हैं। n शीर्षों वाले वृक्ष में n − 1 कोरें होती हैं, और m कोरों वाला संबद्ध ग्राफ़ m − n + 1 कोरें हटाने के बाद स्पैनिंग ट्री रखता है।

घात

deg(A) = 1, deg(B) = 4, deg(C) = 2, deg(D) = 4, deg(E) = 4, deg(F) = 2, deg(G) = 3

विषम शीर्ष

A, G → 2

यूलर पथ, परिपथ नहीं

उत्तर

यूलर पथ, परिपथ नहीं

यूलर पथ एक विषम शीर्ष से शुरू होता है और दूसरे पर समाप्त होता है।

उदाहरण 3कठिन

लंबाई 3 की कितनी बंद वॉक E से शुरू और समाप्त होती हैं? वॉक में शीर्ष और कोरें दोहराई जा सकती हैं। संख्या को N कहें।

M = संलग्नता आव्यूहL = 3

ज्ञात करें: N

संकेत दिखाएँ

संलग्नता आव्यूह M के साथ, i से j तक लंबाई L की वॉक की संख्या Mᴸ की प्रविष्टि (i, j) है।
पहले E से हर शीर्ष तक लंबाई 2 की वॉक गिनें, फिर एक कदम और लें।
E से लंबाई 2 की वॉक: A: 2, B: 1, C: 0, D: 2, E: 4, F: 1।

उत्तर और चरण-दर-चरण हल दिखाएँ

संलग्नता आव्यूह

A: 0 1 1 0 0 0

B: 1 0 0 1 1 0

C: 1 0 0 0 1 0

D: 0 1 0 0 1 1

E: 0 1 1 1 0 1

F: 0 0 0 1 1 0

एक कदम और

(M³)_EE = 2·0 + 1·1 + 0·1 + 2·1 + 4·0 + 1·1 = 4

उत्तर

N = 4

प्रश्न और उत्तर

ग्राफ़ सिद्धांत क्या है?

ग्राफ़ सिद्धांत के प्रश्न चरण-दर-चरण कैसे हल करें?

हर शीर्ष की घात लिखें; घातों का योग कोरों की संख्या का दोगुना होता है।
यूलर के प्रश्नों में जाँचें कि ग्राफ़ संबद्ध है और विषम घात वाले शीर्षों को गिनें।
वृक्षों के लिए n − 1 कोरों और हैंडशेक लेमा का उपयोग करें।
डाइक्स्ट्रा के लिए अस्थायी दूरियों की सारणी रखें और हर चक्र में सबसे छोटी दूरी वाले अनिर्धारित शीर्ष को निर्धारित करें।
न्यूनतम स्पैनिंग ट्री के लिए कोरों को भार के अनुसार क्रमबद्ध करें और चक्र बनाने वाली हर कोर छोड़ दें (क्रुस्कल), या किसी प्रारंभिक शीर्ष से एक वृक्ष बढ़ाएँ (प्रिम)।

ग्राफ़ सिद्धांत में आम गलतियाँ क्या हैं?

घातों के योग को 2 से भाग देना भूल जाना।
संबद्धता जाँचे बिना ग्राफ़ को यूलरीय कह देना।
डाइक्स्ट्रा में किसी शीर्ष की दूरी सबसे छोटी होने से पहले उसे निर्धारित कर देना।
चक्र की जाँच किए बिना सबसे हल्की कोरें ले लेना।
K_n के हैमिल्टन परिपथों की संख्या (n − 1)!/2 की जगह n! गिनना।

ग्राफ़ सिद्धांत के अभ्यास में क्या शामिल है?

आसान: घात और कोरें
मध्यम: यूलर पथ और वृक्ष
कठिन: सबसे छोटे पथ और स्पैनिंग ट्री

हर प्रश्न में नए मान होते हैं, इसलिए आप उत्तर नहीं बल्कि विधि सीखते हैं। अटक गए? पहले एक छोटा संकेत खोलें, और पूरी व्याख्या तभी जब ज़रूरत हो।

अभ्यास कैसे काम करता है

हर प्रश्न में नए मान होते हैं, इसलिए आप उत्तर नहीं बल्कि विधि सीखते हैं।
अटक गए? पहले एक छोटा संकेत खोलें, और पूरी व्याख्या तभी जब ज़रूरत हो।
आपकी प्रगति, गलतियाँ और सहेजे गए प्रश्न रखे जाते हैं, ताकि आप परीक्षा से पहले दोहरा सकें।

इससे पहले और बाद के विषय

पहले सीखें

समुच्चय, संबंध और फलन

इस विषय वाले कोर्स

डेटा संरचना और एल्गोरिदम कंप्यूटर विज्ञान के मूल सिद्धांत असतत गणित

गणित और सांख्यिकी में और विषय

सीमाएँ अवकलज इष्टतमीकरण समाकल अनुक्रम और श्रेणियाँ बहुचर कलन अवकल समीकरण सम्मिश्र संख्याएँ संख्यात्मक विधियाँ आव्यूह और सारणिक सदिश: अदिश और सदिश गुणनफल प्रस्ताविक तर्क और उपपत्तियाँ समुच्चय, संबंध और फलन संख्या सिद्धांत और मॉड्यूलर अंकगणित प्रायिकता वर्णनात्मक सांख्यिकी प्रसामान्य बंटन विश्वास्यता अंतराल परिकल्पना परीक्षण और विश्वास्यता अंतराल रैखिक समाश्रयण और सहसंबंध काई-वर्ग परीक्षण

प्रिंट करने योग्य वर्कशीट

उत्तरों सहित ग्राफ़ सिद्धांत वर्कशीट