Graph Theory MCQ Quiz in हिन्दी - Objective Question with Answer for Graph Theory - मुफ्त [PDF] डाउनलोड करें

दिया गया है:

आलेख में घात का योग = d योग um

आलेख में किनारों की संख्या = e

सूत्र:

हस्तमिलन प्रमेयिका द्वारा:

d योग = 2 × e

गणना

विषम घातों का योग + सम घातों का योग = 2× e

विषम घातों का योग = 2× e - सम घातों का योग

2 × e → सम है

सम घातों का योग → सम

सम - सम = सम

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

इसलिए, विकल्प 1 गलत है। 

सही उत्तर A - III; B - IV; C - I; D - II है।

Key Points

• A. प्लैनर ग्राफ - III. 4-रंगनीय।
  • चार-रंग प्रमेय कहता है कि किसी भी समतल में मानचित्र को चार रंगों का उपयोग करके इस तरह से रंगा जा सकता है कि एक सामान्य सीमा (एक बिंदु के अतिरिक्त) साझा करने वाले क्षेत्र एक ही रंग साझा नहीं करते हैं।
  • 
• B. बाइपार्टाइट ग्राफ - IV. 2-रंगनीय।
  • एक बाइपार्टाइट ग्राफ को शीर्ष के दो समूहों में विभाजित किया जा सकता है जैसे कि सभी किनारे एक समूह में एक शीर्ष को दूसरे समूह में एक शीर्ष से जोड़ते हैं। इसलिए, वे 2-रंगनीय हैं।
  • 
• C. PERT (प्रोग्राम इवैल्यूएशन एंड रिव्यू टेक्निक) - I. प्रायिकतात्मक मॉडल।
  • PERT एक सांख्यिकीय उपकरण है, जिसका उपयोग परियोजना प्रबंधन में किया जाता है, जिसे किसी दिए गए प्रोजेक्ट को पूरा करने में शामिल कार्यों का विश्लेषण और प्रतिनिधित्व करने के लिए डिज़ाइन किया गया है। यह प्रायिकतात्मक समय अनुमानों का उपयोग करता है।
• D. CPM (क्रिटिकल पाथ मेथड) - II. नियतात्मक मॉडल।
  • ​CPM प्रोजेक्ट प्रबंधन में उपयोग की जाने वाली एक विधि है जो परियोजना में विभिन्न चरणों की योजना बनाने और शेड्यूल करने के लिए है। यह एक नियतात्मक मॉडल है क्योंकि यह प्रत्येक कार्य के लिए एक निश्चित समय अवधि मानता है।

सही उत्तर N - 1 है।

Key Points

• किसी ग्राफ का स्पैनिंग ट्री एक ऐसा उपग्राफ होता है जिसमें मूल ग्राफ के सभी शीर्ष शामिल होते हैं।
• स्पैनिंग ट्री में, सभी शीर्ष न्यूनतम संभव संख्या में किनारों से जुड़े होते हैं।
• N शीर्षों वाले ग्राफ के लिए, स्पैनिंग ट्री में ठीक N - 1 किनारे होंगे।
• ऐसा इसलिए है क्योंकि एक और किनारा जोड़ने से चक्र बन जाएगा, जो एक ट्री में अनुमत नहीं है।

Additional Information

• विकल्प 1: N - यह गलत है क्योंकि N शीर्षों वाले स्पैनिंग ट्री में N किनारे नहीं हो सकते हैं। N किनारे होने का अर्थ होगा कि एक चक्र है।
• विकल्प 3: N(N - 1)/2 - यह गलत है क्योंकि यह एक पूर्ण ग्राफ में किनारों की अधिकतम संख्या का प्रतिनिधित्व करता है, न कि स्पैनिंग ट्री में।

सही उत्तर 4 है

प्रमुख बिंदु

दिए गए प्रवाह ग्राफ की चक्रीय जटिलता निर्धारित करने के लिए, हम मैककेब के सूत्र का उपयोग कर सकते हैं: V(G) = E - N + 2P

कहाँ:

• V(G) चक्रीय जटिलता है।
• E ग्राफ में किनारों की संख्या है।
• N ग्राफ में नोड्स की संख्या है।
• P जुड़े हुए घटकों की संख्या है (एकल जुड़े हुए ग्राफ के लिए, P = 1.

आइए दिए गए प्रवाह ग्राफ में किनारों (E) और नोड्स (N) की संख्या गिनें।

1. नोड्स (N) की गणना करें:
इसमें 1 से 10 तक लेबल वाले 9 नोड हैं।

2. किनारों की गिनती करें (E): इनकी गिनती करने पर हमें 11 किनारे मिलते हैं।

3. साइक्लोमैटिक जटिलता की गणना करें:
सूत्र का उपयोग करके: V(G) = E - N + 2P
यहाँ, E = 11, N = 9, और P = 1.

   V(G) = 11 - 9 + 2 x 1
   V(G) = 11 - 9 + 2
   V(G) = 4

तो, दिए गए प्रवाह ग्राफ की चक्रीय जटिलता है: 2) 4

सही उत्तर (A) और (B) केवल है।

Key Points

• वृक्ष:
  • एक वृक्ष एक प्रकार का ग्राफ़ है जो एसाइक्लिक होता है, जिसका अर्थ है कि कोई साइकल या लूप नहीं होते हैं। इसमें एक पदानुक्रमित संरचना में किनारों से जुड़े नोड्स होते हैं। प्रत्येक नोड, मूल को छोड़कर, जिसका ठीक एक पैरेंट होता है, जो पैरेंट-चाइल्ड के संबंध का निर्माण करता है।
  • ट्री संरचना में कोई लूप या साइकल नहीं होते हैं।
  • एक ट्री एक जुड़ा हुआ ग्राफ़ है, जिसका अर्थ है कि नोड्स की किसी भी जोड़ी के बीच एक विशिष्ट पथ है।
  • एक ट्री में प्रत्येक नोड (मूल को छोड़कर) का ठीक एक पैरेंट होता है।
  • एक विशिष्ट शीर्ष नोड होता है जिसे मूल कहा जाता है जिससे अन्य सभी नोड वंशज होते हैं।
  • वृक्ष आमतौर पर निर्देशित होते हैं, जिसका अर्थ है कि किनारों की एक विशिष्ट दिशा होती है (पैरेंट से चाइल्ड तक)।
  • ट्री का उपयोग आमतौर पर पदानुक्रमित डेटा प्रतिनिधित्व के लिए किया जाता है, जैसे फ़ाइल सिस्टम, संगठनात्मक चार्ट और अभिव्यक्ति ट्री। बाइनरी सर्च ट्री (BST) एक विशिष्ट प्रकार का ट्री है जिसका उपयोग कुशल सर्चिंग और सॉर्टिंग के लिए किया जाता है।
  • 
• ग्राफ़:
  • एक ग्राफ़ एक अधिक सामान्य संरचना है जो साइक्लिक या एसाइक्लिक हो सकती है। इसमें नोड्स (शीर्ष) और इन नोड्स को जोड़ने वाले किनारे होते हैं। एक ग्राफ़ में नोड्स के बीच कोई सख्त पदानुक्रमित संबंध नहीं होता है।
  • एक ग्राफ़ जुड़ा हुआ हो सकता है या नहीं भी हो सकता है। एक ग्राफ़ के भीतर अलग-अलग घटक हो सकते हैं।
  • एक ग्राफ़ में नोड्स में कई आने वाले किनारे हो सकते हैं, जिसका अर्थ है कि उनके कई पैरेंट हो सकते हैं।
  • एक सामान्य ग्राफ़ में मूल नोड की कोई अवधारणा नहीं होती है।
  • ग्राफ़ निर्देशित या निदेशित हो सकते हैं। निर्देशित ग्राफ़ में, किनारों की एक दिशा होती है, जबकि निदेशित ग्राफ़ में, किनारों की कोई दिशा नहीं होती है।
  • ग्राफ़ अधिक सामान्य-उद्देश्यीय होते हैं और संस्थाओं के बीच विभिन्न प्रकार के संबंधों का प्रतिनिधित्व कर सकते हैं। उनका उपयोग सामाजिक नेटवर्क, सड़क नेटवर्क, निर्भरता ग्राफ़ और बहुत कुछ जैसे अनुप्रयोगों में किया जाता है।
  • 
  • विकल्प D असंबद्ध ग्राफ़ है इसलिए यह ट्री नहीं है।
  • 

केवल विकल्प A और B एसाइक्लिक ग्राफ़ हैं इसलिए सही उत्तर विकल्प 1 है।

दिया गया है:

बहुफलक के किनारे  = 30

बहुफलक के फलक = 12

प्रयुक्त सूत्र:

बहुफलक के लिए यूलर का सूत्र

F + V = E + 2      (जहाँ F = बहुफलक के फलक, V = बहुफलक के शीर्ष और E = बहुफलक के किनारे)

गणना:

माना बहुफलक का शीर्ष V है

⇒ 12 + V = 30 + 2

⇒ V = 32 - 12 = 20

∴ अभीष्ट परिणाम 20 होगा। 

दिया गया है:

पाई-चार्ट में 2010 में राज्यों की जनसंख्या दर्शाई गई है।

कुल जनसंख्या = 16200000

गणना:

राजस्थान की जनसंख्या 180 ° है।

इसलिए, 16200000 × ( 180 / 360 ) 

= 8100000

∴ वर्ष 2010 में राजस्थान की जनसंख्या 8100000 है। 

एक निर्देशित आलेख G में दृढ़ता से संयोजित होने के लिए प्रत्येक शीर्ष से प्रत्येक अन्य शीर्ष तक एक पथ होना चाहिए।

यदि कोरों की दिशा उलट दी जाती है, तब भी आलेख G के समान दृढ़ता से संयोजित घटक होंगे।

विकल्प 2: G₂ = (V, E₂) जहाँ E₂ = {(u, v)|(v, u) ∈ E}

इस विकल्प G₂ में, कोर उलट दिए गए हैं और इसलिए यह G के समान दृढ़ता से संयोजित घटक हैं।

इसलिए, सभी कोरों की दिशा बदलने से, SCC नहीं बदलेगा।

अवधारणा:-

तुल्याकारी ग्राफ:-

यदि दो ग्राफ़ में कुछ संख्या में नोड्स और कुछ शाखाओं की संख्या होती है और वे अलग दिखते हैं लेकिन कुछ आपतन आव्यूह होते हैं जिन्हें तुल्याकारी ग्राफ कहा जाता है

यह दोनों ग्राफ़ के लिए समान आपतन आव्यूह है

Additional Information

​ट्री:- ​ट्री किसी दिए गए ग्राफ का एक जुड़ा हुआ उप ग्राफ है, जिसमें एक ग्राफ के सभी नोड होते हैं, लेकिन फिर उप ग्राफ में कोई लूप नहीं होना चाहिए जिसे ट्री कहा जाता है।

कट वर्टेक्स​:

• एक ग्राफ से कटा हुआ वर्टेक्स हटाने से इसे दो या दो से अधिक ग्राफ़ में तोड़ दिया जाता है।
• संयोजित ग्राफ G में अधिकतम (v - 2) कट वर्टेक्स हो सकते हैं, यहाँ v कोई वर्टेक्स नहीं है।

टर्मिनल वर्टेक्स:

• एक रूटेड ट्री में एक वर्टेक्स है जिसका कोई परवर्ती नहीं है, जिसे लीफ नोड के रूप में भी जाना जाता है।

स्पष्टीकरण:

यहाँ a, b, और e वर्टेक्स संधि बिन्दु हैं और f टर्मिनल वर्टेक्स है।

इसलिए विकल्प 3 सही उत्तर है।

हैमिल्टनियन ग्राफ:

एक हैमिल्टनियन ग्राफ वह होता है जिसमें हैमिल्टनियन चक्र होता है। हैमिल्टनियन चक्र एक ऐसा चक्र है जिसमें प्रत्येक शीर्ष पर ठीक एक बार दौरा किया जाता है।

हैमिल्टनियन ग्राफ के गुण:

1) एक ग्राफ में हैमिल्टनियन परिपथ होता है यदि प्रत्येक शीर्ष की डिग्री >=3 है

2) यदि G= (V, E) में n>=3 शीर्ष हैं और प्रत्येक शीर्ष की डिग्री>=n/2 है, तो G में हैमिल्टन परिपथ है।

3) यदि G n शीर्षों वाला एक ग्राफ है और n>=3, deg(u) + deg(v) >=n भी है, यदि u और v एक किनारे से नहीं जुड़े हैं, तो G में हैमिल्टनियन परिपथ है।

अवधारणा:

तीन-चरण परिपथ में:​

कुल वास्तविक या सक्रिय शक्ति (P) = 3 V_phI_ph cosϕ =√3 V_LI_Lcosϕ 

कुल प्रतिक्रियाशील शक्ति (Q) = 3 VphIph sinϕ =√3 VLILsinϕ 

कुल आभासी शक्ति (S) = 3 VphIph  =√3 VLIL

जहाँ,

V_L, I_L → लाइन वोल्टता और धारा 

Vph, Iph  → चरण वोल्टता, और धारा 

cosϕ → शक्ति गुणांक 

एक संतुलित स्टार-संबंध नेटवर्क के लिए

VL = √3Vph

IL = Iph 

गणना:

सक्रिय शक्ति (P) = 20 kW

Vph = 230 V

V_L = 230√3 V

शक्ति गुणांक (cosϕ ) =  0.8.

cosϕ = P/S

S = P\cosϕ = 20/0.8 = 25 KVA

तब;

   S = √3 VLIL

⇒I_L = S/ √3 VL

⇒IL = 25000/ (3×230)= 36.23 A

I_L = I_ph = 36.23 A

साथ ही,

    S = 3 |I_ph|²Z_p

⇒ Zp = S/(3 |Iph|2) = 25000/ [3× (36.23)²)] = 6.34 Ω 

    cosϕ = R_p/Z_p

∴ Rp = Zpcosϕ = 5.072 Ω

मुख्य नोड अर्थात वह संधि जहाँ शाखा धारा संयोजित अथवा विभाजित हो सकती है।

महत्वपूर्ण:

नोड:

एक नोड वह बिंदु अथवा संधि है, जहाँ दो या अधिक परिपथ के घटक (प्रतिरोधक, संधारित्र, प्रेरक इत्यादि) मिलते हैं। अन्य शब्दों में, दो या अधिक शाखाओं के बीच के संयोजन के बिंदु को नोड कहा जाता है।

शाखा:

एक परिपथ का वह भाग अथवा प्रभाग जो दो संधियों के बीच स्थित होता है, उसे शाखा कहते हैं। एक शाखा में, एक या अधिक घटक संयोजित हो सकते हैं, और उनके दो टर्मिनल होते हैं।

लूपः

एक परिपथ में एक संवृत पथ, जहाँ दो से अधिक मेश हो सकते हैं, उसे लूप कहते हैं, अर्थात एक लूप में कई मेश हो सकते हैं, पर एक मेश में एक लूप नहीं हो सकता।

मेश:

संकल्पना:

• ट्री का समूह और कुछ नहीं बल्कि फॉरेस्ट है।

व्याख्या:

उदाहरण:

• उपरोक्त ग्राफ G में 3 ट्रेस, k=3 और कुल 6 नोड्स, n=6 हैं, इसलिए यदि हम n से k घटाते हैं तो हमें किनारों की संख्या 3 के बराबर मिलेगी।
• किनारों की कुल संख्या प्राप्त करने का सामान्य सूत्र होगा n - k

अतः विकल्प 2 सही उत्तर है।