यदि दो ग्राफ आइसोमॉर्फिक हैं तो क्या उनके निर्धारक बराबर होंगे?
10 कोने ग्राफ G1 और G2
मैं ग्राफ थ्योरी से एल्गोरिथम और उसके अनुप्रयोगों के अध्याय 2 में अभ्यासों को हल कर रहा हूं। अब तक, समरूपता के लिए मैं सिर्फ सभी किनारों को लिखता हूं और पैटर्न खोजने की कोशिश करता हूं, जो छोटे रेखांकन के लिए पर्याप्त है। इन 2 10-कोने के 30-किनारों वाले ग्राफ़ के लिए मुझे लगता है कि मुझे कुछ और मापनीय चाहिए। मैंने दोनों ग्राफ़ को एक एकीकृत संरचना में 'अनुवाद' करने की कोशिश की, लेकिन निश्चित रूप से यदि कोई वर्टेक्स नाम बदलता है तो ग्राफ़ भी अलग दिखाई देगा। मैंने आसन्न मैट्रिक्स को एक पैटर्न खोजने की कोशिश करते हुए लिखा है, और एक स्तंभ है जो मुझे संदेह करता है कि ये दोनों आइसोमॉर्फिक नहीं हो सकते हैं। हालाँकि, मैं हमेशा कॉलम को थोड़ा और समान दिखने के लिए एक शीर्ष के नाम को बदल सकता था। वैसे भी, मैंने पाया कि यदि A = PBP (t) जहां P एक क्रमपरिवर्तन मैट्रिक्स है, तो दो रेखांकन (A, B) आइसोमोर्फिक हैं और P (t) इसका स्थानान्तरण है।
चूंकि det (P) = 1 या -1 = det (P (t)) और det (AB) = det (A) * det (B) तब यदि A और B समद्विबाहु हैं:
det (A) = 1 | -1 * det (B) * 1 | -1 det (A) = det (B)
क्या दो आसन्न मैट्रिसेस एक ही निर्धारक होते हैं और आइसोमॉर्फिक नहीं होते हैं? या निर्धारक में समतावाद के लिए एक पर्याप्त स्थिति (और बहुत अधिक मापनीय) में समानता है?
श्रेष्ठ,
सर्जियो
जवाब
यह वास्तव में सच है कि आइसोमोर्फिक ग्राफ़ के आसन्न मैट्रिक्स में एक ही निर्धारक होगा। वास्तव में, यदि$A = PBP^T$ एक क्रमपरिवर्तन मैट्रिक्स के लिए $P$, फिर $$ \det(A) = \det(P) \det(B) \det(P^T) = \det(P)^2 \det(B) = \det(B). $$ वास्तव में, हम और अधिक कह सकते हैं: क्योंकि $A$ तथा $B$इसी तरह के मेट्रिसेस हैं, उनके समान स्वदेशी होंगे। ध्यान दें कि यदि दो मैट्रिसेस में एक समान प्रतिरूप हैं, तो वे स्वचालित रूप से एक ही निर्धारक हैं।
आक्षेप पकड़ में नहीं आता: यदि $A,B$ दो ग्राफ के आसन्न मैट्रिसेस हैं और हमारे पास हैं $\det(A) = \det(B)$, यह जरूरी नहीं है कि रेखांकन आइसोमॉर्फिक है। वास्तव में, भले ही$A$ तथा $B$एक ही eigenvalues है, यह जरूरी नहीं है कि रेखांकन isomorphic हैं। इस घटना के उदाहरणों को ग्राफ़ के आइसोस्पेक्ट्रल (या कोस्पेक्ट्रल) जोड़े कहा जाता है ।
लंबाई 2 की संख्या (2 किनारों, 3 कोने) में 0 है, और 3 कोने के साथ ग्राफ है और किसी भी किनारे पर 0 नहीं है।