ग्राफ में कोने और किनारे होते हैं। एक निश्चित संपत्ति के अनुसार कोने किनारों से जुड़े हुए हैं - घटना संबंध, जो किनारों के सेट को परिभाषित करता है। इस मामले में, लूप और पृथक कोने बन सकते हैं।
अनुदेश
चरण 1
मान लीजिए कि ग्राफ के किनारों का समुच्चय दिया गया है और वह संबंध दिया गया है जिसके साथ एक किनारे को एक शीर्ष से दूसरे शीर्ष पर खींचना संभव है। उदाहरण के तौर पर, शीर्षों का समुच्चय {1, 2, 3, 4, 5, 6, 7, 8}, दो शीर्ष x और y x + y <8 के अनुपात में हैं।
चरण दो
एक शीर्ष आसन्नता मैट्रिक्स बनाएँ। ऐसा करने के लिए, एक वर्ग तालिका बनाएं, तालिका में पंक्तियों और स्तंभों की संख्या कोने की संख्या के साथ मेल खाती है। फिर i-वें पंक्ति और j-वें स्तंभ के प्रतिच्छेदन पर 1 लगाएं यदि शीर्ष i और j दिए गए अनुपात को संतुष्ट करते हैं। यदि संबंधित तत्वों का अनुपात पूरा नहीं होता है, तो i-वें पंक्ति और j-वें स्तंभ के चौराहे पर 0 लगाएं।
हमारे उदाहरण में, पहली पंक्ति इस प्रकार भरी गई है:
1 + 1 <8, इसलिए पहली पंक्ति और पहले कॉलम के चौराहे पर 1 है
1 + 2 <8, फिर से 1
1 + 3 <8, फिर से 1
1 + 7 <8, गलत असमानता, इसलिए तालिका का यह तत्व होगा 0
1 + 8 <8, फिर से 0
चरण 3
किनारों की संख्या का पता लगाने के लिए, किनारों की नकल किए बिना आसन्न मैट्रिक्स में लोगों की संख्या गिनें।
उदाहरण में, एक सममित मैट्रिक्स प्राप्त किया गया था, इसलिए हमने पहले मैट्रिक्स के मुख्य विकर्ण (नीले रंग में चिह्नित) के ऊपर गिना, और फिर मुख्य विकर्ण (लाल रंग में चिह्नित) पर गिना। पसलियों की कुल संख्या 12 है।
चरण 4
घटनाओं (किनारों) का एक मैट्रिक्स बनाएँ। ऐसा करने के लिए, एक तालिका बनाएं, उसमें पंक्तियों की संख्या ग्राफ़ में शीर्षों की संख्या के बराबर है, और स्तंभों की संख्या किनारों की संख्या के बराबर है। इकाइयों को उन रेखाओं पर रखें जो एक किनारे से जुड़ी होंगी। शीर्ष से इसकी ओर जाने वाले किनारों को लूप कहा जाता है और मैट्रिक्स के अंत में जोड़ा जाता है। छोरों के अनुरूप स्तंभों में, शेष किनारों के विपरीत, केवल एक इकाई होती है।
चरण 5
अब एक ग्राफ बनाएं। कोने को किसी भी तरह से कागज़ पर रखें और निर्मित तालिकाओं का उपयोग करके उन्हें किनारों से जोड़ दें। वे शीर्ष जो किनारों से जुड़े नहीं हैं, पृथक कहलाते हैं।
