तत्वों 

डिग्राफ और बाइनरी संबंध। एक डिग्राफ के शीर्षों की पहुंच योग्यता अनुपात

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

रीचैबिलिटी और काउंटररीचैबिलिटी

कार्य जिसमें अवधारणा का उपयोग किया जाता है गम्यता, काफी कुछ।

उनमें से एक यहां पर है। ग्राफ़कुछ संगठन का एक मॉडल हो सकता है जिसमें लोगों को शिखर द्वारा दर्शाया जाता है, और चाप संचार चैनलों की व्याख्या करते हैं। इस तरह के एक मॉडल पर विचार करते समय, कोई यह पूछ सकता है कि क्या एक व्यक्ति से जानकारी को दूसरे व्यक्ति को स्थानांतरित किया जा सकता है, यानी, क्या कोई रास्ता है जो कोने से कोने तक जा रहा है। यदि ऐसा पथ मौजूद है, तो हम कहते हैं कि शीर्ष j प्राप्तकोने से मैं। किसी को केवल उन पथों पर, जिनकी लंबाई किसी दिए गए मान से अधिक नहीं है या जिनकी लंबाई ग्राफ़ में सबसे बड़ी संख्या में शीर्षों से कम है, समस्या के लिए केवल i से कोने j की पहुंच में रुचि हो सकती है।

ग्राफ़ में रीचैबिलिटी को रीचैबिलिटी मैट्रिक्स R=, i, j=1, 2, ... n द्वारा वर्णित किया गया है, जहां n ग्राफ़ वर्टिस की संख्या है, और प्रत्येक तत्व को निम्नानुसार परिभाषित किया गया है:

r ij =1, यदि शीर्षों j x i से पहुंच योग्य हैं,

आर ij = 0, अन्यथा।

किसी दिए गए शीर्ष x i से पहुंच योग्य ग्राफ़ G के शिखर R(x i) के सेट में x i तत्व होते हैं, जिसके लिए (i, j) - रीचैबिलिटी मैट्रिक्स में तत्व 1 के बराबर होता है। जाहिर है, सभी विकर्ण मैट्रिक्स आर में तत्व 1 के बराबर हैं, क्योंकि प्रत्येक शीर्ष लंबाई 0 के पथ से स्वयं से पहुंच योग्य है। चूंकि प्रथम-क्रम प्रत्यक्ष मानचित्रण Г +1 (x i) ऐसे शीर्षों का समूह है x j जो x i का उपयोग करके पहुंच योग्य हैं लंबाई 1 के पथ, फिर सेट Г + (Г +1 (x i)) = Г +2 (x i) में लंबाई 2 के पथ का उपयोग करके x i से पहुंचने योग्य शिखर होते हैं। इसी प्रकार, r+p (x i) का सेट है लंबाई p के पथों का उपयोग करके x i से पहुंचने योग्य शीर्ष।

चूंकि कोई भी ग्राफ़ वर्टेक्स जो x i से पहुंच योग्य है, लंबाई 0 या 1, या 2, ..., या p के पथ (या पथ) का उपयोग करके पहुंच योग्य होना चाहिए, वर्टेक्स x i के लिए पहुंचने योग्य शिखरों के सेट को इस रूप में दर्शाया जा सकता है

आर (एक्स आई) = (एक्स आई) जी +1 (एक्स आई) जी +2 (एक्स आई) ... जी + पी (एक्स आई)।

जैसा कि आप देख सकते हैं, पहुंच योग्य शीर्षों का समुच्चय R(x i) शीर्ष x i का प्रत्यक्ष संक्रमणीय समापन है, अर्थात R(x i) = T + (x i)। इसलिए, रीचैबिलिटी मैट्रिक्स का निर्माण करने के लिए, हम सभी शीर्षों x i X के लिए रीचेबल सेट R(x i) पाते हैं। r ij =1 सेट करना यदि x j R(x i) और r ij =0 अन्यथा।

चावल। 4.1. ग्राफ में पहुंच योग्यता: ए - ग्राफ; बी - आसन्नता मैट्रिक्स; सी - पहुंच योग्यता मैट्रिक्स; r प्रतिबाधा मैट्रिक्स है।

अंजीर में दिखाए गए ग्राफ के लिए। 4.1, ए, पहुंच योग्य सेटनिम्नानुसार स्थित हैं:

आर (एक्स 1) = ( एक्स 1 ) ( एक्स 2 , एक्स 5 ) ( एक्स 2 , एक्स 4 , एक्स 5 ) ( एक्स 2 , एक्स 4 , एक्स 5 ) = ( एक्स 1 , एक्स 2 , एक्स 4 , एक्स 5 ),

आर (एक्स 2) = ( एक्स 2 ) ( एक्स 2 , एक्स 4 ) ( एक्स 2 , एक्स 4 , एक्स 5 ) ( एक्स 2 , एक्स 4 , एक्स 5 ) = ( एक्स 2 , एक्स 4 , एक्स 5 ),

आर (एक्स 3) = ( एक्स 3 )( एक्स 4 )( एक्स 5 )( एक्स 5 ) = ( एक्स 3 , एक्स 4 , एक्स 5 ),

आर (एक्स 4) = ( एक्स 4 )( एक्स 5 )( एक्स 5 ) = ( एक्स 4 , एक्स 5 ),

आर (एक्स 5) = ( एक्स 5 )( एक्स 5 ) = ( एक्स 5 ),

आर (एक्स 6) = (एक्स 6) (एक्स 3, एक्स 7) (एक्स 4, एक्स 6) (एक्स 3, एक्स 5, एक्स 7) (एक्स 4, एक्स 5, एक्स 6) = (एक्स 3, एक्स 4, एक्स 5, एक्स 6, एक्स 7),

आर (x 7) = ( x 7 )( x 4 , x 6 )( x 3 , x 5 , x 7 )( x 4 , x 5 , x 6 ) = ( x 3 , x 4 , x 5 , x 6 ) , एक्स 7)।

रीचैबिलिटी मैट्रिक्स रूप है जैसा कि चित्र में दिखाया गया है। 4.1, सी. रीचैबिलिटी मैट्रिक्सके अनुसार बनाया जा सकता है सहखंडज मैट्रिक्स(चित्र 4.1b), प्रत्येक शीर्ष x i के लिए समुच्चयT + (x i) बनाता है।

काउंटररीचैबिलिटी मैट्रिक्स Q = [ q ij ],i, j =1, 2, ... n, जहां n ग्राफ के शीर्षों की संख्या है, को निम्नानुसार परिभाषित किया गया है:

q ij = 1, यदि शीर्ष x j से शीर्ष x i तक पहुंचना संभव है,

क्यू ij = 0, अन्यथा।

प्रतिपूर्ति योग्यसमुच्चय Q (x i) शीर्षों का समुच्चय इस प्रकार है कि इस समुच्चय के किसी भी शीर्ष से शीर्ष x i तक पहुंचना संभव है। इसी तरह पहुंच योग्य सेट R (x i) के निर्माण के लिए, हम Q (x i) के लिए एक व्यंजक लिख सकते हैं:

क्यू (एक्स आई) = (एक्स आई) Г -1 (एक्स आई) Г - 2 (एक्स आई) ... Г -पी (एक्स आई)।

इस प्रकार, यह स्पष्ट है कि Q (x i) शीर्ष x i, यानी Q (x i) = T - (x i) के रिवर्स ट्रांजिटिव क्लोजर से ज्यादा कुछ नहीं है। परिभाषाओं से यह स्पष्ट है कि मैट्रिक्स Q का कॉलम x i (जिसमें q ij =1 यदि x j Q (x i), और q ij =0 अन्यथा) मैट्रिक्स R की पंक्ति x i के साथ मेल खाता है, अर्थात, Q = R T , जहां आर टी मैट्रिक्स को स्थानांतरित किया गया है रीचैबिलिटी मैट्रिक्सआर।

काउंटररीचैबिलिटी मैट्रिक्सअंजीर में दिखाया गया है। 4.1, जी.

यह ध्यान दिया जाना चाहिए कि चूंकि मैट्रिक्स आर और क्यू के सभी तत्व 1 या 0 के बराबर हैं, इसलिए प्रत्येक पंक्ति को बाइनरी रूप में संग्रहीत किया जा सकता है, जिससे कंप्यूटर मेमोरी लागत की बचत होती है। कंप्यूटर पर प्रोसेसिंग के लिए मैट्रिस आर और क्यू सुविधाजनक हैं, क्योंकि कम्प्यूटेशनल दृष्टिकोण से, मुख्य ऑपरेशन हाई-स्पीड लॉजिकल ऑपरेशंस हैं।

पथ में शामिल शीर्षों का समुच्चय ढूँढना

यदि आपको इन पथों में शामिल ग्राफ़ के शीर्षों के बारे में जानने की आवश्यकता है, तो आपको प्रत्यक्ष और व्युत्क्रम सकर्मक क्लोजर की परिभाषाओं को याद रखना चाहिए। चूँकि T + (x i) शीर्षों का समुच्चय है जिसमें शीर्ष x i से पथ हैं, और T - (x j) शीर्षों का समुच्चय है जहाँ से x j तक पथ हैं, तो T + (x i) T - (x j) ) शीर्षों का समुच्चय है, जिनमें से प्रत्येक x i से x j तक जाने वाले कम से कम एक पथ से संबंधित है। इन शीर्षों को दो सिरों x i और x j के संबंध में आवश्यक या समाकलक कहा जाता है। ग्राफ़ के अन्य सभी शीर्षों को महत्वहीन या निरर्थक कहा जाता है, क्योंकि उनके हटाने से x i से x j तक के पथ प्रभावित नहीं होते हैं।

चावल। 4.2. संयुक्ताक्षर

तो अंजीर में ग्राफ के लिए। 4.2 पथ में शामिल शीर्षों को खोजना, उदाहरण के लिए, शीर्ष x 2 से शीर्ष 4 तक, घटाकर T + (x 2) \u003d ( x 2, x 3, x 4, x 5, x 6 ) ज्ञात करना है।

टी - (एक्स 4) \u003d ( एक्स 1, एक्स 2, एक्स 3, एक्स 4, एक्स 5), और उनके चौराहे टी + (एक्स 2) टी - (एक्स 4) \u003d ( एक्स 2, एक्स 3, एक्स 4, एक्स 5)।

ग्राफ में पथ खोजने के लिए मैट्रिक्स विधि

आसन्न मैट्रिक्स ग्राफ की संरचना को पूरी तरह से परिभाषित करता है। आइए गणित के नियमों के अनुसार आसन्न मैट्रिक्स को वर्गाकार करें। मैट्रिक्स ए 2 का प्रत्येक तत्व सूत्र द्वारा निर्धारित किया जाता है

a (2) ik = n j=1 a ij a jk

सूत्र में पद 1 के बराबर है यदि और केवल यदि दोनों संख्याएँ a ij और a jk 1 के बराबर हैं, अन्यथा यह 0 के बराबर है। चूँकि समानता a ij = a jk = 1 लंबाई के पथ के अस्तित्व का तात्पर्य है 2 शीर्ष x i से शीर्ष k तक शीर्ष x j से होकर गुजरता है, तो मैट्रिक्स A 2 का (i -th, k-th) तत्व x i से k तक जाने वाले लंबाई 2 के पथों की संख्या के बराबर है।

तालिका 4.1a अंजीर में दिखाए गए ग्राफ के आसन्न मैट्रिक्स को दिखाती है। 4.2. आसन्न मैट्रिक्स ए 2 का वर्ग करने का परिणाम तालिका 4.1 बी में दिखाया गया है।

तो "1", दूसरी पंक्ति और चौथे स्तंभ के चौराहे पर खड़ा होना, लंबाई 2 के एक पथ के अस्तित्व को इंगित करता है जो शीर्ष x 2 से शीर्ष 4 तक है। दरअसल, जैसा कि हम में देखते हैं कॉलमअंजीर में। 4.2, ऐसा मार्ग है: a 6 , a 5 । मैट्रिक्स ए 2 में "2" लंबाई 2 के दो पथों के अस्तित्व को इंगित करता है जो शीर्ष 3 से शीर्ष 6: a 8 , a 4 और a 10 , a 3 तक होते हैं।

इसी प्रकार, तीसरी घात A 3 (तालिका 4.1c) तक बढ़ाए गए आसन्न मैट्रिक्स के लिए, a (3) ik लंबाई 3 के x i से x k तक जाने वाले पथों की संख्या के बराबर है। मैट्रिक्स ए 3 की चौथी पंक्ति से यह देखा जा सकता है कि लंबाई 3 के पथ हैं: 4 में x 4 में से एक (ए 9, ए 8, ए 5), x 4 में से एक

x 5 (a 9, a 10, a 6) और x 4 से 6 में दो पथ (a 9, a 10, a 3 और a 9, a 8, a 4)। मैट्रिक्स ए 4 लंबाई 4 (तालिका 4.1 डी) के पथों के अस्तित्व को दर्शाता है।

इस प्रकार, यदि a p ik आव्यूह A p का एक अवयव है, तो a p ik x i से x k तक जाने वाले p लंबाई के पथों (जरूरी नहीं कि या जंजीर या सरल या जंजीर) की संख्या के बराबर है।

रीचैबिलिटी ग्राफ

रेखांकन के अध्ययन में जो पहला प्रश्न उठता है, वह है दिए गए या सभी युग्मों के बीच पथों के अस्तित्व का प्रश्न। इस प्रश्न का उत्तर ग्राफ़ G=(V,E) के शीर्ष पर पुन: प्रयोज्यता का उपरोक्त संबंध है: वर्टेक्स w वर्टेक्स v से पहुंच योग्य है यदि v = w या G में v से w तक का पथ है। दूसरे शब्दों में, रीचैबिलिटी रिलेशन संबंध ई का रिफ्लेक्सिव और ट्रांजिटिव क्लोजर है। अप्रत्यक्ष ग्राफ के लिए, यह संबंध भी सममित है और इसलिए, वर्टेक्स सेट वी पर एक समकक्ष संबंध है। एक अप्रत्यक्ष ग्राफ में, रीचैबिलिटी समकक्ष वर्ग हैं जुड़े घटक कहलाते हैं। निर्देशित ग्राफ़ के लिए, सामान्य रूप से, रीचैबिलिटी को एक सममित संबंध नहीं होना चाहिए। पारस्परिक पहुंच योग्यता सममित है।

परिभाषा 9.8.एक निर्देशित ग्राफ G=(V,E) के शीर्षों v और w को पारस्परिक रूप से पहुंच योग्य कहा जाता है यदि G के पास v से w तक का पथ और w से v तक का पथ है।

यह स्पष्ट है कि पारस्परिक रीचैबिलिटी संबंध रिफ्लेक्सिव, सममित और संक्रमणीय है, और इसलिए ग्राफ के शीर्ष सेट पर एक समानता है। पारस्परिक पहुंच योग्यता के संबंध में समानता वर्गों को दृढ़ता से जुड़े घटक कहा जाता है या दोगुने जुड़े घटकग्राफ।

आइए पहले पहुंच योग्यता संबंध के निर्माण के प्रश्न पर विचार करें। आइए हम प्रत्येक ग्राफ़ के लिए इसके रीचैबिलिटी ग्राफ़ (कभी-कभी ट्रांज़िटिव क्लोजर ग्राफ़ भी कहा जाता है) को परिभाषित करें, जिसके किनारे मूल ग्राफ़ के पथ से मेल खाते हैं।

परिभाषा 9.9.माना G=(V,E) एक निर्देशित ग्राफ है। जी के लिए रीचैबिलिटी ग्राफ जी * = (वी, ई *) में शिखर वी का एक ही सेट है और किनारों के निम्नलिखित सेट ई * = ((यू, वी) | ग्राफ जी में, वर्टेक्स वी वर्टेक्स से पहुंच योग्य है यू)।

उदाहरण 9.3।उदाहरण 9.2 से आलेख G पर विचार करें।

चावल। 9.2.गिनती जी

फिर हम जांच सकते हैं कि जी के लिए रीचैबिलिटी ग्राफ जी * इस तरह दिखता है (प्रत्येक कोने में 1-5 नए लूप किनारों को नहीं दिखाया गया है):

चावल। 9.3.गिनती जी*

ग्राफ़ G से ग्राफ़ G * का निर्माण कैसे किया जा सकता है? एक तरीका यह है कि ग्राफ जी के प्रत्येक शीर्ष के लिए यह निर्धारित किया जाए कि इससे प्राप्त होने वाले शिखरों का सेट क्रमिक रूप से इसमें 0, 1, 2, और इसी तरह की लंबाई के पथों से पहुंचने योग्य शिखरों को जोड़कर।

हम ग्राफ जी और बूलियन संचालन के आसन्न मैट्रिक्स ए जी के उपयोग के आधार पर एक और विधि पर विचार करेंगे। माना शीर्षों का समुच्चय V=(v 1 , … , v n ) है। तब आव्यूह A G एक n × n बूलियन आव्यूह है।

नीचे, मैट्रिसेस पर सामान्य संचालन के साथ समानता को बनाए रखने के लिए, हम बूलियन संचालन के लिए "अंकगणित" संकेतन का उपयोग करेंगे: हम संयोजन को + से और संयोजन को · द्वारा निरूपित करेंगे।

आकार n × n के पहचान मैट्रिक्स E n द्वारा निरूपित करें। चलो रखो . माना G* के निर्माण की हमारी प्रक्रिया निम्नलिखित कथन पर आधारित है।

लेम्मा 9.2।होने देना । फिर

सबूतआइए k पर प्रेरण द्वारा क्रियान्वित करें।

आधार। k=0 और k=1 के लिए, कथन परिभाषा के अनुसार सत्य है और .

प्रेरण कदम।मान लीजिए कि लेम्मा k के लिए मान्य है। आइए हम दिखाते हैं कि यह k + 1 के लिए भी मान्य रहता है। परिभाषा के अनुसार हमारे पास है:

मान लें कि ग्राफ G में v i से v j तक लंबाई k+1 का पथ है। इनमें से सबसे छोटे रास्तों पर विचार करें। यदि इसकी लंबाई k है, तो प्रेरण परिकल्पना द्वारा a_(ij)^((k))=1. इसके अलावा, एक jj (1) = 1। इसलिए a ij (k) a jj (1) =1 और a ij (k+1) =1. यदि v i से v j तक के सबसे छोटे पथ की लंबाई k+1 के बराबर है, तो मान लें कि v r इसका अंतिम शीर्ष है। फिर v i से v r तक लंबाई k का एक पथ है और, प्रेरण परिकल्पना द्वारा, एक ir (k) = 1। चूँकि (v r ,v j) E, तो a_(rj)^((1))=1. इसलिए a ir (k) a rj (1) =1 और a ij (k+1) =1.

इसके विपरीत, यदि a ij (k+1) =1, तो कम से कम एक r के लिए सारांश a ir (k) a rj (1) 1 के बराबर है। यदि यह r=j है, तो a ij (k) = 1 और आगमनात्मक परिकल्पना के अनुसार, G की लंबाई k से v i से v j तक का पथ है। अगर आर जे, फिर एक आईआर (के) = 1 और एक आरजे (1) = 1। इसका मतलब यह है कि G के पास लंबाई k और एक किनारे (v r ,v j) E से v i से v r तक का पथ है। उन्हें मिलाकर, हमें v i से v j लंबाई k+1 का पथ मिलता है।

लेम्मास 9.1 और 9.2 से हम सीधे प्राप्त करते हैं

परिणाम 1.माना G=(V,E) एक निर्देशित ग्राफ है जिसमें n शीर्ष हैं और G * इसकी पहुंच योग्यता ग्राफ है। तब ए_(जी*) = . सबूत।लेम्मा 5.1 का तात्पर्य है कि यदि G के पास u से v u तक का पथ है, तो इसका u से v लंबाई n-1 तक का एक सरल पथ भी है। और लेम्मा 5.2 द्वारा, ऐसे सभी पथ मैट्रिक्स में दर्शाए गए हैं।

इस प्रकार, जी के लिए रीचैबिलिटी ग्राफ के आसन्न मैट्रिक्स ए जी * के निर्माण की प्रक्रिया मैट्रिक्स को एन -1 की शक्ति तक बढ़ाने के लिए कम कर दी गई है। आइए इस प्रक्रिया को सरल बनाने के लिए कुछ टिप्पणियां करें।

जहाँ k सबसे छोटी संख्या इस प्रकार है कि 2 k n है।

ऐसा r पाया जाता है कि a ir = 1 और a rj = 1, तो संपूर्ण योग a ij (2) =1. इसलिए, बाकी शर्तों को अनदेखा किया जा सकता है।

उदाहरण 9.3।आइए एक उदाहरण के रूप में प्रस्तुत ग्राफ जी के लिए रीचैबिलिटी ग्राफ ए जी * के मैट्रिक्स की गणना पर विचार करें अंजीर.9.2. इस मामले में

चूँकि G के 6 शीर्ष हैं, तो . आइए इस मैट्रिक्स की गणना करें:

और (अंतिम समानता की जांच करना आसान है)। इस तरह,

जैसा कि आप देख सकते हैं, यह मैट्रिक्स वास्तव में दिखाए गए ग्राफ को परिभाषित करता है अंजीर.9.3.

म्युचुअल रीचैबिलिटी, मजबूती से जुड़े घटक, और ग्राफ़ बेस

रीचैबिलिटी ग्राफ के अनुरूप, हम मजबूत रीचैबिलिटी के ग्राफ को परिभाषित करते हैं।

परिभाषा 9.10.माना G=(V,E) एक निर्देशित ग्राफ है। G के लिए दृढ़ता से पहुंचने योग्य ग्राफ G * * =(V,E * *) में शिखर V का एक ही सेट है और किनारों का निम्नलिखित सेट E * * =( (u, v) | G में, शीर्ष v और u परस्पर हैं पहुंच योग्य)।

रीचैबिलिटी ग्राफ के मैट्रिक्स से, मजबूत रीचैबिलिटी ग्राफ के मैट्रिक्स का निर्माण करना आसान है। वास्तव में, यह रीचैबिलिटी और मजबूत रीचैबिलिटी की परिभाषाओं से सीधे अनुसरण करता है कि सभी जोड़े (i,j), 1 i,j n के लिए, एक तत्व का मान 1 के बराबर होता है यदि और केवल यदि दोनों तत्व A G* (i, j) और A G* (j, i) 1 के बराबर हैं, अर्थात।

मैट्रिक्स के आधार पर, ग्राफ G के दृढ़ता से जुड़े घटकों को निम्नानुसार अलग किया जा सकता है।

    आइए हम घटक K 1 में शीर्ष v 1 और सभी शीर्षों v j को इस प्रकार रखें कि A_(G_*^*)(1,j) = 1.

    मान लें कि घटक K 1 ,…, K i और v k पहले से ही बनाए जा चुके हैं - यह न्यूनतम संख्या वाला शीर्ष है जिसे अभी तक घटकों में शामिल नहीं किया गया है। फिर हम घटक K_(i+1) शीर्ष v k और ऐसे सभी शीर्षों v j को रखते हैं,

    कि A_(G_*^*)(k,j) = 1.

चरण (2) दोहराएं जब तक कि सभी कोने घटकों के बीच वितरित न हो जाएं।

हमारे उदाहरण में, ग्राफ G on . के लिए रेखा चित्र नम्बर 2मैट्रिक्स द्वारा, हम मजबूत रीचैबिलिटी के ग्राफ के निम्नलिखित मैट्रिक्स प्राप्त करते हैं:

ऊपर वर्णित प्रक्रिया का उपयोग करते हुए, हम पाते हैं कि ग्राफ G के शीर्षों को 4 दृढ़ता से जुड़े घटकों में विभाजित किया गया है: K 1 = (v 1, v 2 , v 3 ), \ K 2 = (v 4 ), \ K 3 = ( वी 5 ), \ के 4 =( वी 6 )। दृढ़ता से जुड़े घटकों के सेट पर, हम रीचैबिलिटी संबंध को भी परिभाषित करते हैं।

परिभाषा 9.11.मान लीजिए K और K" ग्राफ G के दृढ़ता से जुड़े हुए घटक हैं। घटक K से पहुंचा जा सकता हैघटक K^\prime अगर K= K" या दो कोने u K और v K" हैं, जैसे कि u v से पहुंच योग्य है। क से सख्ती से प्राप्त करने योग्य K^\ prime अगर K K" और K K से पहुंच योग्य है"। K घटक कहा जाता है न्यूनतमअगर यह किसी भी घटक से सख्ती से उपलब्ध नहीं है।

चूंकि एक घटक में सभी कोने परस्पर पहुंच योग्य हैं, इसलिए यह देखना आसान है कि घटकों पर पहुंच योग्यता और सख्त पहुंच योग्यता के संबंध यू के और वी के शिखर की पसंद पर निर्भर नहीं हैं"।

सख्त रीचैबिलिटी की निम्नलिखित विशेषता को परिभाषा से आसानी से निकाला जा सकता है।

लेम्मा 9.3।सख्त पहुंच योग्यता संबंध आंशिक आदेश संबंध है, यानी। यह एंटीरफ्लेक्सिव, एंटीसिमेट्रिक और ट्रांजिटिव है।

इस संबंध को एक निर्देशित ग्राफ के रूप में दर्शाया जा सकता है जिसका शिखर घटक हैं, और किनारे (के", के) का अर्थ है कि के के से सख्ती से पहुंचा जा सकता है"। पर चावल। 9.4घटकों का यह ग्राफ ऊपर माने गए ग्राफ G के लिए दिखाया गया है।

चावल। 9.4.

इस मामले में, एक न्यूनतम घटक K 2 है।

कई अनुप्रयोगों में, एक निर्देशित ग्राफ कुछ संसाधनों का वितरण नेटवर्क होता है: उत्पाद, उत्पाद, सूचना, आदि। ऐसे मामलों में, समस्या स्वाभाविक रूप से ऐसे बिंदुओं (शिखरों) की न्यूनतम संख्या खोजने की उत्पन्न होती है, जिनसे यह संसाधन नेटवर्क के किसी भी बिंदु तक पहुंचाया जा सकता है।

परिभाषा 9.12.माना G=(V,E) एक निर्देशित ग्राफ है। W V शीर्षों के उपसमुच्चय को कहा जाता है उत्पादक, यदि W के शीर्षों से ग्राफ के किसी भी शीर्ष तक पहुंचना संभव है। शीर्षों के एक उपसमुच्चय W V को एक ग्राफ आधार कहा जाता है यदि यह उत्पन्न कर रहा है, लेकिन इसका कोई भी उपसमुच्चय उत्पन्न नहीं कर रहा है।

निम्नलिखित प्रमेय एक ग्राफ के सभी आधारों को कुशलतापूर्वक खोजने की अनुमति देता है।

प्रमेय 9.1.माना G=(V,E) एक निर्देशित ग्राफ है। शीर्षों का एक उपसमुच्चय W V, G का आधार होता है यदि और केवल यदि इसमें G के प्रत्येक न्यूनतम दृढ़ता से जुड़े घटक से एक शीर्ष होता है और इसमें कोई अन्य शीर्ष नहीं होता है।

सबूतपहले ध्यान दें कि ग्राफ़ का प्रत्येक शीर्ष एक ऐसे शीर्ष से पहुँचा जा सकता है जो कुछ न्यूनतम घटक से संबंधित है। इसलिए, प्रत्येक न्यूनतम घटक से एक शीर्ष युक्त वर्टिस W का सेट उत्पन्न हो रहा है, और जब कोई शीर्ष इससे हटा दिया जाता है, तो यह ऐसा होना बंद हो जाता है, क्योंकि संबंधित न्यूनतम घटक से कोने पहुंच से बाहर हो जाते हैं। इसलिए W एक आधार है।

इसके विपरीत, यदि W एक आधार है, तो इसमें प्रत्येक न्यूनतम घटक से कम से कम एक शीर्ष शामिल होना चाहिए, अन्यथा ऐसे न्यूनतम घटक के शीर्ष दुर्गम होंगे। डब्ल्यू में कोई अन्य शिखर नहीं हो सकता है, क्योंकि उनमें से प्रत्येक पहले से शामिल शिखर से पहुंच योग्य है।

इस प्रमेय का तात्पर्य ग्राफ G के सभी आधारों को एक बनाने या सूचीबद्ध करने के लिए निम्नलिखित प्रक्रिया से है।

    G के सभी दृढ़ता से जुड़े घटकों का पता लगाएं।

    उन पर आदेश निर्धारित करें और उन घटकों का चयन करें जो इस आदेश के संबंध में न्यूनतम हैं।

    प्रत्येक न्यूनतम घटक से एक शीर्ष चुनकर ग्राफ के एक या सभी आधार उत्पन्न करें।

उदाहरण 9.5।हम निर्देशित ग्राफ G के सभी आधारों को परिभाषित करते हैं अंजीर.9.5.

चावल। 9.5गिनती जी

पहले चरण में, हम G के दृढ़ता से जुड़े हुए घटक पाते हैं:

दूसरे चरण में, हम इन घटकों पर एक सख्त रीचैबिलिटी ग्राफ का निर्माण करते हैं।

चावल। 9.6.जी घटकों पर रीचैबिलिटी संबंध ग्राफ

हम न्यूनतम घटक निर्धारित करते हैं: के 2 = (बी), के 4 = (डी, ई, एफ, जी) और के 7 = (आर)।

अंत में, हम जी के सभी चार आधारों को सूचीबद्ध करते हैं: बी 1 = (बी, डी, आर), बी 2 = (बी, ई, आर), बी 3 = (बी, एफ, आर) और बी 1 = (बी, जी , आर)।

कार्य

समस्या 9.1।सिद्ध कीजिए कि एक मनमाना निर्देशित आलेख के सभी शीर्षों की घातों का योग सम होता है।

इस समस्या की एक लोकप्रिय व्याख्या है: यह साबित करने के लिए कि पार्टी में आए लोगों द्वारा आदान-प्रदान किए गए हैंडशेक की कुल संख्या हमेशा सम होती है।

समस्या 9.2।उन सभी गैर-समरूपी अप्रत्यक्ष ग्राफ़ों की सूची बनाएं जिनमें अधिकतम चार शीर्ष हों।

समस्या 9.3।सिद्ध कीजिए कि एक अप्रत्यक्ष जुड़ा ग्राफ किसी किनारे को हटाने के बाद भी जुड़ा रहता है यह किनारा किसी चक्र का है।

समस्या 9.4।सिद्ध कीजिए कि n शीर्षों वाला एक अप्रत्यक्ष जुड़ा हुआ ग्राफ

    कम से कम n-1 किनारे होते हैं,

    यदि इसमें n-1 से अधिक किनारे हैं, तो इसका कम से कम एक चक्र है।

समस्या 9.5.सिद्ध कीजिए कि 6 लोगों के किसी भी समूह में तीन जोड़ीदार परिचित या तीन जोड़ीदार अजनबी हैं।

समस्या 9.6।साबित करें कि अप्रत्यक्ष ग्राफ G=(V,E) जुड़ा हुआ है ↔ प्रत्येक विभाजन के लिए V= V 1 V 2 गैर-रिक्त V 1 और V 2 के साथ V 1 को V 2 से जोड़ने वाला एक किनारा है।

समस्या 9.7।सिद्ध कीजिए कि यदि एक अप्रत्यक्ष ग्राफ में विषम अंश के ठीक दो शीर्ष हों, तो वे एक पथ से जुड़े होते हैं।

समस्या 9.8.माना G=(V,E) एक अप्रत्यक्ष ग्राफ है |E|< |V|-1. Докажите, что тогда G несвязный граф.

समस्या 9.9.सिद्ध कीजिए कि जुड़े अप्रत्यक्ष ग्राफ में अधिकतम लंबाई के किन्हीं दो सरल पथों में एक उभयनिष्ठ शीर्ष होता है।

समस्या 9.10.चलो एक अप्रत्यक्ष ग्राफ बिना लूप के G=(V,E) में k जुड़े हुए घटक हैं। सिद्ध करो कि तब

समस्या 9.11.परिभाषित करें कि के लिए रीचैबिलिटी ग्राफ़ क्या है

    n शीर्षों वाला एक ग्राफ और किनारों का एक खाली सेट;

    n शीर्षों वाला ग्राफ: V= (v 1 ,… , v n ), जिसके किनारे एक चक्र बनाते हैं:

समस्या 9.12.ग्राफ़ के लिए रीचैबिलिटी ग्राफ़ मैट्रिक्स की गणना करें

और संबंधित रीचैबिलिटी ग्राफ का निर्माण करें। ग्राफ G के सभी आधार ज्ञात कीजिए।

समस्या 9.13.दिए गए के लिए निर्माण चावल। 9.7निर्देशित ग्राफ G 1 =(V,E) इसकी आसन्नता मैट्रिक्स A G1, घटना मैट्रिक्स B G1 और आसन्नता सूचियाँ। रीचैबिलिटी मैट्रिक्स ए जी 1 * की गणना करें और संबंधित रीचैबिलिटी ग्राफ जी 1 * का निर्माण करें।

चावल। 9.7.

अप्रत्यक्ष और उन्मुख पेड़

पेड़ विभिन्न प्रकार की पदानुक्रमित संरचनाओं का प्रतिनिधित्व करने के लिए उपयोग किए जाने वाले रेखांकन के सबसे दिलचस्प वर्गों में से एक हैं।

परिभाषा 10.1।एक अप्रत्यक्ष ग्राफ को एक पेड़ कहा जाता है यदि यह जुड़ा हुआ है और इसमें कोई चक्र नहीं है।

परिभाषा 10.2.एक निर्देशित ग्राफ G=(V,E) को एक (निर्देशित) वृक्ष कहा जाता है यदि

पर चावल। 10.1एक अप्रत्यक्ष पेड़ जी 1 और एक निर्देशित पेड़ जी 2 के उदाहरण दिखाए गए हैं। ध्यान दें कि पेड़ जी 2 को रूट के रूप में वर्टेक्स सी चुनकर और "रूट से दूर" दिशा में सभी किनारों को उन्मुख करके जी 1 से प्राप्त किया जाता है।

चावल। 10.1.अप्रत्यक्ष और निर्देशित पेड़

यह कोई संयोग नहीं है। अप्रत्यक्ष और निर्देशित पेड़ों के बीच संबंध के बारे में निम्नलिखित कथन को स्वयं सिद्ध करें।

लेम्मा 10.1।यदि किसी अप्रत्यक्ष वृक्ष G=(V,E) में हम जड़ के रूप में एक मनमाना शीर्ष v V चुनते हैं और सभी किनारों को "रूट से" दिशा में उन्मुख करते हैं, अर्थात। v को इसके सभी किनारों की घटना की शुरुआत करें, v से सटे कोने - सभी की शुरुआत जो अभी तक निर्देशित किनारों की घटना से v, आदि नहीं है, फिर परिणामी निर्देशित ग्राफ G" एक निर्देशित पेड़ होगा।

अप्रत्यक्ष और निर्देशित पेड़ों में कई समान विशेषताएं हैं।

प्रमेय 10.1।चलो G=(V,E) एक अप्रत्यक्ष ग्राफ हो। फिर निम्नलिखित शर्तें समान हो जाती हैं।

    जी एक पेड़ है।

    G में किन्हीं दो शीर्षों के लिए, उन्हें जोड़ने वाला एक अनूठा पथ है।

    G जुड़ा हुआ है, लेकिन जब E से कोई किनारा हटा दिया जाता है, तो वह जुड़ना बंद कर देता है।

    G जुड़ा हुआ है और |E| = |वी| -एक।

    G विश्वकोश है और |E| = |वी| -एक।

    G विश्वकोश है, लेकिन E में किसी भी किनारे को जोड़ने से एक चक्र उत्पन्न होता है।

सबूत(1) (2) : यदि G के कुछ दो शीर्षों को दो पथों से जोड़ा जाता है, तो जाहिर है, G में एक चक्र होगा। लेकिन यह (1) में पेड़ की परिभाषा के विपरीत है।

(2) (3): यदि G जुड़ा है, लेकिन E जुड़ा रहता है जब कुछ किनारे (u,v) को हटा दिया जाता है, तो u और v के बीच एक पथ होता है जिसमें यह किनारा नहीं होता है। लेकिन तब G के पास u और v को जोड़ने वाले कम से कम दो पथ हैं, जो कि स्थिति (2) के विपरीत है।

(3) (4): पाठक को प्रदान किया गया (देखें समस्या 9.4)।

(4) (5): यदि G में एक चक्र है और जुड़ा हुआ है, तो चक्र से किसी भी किनारे को हटाते समय, कनेक्टिविटी नहीं टूटनी चाहिए, लेकिन किनारे बने रहते हैं |E|=V-2, और समस्या 9.4(a) से ), कनेक्टेड ग्राफ़ में कम से कम V-1 पसलियां होनी चाहिए। परिणामी विरोधाभास दर्शाता है कि G में कोई चक्र नहीं है और स्थिति (5) संतुष्ट है।

(5) (6): मान लीजिए कि E में एक किनारा (u,v) जोड़ने से चक्र नहीं बनता है। फिर G में शीर्ष u और v अलग-अलग जुड़े हुए घटकों में हैं। चूँकि |E|= V -1, तो इन घटकों में से एक में, इसे (V 1, E 1) होने दें, किनारों की संख्या और शीर्षों की संख्या समान है: |E 1 |=|V 1 |। लेकिन फिर इसमें एक चक्र होता है (समस्या 9.4 (बी) देखें), जो इस तथ्य का खंडन करता है कि जी चक्रीय है।

(6) (1): यदि G कनेक्ट नहीं होता, तो अलग-अलग कनेक्टेड घटकों से दो कोने u और v होते। फिर किनारे (u,v) को E में जोड़ने से एक चक्र का आभास नहीं होगा, जो विरोधाभासी (6) है। इसलिए G जुड़ा हुआ है और एक पेड़ है।

निर्देशित पेड़ों के लिए, निम्नलिखित आगमनात्मक परिभाषा का उपयोग करना अक्सर सुविधाजनक होता है।

परिभाषा 10.3.हम प्रेरण द्वारा निर्देशित रेखांकन के एक वर्ग को परिभाषित करते हैं जिसे पेड़ कहा जाता है। उसी समय, उनमें से प्रत्येक के लिए, हम एक चयनित शीर्ष - रूट को परिभाषित करते हैं।

चावल। 10.2इस परिभाषा को दर्शाता है।

चावल। 10.2निर्देशित पेड़ों की आगमनात्मक परिभाषा

प्रमेय 10.2।निर्देशित पेड़ों की परिभाषाएँ 10.2 और 10.3 समतुल्य हैं।

सबूतमान लीजिए कि ग्राफ G=(V,E) परिभाषा 10.2 की शर्तों को पूरा करता है। आइए हम शीर्षों की संख्या पर प्रेरण द्वारा दिखाते हैं |V| कि ।

यदि |V|=1, तो केवल शीर्ष v V संपत्ति के अनुसार पेड़ की जड़ है (1), अर्थात। इस ग्राफ में कोई किनारा नहीं है: E = . फिर ।

मान लीजिए कि n शीर्षों वाला कोई भी ग्राफ जो परिभाषा 10.2 को संतुष्ट करता है, में शामिल है। मान लीजिए कि ग्राफ G=(V,E) (n+1)-वें शीर्ष के साथ परिभाषा 10.2 की शर्तों को पूरा करता है। शर्त के अनुसार (1), इसका एक मूल शीर्ष r 0 है। माना k किनारे r 0 से निकलते हैं और वे शीर्षों r 1 , … , r k (k 1) की ओर ले जाते हैं। G i ,(i=1,…, k) द्वारा निरूपित करें जिसमें शीर्ष V i =(v V|v \textit( से पहुंच योग्य )r i ) और किनारों E i E को जोड़ने वाले ग्राफ़ शामिल हैं। यह देखना आसान है कि G, परिभाषा 10.2 की शर्तों को पूरा करता है। वास्तव में, r में किनारे नहीं होते हैं, अर्थात, यह शीर्ष G i का मूल है। V i के अन्य शीर्षों में से प्रत्येक का एक किनारा है, ठीक G की तरह। यदि v V i , तो यह ग्राफ़ G i की परिभाषा के द्वारा मूल r i से प्राप्त किया जा सकता है। चूंकि |वी मैं | n, फिर आगमनात्मक परिकल्पना द्वारा। फिर ग्राफ़ G, परिभाषा 10.3 के आगमनात्मक नियम (2) द्वारा पेड़ों G 1, ..., G k से प्राप्त किया जाता है और इसलिए वर्ग से संबंधित है।

यदि कुछ ग्राफ G=(V,E) वर्ग से संबंधित है, तो परिभाषा 10.2 की शर्तों (1)-(3) की पूर्ति इसके लिए परिभाषा 10.2 पर प्रेरण द्वारा आसानी से स्थापित की जा सकती है। हम इसे एक अभ्यास के रूप में पाठक पर छोड़ते हैं।

उन्मुख पेड़ों से जुड़ी एक समृद्ध शब्दावली है, जो दो स्रोतों से आती है: वनस्पति विज्ञान और पारिवारिक संबंधों का क्षेत्र।

जड़ ही एकमात्र शीर्ष है जिसमें किनारे नहीं होते हैं, पत्ते ऐसे शीर्ष होते हैं जिनमें किनारे नहीं होते हैं। जड़ से पत्ती तक के मार्ग को वृक्ष की शाखा कहते हैं। एक पेड़ की ऊंचाई उसकी शाखाओं की अधिकतम लंबाई है। एक शीर्ष की गहराई मूल से उस शीर्ष तक पथ की लंबाई है। एक शीर्ष v V के लिए, पेड़ T=(V,E) का उप-ग्राफ, जिसमें v से पहुंचने योग्य सभी शीर्ष और उन्हें जोड़ने वाले E से किनारे शामिल हैं, रूट v के साथ पेड़ T का एक उपवृक्ष T v बनाता है (समस्या 10.3 देखें) ) वी की ऊंचाई टी वी पेड़ की ऊंचाई है। एक ग्राफ जो कई अप्रतिच्छेदित वृक्षों का मिलन होता है, वन कहलाता है।

यदि कोई किनारा शीर्ष v से शीर्ष w की ओर जाता है, तो v कहलाता है पिताडब्ल्यू, और डब्ल्यू - बेटा v (हाल ही में, अंग्रेजी भाषा के साहित्य में अलैंगिक शब्दों का इस्तेमाल किया गया है: माता-पिता - बच्चा)। यह एक पेड़ की परिभाषा से सीधे अनुसरण करता है कि प्रत्येक शीर्ष में जड़ के अलावा एक अद्वितीय पिता होता है। यदि कोई पथ शीर्ष v से शीर्ष w तक जाता है, तो v को w का पूर्वज कहा जाता है, और w को v का वंशज कहा जाता है। जिन शीर्षों में एक समान पिता होता है उन्हें कहा जाता है भाई बंधुया बहन की.

हम रेखांकन के एक और वर्ग को अलग करते हैं जो निर्देशित पेड़ों को सामान्य करता है - निर्देशित विश्वकोश। बूलियन फ़ंक्शंस का प्रतिनिधित्व करने के लिए दो प्रकार के ऐसे लेबल वाले ग्राफ़ का उपयोग नीचे किया जाएगा। इन ग्राफ़ में कई जड़ें हो सकती हैं - कोने जिनमें किनारे शामिल नहीं होते हैं, और प्रत्येक शीर्ष में कई किनारे हो सकते हैं, और एक नहीं, जैसे कि पेड़।


संगणक तकनीकी, विशेष रूप से कार्यक्रम ... 2009 वर्ष काप्राथमिक विद्यालय एक प्रायोगिक स्थल है परसंघीय की शुरूआत राज्य ...

  • एम ओनिटोरिंग मीडिया व्यावसायिक शिक्षा का आधुनिकीकरण मार्च-अगस्त 2011

    सारांश

    यूनाइटेड राज्यपरीक्षा" परपसंद": सूचनात्मक संगणकतकनीकी, जीव विज्ञान और साहित्य। वैसे, इसमें सालउपयोग... प्रश्न"कार्यान्वयन के परिणामों पर कार्यक्रमोंमें राष्ट्रीय अनुसंधान विश्वविद्यालयों का विकास 2009 -2010 वर्षों". ...

  • सामरिक विकास कार्यक्रम Tver 2011

    कार्यक्रम

    पर 2009 साल. 2010 में देखे गए संरचनात्मक बदलाव सालपरकी ओर 2009 , ... पेशेवर रूप से – उन्मुखीविदेशी भाषा", "आधुनिक शैक्षिक" तकनीकी". सभी में कार्यक्रमउन्नत प्रशिक्षण मॉड्यूल " राज्य ...

    • 1. रीचैबिलिटी और काउंटररीचैबिलिटी

    ऐसी बहुत सी समस्याएं हैं जिनमें रीचैबिलिटी की धारणा का उपयोग किया जाता है। यहाँ उपनामों में से एक है। एक ग्राफ किसी प्रकार के संगठन का एक मॉडल हो सकता है, जिसमें लोगों को शीर्षों द्वारा दर्शाया जाता है, और चाप संचार चैनलों की व्याख्या करते हैं। इस तरह के एक मॉडल पर विचार करते समय, कोई यह सवाल उठा सकता है कि क्या एक व्यक्ति x की जानकारी दूसरे व्यक्ति x 7 को स्थानांतरित की जा सकती है, अर्थात। क्या शीर्ष x से शीर्ष X/ तक पथ है। यदि ऐसा पथ मौजूद है, तो शीर्ष x को शीर्ष x से पहुंच योग्य कहा जाता है। किसी को शीर्ष x की पहुंच योग्यता में रुचि हो सकती है, - शीर्ष x से, केवल ऐसे पथों पर, जिनकी लंबाई किसी दिए गए मान से अधिक नहीं होती है या जिसकी लंबाई ग्राफ़ में सबसे बड़ी संख्या में कोने से कम होती है।

    ग्राफ़ में रीचैबिलिटी को रीचैबिलिटी मैट्रिक्स R = ||r, y|| द्वारा वर्णित किया गया है, मैं, जो =1,2,... पी,कहाँ पे पीग्राफ़ के शीर्षों की संख्या है, और प्रत्येक तत्व को इस प्रकार परिभाषित किया गया है:

    गुजरात 1 अगर शीर्ष एक्स,एक्स से पहुंच योग्य,

    गु = 0 अन्यथा।

    किसी दिए गए शीर्ष xn से पहुंच योग्य ग्राफ G के शीर्षों R(x,) के समुच्चय में ऐसे तत्व x होते हैं; , जिसके लिए (/, /) - रीचैबिलिटी मैट्रिक्स में तत्व 1 के बराबर है। यह स्पष्ट है कि मैट्रिक्स आर में सभी विकर्ण तत्व 1 के बराबर हैं, क्योंकि प्रत्येक शीर्ष एक पथ द्वारा स्वयं से पहुंच योग्य है लंबाई 0. चूंकि पहले क्रम का प्रत्यक्ष मानचित्रण +1 (x,) ऐसे शीर्षों का समुच्चय है एक्सजे,जो लंबाई 1 के पथों का उपयोग करके x से पहुंच योग्य हैं, फिर सेट Γ (Γ (x,)) = Γ एक्स,)लंबाई 2 के पथों का उपयोग करके x से पहुंचने योग्य शिखर होते हैं। इसी प्रकार, पी (एक्स,)लंबाई के पथ का उपयोग करके x से पहुंचने योग्य शिखर का सेट है आर।

    चूँकि xn से पहुँचा जा सकने वाला कोई भी ग्राफ़ शीर्ष 0 या 1 या 2,..., या लंबाई के पथ (या पथ) का उपयोग करके पहुँचा जा सकता है, या आर, तो शीर्ष xn के लिए उपलब्ध शीर्षों के समुच्चय को इस प्रकार दर्शाया जा सकता है

    जैसा कि हम देखते हैं, पहुंच योग्य शीर्षों का समुच्चय R(x,) शीर्ष xn का प्रत्यक्ष संक्रमणीय समापन है, अर्थात। आर (एक्स,) = टी (एक्स,)। इसलिए, रीचैबिलिटी मैट्रिक्स का निर्माण करने के लिए, हम सभी शीर्षों x, e X के लिए रीचेबल सेट R(x,) पाते हैं। सेटिंग जी वाई - 1 अगर x 7 ई आर(एक्स,) और गुजरात 0 अन्यथा। अंजीर में दिखाए गए ग्राफ के लिए। 59.4, एक, रीचैबिलिटी सेट निम्नानुसार पाए जाते हैं:

    चावल। 59.4.

    आसन्नता (ए), रीचैबिलिटी (आर), काउंटररीचैबिलिटी (क्यू) के मैट्रिक्स के निम्नलिखित रूप हैं:

    काउंटररीचैबिलिटी मैट्रिक्स क्यू = क्यूज, मैं, जे = 1,2,... पी,कहाँ पे पी- ग्राफ के शीर्षों की संख्या निम्नानुसार निर्धारित की जाती है:

    क्यूज = 1 यदि xy . से शीर्ष पर पहुंचना संभव है एक्स एच क्यूटीजे =ओह अन्यथा।

    प्रतिपहुंच योग्य सेट क्यू (एक्स,)शीर्षों का समुच्चय इस प्रकार है कि इस समुच्चय के किसी भी शीर्ष से कोई व्यक्ति शीर्ष X/ पर जा सकता है। इसी तरह पहुंच योग्य सेट R(x,) के निर्माण के लिए कोई व्यंजक लिख सकता है क्यू (एक्स,):

    इस प्रकार, यह स्पष्ट है कि Q(x,) शीर्ष x के व्युत्क्रम संक्रमणीय बंद होने के अलावा और कुछ नहीं है, अर्थात। क्यू (एक्स () \u003d टी "(एक्स,)। यह परिभाषाओं से स्पष्ट है कि कॉलम एक्स, मैट्रिक्स क्यू (जिसमें क्यू टी जे = 1 अगर xy € Q(x,), और एस/वाई = 0अन्यथा) मैट्रिक्स R की पंक्ति x से मेल खाता है, अर्थात। क्यू = आर, जहां आर रीचैबिलिटी मैट्रिक्स आर में स्थानांतरित मैट्रिक्स है।

    काउंटररीचैबिलिटी मैट्रिक्स को पहले दिखाया गया है।

    यह ध्यान दिया जाना चाहिए कि चूंकि मैट्रिक्स आर और क्यू के सभी तत्व 1 या 0 के बराबर हैं, इसलिए प्रत्येक पंक्ति को बाइनरी रूप में संग्रहीत किया जा सकता है, जिससे कंप्यूटर मेमोरी लागत की बचत होती है। कंप्यूटर पर प्रसंस्करण के लिए मैट्रिक्स आर और क्यू सुविधाजनक हैं, क्योंकि गणना के संदर्भ में, मुख्य संचालन उच्च गति वाले तार्किक संचालन हैं।

    2. पथ में शामिल शीर्षों के समुच्चय का पता लगाना यदि आपको इन पथों में शामिल ग्राफ़ के शीर्षों के बारे में पता लगाना है, तो आपको प्रत्यक्ष और प्रतिलोम सकर्मक क्लोजर की परिभाषाओं को याद रखना चाहिए। चूँकि T + (x,) शीर्षों का समुच्चय है जिसमें शीर्ष x से पथ हैं, और T "(Y) शीर्षों का समुच्चय है जहाँ से x / तक पथ हैं, फिर T (x,) n T (एक्सजे)- शीर्षों का एक समूह, जिनमें से प्रत्येक x से xy तक कम से कम एक पथ से संबंधित है। इन शीर्षों को दो सिरों के संबंध में आवश्यक, या अभिन्न कहा जाता है। एक्स,और हू। ग्राफ़ के अन्य सभी शीर्षों को अप्रासंगिक या निरर्थक कहा जाता है, क्योंकि उनके हटाने से x/ से xy तक के पथ प्रभावित नहीं होते हैं।

    तो, अंजीर में ग्राफ के लिए। 59.5 पथ में शामिल शीर्षों को खोजना, उदाहरण के लिए, शीर्ष X2 से शीर्ष X4 तक, T + (xr) \u003d (xr, xs, X4, X5, Xb), T "(x4) \ u003d (xi, X2, X3, X4, X5), और उनके प्रतिच्छेदन T + (xz) n T(x4) = (X2, X3, X4, X 5 )।

    होने देना जी = (एक्स, डी) - मॉड्यूलर संरचना का ग्राफ, आर, एक्स-। -से संबंधित शीर्ष एक्स।अगर ग्राफ में जी x, to . से एक ओरिएंटेड चेन है एक्सपीफिर शीर्ष x, - शीर्ष x से पहुंच योग्य,-. निम्नलिखित कथन सत्य है: यदि एक शीर्ष Xjएक्स, कुल्हाड़ी से पहुंचा जा सकता है (- से एक्सपीफिर एक्स/से पहुंचा जा सकता है एक्स ^इस तथ्य का प्रमाण स्पष्ट है। सेट पर एक द्विआधारी संबंध पर विचार करें एक्स,जो ग्राफ़ के शीर्षों के बीच पहुंच योग्यता निर्धारित करता है। हम अंकन x का परिचय देते हैं, -> x, शीर्ष x की पहुंच योग्यता के लिए, - from एक्सजेसंबंध सकर्मक है। ग्राफ़ के शीर्षों के समुच्चय H(x,) से निरूपित करें जी,एक्स से पहुंच योग्य; . फिर समानता

    रीचैबिलिटी के संबंध में x के ट्रांजिटिव क्लोजर को परिभाषित करता है।

    आइए हम निम्नलिखित प्रमेय को सिद्ध करें।

    प्रमेय 1.1. मॉड्यूलर संरचना के ग्राफ के चयनित कनेक्टेड घटक के लिए, इस घटक के अनुरूप रूट से किसी भी शीर्ष तक पहुंचा जा सकता है, यानी। समानता (एक्स/-जड़ ऊपर)

    सबूत।मान लीजिए कि शीर्ष, (x, e .) एक्स) Xj से पहुंच योग्य नहीं है। फिर x, e X/ और समुच्चय एक्स" = एक्स x) खाली नहीं है। चूंकि ग्राफ का चयनित घटक जुड़ा हुआ है, तो शीर्ष x हैं, - इएक्स, और श्रृंखला /7(x; , एक्सजे), x, से x, - की ओर अग्रसर। ग्राफ की चक्रीयता के आधार पर जी,में एक्स"एक साधारण श्रृंखला होनी चाहिए एच (एक्स /, एक्सजे),शीर्ष पर कहाँ एक्स एफचाप शामिल न करें (यह श्रृंखला खाली हो सकती है यदि एक्स"केवल x,) के होते हैं। श्रृंखला एच (एक्स /, पर विचार करें) एक्सजे) = एच(एक्स/, एक्स,) यू आई (एक्स, एक्सजे)।इसका मतलब है कि एक्स। शीर्ष x, और . से पहुँचा जा सकता है Xjऔर दोनों शीर्षों में आवक चाप नहीं होते हैं। और यह एक एकल मूल शीर्ष के साथ एक मॉड्यूलर संरचना के ग्राफ की परिभाषा के विपरीत है। प्रमेय सिद्ध हो चुका है।

    रीचैबिलिटी के लिए मुख्य आवश्यकता ग्राफ़ में अप्रत्यक्ष चक्रों की अनुपस्थिति है। अंजीर में ग्राफ के आधार पर। 1.4, हम ध्यान दें कि ग्राफ में एक निर्देशित चक्र और कोने के अनुरूप मॉड्यूल होते हैं एक्स 4, एक्स 5, f 6 , कभी भी निष्पादित नहीं किया जाएगा। इस प्रकार, प्रमेय 1.1 के परिणाम इस आवश्यकता को मजबूत करते हैं कि मॉड्यूली ग्राफ में कोई निर्देशित चक्र नहीं है।

    मॉड्यूलर संरचना के ग्राफ के रीचैबिलिटी संबंध के मैट्रिक्स प्रतिनिधित्व का विश्लेषण करने के लिए, अंजीर में दिखाए गए रीचैबिलिटी मैट्रिक्स के ग्राफ पर विचार करें। 1.1.

    गुणक ए, वाई = 1 यदि इंडेक्स / के अनुरूप मॉड्यूल इंडेक्स से संबंधित मॉड्यूल से उपलब्ध है मैं।निम्नलिखित परिणाम ग्राफ सिद्धांत के एक प्रसिद्ध प्रमेय पर आधारित हैं।

    चावल। 1.4.

    प्रमेय 1.2. गुणक वह एल-थूआसन्न मैट्रिक्स की डिग्री विभिन्न मार्गों की संख्या को बढ़ाता है जिसमें / चाप होते हैं और शीर्ष को जोड़ते हैं एक्स/एस^-निर्देशित ग्राफ का शीर्ष।

    इस प्रमेय के निम्नलिखित तीन उपफलों पर विचार कीजिए।

    कोरोलरी 1.1.आव्यूह एम \u003d "? जे एम टी,कहाँ पे एम- अभिविन्यास की आसन्नता मैट्रिक्स

    के साथ थका हुआ ग्राफ पीकोने, रीचैबिलिटी मैट्रिक्स के साथ गुणांक के संख्यात्मक मानों तक मेल खाता है लेकिन।

    सबूत।एक निर्देशित ग्राफ़ में जिसमें पीशिखर, बिना चापों को दोहराए पथ की अधिकतम लंबाई से अधिक नहीं हो सकती पी।इसलिए, आसन्न मैट्रिक्स एम 1 की डिग्री का क्रम, जहां मैं = 1,2,

    i, n चापों वाले ग्राफ़ में सभी संभावित पथों की संख्या निर्धारित करता है। मान लीजिए गुणांक टी 1)मैट्रिक्स एमशून्य से भिन्न। इसका मतलब है कि मैट्रिक्स की एक डिग्री है एम>,जिसके लिए संबंधित गुणांक टी ()शून्य से भी भिन्न है। इसलिए ऊपर से रास्ता है Xjप्रति एक्सपीवे। शीर्ष ^ से पहुंच योग्य है एक्स आरयह कोरोलरी एक मॉड्यूलर संरचना के ग्राफ के कॉल मैट्रिक्स के कनेक्शन को निर्धारित करता है, जो रीचैबिलिटी मैट्रिक्स के साथ आसन्न मैट्रिक्स ए / के साथ मेल खाता है। लेकिनऔर बाद के निर्माण के लिए एल्गोरिथ्म निर्धारित करता है।

    कोरोलरी 1.2.कुछ के लिए चलो मैंआसन्न मैट्रिक्स की शक्तियों के क्रम में एम*एक गुणांक है टी X1> 0. फिर मूल ग्राफ में एक निर्देशित चक्र होता है।

    सबूत।होने देना मी (मैं > 0 कुछ के लिए मैं।फलस्वरूप, Xjसे पहुंचा जा सकता है एक्स वीवे। एक चक्र है। प्रमेय 1.2 के अनुसार, इस चक्र में / चाप होते हैं (आमतौर पर दोहराते हैं)।

    कोरोलरी 1.3।होने देना पी-आईनिकटता मैट्रिक्स डिग्री एमपीएसाइक्लिक ग्राफ शून्य मैट्रिक्स के साथ मेल खाता है (सभी गुणांक शून्य के बराबर हैं)।

    सबूत।यदि ग्राफ एसाइक्लिक है, तो इसमें सबसे सरल पथ में . से अधिक नहीं हो सकता है पी- 1 चाप। मैं फ़िन एमपीएक गैर-शून्य गुणांक है, तो एक पथ होना चाहिए जिसमें पीचाप और यह मार्ग केवल एक उन्मुख चक्र हो सकता है। इसलिए, सभी गुणांक एमपीएक चक्रीय ग्राफ के लिए शून्य हैं। यह कोरोलरी एक मॉड्यूलर संरचना के ग्राफ में चक्रों की अनुपस्थिति के लिए एक आवश्यक और पर्याप्त स्थिति प्रदान करता है।

    एसाइक्लिक ग्राफ़ के लिए, रीचैबिलिटी संबंध आंशिक सख्त क्रम के बराबर है। रीचैबिलिटी रिलेशन की ट्रांजिटिविटी पर ऊपर चर्चा की गई थी। एंटीसिमेट्री निर्देशित चक्रों की अनुपस्थिति से होती है: यदि शीर्ष एक्स )से पहुंचा जा सकता है एक्स वीतो उलटा सच नहीं है। हम संकेतन का परिचय देते हैं एक्स एक्स > एक्सपीअगर शीर्ष Xjऊपर से पहुंचा जा सकता है एक्स वी

    होने देना जी =(X, ) कुछ मॉड्यूलर संरचना के अनुरूप एक चक्रीय ग्राफ है। आंशिक रूप से क्रमित सेट X के तत्वों की अवरोही श्रृंखला पर विचार करें:

    जहां ">" चिह्न पहुंच योग्यता संबंध को दर्शाता है। क्यों कि एक्सबेशक, जंजीर टूट गई है एक्स एन > एक्स i2 > ... > एक्स इन।शिखर xjnकोई जावक चाप नहीं है, अर्थात। तत्व एक्स इनन्यूनतम (यह एक मॉड्यूल से मेल खाता है जिसमें अन्य मॉड्यूल के लिए कॉल नहीं होते हैं)। समुच्चय X में अधिकतम अवयव मूल शीर्ष है।

    • इस प्रमेय का प्रमाण कार्य (पुस्तक) में दिया गया है: Lavrishcheva E. M., Grishchenko V. N. असेंबली प्रोग्रामिंग। कीव: नौकोवा दुमका, 1991. 287 पी।

    रेखांकन में पहुंच और कनेक्टिविटी व्याख्यान की रूपरेखा: एक श्रृंखला और चक्र के पथ। ग्राफ कनेक्टिविटी और कनेक्टिविटी घटक। व्यास, त्रिज्या और ग्राफ का केंद्र।


    सामाजिक नेटवर्क पर काम साझा करें

    यदि यह कार्य आपको शोभा नहीं देता है, तो पृष्ठ के नीचे समान कार्यों की एक सूची है। आप खोज बटन का भी उपयोग कर सकते हैं



    बारानोव विक्टर पावलोविच डिस्क्रीट मैथ। धारा 3रेखांकन, नेटवर्क, कोड।

    व्याख्यान 8

    व्याख्यान 8 रेखांकन में पहुंच और जुड़ाव

    व्याख्यान योजना:

    1. मार्ग, जंजीर और चक्र।
    2. ग्राफ कनेक्टिविटी और कनेक्टिविटी घटक।
    3. व्यास, त्रिज्या और ग्राफ का केंद्र।
    4. रीचैबिलिटी और काउंटररीचैबिलिटी मैट्रिसेस।
    1. मार्ग, सर्किट और लूप

    उन्मुख मार्ग(या द्वारा ) एक डिग्राफ चापों का एक क्रम है जिसमें पिछले एक के अलावा किसी भी चाप का अंतिम शीर्ष अगले एक का प्रारंभिक शीर्ष होता है। अंजीर पर। 1 चाप अनुक्रम

    , (1)

    , (2)

    (3)

    रास्ते हैं।

    चावल। एक।

    उन्मुख श्रृंखला(या orepio ) वह पथ कहलाता है जिसमें प्रत्येक चाप औरसाथ एक से अधिक बार उपयोग नहीं किया। तो, उदाहरण के लिए, पथ (2) और (3) ऑर्चेन हैं, लेकिन पथ (1) नहीं है, क्योंकि इसमें दो बार चाप का उपयोग किया जाता है।

    सरल एक श्रृंखला कहलाती है जिसमें प्रत्येक शीर्ष का अधिकतम एक द्वारा उपयोग किया जाता हैके बारे में बार। उदाहरण के लिए, ऑर्चैन (3) सरल है, लेकिन ऑर्चैन (2) नहीं है।

    रास्ता पथ का एक अप्रत्यक्ष जुड़वां है, अर्थात, किनारों का एक क्रम जिसमें प्रत्येक किनारे, पहले और अंतिम को छोड़कर, किनारों के साथ अंतिम कोने से जुड़ा हुआ है और। एक चाप प्रतीक पर एक पट्टी का अर्थ है कि इसे किनारे के रूप में माना जाता है।

    जैसे हमने जंजीरों और सरल जंजीरों को परिभाषित किया है, वैसे ही हम जंजीरों और सरल जंजीरों को परिभाषित कर सकते हैं।

    एक पथ या मार्ग को शीर्षों के अनुक्रम द्वारा भी दर्शाया जा सकता है। उदाहरण के लिएतथा उपाय, पथ (1) को इस प्रकार लिखा जा सकता है: .

    रास्ता बंद कहा जाता है , यदि चाप का प्रारंभिक शीर्ष घोड़े के साथ मेल खाता हैएच चाप के नूह शीर्ष। बंद ऑर्चेन (चेन) कहलाते हैंचक्र (चक्र) ) चक्रों को भी कहा जाता हैआकृति . बंद सरल ऑर्चेन (जंजीर) कहा जाता हैएस साधारण साइकिल(चक्र)। बंद मार्गअनियंत्रित हैएन बंद डबलआप पर।

    1. ग्राफ कनेक्टिविटी और कनेक्टिविटी घटक

    डायग्राफ में एक शीर्ष को शीर्ष से पहुंचने योग्य कहा जाता है यदि कोई पथ है। अगर, इसके अलावा, पहुंच योग्य है, तो इन शिखरों को परस्पर पहुंच योग्य कहा जाता है।

    एक डिग्राफ को दृढ़ता से जुड़ा या मजबूत कहा जाता है , यदि इसमें कोई दो शीर्ष हैंएक आईएमओ प्राप्त करने योग्य। एक मजबूत डिग्राफ का एक उदाहरण अंजीर में दिखाया गया है। 2 क. चूंकि कॉलम मेंइ एक चक्र दिया गया है जिसमें सभी शीर्ष शामिल हैं, फिर उनमें से किन्हीं दो को लिया जाता हैलेकिन प्राप्य।

    ° ° °

    ° ° ° ° ° °

    ° ° ° ° ° °

    ए बी सी

    चावल। 2.

    डिग्राफ कहा जाता हैएक तरह से जुड़ाया एकतरफा यदि इसके शीर्षों के किसी भी युग्म में कम से कम एक दूसरे से पहुँचा जा सकता है। एकतरफा ग्राफ का एक उदाहरण अंजीर में दिखाया गया है। 2 ख. इस ग्राफ में एक चक्र है जिसमें चार परस्पर पहुंच योग्य शीर्ष शामिल हैं। शीर्ष में शून्य की प्रविष्टि की डिग्री है, जिसका अर्थ है कि इस शीर्ष पर जाने के लिए कोई रास्ता नहीं है। इसके अलावा, अन्य चार शीर्षों में से कोई भी इससे पहुंचा जा सकता है।

    डिग्राफ कहा जाता हैशिथिल रूप से जुड़ा या कमजोर , यदि इसमें कोई दो शीर्ष शामिल हैंसंयुक्त आधे रास्ते के बारे में . आधे रास्ते में, रास्ते के विपरीत, विपरीत दिशा हो सकती है।में आलसी चाप। कमजोर डिग्राफ का एक उदाहरण अंजीर में दिखाया गया है। 2 इंच यह स्पष्ट है कि ग्राफ में शामिल नहीं हैपर ty शीर्षों के बीच और, लेकिन विपरीत n . से मिलकर एक आधा पथ हैएक शासित चाप और।

    यदि कुछ शीर्ष शीर्षों के लिए उन्हें जोड़ने वाला कोई मार्ग नहीं है, तो tएक कौन सा डिग्राफ कहा जाता हैअसंगत।

    एक डिग्राफ के लिए तीन प्रकार के जुड़े घटकों को परिभाषित किया गया है:मजबूत घटक- मा को सबसे मजबूत सबग्राफ,एक तरफा घटक- अधिकतम एकलके बारे में रोनी सबग्राफ औरकमजोर घटकसबसे कमजोर सबग्राफ है।

    एक मजबूत घटक की अवधारणा को अंजीर में दिखाया गया है। 3.

    ° ° ° ° ° °

    ° ° ° °

    ° ° ° ° ° °

    ° ° ° ° ° °

    ° ° °

    ° ° ° ° °

    चावल। 3

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

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

    ग्राफ जुड़े हुए हैं और एक ग्राफ में जोड़ते हैं। इन रेखांकन को कहा जाता हैकनेक्टिविटी घटकग्राफ। एक संख्या एक ग्राफ की एक और संख्यात्मक विशेषता है। कनेक्टेड ग्राफ़ के लिए, यदि ग्राफ़ डिस्कनेक्ट किया गया है, तो।

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

    1. व्यास, त्रिज्या और ग्राफ केंद्र

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

    2) ;

    3) .

    ग्राफ के प्रत्येक शीर्ष से सबसे दूर के शीर्ष तक की दूरी निर्धारित करें

    जिसे कहा जाता हैसनक. जाहिर है, पूर्ण ग्राफ़ में सभी शीर्षों के लिए उत्केंद्रता एक के बराबर होती है, और एक साधारण चक्र के शीर्षों के लिए - .

    अधिकतम उत्केन्द्रता कहलाती हैव्यास ग्राफ, और न्यूनतम - RADIUS ग्राफ। पूर्ण ग्राफ में हमारे पास है, और एक साधारण चक्र में - .

    एक शीर्ष को केंद्रीय कहा जाता है यदि। ग्राफ में कई हो सकते हैंबी ऐसे शीर्ष, और कुछ आलेखों में सभी शीर्ष केंद्रीय होते हैं। एक साधारण श्रृंखला में, विषम संख्या में शीर्षों के साथ, केवल एक केंद्रीय होता है, और उनमें से एक सम संख्या के साथसाथ ऐसे दो शीर्ष हैं। एक पूर्ण ग्राफ में और एक साधारण चक्र के लिए, सभी शीर्ष केंद्रीय होते हैं। केंद्रीय शीर्षों के समुच्चय को कहते हैंग्राफ का केंद्र।

    उदाहरण 1 चित्र में दिखाए गए ग्राफ का व्यास, त्रिज्या और केंद्र ज्ञात कीजिए। चार।

    ° °

    ° ° °

    ° °

    ° °

    चावल। चार।

    इस समस्या को हल करने के लिए, पूर्व-गणना करना सुविधाजनक हैदूरी मैट्रिक्सशीर्ष के बीच मील गिनती। इस मामले में, यह आकार का एक मैट्रिक्स होगा, जिसमें शीर्ष से शीर्ष तक की दूरी होती है:

    मैट्रिक्स की प्रत्येक पंक्ति के लिए, हम सबसे बड़ा तत्व ढूंढते हैं और इसे लिखते हैंएक डैश से वा. इनमें से सबसे बड़ी संख्या ग्राफ के व्यास के बराबर है, सबसे छोटी p . हैएक ग्राफ का dius. ग्राफ का केंद्र केंद्रीय शीर्षों द्वारा बनता है और।

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

    1. रीचैबिलिटी और काउंटररीचैबिलिटी मैट्रिसेस

    रीचैबिलिटी मैट्रिक्सनिम्नानुसार परिभाषित किया गया है:

    किसी दिए गए शीर्ष से पहुंचने योग्य ग्राफ़ शिखर के सेट में वे तत्व होते हैं जिनके लिए मैट्रिक्स में वें तत्व 1 के बराबर होता है। इस सेट को इस प्रकार दर्शाया जा सकता है

    काउंटररीचैबिलिटी मैट्रिक्स (उलटा पहुंच योग्यता) परिभाषित करना इस प्रकार है:

    इसी तरह एक सुलभ सेट के निर्माण के लिए, कोई एक सेट बना सकता हैके बारे में निम्नलिखित अभिव्यक्ति का उपयोग कर इशारा:

    यह परिभाषाओं से इस प्रकार है कि मैट्रिक्स का -th कॉलम ma . की -th पंक्ति के साथ मेल खाता हैटी , यानी, मैट्रिक्स को मैट्रिक्स में स्थानांतरित किया गया है।

    उदाहरण 2 ग्राफ़ आदि के लिए रीचैबिलिटी और काउंटररीचैबिलिटी के मैट्रिसेस खोजें।तथा चित्र में दिखाया गया है 5.

    चावल। 5.

    आइए हम ग्राफ़ वर्टिस के लिए रीचैबिलिटी सेट को परिभाषित करें:

    इसलिए, रीचैबिलिटी और काउंटररीचैबिलिटी मैट्रिसेस का रूप है:

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

    आप मैट्रिक्स को भी परिभाषित कर सकते हैंसीमित रीचैबिलिटी और काउंटररीचैबिलिटीतथा पुलों, यदि हम चाहते हैं कि पथों की लंबाई कुछ दी गई संख्या से अधिक न हो। फिर अनुमेय पथों की लंबाई पर ऊपरी सीमा होगी।

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