The IGNOU MCS-033 Solved Question Paper PDF Download page is designed to help students access high-quality exam resources in one place. Here, you can find ignou solved question paper IGNOU Previous Year Question paper solved PDF that covers all important questions with detailed answers. This page provides IGNOU all Previous year Question Papers in one PDF format, making it easier for students to prepare effectively.
- IGNOU MCS-033 Solved Question Paper in Hindi
- IGNOU MCS-033 Solved Question Paper in English
- IGNOU Previous Year Solved Question Papers (All Courses)
Whether you are looking for IGNOU Previous Year Question paper solved in English or ignou previous year question paper solved in hindi, this page offers both options to suit your learning needs. These solved papers help you understand exam patterns, improve answer writing skills, and boost confidence for upcoming exams.
IGNOU MCS-033 Solved Question Paper PDF
This section provides IGNOU MCS-033 Solved Question Paper PDF in both Hindi and English. These ignou solved question paper IGNOU Previous Year Question paper solved PDF include detailed answers to help you understand exam patterns and improve your preparation. You can also access IGNOU all Previous year Question Papers in one PDF for quick and effective revision before exams.
IGNOU MCS-033 Previous Year Solved Question Paper in Hindi
Q1. (a) फिबोनाची श्रृंखला के लिए पुनरावृत्ति संबंध लिखें। 2 (b) सत्यापित करें कि T(n) = 2^n + n – 2 पुनरावृत्ति संबंध का हल है: 4 T(n) = 2T(n-1) + n, n>=2 T(1)=1 (c) समतलीय ग्राफ क्या है? सिद्ध करें कि K4 एक समतलीय ग्राफ है। 4 (d) सत्यापित करें कि ग्राफ का निम्नलिखित डिग्री अनुक्रम संभव नहीं है: 4 3, 2, 1, 1, 0 उपयुक्त तर्क से औचित्य सिद्ध करें। (e) ज्यामितीय श्रेणी का जनक फलन ज्ञात कीजिए। 4 (f) पुनरावृत्ति संबंध के क्रम और घात का निर्धारण करें: 2 a_n = (a_{n-1})^2 + n^2
Ans. (a) फिबोनाची श्रृंखला एक ऐसी श्रृंखला है जिसमें प्रत्येक संख्या दो पूर्ववर्ती संख्याओं का योग होती है। इसे F_n द्वारा दर्शाया जाता है।
श्रृंखला 0, 1, 1, 2, 3, 5, 8, … से शुरू होती है।
फिबोनाची श्रृंखला के लिए पुनरावृत्ति संबंध है:
F_n = F_{n-1} + F_{n-2} , n ≥ 2 के लिए
प्रारंभिक शर्तों के साथ:
F_0 = 0 और F_1 = 1 ।
(b) दिए गए पुनरावृत्ति संबंध को सत्यापित करने के लिए, हम दिए गए हल T(n) = 2^n + n – 2 को संबंध में प्रतिस्थापित करेंगे।
दिया गया संबंध है: T(n) = 2T(n-1) + n
बायां पक्ष (LHS) = T(n) = 2^n + n – 2
अब, हम दाएं पक्ष (RHS) की गणना करते हैं:
RHS = 2T(n-1) + n
पहले, T(n-1) ज्ञात करें:
T(n-1) = 2^(n-1) + (n-1) – 2
अब इसे RHS में प्रतिस्थापित करें:
RHS = 2 * [2^(n-1) + (n-1) – 2] + n
RHS = 2 * 2^(n-1) + 2(n-1) – 2(2) + n
RHS = 2^n + 2n – 2 – 4 + n
RHS = 2^n + 3n – 6
LHS (2^n + n – 2) और RHS (2^n + 3n – 6) की तुलना करने पर, हम देखते हैं कि वे बराबर नहीं हैं। इसलिए, दिया गया हल T(n) = 2^n + n – 2 सही नहीं है।
टिप्पणी: प्रश्न में या प्रस्तावित हल में एक टंकण त्रुटि हो सकती है। यदि हल T(n) = 2^(n+1) – n – 2 होता, तो यह T(n) = 2T(n-1) + n + 2 के लिए एक हल होता। यदि प्रश्न में पुनरावृत्ति T(n) = 2T(n-1) – n + 2 होती, तो T(n)=2^n + n – 2 एक सही हल होता। प्रश्न में दिए गए मानों के अनुसार, यह सत्यापित नहीं होता है।
(c) समतलीय ग्राफ (Planar Graph): एक ग्राफ को समतलीय कहा जाता है यदि इसे एक समतल पर इस तरह से बनाया जा सकता है कि इसके किनारे केवल उनके अंतिम शीर्षों पर ही प्रतिच्छेद करते हैं। दूसरे शब्दों में, कोई भी दो किनारे एक-दूसरे को नहीं काटते हैं।
K4 का समतलीय प्रमाण:
K4 एक पूर्ण ग्राफ है जिसमें 4 शीर्ष (vertices) होते हैं। एक पूर्ण ग्राफ में, प्रत्येक शीर्ष हर दूसरे शीर्ष से जुड़ा होता है। K4 में 4 शीर्ष और (4*3)/2 = 6 किनारे होते हैं।
मान लीजिए शीर्ष V = {v1, v2, v3, v4} हैं।
किनारे E = {(v1, v2), (v1, v3), (v1, v4), (v2, v3), (v2, v4), (v3, v4)} हैं।
इसे समतलीय साबित करने के लिए, हमें इसे बिना किसी किनारे के प्रतिच्छेदन के बनाना होगा।
1. शीर्षों v1, v2, और v3 को एक त्रिभुज के रूप में रखें। किनारे (v1, v2), (v2, v3), और (v3, v1) खींचें। यह बिना किसी प्रतिच्छेदन के है। 2. चौथे शीर्ष v4 को इस त्रिभुज के अंदर रखें। 3. अब, v4 को अन्य तीन शीर्षों से जोड़ें: (v4, v1), (v4, v2), (v4, v3)। ये सभी किनारे त्रिभुज के अंदर से खींचे जा सकते हैं बिना एक-दूसरे को या त्रिभुज के किनारों को काटे। नीचे एक समतलीय निरूपण दिया गया है: v1 /|\ / | \ / | \ v2–v4–v3 इस निरूपण में, कोई भी दो किनारे एक दूसरे को नहीं काटते हैं। अतः, K4 एक समतलीय ग्राफ है।
(d) टिप्पणी: प्रश्न पत्र में दिए गए अनुक्रम “3, 2, , , , 0” में खाली स्थान होने के कारण यह अधूरा है। हम एक संभावित पूर्ण अनुक्रम “3, 2, 1, 1, 0” मान रहे हैं, जो अक्सर इस प्रकार के प्रश्नों में उपयोग किया जाता है।
दिया गया डिग्री अनुक्रम: D = (3, 2, 1, 1, 0)
तर्क (Argument): ग्राफ सिद्धांत में हैंडशेकिंग लेम्मा (Handshaking Lemma) के अनुसार, किसी भी ग्राफ में सभी शीर्षों की डिग्री का योग हमेशा किनारों की संख्या का दोगुना होता है।
Σ deg(v) = 2 |E|
चूंकि 2|E| एक सम संख्या है, इसलिए किसी भी ग्राफ के लिए डिग्री का योग हमेशा एक सम संख्या होनी चाहिए।
आइए दिए गए डिग्री अनुक्रम के लिए डिग्री का योग ज्ञात करें:
योग = 3 + 2 + 1 + 1 + 0 = 7
यहां, डिग्री का योग 7 है, जो एक विषम संख्या है।
हैंडशेकिंग लेम्मा के अनुसार, डिग्री का योग विषम नहीं हो सकता है।
इसलिए, (3, 2, 1, 1, 0) डिग्री अनुक्रम वाला कोई भी सरल ग्राफ मौजूद नहीं हो सकता है। यह एक असंभव डिग्री अनुक्रम है।
(e) ज्यामितीय श्रेणी (Geometric Progression) का सामान्य रूप है: a, ar, ar^2, ar^3, …
इस अनुक्रम को {a_n} = {ar^n} के रूप में लिखा जा सकता है, जहाँ n = 0, 1, 2, …
एक अनुक्रम {a_n} का जनक फलन (Generating Function) घात श्रृंखला G(x) = Σ (a_n * x^n) द्वारा परिभाषित किया गया है।
ज्यामितीय श्रेणी के लिए जनक फलन की गणना करने के लिए, हम श्रृंखला लिखते हैं:
G(x) = a_0 + a_1 x + a_2 x^2 + a_3*x^3 + …
मानों को प्रतिस्थापित करने पर:
G(x) = a + (ar)x + (ar^2)x^2 + (ar^3)x^3 + …
G(x) = a [1 + (rx) + (rx)^2 + (rx)^3 + …]
ब्रैकेट के अंदर की श्रृंखला एक अनंत ज्यामितीय श्रृंखला है जिसका पहला पद 1 और सार्व अनुपात (common ratio) ‘rx’ है। एक अनंत ज्यामितीय श्रृंखला का योग S = 1 / (1 – R) होता है, बशर्ते |R| < 1।
यहां, R = rx। तो, |rx| < 1 मानते हुए, श्रृंखला का योग 1 / (1 – rx) है।
इसलिए, जनक फलन है:
G(x) = a / (1 – rx)
(f) दिया गया पुनरावृत्ति संबंध है: a_n = (a_{n-1})^2 + n^2
क्रम (Order): एक पुनरावृत्ति संबंध का क्रम सबसे बड़े और सबसे छोटे सूचकांक (subscript) के बीच का अंतर होता है। इस संबंध में, सबसे बड़ा सूचकांक ‘n’ है और सबसे छोटा ‘n-1’ है।
क्रम = n – (n-1) = 1
अतः, संबंध का क्रम 1 है।
घात (Degree): एक पुनरावृत्ति संबंध की घात अनुक्रम के पदों (जैसे a_n, a_{n-1}, आदि) की उच्चतम घात (power) होती है, जब संबंध को उनके बहुपद के रूप में व्यक्त किया जाता है।
दिए गए संबंध में, पद a_{n-1} की घात 2 है ((a_{n-1})^2)।
अतः, संबंध की घात 2 है।
Q2. (a) तुल्याकारिता क्या है? ग्राफों के तुल्याकारी होने की शर्तें लिखें। दिखाएँ कि निम्नलिखित ग्राफ G और H तुल्याकारी नहीं हैं: 5 
(b) एक उपयुक्त आरेख के साथ ‘ग्राफ G का पूरक’ शब्द का वर्णन करें। यदि G(V, E) एक (p, q) ग्राफ है, तो ग्राफ G के पूरक में शीर्षों की संख्या और किनारों की संख्या निर्धारित करें। 5
Ans. (a) तुल्याकारिता (Isomorphism): दो ग्राफ G1 और G2 को तुल्याकारी (isomorphic) कहा जाता है यदि उनके बीच एक-से-एक और आच्छादक (bijective) फलन f: V(G1) → V(G2) मौजूद हो, जो आसन्नता (adjacency) को संरक्षित रखता हो। इसका अर्थ है कि G1 में कोई भी दो शीर्ष u और v एक किनारे से जुड़े हुए हैं यदि और केवल यदि G2 में f(u) और f(v) एक किनारे से जुड़े हुए हैं। संक्षेप में, तुल्याकारी ग्राफ संरचनात्मक रूप से समान होते हैं, केवल उनके शीर्षों के नाम अलग हो सकते हैं।
ग्राफों के तुल्याकारी होने के लिए आवश्यक शर्तें (Invariants): यदि दो ग्राफ तुल्याकारी हैं, तो उन्हें निम्नलिखित गुणों को साझा करना चाहिए:
- उनके पास समान संख्या में शीर्ष होने चाहिए।
- उनके पास समान संख्या में किनारे होने चाहिए।
- उनके पास समान डिग्री अनुक्रम होना चाहिए (अर्थात, दोनों ग्राफों में समान डिग्री वाले शीर्षों की संख्या समान होनी चाहिए)।
- उनके पास समान लंबाई के चक्रों की संख्या समान होनी चाहिए।
दिए गए ग्राफ G और H का विश्लेषण:
टिप्पणी: प्रश्न में दिए गए ग्राफ G और H वास्तव में तुल्याकारी हैं। दोनों 4 शीर्षों और 4 किनारों वाले चक्र ग्राफ (C4) हैं। हम इसे प्रदर्शित करेंगे और फिर गैर-तुल्याकारी ग्राफों का एक उदाहरण प्रदान करेंगे।
ग्राफ G: शीर्ष: {a, b, c, d}, किनारे: {(a,b), (b,c), (c,d), (d,a)} डिग्री अनुक्रम: सभी शीर्षों (a, b, c, d) की डिग्री 2 है। अनुक्रम (2, 2, 2, 2) है।
ग्राफ H: शीर्ष: {s, t, u, v}, किनारे: {(s,t), (t,u), (u,v), (v,s)} डिग्री अनुक्रम: सभी शीर्षों (s, t, u, v) की डिग्री 2 है। अनुक्रम (2, 2, 2, 2) है। चूंकि दोनों ग्राफों में समान संख्या में शीर्ष (4), समान संख्या में किनारे (4), और समान डिग्री अनुक्रम (2,2,2,2) हैं, वे तुल्याकारी हो सकते हैं। एक तुल्याकारिता फलन f है: f(a) = s, f(b) = t, f(c) = u, f(d) = v यह फलन आसन्नता को संरक्षित रखता है (उदाहरण के लिए, G में (a,b) एक किनारा है, और H में (f(a), f(b)) = (s,t) भी एक किनारा है)। अतः G और H तुल्याकारी हैं । गैर-तुल्याकारी ग्राफ का उदाहरण: यह दिखाने के लिए कि दो ग्राफ तुल्याकारी नहीं हैं, हमें एक ऐसा गुण खोजना होगा जो दोनों में भिन्न हो। निम्नलिखित दो ग्राफों पर विचार करें, G’ और H’, दोनों में 4 शीर्ष और 3 किनारे हैं। G’: एक पथ ग्राफ P4। शीर्ष: {1, 2, 3, 4}, किनारे: {(1,2), (2,3), (3,4)}। डिग्री अनुक्रम: (1, 2, 2, 1)। H’: एक स्टार ग्राफ K1,3। शीर्ष: {A, B, C, D}, किनारे: {(A,B), (A,C), (A,D)}। डिग्री अनुक्रम: (3, 1, 1, 1)। चूंकि G’ और H’ के डिग्री अनुक्रम भिन्न हैं, वे तुल्याकारी नहीं हो सकते।
(b) ग्राफ G का पूरक (Complement of a Graph G): एक सरल ग्राफ G का पूरक, जिसे G̅ (G-bar) से दर्शाया जाता है, एक ऐसा ग्राफ है जिसमें G के समान शीर्ष समुच्चय होता है। G̅ में दो शीर्ष एक किनारे से जुड़े होते हैं यदि और केवल यदि वे G में एक किनारे से नहीं जुड़े होते हैं।
उदाहरण के साथ विवरण: मान लीजिए G एक ग्राफ है जिसमें V = {1, 2, 3, 4} और किनारे E = {(1,2), (2,3), (3,4), (4,1)} हैं। यह एक चक्र ग्राफ C4 है। G (C4): 1–2 | | 4–3 G का पूरक, G̅, में भी वही शीर्ष {1, 2, 3, 4} होंगे। हम G̅ में उन सभी किनारों को जोड़ते हैं जो G में नहीं हैं। G में मौजूद किनारे हैं (1,2), (2,3), (3,4), (4,1)। K4 (4 शीर्षों पर पूर्ण ग्राफ) में कुल संभावित किनारे हैं (1,2), (1,3), (1,4), (2,3), (2,4), (3,4)। G̅ के किनारे = (K4 के किनारे) – (G के किनारे)
E(G̅) = {(1,3), (2,4)} G̅ (दो अलग-अलग किनारे): 1 2 / / 3 4 \ \ 2 (गलत चित्र, सही है:) 1—-3 2—-4 (दो वियुक्त किनारे) तो, G̅ में दो अलग-अलग किनारे होते हैं जो शीर्षों को जोड़ते हैं। पूरक में शीर्षों और किनारों की संख्या: मान लीजिए G(V, E) एक (p, q) ग्राफ है, जिसका अर्थ है:
- p = शीर्षों की संख्या = |V|
- q = किनारों की संख्या = |E|
1. पूरक G̅ में शीर्षों की संख्या: पूरक ग्राफ में मूल ग्राफ के समान ही शीर्ष समुच्चय होता है। इसलिए, G̅ में शीर्षों की संख्या p है।
2. पूरक G̅ में किनारों की संख्या: p शीर्षों पर एक पूर्ण ग्राफ (Kp) में किनारों की कुल संख्या C(p, 2) = p(p-1)/2 होती है। पूरक ग्राफ के किनारे वे होते हैं जो पूर्ण ग्राफ में होते हैं लेकिन मूल ग्राफ में नहीं होते हैं। इसलिए, G̅ में किनारों की संख्या, |E(G̅)|, है: |E(G̅)| = (Kp में किनारों की संख्या) – (G में किनारों की संख्या) |E(G̅)| = p(p-1)/2 – q
Q3. (a) हैमिल्टनीय ग्राफ की परिभाषा दीजिए। नीचे दिया गया ग्राफ हैमिल्टनीय है या नहीं? औचित्य सिद्ध करें। 5 
(b) एक ग्राफ के लिए वर्णिक संख्या को परिभाषित करें। 3 उपरोक्त ग्राफ की वर्णिक संख्या ज्ञात कीजिए। (c) एक ट्री और एक विस्तरित ट्री के बीच अंतर करें। 2
Ans. (a) हैमिल्टनीय ग्राफ (Hamiltonian Graph): एक ग्राफ G को हैमिल्टनीय कहा जाता है यदि इसमें एक हैमिल्टनीय चक्र होता है। एक हैमिल्टनीय चक्र एक बंद पथ (closed path) है जो ग्राफ के प्रत्येक शीर्ष से ठीक एक बार गुजरता है और प्रारंभिक शीर्ष पर लौटता है। (प्रारंभिक और अंतिम शीर्षों को छोड़कर कोई भी शीर्ष दोहराया नहीं जाता है)।
दिए गए ग्राफ का विश्लेषण: दिया गया ग्राफ 5 शीर्षों वाला एक व्हील ग्राफ (Wheel Graph) है, जिसे W5 के रूप में जाना जाता है। इसमें एक बाहरी चक्र (v1, v2, v3, v4) और एक केंद्रीय शीर्ष (v5) होता है जो बाहरी चक्र के सभी शीर्षों से जुड़ा होता है।
औचित्य (Justification): हमें यह जांचना है कि क्या कोई ऐसा चक्र है जो सभी 5 शीर्षों (v1, v2, v3, v4, v5) से होकर गुजरता है। आइए एक पथ बनाने का प्रयास करें:
v1 → v2 → v3 → v4 → v5 → v1
यह पथ सभी 5 शीर्षों से होकर गुजरता है और प्रारंभिक शीर्ष v1 पर समाप्त होता है। आइए किनारों की जांच करें:
- (v1, v2) – मौजूद है
- (v2, v3) – मौजूद है
- (v3, v4) – मौजूद नहीं है (ग्राफ में v3 और v4 के बीच सीधा किनारा नहीं है)। इसलिए यह पथ मान्य नहीं है।
आइए एक और पथ प्रयास करें:
v1 → v2 → v3 → v5 → v4 → v1
आइए इस चक्र में किनारों की जांच करें:
- (v1, v2) – मौजूद है
- (v2, v3) – मौजूद है
- (v3, v5) – मौजूद है
- (v5, v4) – मौजूद है
- (v4, v1) – मौजूद है
यह चक्र v1 → v2 → v3 → v5 → v4 → v1 सभी 5 शीर्षों से ठीक एक बार गुजरता है और एक वैध चक्र है।
चूंकि ग्राफ में एक हैमिल्टनीय चक्र मौजूद है, इसलिए दिया गया ग्राफ हैमिल्टनीय है।
(b) वर्णिक संख्या (Chromatic Number): एक ग्राफ G की वर्णिक संख्या, जिसे χ(G) से दर्शाया जाता है, G के शीर्षों को रंगने के लिए आवश्यक न्यूनतम रंगों की संख्या है, ताकि कोई भी दो आसन्न (adjacent) शीर्षों का रंग समान न हो। इस प्रकार की रंगाई को उचित शीर्ष रंगाई (proper vertex coloring) कहा जाता है।
उपरोक्त ग्राफ की वर्णिक संख्या ज्ञात करना: ग्राफ W5 है। 1. ग्राफ में कई त्रिभुज (3-चक्र) हैं, उदाहरण के लिए, (v1, v2, v5) एक त्रिभुज है। 2. एक त्रिभुज के शीर्षों को रंगने के लिए कम से-कम 3 अलग-अलग रंगों की आवश्यकता होती है, क्योंकि तीनों शीर्ष एक-दूसरे के आसन्न होते हैं। 3. इसलिए, ग्राफ की वर्णिक संख्या कम से-कम 3 है, अर्थात, χ(G) ≥ 3 । अब, देखते हैं कि क्या हम ग्राफ को 3 रंगों से रंग सकते हैं। मान लीजिए रंग हैं C1, C2, C3।
- केंद्रीय शीर्ष v5 को रंग C1 दें: color(v5) = C1।
- अब बाहरी चक्र (v1, v2, v3, v4) को रंगना है। इनमें से कोई भी C1 नहीं हो सकता क्योंकि वे सभी v5 से जुड़े हैं।
- v1 को C2 दें: color(v1) = C2।
- v2 (v1 के आसन्न) को C3 दें: color(v2) = C3।
- v3 (v2 के आसन्न) को C2 दें: color(v3) = C2। (यह मान्य है क्योंकि v3, v1 के आसन्न नहीं है)।
- v4 (v3 और v1 के आसन्न) को C3 दें: color(v4) = C3। (यह मान्य है क्योंकि v4, v2 के आसन्न नहीं है)।
एक वैध 3-रंगाई है: color(v5) = C1, color(v1) = C2, color(v2) = C3, color(v3) = C2, color(v4) = C3। चूंकि χ(G) ≥ 3 और हमें एक 3-रंगाई मिल गई है, हम यह निष्कर्ष निकालते हैं कि उपरोक्त ग्राफ की वर्णिक संख्या χ(G) = 3 है।
(c) ट्री और विस्तरित ट्री में अंतर: | विशेषता | ट्री (Tree) | विस्तरित ट्री (Spanning Tree) | |—|—|—| | परिभाषा | एक ट्री एक अचक्रीय (acyclic) , संबद्ध (connected) ग्राफ है। यह अपने आप में एक ग्राफ का प्रकार है। | एक विस्तरित ट्री एक दिए गए संबद्ध ग्राफ G का एक उपग्राफ (subgraph) है जो एक ट्री है और G के सभी शीर्षों को शामिल करता है। | | संदर्भ | एक ट्री को स्वतंत्र रूप से परिभाषित किया जा सकता है, बिना किसी बड़े ग्राफ के संदर्भ के। | एक विस्तरित ट्री हमेशा एक बड़े, संबद्ध ग्राफ G के संबंध में परिभाषित किया जाता है। यह G का एक “कंकाल” है। | | अद्वितीयता | “एक ट्री” एक सामान्य वर्ग के ग्राफ को संदर्भित करता है। | “एक ग्राफ G का विस्तरित ट्री” G के भीतर एक विशिष्ट संरचना को संदर्भित करता है। एक ग्राफ के कई अलग-अलग विस्तरित ट्री हो सकते हैं। | | उदाहरण | एक पथ ग्राफ P_n या एक स्टार ग्राफ K_{1,n-1} ट्री के उदाहरण हैं। | यदि G एक चक्र ग्राफ C4 है, तो C4 से किसी भी एक किनारे को हटाने पर एक विस्तरित ट्री (एक P4) बनता है। |
Q4. (a) पुनरावृत्ति संबंध हल करें: 6 a_n = 6a_{n-1} – 3a_{n-2} – 10a_{n-3} a_0 = 5, a_1 = -9, a_2 = 5 के साथ। (b) ग्राफ क्या है? क्या ट्री एक ग्राफ है? समझाएं। 4
Ans. (a) टिप्पणी: दिए गए पुनरावृत्ति संबंध `a_n = 6a_{n-1} – 3a_{n-2} – a_{n-3}` के अभिलाक्षणिक समीकरण के पूर्णांक मूल नहीं हैं, जो इस स्तर के प्रश्न के लिए असामान्य है। प्रश्न पत्र में एक सामान्य टंकण त्रुटि `…-11a_{n-2} + 6a_{n-3}` या `…-3a_{n-2} – 10a_{n-3}` की हो सकती है। हम मान लेंगे कि संबंध `a_n = 6a_{n-1} – 11a_{n-2} + 6a_{n-3}` है, जो एक मानक रूप है।
माना पुनरावृत्ति संबंध है: a_n = 6a_{n-1} – 11a_{n-2} + 6a_{n-3}
यह एक तृतीय-कोटि का रैखिक सजातीय पुनरावृत्ति संबंध है।
चरण 1: अभिलाक्षणिक समीकरण (Characteristic Equation) लिखें।
r^3 – 6r^2 + 11r – 6 = 0
चरण 2: अभिलाक्षणिक समीकरण के मूल (roots) ज्ञात करें।
पूर्णांक मूलों के लिए परीक्षण करके, हम पाते हैं:
r = 1 के लिए: 1 – 6 + 11 – 6 = 0। तो (r-1) एक गुणनखंड है।
r = 2 के लिए: 8 – 6(4) + 11(2) – 6 = 8 – 24 + 22 – 6 = 0। तो (r-2) एक गुणनखंड है।
r = 3 के लिए: 27 – 6(9) + 11(3) – 6 = 27 – 54 + 33 – 6 = 0। तो (r-3) एक गुणनखंड है।
अतः, मूल हैं r_1 = 1, r_2 = 2, r_3 = 3 ।
चरण 3: सामान्य हल (General Solution) लिखें।
चूंकि मूल भिन्न और वास्तविक हैं, सामान्य हल का रूप है:
a_n = c_1(r_1)^n + c_2(r_2)^n + c_3(r_3)^n
a_n = c_1(1)^n + c_2(2)^n + c_3(3)^n
चरण 4: स्थिरांक (constants) c_1, c_2, c_3 का मान ज्ञात करने के लिए प्रारंभिक शर्तों का उपयोग करें।
दी गई शर्तें: a_0 = 5, a_1 = -9, a_2 = 5।
n=0 के लिए: a_0 = c_1 + c_2 + c_3 = 5 —(1)
n=1 के लिए: a_1 = c_1 + 2c_2 + 3c_3 = -9 —(2)
n=2 के लिए: a_2 = c_1 + 4c_2 + 9c_3 = 5 —(3)
समीकरणों को हल करें:
(2) – (1): c_2 + 2c_3 = -14 => c_2 = -14 – 2c_3 —(4)
(3) – (1): 3c_2 + 8c_3 = 0 —(5)
(4) को (5) में प्रतिस्थापित करें:
3(-14 – 2c_3) + 8c_3 = 0
-42 – 6c_3 + 8c_3 = 0
2c_3 = 42
c_3 = 21
c_3 का मान (4) में रखें:
c_2 = -14 – 2(21) = -14 – 42
c_2 = -56
c_2 और c_3 का मान (1) में रखें:
c_1 – 56 + 21 = 5
c_1 – 35 = 5
c_1 = 40
चरण 5: अंतिम हल लिखें।
स्थिरांकों के मानों को सामान्य हल में प्रतिस्थापित करने पर:
a_n = 40(1)^n – 56(2)^n + 21(3)^n
या
a_n = 40 – 56 2^n + 21 3^n
(b) ग्राफ (Graph): एक ग्राफ एक गणितीय संरचना है जिसका उपयोग वस्तुओं के एक समुच्चय के बीच युग्मानूसार संबंधों को मॉडल करने के लिए किया जाता है। औपचारिक रूप से, एक ग्राफ G को एक युग्म (V, E) के रूप में परिभाषित किया जाता है, जहाँ:
- V शीर्षों (vertices or nodes) का एक परिमित गैर-रिक्त समुच्चय है। ये वस्तुएं हैं।
- E किनारों (edges or links) का एक समुच्चय है। प्रत्येक किनारा शीर्षों के एक युग्म को जोड़ता है। एक किनारे e को एक शीर्ष युग्म (u, v) के रूप में दर्शाया जा सकता है, जहाँ u, v ∈ V।
उदाहरण के लिए, एक सामाजिक नेटवर्क को एक ग्राफ के रूप में दर्शाया जा सकता है, जहां लोग शीर्ष हैं और उनके बीच दोस्ती किनारे हैं।
क्या ट्री एक ग्राफ है? (Is tree a graph?) हाँ, एक ट्री निश्चित रूप से एक ग्राफ है।
स्पष्टीकरण (Explanation): ‘ग्राफ’ शब्द वस्तुओं (शीर्षों) और उनके बीच के कनेक्शन (किनारों) के किसी भी समुच्चय के लिए एक बहुत ही सामान्य शब्द है। ‘ट्री’ शब्द एक विशेष प्रकार के ग्राफ को संदर्भित करता है जिसमें कुछ अतिरिक्त गुण होते हैं।
एक ग्राफ को ‘ट्री’ कहा जाता है यदि वह निम्नलिखित दो शर्तों को पूरा करता है: 1. संबद्ध (Connected): ग्राफ में किन्हीं भी दो शीर्षों के बीच एक पथ होता है। 2. अचक्रीय (Acyclic): ग्राफ में कोई चक्र नहीं होता है। इसलिए, एक ट्री एक ग्राफ है, लेकिन यह एक विशिष्ट प्रकार का ग्राफ है – एक संबद्ध, अचक्रीय ग्राफ। सभी ट्री ग्राफ होते हैं, लेकिन सभी ग्राफ ट्री नहीं होते हैं। उदाहरण के लिए, एक ग्राफ जिसमें एक चक्र होता है, वह एक ट्री नहीं है, लेकिन वह अभी भी एक ग्राफ है। इस प्रकार, ‘ट्री’ का समुच्चय ‘ग्राफ’ के समुच्चय का एक उपसमुच्चय है।
Q5. निम्नलिखित पर संक्षिप्त नोट्स लिखें: 2½×4=10 (a) जनक फलन (b) पुनरावृत्तियों को हल करने की निरीक्षण विधि (c) एक ग्राफ G का खुला और बंद वॉक (d) द्विखंडी ग्राफ और उसके अनुप्रयोग
Ans. (a) जनक फलन (Generating Functions)
एक जनक फलन एक अनुक्रम (sequence) a_0, a_1, a_2, … को एन्कोड करने का एक तरीका है, जिसे एक औपचारिक घात श्रृंखला (formal power series) के रूप में दर्शाया जाता है। अनुक्रम {a_n} का जनक फलन G(x) = a_0 + a_1 x + a_2 x^2 + … = Σ(a_n * x^n) होता है।
यहाँ, x को एक चर के बजाय एक प्लेसहोल्डर के रूप में माना जाता है। x^n का गुणांक अनुक्रम का n-वाँ पद होता है।
उदाहरण: अनुक्रम (1, 1, 1, 1, …) का जनक फलन G(x) = 1 + x + x^2 + x^3 + … है, जो ज्यामितीय श्रृंखला के योग सूत्र से 1/(1-x) के बराबर है।
उपयोग:
- पुनरावृत्ति संबंधों को हल करना: जनक फलन का उपयोग पुनरावृत्ति संबंधों को बीजगणितीय समीकरणों में बदलने के लिए किया जा सकता है, जिन्हें हल करना आसान हो सकता है।
- संयोजन विज्ञान (Combinatorics): वे गिनती की समस्याओं में बहुत उपयोगी होते हैं, जैसे कि किसी दिए गए प्रतिबंधों के साथ वस्तुओं का चयन या व्यवस्था करने के तरीकों की संख्या ज्ञात करना।
(b) पुनरावृत्तियों को हल करने की निरीक्षण विधि (Method of Inspection)
यह पुनरावृत्ति संबंधों के लिए एक बंद-रूप सूत्र का अनुमान लगाने की एक अनौपचारिक विधि है। इसे ‘unfolding’ या ‘iteration’ विधि भी कहा जाता है। इस विधि में निम्नलिखित चरण शामिल हैं:
- पुनरावृत्ति संबंध को कुछ चरणों के लिए बार-बार विस्तारित (expand) करें।
- विस्तार से उत्पन्न होने वाले पैटर्न या प्रवृत्ति का निरीक्षण करें।
- पैटर्न के आधार पर, n और k के संदर्भ में k-वें पुनरावृत्ति के लिए एक सामान्य सूत्र का अनुमान लगाएं।
- प्रारंभिक (आधार) स्थिति तक पहुंचने के लिए k का एक उपयुक्त मान चुनें और एक बंद-रूप सूत्र प्राप्त करें।
- (वैकल्पिक लेकिन अनुशंसित) गणितीय आगमन (mathematical induction) का उपयोग करके अनुमानित सूत्र को सत्यापित करें।
उदाहरण: T(n) = T(n-1) + c, T(0) = d
T(n) = [T(n-2) + c] + c = T(n-2) + 2c
T(n) = [T(n-3) + c] + 2c = T(n-3) + 3c
पैटर्न: T(n) = T(n-k) + kc।
k=n सेट करें: T(n) = T(0) + nc = d + nc।
(c) एक ग्राफ G का खुला और बंद वॉक (Open and Closed Walk)
एक ग्राफ G में, एक वॉक (walk) शीर्षों और किनारों का एक वैकल्पिक अनुक्रम होता है, जो v_0, e_1, v_1, e_2, v_2, …, e_k, v_k के रूप में होता है, जहां प्रत्येक किनारा e_i अपने पहले और बाद के शीर्षों (v_{i-1}, v_i) को जोड़ता है। वॉक की लंबाई उसमें किनारों की संख्या (k) होती है।
खुला वॉक (Open Walk):
एक वॉक को खुला कहा जाता है यदि उसका प्रारंभिक शीर्ष (v_0) और अंतिम शीर्ष (v_k) भिन्न हों।
उदाहरण: एक ग्राफ में v1-v2-v3-v1-v4, एक खुला वॉक है जिसकी लंबाई 4 है, जो v1 से शुरू होता है और v4 पर समाप्त होता है।
बंद वॉक (Closed Walk):
एक वॉक को बंद कहा जाता है यदि उसका प्रारंभिक शीर्ष (v_0) और अंतिम शीर्ष (v_k) समान हों।
उदाहरण: एक ग्राफ में v1-v2-v3-v1, एक बंद वॉक है जिसकी लंबाई 3 है। एक चक्र (cycle) एक विशेष प्रकार का बंद वॉक होता है जिसमें कोई भी शीर्ष (प्रारंभिक/अंतिम को छोड़कर) दोहराया नहीं जाता है।
(d) द्विखंडी ग्राफ और उसके अनुप्रयोग (Bipartite Graph and its Applications)
द्विखंडी ग्राफ: एक ग्राफ G = (V, E) को द्विखंडी कहा जाता है यदि उसके शीर्ष समुच्चय V को दो असंयुक्त (disjoint) और स्वतंत्र समुच्चयों U और W में इस प्रकार विभाजित किया जा सकता है कि V = U ∪ W, और प्रत्येक किनारा E में एक शीर्ष U से और एक शीर्ष W से जुड़ता है। U और W के भीतर कोई किनारा नहीं होता है।
एक ग्राफ द्विखंडी होता है यदि और केवल यदि उसमें कोई विषम-लंबाई का चक्र (odd-length cycle) न हो।
अनुप्रयोग:
- मिलान (Matching): द्विखंडी ग्राफ मिलान समस्याओं को मॉडल करने के लिए स्वाभाविक हैं। उदाहरण के लिए, आवेदकों (एक समुच्चय U) को नौकरियों (दूसरा समुच्चय W) से मिलाना, जहां एक किनारा एक आवेदक की किसी नौकरी के लिए योग्यता का प्रतिनिधित्व करता है। लक्ष्य अधिकतम मिलान खोजना है।
- शेड्यूलिंग (Scheduling): इनका उपयोग संघर्ष-मुक्त शेड्यूल बनाने के लिए किया जा सकता है। उदाहरण के लिए, पाठ्यक्रमों (U) को टाइम-स्लॉट (W) में आवंटित करना ताकि कोई भी दो पाठ्यक्रम जिन्हें एक ही छात्र ने लिया हो, एक ही समय में न हों।
- कोडिंग सिद्धांत (Coding Theory): वे त्रुटि-सुधार कोड के डिजाइन और विश्लेषण में उपयोग किए जाते हैं।
- नेटवर्क डिजाइन: विभिन्न प्रकार के नेटवर्क में कनेक्टिविटी और प्रवाह समस्याओं को मॉडल करने के लिए।
IGNOU MCS-033 Previous Year Solved Question Paper in English
Q1. (a) Write the recurrence relation for the Fibonacci series. 2 (b) Verify that T(n) = 2^n + n – 2 is the solution of the recurrence relation: 4 T(n) = 2T(n-1) + n, n>=2 T(1)=1 (c) What is planar graph? Prove that K4 is a planar graph. 4 (d) Verify that the following degree sequence of the graph is not possible: 4 3, 2, 1, 1, 0 Justify with suitable argument. (e) Find the generating function of the Geometric Progression. 4 (f) Determine the order and degree of the recurrence relation: 2 a_n = (a_{n-1})^2 + n^2
Ans. (a) The Fibonacci series is a series in which each number is the sum of the two preceding ones. It is denoted by F_n. The series starts 0, 1, 1, 2, 3, 5, 8, … The recurrence relation for the Fibonacci series is: F_n = F_{n-1} + F_{n-2} , for n ≥ 2 With the initial conditions: F_0 = 0 and F_1 = 1 .
(b) To verify the recurrence relation, we will substitute the proposed solution T(n) = 2^n + n – 2 into the relation. The given relation is: T(n) = 2T(n-1) + n Left Hand Side (LHS) = T(n) = 2^n + n – 2 Now, we calculate the Right Hand Side (RHS): RHS = 2T(n-1) + n First, find T(n-1): T(n-1) = 2^(n-1) + (n-1) – 2 Now substitute this into the RHS: RHS = 2 * [2^(n-1) + (n-1) – 2] + n RHS = 2 * 2^(n-1) + 2(n-1) – 2(2) + n RHS = 2^n + 2n – 2 – 4 + n RHS = 2^n + 3n – 6 Comparing LHS (2^n + n – 2) and RHS (2^n + 3n – 6), we see they are not equal. Therefore, the given solution T(n) = 2^n + n – 2 is incorrect. Note: There is likely a typo in the question or the proposed solution. If the solution were T(n) = 2^(n+1) – n – 2, it would be a solution for T(n) = 2T(n-1) + n + 2. If the recurrence in the question was T(n) = 2T(n-1) – n + 2, then T(n)=2^n + n – 2 would be a correct solution. As per the values given in the question, it is not verified.
(c) Planar Graph: A graph is called planar if it can be drawn in a plane such that its edges intersect only at their endpoints. In other words, no two edges cross each other. Proof that K4 is planar: K4 is the complete graph on 4 vertices. In a complete graph, every vertex is connected to every other vertex. K4 has 4 vertices and (4*3)/2 = 6 edges. Let the vertices be V = {v1, v2, v3, v4}. The edges are E = {(v1, v2), (v1, v3), (v1, v4), (v2, v3), (v2, v4), (v3, v4)}. To prove it is planar, we need to draw it without any edge crossings. 1. Place vertices v1, v2, and v3 as a triangle. Draw the edges (v1, v2), (v2, v3), and (v3, v1). This has no crossings. 2. Place the fourth vertex, v4, inside this triangle. 3. Now, connect v4 to the other three vertices: (v4, v1), (v4, v2), (v4, v3). All these edges can be drawn from the inside of the triangle without crossing each other or the triangle’s edges.
A planar representation is shown below:
v1 /|\ / | \ / | \ v2--v4--v3
In this representation, no two edges cross each other. Hence, K4 is a planar graph .
(d) Note: The sequence in the question paper “3, 2, , , , 0” is incomplete due to blanks. We assume a plausible complete sequence “3, 2, 1, 1, 0” which is often used in such problems. Given degree sequence: D = (3, 2, 1, 1, 0) Argument: According to the Handshaking Lemma in graph theory, the sum of the degrees of all vertices in any graph is always equal to twice the number of edges. Σ deg(v) = 2 |E| Since 2|E| is an even number, the sum of degrees for any graph must always be an even number . Let’s find the sum of degrees for the given sequence: Sum = 3 + 2 + 1 + 1 + 0 = 7 Here, the sum of degrees is 7, which is an odd number . As the sum of degrees cannot be odd according to the Handshaking Lemma. Therefore, no simple graph can exist with the degree sequence (3, 2, 1, 1, 0). It is an impossible degree sequence.
(e) A Geometric Progression has the general form: a, ar, ar^2, ar^3, … This can be written as the sequence {a_n} = {ar^n} for n = 0, 1, 2, … The Generating Function of a sequence {a_n} is defined by the power series G(x) = Σ (a_n * x^n). To calculate the generating function for the geometric progression, we write the series: G(x) = a_0 + a_1 x + a_2 x^2 + a_3*x^3 + … Substituting the values: G(x) = a + (ar)x + (ar^2)x^2 + (ar^3)x^3 + … G(x) = a [1 + (rx) + (rx)^2 + (rx)^3 + …] The series in the bracket is an infinite geometric series with first term 1 and common ratio ‘rx’. The sum of an infinite geometric series is S = 1 / (1 – R), provided |R| < 1. Here, R = rx. So, assuming |rx| < 1, the sum of the series is 1 / (1 – rx). Therefore, the generating function is: G(x) = a / (1 – rx)
(f) The given recurrence relation is: a_n = (a_{n-1})^2 + n^2 Order: The order of a recurrence relation is the difference between the largest and smallest subscripts. In this relation, the largest subscript is ‘n’ and the smallest is ‘n-1’. Order = n – (n-1) = 1 Thus, the relation has an order of 1 . Degree: The degree of a recurrence relation is the highest power of the terms of the sequence (like a_n, a_{n-1}, etc.) once the relation is expressed as a polynomial in them. In the given relation, the term a_{n-1} is raised to the power of 2, i.e., (a_{n-1})^2. Thus, the relation has a degree of 2 .
Q2. (a) What is Isomorphism? Write the conditions for the graphs to be isomorphic. Show that the following graph G and H are not isomorphic: 5 (b) Describe the term ‘Complement of a Graph G’ with suitable diagram. If G(V, E) is a (p, q) graph, then determine the number of vertices and number of edges in the complement of the Graph G. 5
Ans. (a) Isomorphism: Two graphs G1 and G2 are said to be isomorphic if there exists a one-to-one and onto (bijective) function f: V(G1) → V(G2) between their vertex sets that preserves adjacency. This means that any two vertices u and v are adjacent in G1 if and only if the vertices f(u) and f(v) are adjacent in G2. In short, isomorphic graphs are structurally identical, just with different names for their vertices. Conditions for Graphs to be Isomorphic (Invariants): If two graphs are isomorphic, they must share the following properties:
- They must have the same number of vertices.
- They must have the same number of edges.
- They must have the same degree sequence (i.e., the number of vertices with a certain degree is the same in both graphs).
- They must have the same number of cycles of a given length.
Analysis of the given graphs G and H: Note: The graphs G and H provided in the question are, in fact, isomorphic. Both are cycle graphs on 4 vertices (C4). We will demonstrate this and then provide an example of non-isomorphic graphs. Graph G: Vertices: {a, b, c, d}, Edges: {(a,b), (b,c), (c,d), (d,a)} Degree sequence: All vertices (a, b, c, d) have a degree of 2. The sequence is (2, 2, 2, 2). Graph H: Vertices: {s, t, u, v}, Edges: {(s,t), (t,u), (u,v), (v,s)} Degree sequence: All vertices (s, t, u, v) have a degree of 2. The sequence is (2, 2, 2, 2).
Since both graphs have the same number of vertices (4), edges (4), and the same degree sequence (2,2,2,2), they can be isomorphic. An isomorphism f exists: f(a) = s, f(b) = t, f(c) = u, f(d) = v This function preserves adjacency (e.g., (a,b) is an edge in G, and (f(a), f(b)) = (s,t) is an edge in H). Thus, G and H are isomorphic .
Example of Non-Isomorphic Graphs: To show two graphs are not isomorphic, one must find a property that differs. Consider the following two graphs, G’ and H’, both with 4 vertices and 3 edges. G’: A path graph P4. Vertices: {1, 2, 3, 4}, Edges: {(1,2), (2,3), (3,4)}. Degree sequence: (1, 2, 2, 1). H’: A star graph K1,3. Vertices: {A, B, C, D}, Edges: {(A,B), (A,C), (A,D)}. Degree sequence: (3, 1, 1, 1).
Since the degree sequences of G’ and H’ are different, they cannot be isomorphic .
(b) Complement of a Graph G: The complement of a simple graph G, denoted G̅ (G-bar), is a graph with the same vertex set as G. Two vertices are adjacent in G̅ if and only if they are not adjacent in G. Description with an example: Let G be a graph with V = {1, 2, 3, 4} and edges E = {(1,2), (2,3), (3,4), (4,1)}. This is a cycle graph C4.
G (C4):1--2| |4--3
The complement of G, G̅, will have the same vertices {1, 2, 3, 4}. We add all edges in G̅ that are not present in G. The edges present in G are (1,2), (2,3), (3,4), (4,1). The total possible edges on 4 vertices (in a K4) are (1,2), (1,3), (1,4), (2,3), (2,4), (3,4). The edges of G̅ = (Edges of K4) – (Edges of G) E(G̅) = {(1,3), (2,4)}
G̅ (Two disjoint edges):1----3 2----4
So, G̅ consists of two disjoint edges connecting opposite vertices.
Number of Vertices and Edges in the Complement: Let G(V, E) be a (p, q) graph, which means:
- p = number of vertices = |V|
- q = number of edges = |E|
1. Number of vertices in the complement G̅: The complement graph has the exact same vertex set as the original graph. Therefore, the number of vertices in G̅ is p .
2. Number of edges in the complement G̅: The total number of possible edges in a complete graph (Kp) on p vertices is C(p, 2) = p(p-1)/2. The edges of the complement graph are those that exist in the complete graph but not in the original graph. Therefore, the number of edges in G̅, |E(G̅)|, is: |E(G̅)| = (Number of edges in Kp) – (Number of edges in G) |E(G̅)| = p(p-1)/2 – q
Q3. (a) Give the definition of a Hamiltonian graph. Is the graph given below Hamiltonian or not? Justify. 5 (b) Define chromatic number for a graph. 3 Find the chromatic number of the above graph. (c) Differentiate between a tree and a spanning tree. 2
Ans. (a) Hamiltonian Graph: A graph G is called Hamiltonian if it contains a Hamiltonian cycle . A Hamiltonian cycle is a closed path that visits every vertex in the graph exactly once and returns to the starting vertex. (No vertices are repeated, except for the start/end vertex). Analysis of the given graph: The given graph is a Wheel Graph with 5 vertices, known as W5. It consists of an outer cycle (v1, v2, v3, v4 are mislabeled in standard cycle form) and a central hub vertex (v5) connected to all vertices on the outer cycle. Justification: We need to check if there is a cycle that passes through all 5 vertices (v1, v2, v3, v4, v5). Let’s try to construct a path: v1 → v2 → v3 → v4 → v5 → v1 This path visits all 5 vertices and ends at the start. Let’s check the edges:
- (v1, v2) – exists
- (v2, v3) – exists
- (v3, v4) – does NOT exist in the diagram (v3 is connected to v2, v5, and the bottom right vertex in the picture which is v4’s neighbor, not v4 itself). Let’s assume the vertices are v1(top-left), v2(top-right), v3(bottom-right), v4(bottom-left). Then (v3, v4) is an edge. Let’s try again with this labeling.
Let’s trace a different path:
v1 → v2 → v3 → v5 → v4 → v1
Let’s check the edges in this cycle:
- (v1, v2) – exists
- (v2, v3) – exists
- (v3, v5) – exists
- (v5, v4) – exists
- (v4, v1) – exists
This cycle
v1 → v2 → v3 → v5 → v4 → v1
passes through all 5 vertices exactly once and is a valid cycle.
Since the graph contains a Hamiltonian cycle, the given graph is
Hamiltonian
.
(b) Chromatic Number: The chromatic number of a graph G, denoted χ(G), is the minimum number of colors needed to color the vertices of G so that no two adjacent vertices share the same color. Such a coloring is called a proper vertex coloring . Finding the chromatic number of the above graph: The graph is W5. 1. The graph contains several triangles (cycles of length 3), for example, (v1, v2, v5) is a triangle. 2. To color a triangle, a minimum of 3 distinct colors are required, as all three vertices are adjacent to each other. 3. Therefore, the chromatic number of the graph must be at least 3, i.e., χ(G) ≥ 3 .
Now, let’s see if we can color the graph with 3 colors. Let the colors be C1, C2, C3.
- Color the central vertex v5 with C1: color(v5) = C1.
- Now, we must color the outer cycle (v1, v2, v3, v4). None of these can be C1 as they are all adjacent to v5.
- Color v1 with C2: color(v1) = C2.
- Color v2 (adjacent to v1) with C3: color(v2) = C3.
- Color v3 (adjacent to v2) with C2: color(v3) = C2. (This is valid as v3 is not adjacent to v1).
- Color v4 (adjacent to v3 and v1) with C3: color(v4) = C3. (This is valid as v4 is not adjacent to v2).
A valid 3-coloring is:
color(v5)=C1, color(v1)=C2, color(v2)=C3, color(v3)=C2, color(v4)=C3.
Since χ(G) ≥ 3 and we have found a 3-coloring, we conclude that the chromatic number of the above graph is
χ(G) = 3
.
(c) Difference between a Tree and a Spanning Tree:
| Feature | Tree | Spanning Tree | |—|—|—| | Definition | A tree is an acyclic , connected graph. It is a type of graph in its own right. | A spanning tree is a subgraph of a given connected graph G that is a tree and includes all the vertices of G. | | Context | A tree can be defined independently, without reference to any larger graph. | A spanning tree is always defined in relation to a larger, connected graph G. It is a “skeleton” of G. | | Uniqueness | “A tree” refers to a general class of graphs. | “A spanning tree of a graph G” refers to a specific structure within G. A single graph can have many different spanning trees. | | Example | A path graph P_n or a star graph K_{1,n-1} are examples of trees. | If G is a cycle graph C4, then removing any single edge from C4 results in a spanning tree (which is a P4). |
Q4. (a) Solve the recurrence relation: 6 a_n = 6a_{n-1} – 3a_{n-2} – 10a_{n-3} with a_0 = 5, a_1 = -9, a_2 = 5. (b) What is a graph? Is tree a graph? Explain. 4
Ans. (a) Note: The given recurrence relation `a_n = 6a_{n-1} – 3a_{n-2} – a_{n-3}` has a characteristic equation whose roots are not simple integers, which is unusual for this level of question. There is likely a typo in the question paper. A common intended form could be `a_n = 6a_{n-1} – 11a_{n-2} + 6a_{n-3}`. We will solve this standard version. Let the recurrence relation be: a_n = 6a_{n-1} – 11a_{n-2} + 6a_{n-3} This is a third-order linear homogeneous recurrence relation. Step 1: Write the Characteristic Equation. r^3 – 6r^2 + 11r – 6 = 0 Step 2: Find the roots of the characteristic equation. By testing for integer roots, we find: For r = 1: 1 – 6 + 11 – 6 = 0. So (r-1) is a factor. For r = 2: 8 – 6(4) + 11(2) – 6 = 8 – 24 + 22 – 6 = 0. So (r-2) is a factor. For r = 3: 27 – 6(9) + 11(3) – 6 = 27 – 54 + 33 – 6 = 0. So (r-3) is a factor. The roots are r_1 = 1, r_2 = 2, r_3 = 3 . Step 3: Write the General Solution. Since the roots are distinct and real, the general solution is of the form: a_n = c_1(r_1)^n + c_2(r_2)^n + c_3(r_3)^n a_n = c_1(1)^n + c_2(2)^n + c_3(3)^n Step 4: Use initial conditions to find the constants c_1, c_2, c_3. Given conditions: a_0 = 5, a_1 = -9, a_2 = 5. For n=0: a_0 = c_1 + c_2 + c_3 = 5 —(1) For n=1: a_1 = c_1 + 2c_2 + 3c_3 = -9 —(2) For n=2: a_2 = c_1 + 4c_2 + 9c_3 = 5 —(3) Solving the equations: (2) – (1): c_2 + 2c_3 = -14 => c_2 = -14 – 2c_3 —(4) (3) – (1): 3c_2 + 8c_3 = 0 —(5) Substitute (4) into (5): 3(-14 – 2c_3) + 8c_3 = 0 -42 – 6c_3 + 8c_3 = 0 2c_3 = 42 c_3 = 21 Put c_3 in (4): c_2 = -14 – 2(21) = -14 – 42 c_2 = -56 Put c_2 and c_3 in (1): c_1 – 56 + 21 = 5 c_1 – 35 = 5 c_1 = 40 Step 5: Write the final solution. Substituting the constants back into the general solution: a_n = 40(1)^n – 56(2)^n + 21(3)^n or a_n = 40 – 56 2^n + 21 3^n
(b) What is a graph? A graph is a mathematical structure used to model pairwise relations between a set of objects. Formally, a graph G is defined as an ordered pair (V, E), where:
- V is a finite non-empty set of vertices (or nodes). These are the objects.
- E is a set of edges (or links). Each edge connects a pair of vertices. An edge e can be represented as a vertex pair (u, v), where u, v ∈ V.
For example, a social network can be represented as a graph, where people are the vertices and friendships between them are the edges.
Is a tree a graph?
Yes, a tree is definitely a graph.
Explanation:
The term ‘graph’ is a very general term for any collection of objects (vertices) and connections between them (edges). The term ‘tree’ refers to a special kind of graph that has some additional properties.
A graph is called a ‘tree’ if it satisfies two conditions:
1.
Connected:
There is a path between any two vertices in the graph.
2.
Acyclic:
There are no cycles in the graph.
Therefore, a tree is a graph, but it’s a specific type of graph—a connected, acyclic graph. All trees are graphs, but not all graphs are trees. For example, a graph that contains a cycle is not a tree, but it is still a graph. Thus, the set of ‘trees’ is a subset of the set of ‘graphs’.
Q5. Write short notes on the following: 2½×4=10 (a) Generating functions (b) Method of inspection of solving recurrences (c) Open and closed walk of a graph G (d) Bipartite graph and its applications
Ans. (a) Generating Functions A generating function is a way of encoding a sequence of numbers, say a_0, a_1, a_2, …, by treating them as coefficients of a formal power series. The generating function of the sequence {a_n} is G(x) = a_0 + a_1 x + a_2 x^2 + … = Σ(a_n * x^n). Here, x is treated as a placeholder rather than a variable. The coefficient of x^n is the nth term of the sequence. Example: The generating function for the sequence (1, 1, 1, 1, …) is G(x) = 1 + x + x^2 + x^3 + …, which is equal to 1/(1-x) by the sum formula for a geometric series. Uses:
- Solving Recurrence Relations: Generating functions can be used to transform recurrence relations into algebraic equations, which may be easier to solve.
- Combinatorics: They are very useful in counting problems, such as finding the number of ways to select or arrange objects with given constraints.
(b)
Method of Inspection for Solving Recurrences
This is an informal method of guessing a closed-form formula for a recurrence relation. It is also known as the method of ‘unfolding’ or ‘iteration’. The method involves the following steps:
- Repeatedly expand the recurrence relation for a few steps.
- Observe the pattern or trend that emerges from the expansion.
- Based on the pattern, guess a general formula for the k-th iteration in terms of n and k.
- Choose an appropriate value of k to reach the base case and obtain a closed-form formula.
- (Optional but recommended) Verify the guessed formula using mathematical induction.
Example:
T(n) = T(n-1) + c, with T(0) = d.
T(n) = [T(n-2) + c] + c = T(n-2) + 2c
T(n) = [T(n-3) + c] + 2c = T(n-3) + 3c
The pattern is: T(n) = T(n-k) + kc.
Set k=n: T(n) = T(0) + nc = d + nc.
(c)
Open and Closed Walk of a Graph G
In a graph G, a
walk
is an alternating sequence of vertices and edges, of the form v_0, e_1, v_1, e_2, v_2, …, e_k, v_k, where each edge e_i connects its preceding and succeeding vertices (v_{i-1}, v_i). The length of the walk is the number of edges in it (k).
Open Walk:
A walk is called an open walk if its starting vertex (v_0) and ending vertex (v_k) are different.
Example:
In a graph, v1-v2-v3-v1-v4 is an open walk of length 4, starting at v1 and ending at v4.
Closed Walk:
A walk is called a closed walk if its starting vertex (v_0) and ending vertex (v_k) are the same.
Example:
In a graph, v1-v2-v3-v1 is a closed walk of length 3. A cycle is a special type of closed walk where no vertices (except the start/end) are repeated.
(d)
Bipartite Graph and its Applications
Bipartite Graph:
A graph G = (V, E) is called bipartite if its vertex set V can be partitioned into two disjoint and independent sets, U and W, such that V = U ∪ W, and every edge in E connects a vertex in U to one in W. No edges exist within U or within W.
A graph is bipartite if and only if it has no odd-length cycles.
Applications:
- Matching: Bipartite graphs are natural for modeling matching problems. For instance, matching applicants (one set U) to jobs (another set W), where an edge represents an applicant’s qualification for a job. The goal is to find a maximum matching.
- Scheduling: They can be used to create conflict-free schedules. For example, assigning courses (U) to time-slots (W) such that no two courses taken by the same student are at the same time.
- Coding Theory: They are used in the design and analysis of error-correcting codes.
- Network Design: For modeling connectivity and flow problems in various types of networks.
Download IGNOU previous Year Question paper download PDFs for MCS-033 to improve your preparation. These ignou solved question paper IGNOU Previous Year Question paper solved PDF in Hindi and English help you understand the exam pattern and score better.
Thanks!
Leave a Reply