IGNOU MCS-212 Solved Question Paper PDF Download

प्रश्न 1. (a) सत्यापित करें कि [(p → q) ∧ ~q] → ~p एक टॉटोलॉजी (tautology) है या नहीं। (b) दिखाएँ कि √7 अपरिमेय है। (c) व्यंजक (x1 ∧ (x2 ∨ x3)) के लिए तर्क सर्किट (logic circuit) का निर्माण करें और तर्क तालिका (logic table) प्राप्त करें। (d) एक उपयुक्त उदाहरण की सहायता से दो समुच्चयों A और B के सममित अंतर (symmetric difference) शब्द का वर्णन करें। सममित अंतर के लिए वेन आरेख भी बनाएँ। (e) क्लेन क्लोजर (Kleene closure) को परिभाषित करें। Σ1 = {aa, b} और Σ2 = {a, ba} के लिए क्लेन क्लोजर लिखें। (f) क्रमचय (permutation) और संचय (combination) के बीच अंतर करें। एक गोल मेज पर 9 व्यक्तियों को बैठाने के संभव भिन्न तरीकों की संख्या भी ज्ञात करें। (g) सामान्यीकृत कपोत-छिद्र सिद्धांत (Generalized Pigeonhole principle) लिखें। (h) पुनरावृत्ति संबंध (recurrence relation) Cn = C(n-1) + (n-1) का उपयोग करते हुए, सीमा शर्त (boundary condition) C1 = 0 के साथ, दिखाएँ कि Cn = n(n-1)/2, जहाँ n ≥ 1 है।

उत्तर.

(a) टॉटोलॉजी का सत्यापन

यह सत्यापित करने के लिए कि दिया गया कथन [(p → q) ∧ ~q] → ~p एक टॉटोलॉजी है, हम एक सत्य सारणी (truth table) का निर्माण करेंगे। एक टॉटोलॉजी वह कथन है जो इसके चरों (variables) के सभी संभावित सत्य मानों के लिए हमेशा सत्य होता है।

p q ~p ~q p → q (p → q) ∧ ~q [(p → q) ∧ ~q] → ~p T T F F T F T T F F T F F T F T T F T F T F F T T T T T चूंकि अंतिम कॉलम में सभी मान ‘T’ (सत्य) हैं, इसलिए दिया गया कथन [(p → q) ∧ ~q] → ~p एक टॉटोलॉजी है। यह तर्क रूप modus tollens के रूप में भी जाना जाता है। (b) √7 की अपरिमेयता

हम इसे विरोधाभास द्वारा प्रमाण (proof by contradiction) का उपयोग करके सिद्ध करेंगे। मान लीजिए कि √7 परिमेय है। तब, इसे दो पूर्णांकों a और b के अनुपात के रूप में लिखा जा सकता है, जहाँ b ≠ 0 और a और b में 1 के अलावा कोई उभयनिष्ठ गुणनखंड नहीं है (अर्थात, gcd(a, b) = 1)। तो, √7 = a/b दोनों पक्षों का वर्ग करने पर: 7 = a²/b² 7b² = a² इसका मतलब है कि a² 7 से विभाज्य है। यदि a² 7 से विभाज्य है, तो a भी 7 से विभाज्य होना चाहिए। तो, हम a = 7k लिख सकते हैं, जहाँ k एक पूर्णांक है। a के इस मान को समीकरण में प्रतिस्थापित करने पर: 7b² = (7k)² 7b² = 49k² b² = 7k² इसका मतलब है कि b² 7 से विभाज्य है, इसलिए b भी 7 से विभाज्य होना चाहिए। यह हमारी प्रारंभिक धारणा का खंडन करता है कि a और b में कोई उभयनिष्ठ गुणनखंड नहीं है, क्योंकि हमने दिखाया है कि a और b दोनों 7 से विभाज्य हैं। यह विरोधाभास दर्शाता है कि हमारी प्रारंभिक धारणा गलत थी। इसलिए, √7 अपरिमेय है । (c) लॉजिक सर्किट और लॉजिक टेबल

व्यंजक है: y = (x1 ∧ (x2 ∨ x3)) इस व्यंजक के लिए, हमें एक OR गेट (x2 ∨ x3 के लिए) और एक AND गेट (x1 और OR गेट के आउटपुट के लिए) की आवश्यकता है। लॉजिक सर्किट: इनपुट x2 और x3 एक OR गेट से जुड़े होते हैं। इस OR गेट का आउटपुट और इनपुट x1 एक AND गेट से जुड़े होते हैं। AND गेट का अंतिम आउटपुट y है। सर्किट आरेख का विवरण: 1. x2 और x3 से लाइनें एक OR गेट में जाती हैं। 2. OR गेट से आउटपुट लाइन एक AND गेट में जाती है। 3. x1 से एक लाइन उसी AND गेट में जाती है। 4. AND गेट से अंतिम आउटपुट y है। लॉजिक टेबल: इसमें तीन इनपुट (x1, x2, x3) हैं, इसलिए 2³ = 8 संभावित संयोजन होंगे।

x1 x2 x3 x2 ∨ x3 y = x1 ∧ (x2 ∨ x3) 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 1 0 1 0 0 0 0 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 (d) समुच्चयों का सममित अंतर

दो समुच्चयों A और B का सममित अंतर (symmetric difference) , जिसे A Δ B या A ⊕ B से दर्शाया जाता है, उन तत्वों का समुच्चय है जो या तो A में हैं या B में हैं, लेकिन दोनों में नहीं हैं। इसे समुच्चय A और B के संघ (union) में से उनके प्रतिच्छेदन (intersection) को हटाकर प्राप्त किया जा सकता है। गणितीय रूप से: A Δ B = (A ∪ B) – (A ∩ B) या A Δ B = (A – B) ∪ (B – A) उदाहरण: मान लीजिए A = {1, 2, 3, 4} और B = {3, 4, 5, 6}।

• A ∪ B = {1, 2, 3, 4, 5, 6}
• A ∩ B = {3, 4}
• A Δ B = {1, 2, 3, 4, 5, 6} – {3, 4} = {1, 2, 5, 6}

वैकल्पिक रूप से:

• A – B = {1, 2}
• B – A = {5, 6}
• A Δ B = {1, 2} ∪ {5, 6} = {1, 2, 5, 6}

वेन आरेख: सममित अंतर के लिए वेन आरेख में दो प्रतिच्छेदी वृत्तों के वे सभी क्षेत्र शामिल होते हैं जो उनके प्रतिच्छेदन क्षेत्र में नहीं होते हैं। यह दोनों वृत्तों के बाहरी हिस्सों (non-overlapping parts) को छायांकित करके दर्शाया जाता है। (e) क्लेन क्लोजर

एक वर्णमाला (alphabet) Σ का क्लेन क्लोजर (Kleene Closure) , जिसे Σ* से दर्शाया जाता है, Σ के प्रतीकों से बनने वाली सभी परिमित-लंबाई वाली स्ट्रिंग्स का समुच्चय है, जिसमें रिक्त स्ट्रिंग (empty string) (ε या λ) भी शामिल है। यह Σ पर सभी संभव स्ट्रिंग्स का समुच्चय है। उदाहरण: 1. Σ1 = {aa, b} के लिए क्लेन क्लोजर (Σ1*): Σ1* में ε, और ‘aa’ और ‘b’ के किसी भी संयोजन से बनी सभी स्ट्रिंग्स शामिल हैं। Σ1* = {ε, b, aa, bb, aab, baa, aaaa, bbb, aabb, baaa, …} यह Σ1 के तत्वों को शून्य या अधिक बार जोड़कर बनाई गई सभी स्ट्रिंग्स का अनंत समुच्चय है।

2. Σ2 = {a, ba} के लिए क्लेन क्लोजर (Σ2*): Σ2* में ε, और ‘a’ और ‘ba’ के किसी भी संयोजन से बनी सभी स्ट्रिंग्स शामिल हैं। Σ2* = {ε, a, aa, ba, aaa, aba, baa, aaaa, aaba, abaa, baba, …} यह Σ2 के तत्वों को शून्य या अधिक बार जोड़कर बनाई गई सभी स्ट्रिंग्स का अनंत समुच्चय है।

(f) क्रमचय और संचय

अंतर:

• क्रमचय (Permutation): यह वस्तुओं का एक क्रमबद्ध व्यवस्थापन है। क्रमचय में, वस्तुओं का क्रम महत्वपूर्ण होता है। उदाहरण के लिए, ‘ab’ और ‘ba’ दो अलग-अलग क्रमचय हैं। n वस्तुओं में से r वस्तुओं को चुनने और व्यवस्थित करने के तरीकों की संख्या nPr = n! / (n-r)! द्वारा दी जाती है।
• संचय (Combination): यह वस्तुओं का एक अक्रमबद्ध चयन है। संचय में, वस्तुओं का क्रम महत्वपूर्ण नहीं होता है। उदाहरण के लिए, {‘a’, ‘b’} और {‘b’, ‘a’} एक ही संचय हैं। n वस्तुओं में से r वस्तुओं को चुनने के तरीकों की संख्या nCr = n! / (r! * (n-r)!) द्वारा दी जाती है।

संक्षेप में, क्रमचय व्यवस्था से संबंधित है जबकि संचय चयन से संबंधित है। गोल मेज की समस्या: n व्यक्तियों को एक गोल मेज पर बैठाने के तरीकों की संख्या (n-1)! होती है। ऐसा इसलिए है क्योंकि एक वृत्त में, घूर्णी समरूपता (rotational symmetry) के कारण, सभी स्थितियाँ सापेक्ष होती हैं। हम एक व्यक्ति की स्थिति को स्थिर मान लेते हैं और फिर बाकी (n-1) व्यक्तियों को (n-1)! तरीकों से व्यवस्थित करते हैं। यहां, n = 9 व्यक्ति हैं। इसलिए, उन्हें एक गोल मेज पर बैठाने के भिन्न तरीकों की संख्या है: (9 – 1)! = 8! 8! = 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 40,320 अतः, 9 व्यक्तियों को एक गोल मेज पर 40,320 अलग-अलग तरीकों से बैठाया जा सकता है। (g) सामान्यीकृत कपोत-छिद्र सिद्धांत

सामान्यीकृत कपोत-छिद्र सिद्धांत (Generalized Pigeonhole Principle) कहता है कि यदि N वस्तुओं को k बक्सों (या छिद्रों) में रखा जाता है, तो कम से कम एक बक्सा ऐसा होगा जिसमें कम से कम ⌈N/k⌉ वस्तुएँ होंगी। यहाँ, ⌈x⌉ सीलिंग फ़ंक्शन (ceiling function) है, जो x से बड़े या बराबर सबसे छोटे पूर्णांक को दर्शाता है। उदाहरण: यदि एक कक्षा में 100 छात्र हैं, तो उनमें से कम से कम ⌈100/12⌉ = ⌈8.33⌉ = 9 छात्र ऐसे होंगे जिनका जन्म एक ही महीने में हुआ हो। यहाँ, N = 100 (वस्तुएँ/कबूतर) और k = 12 (बक्से/महीने)। (h) पुनरावृत्ति संबंध का उपयोग करके प्रमाण

हमें सिद्ध करना है कि C(n) = n(n-1)/2, पुनरावृत्ति संबंध C(n) = C(n-1) + (n-1) और सीमा शर्त C(1) = 0 का उपयोग करके, जहाँ n ≥ 1 है। हम गणितीय आगमन (mathematical induction) का उपयोग करेंगे। आधार मामला (Base Case): n = 1 के लिए सूत्र के अनुसार: C(1) = 1(1-1)/2 = 1(0)/2 = 0 दी गई सीमा शर्त भी C(1) = 0 है। अतः, आधार मामला सत्य है। आगमनात्मक परिकल्पना (Inductive Hypothesis): मान लीजिए कि सूत्र किसी पूर्णांक k ≥ 1 के लिए सत्य है। अर्थात, C(k) = k(k-1)/2 आगमनात्मक चरण (Inductive Step): हमें सिद्ध करना है कि सूत्र n = k+1 के लिए भी सत्य है। हमें दिखाना है कि C(k+1) = (k+1)((k+1)-1)/2 = (k+1)k/2। पुनरावृत्ति संबंध का उपयोग करते हुए: C(k+1) = C(k) + ((k+1) – 1) C(k+1) = C(k) + k आगमनात्मक परिकल्पना से C(k) का मान प्रतिस्थापित करने पर: C(k+1) = [k(k-1)/2] + k C(k+1) = (k² – k)/2 + 2k/2 C(k+1) = (k² – k + 2k) / 2 C(k+1) = (k² + k) / 2 C(k+1) = k(k+1) / 2 यह वही है जो हमें सिद्ध करना था। इसलिए, गणितीय आगमन के सिद्धांत द्वारा, दिया गया सूत्र सभी पूर्णांकों n ≥ 1 के लिए सत्य है।

प्रश्न 2. (a) हैंडशेकिंग प्रमेय (Handshaking Theorem) का कथन दीजिए और उसे सिद्ध कीजिए। (b) ग्राफ के संदर्भ में निम्नलिखित पदों का उपयुक्त आरेख/उदाहरण के साथ वर्णन कीजिए: (i) वॉक (Walk) (ii) पथ (Path) (iii) सर्किट (Circuit) (iv) चक्र (Cycle) (c) क्या एक द्विपक्षीय ग्राफ (Bipartite graph) का उपग्राफ (subgraph) भी द्विपक्षीय होता है? अपने उत्तर के लिए कारण दीजिए।

उत्तर.

(a) हैंडशेकिंग प्रमेय

कथन: किसी भी अप्रत्यक्ष ग्राफ (undirected graph) G = (V, E) में, सभी शीर्षों (vertices) की कोटियों (degrees) का योग, किनारों (edges) की संख्या का दोगुना होता है। गणितीय रूप से: Σ v∈V deg(v) = 2|E| जहाँ V शीर्षों का समुच्चय है, E किनारों का समुच्चय है, deg(v) शीर्ष v की कोटि है, और |E| किनारों की कुल संख्या है। प्रमाण: एक अप्रत्यक्ष ग्राफ में प्रत्येक किनारा ठीक दो शीर्षों को जोड़ता है। जब हम ग्राफ के सभी शीर्षों की कोटियों का योग करते हैं, तो हम अनिवार्य रूप से प्रत्येक शीर्ष से निकलने वाले किनारों की गिनती कर रहे होते हैं। चूंकि प्रत्येक किनारे के दो समापन बिंदु (endpoints) होते हैं, इसलिए प्रत्येक किनारे को कोटियों के योग में ठीक दो बार गिना जाता है – एक बार इसके प्रत्येक समापन बिंदु के लिए। उदाहरण के लिए, एक किनारा e = {u, v} शीर्ष u की कोटि की गणना में एक बार और शीर्ष v की कोटि की गणना में एक बार योगदान देता है। इसलिए, यदि हम सभी शीर्षों की कोटियों का योग करते हैं, तो कुल योग किनारों की संख्या का ठीक दोगुना होगा। इस प्रकार, Σ v∈V deg(v) = 2|E| सिद्ध होता है। (b) ग्राफ से संबंधित पद

आइए हम निम्नलिखित ग्राफ का उपयोग करके इन पदों को समझें: V = {A, B, C, D, E}, E = {{A,B}, {B,C}, {C,D}, {D,E}, {C,E}, {A,C}} (i) वॉक (Walk): एक वॉक शीर्षों और किनारों का एक वैकल्पिक अनुक्रम होता है, जो एक शीर्ष से शुरू होता है और एक शीर्ष पर समाप्त होता है, जैसे v₀, e₁, v₁, e₂, …, eₖ, vₖ, जहाँ प्रत्येक किनारा eᵢ अपने पूर्ववर्ती शीर्ष vᵢ₋₁ और अनुगामी शीर्ष vᵢ को जोड़ता है। एक वॉक में शीर्षों और किनारों की पुनरावृत्ति हो सकती है। उदाहरण: A-C-D-E-C-B एक वॉक है। इसमें शीर्ष C की पुनरावृत्ति हुई है। (ii) पथ (Path): एक पथ एक ऐसा वॉक होता है जिसमें किसी भी शीर्ष की पुनरावृत्ति नहीं होती है (सिवाय संभवतः पहले और अंतिम के, यदि यह एक बंद वॉक है)। चूँकि कोई भी शीर्ष दोहराया नहीं जाता है, इसलिए कोई भी किनारा भी दोहराया नहीं जाता है। उदाहरण: A-B-C-D-E एक पथ है। इसमें कोई भी शीर्ष दोहराया नहीं गया है। (iii) सर्किट (Circuit): एक सर्किट (या बंद वॉक) एक ऐसा वॉक है जो उसी शीर्ष पर शुरू और समाप्त होता है। इसमें आंतरिक शीर्षों और किनारों की पुनरावृत्ति हो सकती है। उदाहरण: C-D-E-C-B-A-C एक सर्किट है। यह C पर शुरू और समाप्त होता है। (iv) चक्र (Cycle): एक चक्र एक ऐसा सर्किट है जिसमें कम से कम एक किनारा होता है और जिसमें कोई भी शीर्ष (प्रारंभ और अंत शीर्ष को छोड़कर) दोहराया नहीं जाता है। एक चक्र n ≥ 3 शीर्षों वाला एक पथ होता है जो बंद होता है (v₀ = vₙ)। उदाहरण: C-D-E-C एक चक्र है। यह C पर शुरू और समाप्त होता है और कोई अन्य शीर्ष दोहराया नहीं जाता है। A-B-C-A एक और चक्र है। (c) द्विपक्षीय ग्राफ का उपग्राफ

हाँ , एक द्विपक्षीय ग्राफ का कोई भी उपग्राफ हमेशा द्विपक्षीय होता है। कारण: एक ग्राफ G = (V, E) को द्विपक्षीय (bipartite) कहा जाता है यदि इसके शीर्ष समुच्चय V को दो असंयुक्त (disjoint) समुच्चयों V₁ और V₂ में इस प्रकार विभाजित किया जा सकता है कि G का प्रत्येक किनारा V₁ के एक शीर्ष को V₂ के एक शीर्ष से जोड़ता है। V₁ के भीतर या V₂ के भीतर कोई किनारा मौजूद नहीं होता है। अब, मान लीजिए H = (V’, E’) ग्राफ G का एक उपग्राफ है। इसका मतलब है कि V’ ⊆ V और E’ ⊆ E। चूंकि G द्विपक्षीय है, इसलिए G के लिए एक विभाजन (V₁, V₂) मौजूद है। हम H के शीर्षों V’ के लिए एक नया विभाजन (V’₁, V’₂) बना सकते हैं:

• V’₁ = V’ ∩ V₁ (V’ के वे शीर्ष जो V₁ में भी हैं)
• V’₂ = V’ ∩ V₂ (V’ के वे शीर्ष जो V₂ में भी हैं)

चूंकि V₁ और V₂ असंयुक्त हैं, V’₁ और V’₂ भी असंयुक्त होंगे, और V’₁ ∪ V’₂ = V’ होगा। अब, H के किसी भी किनारे e ∈ E’ पर विचार करें। चूंकि E’ ⊆ E, e G का भी एक किनारा है। G की द्विपक्षीय प्रकृति के कारण, e का एक सिरा V₁ में और दूसरा V₂ में होना चाहिए। इसका मतलब है कि H में प्रत्येक किनारे का एक सिरा V’₁ में और दूसरा V’₂ में होगा। V’₁ के भीतर या V’₂ के भीतर कोई किनारा नहीं हो सकता है। इसलिए, उपग्राफ H भी परिभाषा के अनुसार द्विपक्षीय है।

प्रश्न 3. (a) यूलरियन ग्राफ (Eulerian graph) और यूलरियन सर्किट (Eulerian circuit) में अंतर स्पष्ट करें। सिद्ध करें कि नीचे दिया गया ग्राफ यूलरियन है और इसमें एक यूलरियन सर्किट प्रस्तुत करें। (ग्राफ छवि) (b) क्या एक हैमिल्टनियन ग्राफ (Hamiltonian graph) यूलरियन होता है? अपने उत्तर का कारण बताएं। (c) हैमिल्टनियन ग्राफ क्या हैं? किसी भी ग्राफ के हैमिल्टनियन होने के लिए ‘डिराक की कसौटी’ (Dirac’s criterion) और ‘ओरे की कसौटी’ (Ore’s criterion) को लिखें और समझाएं।

उत्तर.

(a) यूलरियन ग्राफ और यूलरियन सर्किट

अंतर:

• यूलरियन सर्किट (Eulerian Circuit): एक कनेक्टेड ग्राफ में एक यूलरियन सर्किट एक ऐसा सर्किट होता है जो ग्राफ के प्रत्येक किनारे (edge) से ठीक एक बार गुजरता है। यह उसी शीर्ष पर शुरू और समाप्त होता है।
• यूलरियन ग्राफ (Eulerian Graph): एक यूलरियन ग्राफ एक ऐसा ग्राफ होता है जिसमें एक यूलरियन सर्किट होता है।

एक कनेक्टेड ग्राफ के यूलरियन होने के लिए आवश्यक और पर्याप्त शर्त यह है कि ग्राफ के प्रत्येक शीर्ष की कोटि (degree) सम (even) होनी चाहिए । दिए गए ग्राफ का विश्लेषण: प्रश्न पत्र में दिया गया ग्राफ अस्पष्ट है और जैसा कि खींचा गया है, उसमें विषम कोटि वाले शीर्ष प्रतीत होते हैं, जिसका अर्थ है कि यह यूलरियन नहीं होगा। उदाहरण के लिए, एक संभावित व्याख्या के तहत, deg(v2)=3 और deg(v6)=1। एक मॉडल उत्तर के रूप में, हम इस अवधारणा को एक स्पष्ट, यूलरियन ग्राफ के साथ प्रदर्शित करेंगे, यह मानते हुए कि प्रश्न में एक मुद्रण त्रुटि थी। उदाहरण यूलरियन ग्राफ: आइए एक ग्राफ G पर विचार करें जिसके शीर्ष V = {a, b, c, d, e} और किनारे E = {{a,b}, {a,c}, {b,c}, {c,d}, {c,e}, {d,e}} हैं। यूलरियन होने का प्रमाण: 1. कनेक्टिविटी: ग्राफ कनेक्टेड है क्योंकि किसी भी दो शीर्षों के बीच एक पथ है। 2. शीर्षों की कोटि:

• deg(a) = 2
• deg(b) = 2
• deg(c) = 4
• deg(d) = 2
• deg(e) = 2

सभी शीर्षों की कोटि सम है। इसलिए, प्रमेय के अनुसार, ग्राफ G यूलरियन है। यूलरियन सर्किट का निर्माण: ग्राफ G में एक यूलरियन सर्किट जो प्रत्येक किनारे से ठीक एक बार गुजरता है, वह है: a → b → c → d → e → c → a यह सर्किट शीर्ष ‘a’ से शुरू होता है, सभी 6 किनारों को कवर करता है, और शीर्ष ‘a’ पर समाप्त होता है। (b) क्या एक हैमिल्टनियन ग्राफ यूलरियन होता है?

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

• हैमिल्टनियन ग्राफ: एक चक्र होता है जो प्रत्येक शीर्ष (vertex) से ठीक एक बार गुजरता है।
• यूलरियन ग्राफ: एक सर्किट होता है जो प्रत्येक किनारे (edge) से ठीक एक बार गुजरता है।

किसी ग्राफ के हैमिल्टनियन होने की शर्त उसकी शीर्ष कनेक्टिविटी से संबंधित है, जबकि यूलरियन होने की शर्त शीर्ष कोटि (सम होनी चाहिए) से संबंधित है। प्रत्युदाहरण (Counterexample): एक ग्राफ पर विचार करें जो हैमिल्टनियन है लेकिन यूलरियन नहीं है। मान लीजिए G एक ऐसा ग्राफ है जिसके शीर्ष V = {1, 2, 3, 4} और किनारे E = {{1,2}, {2,3}, {3,4}, {4,1}, {1,3}} हैं।

• हैमिल्टनियन: ग्राफ में एक हैमिल्टनियन चक्र 1-2-3-4-1 है, जो सभी शीर्षों से गुजरता है। इसलिए, ग्राफ हैमिल्टनियन है।
• यूलरियन: आइए शीर्षों की कोटि की गणना करें:
  • deg(1) = 3
  • deg(2) = 2
  • deg(3) = 3
  • deg(4) = 2

  चूंकि शीर्ष 1 और 3 की कोटि विषम (odd) है, ग्राफ यूलरियन नहीं है।

इस प्रकार, हमने एक ऐसा ग्राफ दिखाया है जो हैमिल्टनियन है लेकिन यूलरियन नहीं है। (c) हैमिल्टनियन ग्राफ और मानदंड

हैमिल्टनियन ग्राफ (Hamiltonian Graphs): एक ग्राफ G को हैमिल्टनियन कहा जाता है यदि इसमें एक हैमिल्टनियन चक्र (Hamiltonian cycle) होता है। एक हैमिल्टनियन चक्र एक साधारण चक्र है जो ग्राफ G के प्रत्येक शीर्ष से ठीक एक बार गुजरता है। यह निर्धारित करने के लिए कोई सरल आवश्यक और पर्याप्त शर्त नहीं है कि कोई ग्राफ हैमिल्टनियन है या नहीं (यह एक NP-पूर्ण समस्या है)। हालांकि, कई पर्याप्त शर्तें हैं जो गारंटी देती हैं कि एक ग्राफ हैमिल्टनियन है। डिराक की कसौटी (Dirac’s Criterion):

कथन: यदि G n ≥ 3 शीर्षों वाला एक साधारण ग्राफ है, जिसमें प्रत्येक शीर्ष की कोटि कम से कम n/2 है (अर्थात, G की न्यूनतम कोटि, δ(G) ≥ n/2), तो G हैमिल्टनियन है। व्याख्या: यह कसौटी कहती है कि यदि किसी ग्राफ में “पर्याप्त” किनारे हैं, इस अर्थ में कि प्रत्येक शीर्ष कम से-कम आधे अन्य शीर्षों से जुड़ा है, तो एक हैमिल्टनियन चक्र का अस्तित्व सुनिश्चित है। यह एक बहुत मजबूत स्थिति है। ओरे की कसौटी (Ore’s Criterion):

कथन: यदि G n ≥ 3 शीर्षों वाला एक साधारण ग्राफ है, जिसमें किसी भी दो असन्निकट (non-adjacent) शीर्षों u और v के लिए, उनकी कोटियों का योग deg(u) + deg(v) ≥ n है, तो G हैमिल्टनियन है। व्याख्या: यह डिराक की कसौटी का एक सामान्यीकरण है। यह आवश्यक नहीं है कि प्रत्येक शीर्ष की कोटि उच्च हो, बल्कि यह कि कोई भी दो शीर्ष जो सीधे नहीं जुड़े हैं, उनके पास सामूहिक रूप से कम से कम n पड़ोसी हों। यदि डिराक की कसौटी पूरी होती है, तो ओरे की कसौटी स्वचालित रूप से पूरी हो जाती है, लेकिन इसका विलोम सत्य नहीं है। ओरे की कसौटी अधिक व्यापक श्रेणी के ग्राफों पर लागू होती है।

प्रश्न 4. (a) गणितीय आगमन (mathematical induction) का उपयोग करके सिद्ध करें कि 2ⁿ > n³, n > 0 के लिए। (b) फलन का व्युत्क्रम (inverse) ज्ञात करें: f(x) = (x-2)/(x+3) (c) उपयुक्त उदाहरण के साथ जटिलताओं (complexities) के ‘P’ और ‘NP’ वर्गों को परिभाषित करें।

उत्तर.

(a) गणितीय आगमन द्वारा प्रमाण

कथन है: 2ⁿ > n³ . प्रश्न में कहा गया है कि यह n > 0 के लिए सत्य है, लेकिन यह गलत है। आइए कुछ छोटे मानों के लिए जांच करें:

• n=1: 2¹ > 1³ (2 > 1) सत्य
• n=2: 2² > 2³ (4 > 8) असत्य
• n=9: 2⁹ > 9³ (512 > 729) असत्य
• n=10: 2¹⁰ > 10³ (1024 > 1000) सत्य

यह असमानता n=1 और सभी पूर्णांकों n ≥ 10 के लिए सत्य है। हम इसे n ≥ 10 के लिए सिद्ध करेंगे। आधार मामला (Base Case): n = 10 के लिए 2¹⁰ = 1024 10³ = 1000 चूंकि 1024 > 1000, आधार मामला सत्य है। आगमनात्मक परिकल्पना (Inductive Hypothesis): मान लीजिए कि असमानता किसी पूर्णांक k ≥ 10 के लिए सत्य है। अर्थात, 2ᵏ > k³ आगमनात्मक चरण (Inductive Step): हमें सिद्ध करना है कि यह n = k+1 के लिए भी सत्य है। हमें दिखाना है कि 2ᵏ⁺¹ > (k+1)³ । LHS से शुरू करते हैं: 2ᵏ⁺¹ = 2 * 2ᵏ आगमनात्मक परिकल्पना का उपयोग करते हुए (2ᵏ > k³), हम लिख सकते हैं: 2ᵏ⁺¹ > 2 * k³ अब हमें यह दिखाना है कि 2k³ > (k+1)³। (k+1)³ = k³ + 3k² + 3k + 1 तो हमें दिखाना है: 2k³ > k³ + 3k² + 3k + 1 k³ > 3k² + 3k + 1 चूंकि k ≥ 10, हम जानते हैं कि k³ को k², k, और 1 के गुणजों के रूप में लिखा जा सकता है। k³ = k * k²। चूंकि k ≥ 10, k > 4। तो k³ > 4k²। 4k² = 3k² + k²। हमें सिद्ध करना है कि k³ > 3k² + 3k + 1। यह दिखाने के लिए पर्याप्त है कि k² > 3k + 1, जब k ≥ 10। k² – 3k – 1 > 0। k(k-3) – 1 > 0। चूंकि k ≥ 10, k(k-3) – 1 निश्चित रूप से 0 से बड़ा है (जैसे, 10(7)-1 = 69 > 0)। अतः, k³ > 3k² + 3k + 1 सत्य है। इसलिए, 2ᵏ⁺¹ > 2k³ = k³ + k³ > k³ + (3k² + 3k + 1) = (k+1)³। इस प्रकार, 2ᵏ⁺¹ > (k+1)³ सिद्ध होता है। गणितीय आगमन द्वारा, 2ⁿ > n³ सभी पूर्णांकों n ≥ 10 के लिए सत्य है। (b) फलन का व्युत्क्रम

दिया गया फलन है: f(x) = (x-2) / (x+3) व्युत्क्रम फलन, f⁻¹(x) ज्ञात करने के लिए, इन चरणों का पालन करें: 1. f(x) को y से बदलें: y = (x-2) / (x+3) 2. x और y को आपस में बदलें: x = (y-2) / (y+3) 3. y के लिए हल करें: x(y+3) = y-2 xy + 3x = y – 2 y वाले पदों को एक तरफ ले जाएँ: xy – y = -3x – 2 y को कॉमन निकालें: y(x – 1) = -3x – 2 y = (-3x – 2) / (x – 1) y = -(3x + 2) / -(1 – x) y = (3x + 2) / (1 – x)

4. y को f⁻¹(x) से बदलें: f⁻¹(x) = (3x + 2) / (1 – x)

फलन f(x) का डोमेन R – {-3} है और रेंज R – {1} है। व्युत्क्रम फलन f⁻¹(x) का डोमेन R – {1} है। (c) ‘P’ और ‘NP’ जटिलता वर्ग

कम्प्यूटेशनल जटिलता सिद्धांत में, ‘P’ और ‘NP’ निर्णय समस्याओं (decision problems) के महत्वपूर्ण वर्ग हैं। P (Polynomial Time): ‘P’ उन सभी निर्णय समस्याओं का वर्ग है जिन्हें एक नियतात्मक ट्यूरिंग मशीन (deterministic Turing machine) द्वारा बहुपदीय समय (polynomial time) में हल किया जा सकता है। इसका मतलब है कि समस्या को हल करने के लिए आवश्यक समय इनपुट के आकार n की किसी घात, जैसे O(n), O(n²), O(n³) आदि से सीमित होता है। ‘P’ में समस्याओं को आमतौर पर “कुशलतापूर्वक हल करने योग्य” माना जाता है। उदाहरण:

• सॉर्टिंग (Sorting): n तत्वों की एक सूची को सॉर्ट करना। मर्ज सॉर्ट या क्विकसॉर्ट जैसे एल्गोरिदम इसे O(n log n) समय में कर सकते हैं, जो बहुपदीय है।
• सबसे छोटा पथ (Shortest Path): एक ग्राफ में दो शीर्षों के बीच सबसे छोटा पथ खोजना। दिज्क्स्ट्रा का एल्गोरिथ्म (Dijkstra’s algorithm) इसे बहुपदीय समय में हल करता है।

NP (Nondeterministic Polynomial Time): ‘NP’ उन सभी निर्णय समस्याओं का वर्ग है जिनके लिए, यदि उत्तर “हाँ” है, तो उस “हाँ” उत्तर के प्रमाण को एक नियतात्मक ट्यूरिंग मशीन द्वारा बहुपदीय समय में सत्यापित (verified) किया जा सकता है। इसका मतलब यह नहीं है कि समस्या को हल करना कठिन है, बल्कि यह है कि समाधान की जाँच करना आसान है। NP का अर्थ “गैर-नियतात्मक बहुपदीय समय” है, जो एक गैर-नियतात्मक ट्यूरिंग मशीन पर बहुपदीय समय में हल करने योग्य समस्याओं को संदर्भित करता है। यह स्पष्ट है कि P ⊆ NP, क्योंकि यदि किसी समस्या को बहुपदीय समय में हल किया जा सकता है, तो उसके समाधान को निश्चित रूप से बहुपदीय समय में सत्यापित किया जा सकता है। उदाहरण:

• हैमिल्टनियन चक्र समस्या (Hamiltonian Cycle Problem): क्या किसी दिए गए ग्राफ में हैमिल्टनियन चक्र है? यदि कोई आपको एक चक्र देता है, तो यह जांचना बहुत आसान (बहुपदीय समय) है कि क्या यह वास्तव में एक हैमिल्टनियन चक्र है (क्या यह सभी शीर्षों से गुजरता है और क्या यह एक वैध चक्र है)। हालांकि, ऐसा चक्र खोजना बहुत कठिन माना जाता है।
• बूलियन संतुष्टि समस्या (SAT): क्या किसी दिए गए बूलियन सूत्र के लिए चरों का ऐसा मान निर्दिष्ट करना संभव है जो सूत्र को सत्य बना दे? समाधान (मानों का निर्दिष्ट सेट) को सत्यापित करना आसान है, लेकिन इसे खोजना कठिन है।

कंप्यूटर विज्ञान में सबसे बड़ी अनसुलझी समस्याओं में से एक यह है कि क्या P = NP है। अधिकांश शोधकर्ता मानते हैं कि P ≠ NP, जिसका अर्थ है कि ऐसी समस्याएँ हैं जिनकी जाँच करना आसान है लेकिन हल करना मौलिक रूप से कठिन है।

प्रश्न 5. (a) नीचे दिए गए परिमित ऑटोमेटा (finite automata) के लिए अवस्था संक्रमण सारणी (state transition table) तैयार करें और स्वीकृत भाषा के लिए नियमित व्यंजक (regular expression) निकालें। क्या यह ऑटोमेटा इनपुट स्ट्रिंग “aaab” को स्वीकार करेगा, जाँच करें। (ऑटोमेटा छवि) (b) निम्नलिखित पर संक्षिप्त नोट्स लिखें: (i) शीर्ष रंगाई (Vertex colouring) (ii) समावेश-बहिष्करण सिद्धांत (Inclusion-Exclusion Principle) (iii) अनिर्णेय समस्या (Undecidable problem) (iv) मीली मशीनें (Mealy machines) (v) सममित संबंध (Symmetric relations)

उत्तर.

(a) परिमित ऑटोमेटा

दिए गए परिमित ऑटोमेटा का विश्लेषण करने पर:

• अवस्थाएँ (States): {S0, S1, S2}
• प्रारंभिक अवस्था (Start State): S0
• अंतिम अवस्था (Final State): S2
• वर्णमाला (Alphabet): {a, b}

संक्रमण इस प्रकार हैं: δ(S0, a) = S1, δ(S0, b) = S2 δ(S1, a) = S0, δ(S1, b) = S2 δ(S2, a) = S2, δ(S2, b) = S2 अवस्था संक्रमण सारणी (State Transition Table):

वर्तमान अवस्था

इनपुट ‘a’

इनपुट ‘b’

→ S0

S1

S2

S1

S0

S2

* S2

S2

S2

(→ प्रारंभिक अवस्था को दर्शाता है, * अंतिम अवस्था को दर्शाता है) नियमित व्यंजक (Regular Expression): ऑटोमेटा का अवलोकन करने पर, हम देखते हैं कि जैसे ही कोई इनपुट ‘b’ पढ़ा जाता है, मशीन अवस्था S2 में चली जाती है। अवस्था S2 एक “सिंक” या “ट्रैप” अवस्था है, क्योंकि एक बार इस अवस्था में पहुंचने के बाद, मशीन किसी भी इनपुट (‘a’ या ‘b’) के लिए इसी अवस्था में रहती है। चूंकि S2 एक अंतिम/स्वीकार्य अवस्था है, इसका मतलब है कि कोई भी स्ट्रिंग जो मशीन को अवस्था S2 में ले जाती है, वह स्वीकार कर ली जाएगी। ऐसा तब होता है जब स्ट्रिंग में कम से कम एक ‘b’ होता है।

• यदि स्ट्रिंग में कोई ‘b’ नहीं है (अर्थात, यह केवल ‘a’ से बनी है), तो मशीन S0 और S1 के बीच दोलन करती रहेगी और कभी भी S2 तक नहीं पहुंचेगी।
• जैसे ही पहला ‘b’ आता है, मशीन S2 में पहुंच जाती है और वहीं रहती है, जिससे स्ट्रिंग स्वीकार हो जाती है।

इसलिए, यह ऑटोमेटा उन सभी स्ट्रिंग्स की भाषा को स्वीकार करता है जिनमें कम से कम एक ‘b’ होता है। इस भाषा के लिए नियमित व्यंजक है: a b(a+b) वैकल्पिक रूप से, इसे (a|b) b(a|b) भी लिखा जा सकता है। इनपुट स्ट्रिंग “aaab” की जाँच: आइए हम स्ट्रिंग “aaab” के लिए ऑटोमेटा के संचालन का पता लगाएं: 1. प्रारंभिक अवस्था S0 है। 2. इनपुट ‘a’: δ(S0, a) → S1 3. इनपुट ‘a’: δ(S1, a) → S0 4. इनपुट ‘a’: δ(S0, a) → S1 5. इनपुट ‘b’: δ(S1, b) → S2 स्ट्रिंग के अंत में, मशीन अवस्था S2 में है। चूंकि S2 एक अंतिम (स्वीकार्य) अवस्था है, इसलिए स्ट्रिंग “aaab” को ऑटोमेटा द्वारा स्वीकार किया जाएगा । (b) संक्षिप्त नोट्स

(i) शीर्ष रंगाई (Vertex Colouring): शीर्ष रंगाई एक ग्राफ के शीर्षों को “रंग” निर्दिष्ट करने की एक विधि है, इस शर्त के साथ कि कोई भी दो आसन्न (adjacent) शीर्ष एक ही रंग के नहीं हो सकते। किसी ग्राफ G के लिए आवश्यक रंगों की न्यूनतम संख्या को उसका वर्णिक संख्या (chromatic number) कहा जाता है, जिसे χ(G) से दर्शाया जाता है। शीर्ष रंगाई का उपयोग कई वास्तविक दुनिया की समस्याओं को मॉडल करने के लिए किया जाता है, जैसे:

• समय-सारणी निर्धारण: परीक्षाओं या कक्षाओं को इस तरह से निर्धारित करना कि जिन छात्रों को एक ही समय में दो परीक्षाओं में बैठना है, उन्हें कोई टकराव न हो।
• नक्शा रंगाई: एक नक्शे पर देशों को रंगना ताकि कोई भी दो पड़ोसी देश एक ही रंग के न हों।

(ii) समावेश-बहिष्करण सिद्धांत (Inclusion-Exclusion Principle): यह एक गणना तकनीक है जो परिमित समुच्चयों के संघ में तत्वों की संख्या ज्ञात करने की अनुमति देती है। यह ओवरलैपिंग समुच्चयों के कारण होने वाली दोहरी गिनती को ठीक करता है। दो समुच्चयों A और B के लिए, सिद्धांत कहता है: |A ∪ B| = |A| + |B| – |A ∩ B| तीन समुच्चयों A, B और C के लिए: |A ∪ B ∪ C| = |A| + |B| + |C| – (|A ∩ B| + |A ∩ C| + |B ∩ C|) + |A ∩ B ∩ C| यह सिद्धांत अधिक संख्या में समुच्चयों के लिए भी सामान्यीकृत किया जा सकता है। (iii) अनिर्णेय समस्या (Undecidable Problem): एक अनिर्णेय समस्या एक निर्णय समस्या है जिसके लिए यह सिद्ध हो चुका है कि एक ऐसा एल्गोरिथ्म बनाना असंभव है जो हमेशा सही ‘हाँ’ या ‘नहीं’ उत्तर पर समाप्त होता है। कोई भी एल्गोरिथ्म जो ऐसी समस्या को हल करने का प्रयास करता है, कुछ इनपुट के लिए या तो हमेशा के लिए चलेगा या गलत उत्तर देगा। सबसे प्रसिद्ध उदाहरण हाल्टिंग समस्या (Halting Problem) है: यह निर्धारित करना कि क्या एक मनमाना कंप्यूटर प्रोग्राम और एक इनपुट दिया गया है, क्या प्रोग्राम अंततः रुक जाएगा (halt) या हमेशा के लिए चलता रहेगा। एलन ट्यूरिंग ने 1936 में साबित किया कि इस समस्या के लिए कोई सामान्य एल्गोरिथ्म मौजूद नहीं है। (iv) मीली मशीनें (Mealy Machines): एक मीली मशीन एक प्रकार की परिमित अवस्था मशीन (finite state machine – FSM) है जिसका आउटपुट वर्तमान अवस्था (current state) और वर्तमान इनपुट (current input) दोनों पर निर्भर करता है। मीली मशीनों में, आउटपुट अवस्था संक्रमणों (transitions) से जुड़े होते हैं। इसे मूर मशीन (Moore machine) से अलग किया जा सकता है, जहाँ आउटपुट केवल वर्तमान अवस्था पर निर्भर करता है। मीली मशीनों को अक्सर कम अवस्थाओं की आवश्यकता होती है और वे इनपुट परिवर्तनों पर तेजी से प्रतिक्रिया कर सकती हैं। इनका उपयोग अनुक्रमिक सर्किट डिजाइन और संचार प्रोटोकॉल में किया जाता है। (v) सममित संबंध (Symmetric Relations): एक समुच्चय A पर एक द्विआधारी संबंध R को सममित कहा जाता है यदि A में सभी a और b के लिए, जब भी (a, b) R में होता है, तो (b, a) भी R में होता है। औपचारिक रूप से: ∀ a, b ∈ A, (aRb → bRa) उदाहरण:

• पूर्णांकों पर “बराबर है” (=) संबंध सममित है, क्योंकि यदि a = b है, तो b = a भी है।
• लोगों के एक समूह पर “एक सहोदर है” (is a sibling of) संबंध सममित है।
• पूर्णांकों पर “से कम है” (<) संबंध सममित नहीं है, क्योंकि यदि a < b है, तो b < a सत्य नहीं है।

एक ग्राफ में, एक सममित संबंध को एक अप्रत्यक्ष ग्राफ के रूप में दर्शाया जा सकता है, जहाँ a और b के बीच एक किनारा संबंध (a, b) और (b, a) दोनों का प्रतिनिधित्व करता है।