🔢 mathematics

On the number of generalized cospectral mates of graphs

यह शोध पत्र वॉक मैट्रिक्स (walk matrix) के स्मिथ नॉर्मल फॉर्म (Smith Normal Form) से प्राप्त अंकगणितीय बाधाओं का उपयोग करके सरल ग्राफों के लिए सामान्यीकृत को-स्पेक्ट्रल मेट्स (generalized cospectral mates) की संख्या पर एक सटीक ऊपरी सीमा स्थापित करता है, जिससे स्पेक्ट्रल विशिष्टता के परिणामों को पहले की तुलना में ग्राफों के एक व्यापक वर्ग तक विस्तारित किया जा सके।

मूल लेखक: Muhammad Raza, Obaid Ullah Ahmad, Mudassir Shabbir, Waseem Abbas

प्रकाशित 2026-03-24

📖 6 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Muhammad Raza, Obaid Ullah Ahmad, Mudassir Shabbir, Waseem Abbas

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

कल्पना कीजिए कि आप एक संदिग्ध की पहचान करने के लिए उसके "फिंगरप्रिंट" के आधार पर एक जासूस हैं। गणित की दुनिया में, ग्राफ (जो केवल रेखाओं से जुड़े बिंदुओं का एक नेटवर्क है) के फिंगरप्रिंट होते हैं जिन्हें स्पेक्ट्रा (spectra) कहा जाता है।

आमतौर पर, यदि दो ग्राफों का स्पेक्ट्रम समान होता है, तो उन्हें "जुड़वा" (twins) माना जाता है। लेकिन यहाँ एक पेंच है: कभी-कभी, दो पूरी तरह से अलग दिखने वाले ग्राफ (non-isomorphic) का स्पेक्ट्रम बिल्कुल एक जैसा हो सकता है। यह कुछ ऐसा है जैसे दो अलग-अलग घरों का फर्श का नक्शा और कमरों का आकार बिल्कुल एक जैसा हो, लेकिन एक का दरवाज़ा नीला हो और दूसरे का लाल।

समस्या: बहुत सारे जुड़वा?

लंबे समय तक, गणितज्ञों ने पूछा: "क्या हम इन ग्राफों के बीच अंतर कर सकते हैं?"

पुराना तरीका: ग्राफ के स्पेक्ट्रम को देखें। (कभी-कभी यह काम करता है, कभी-कभी नहीं)।
नया तरीका (सामान्यीकृत स्पेक्ट्रम/Generalized Spectrum): ग्राफ के स्पेक्ट्रम और उसके "विपरीत" (complement graph) के स्पेक्ट्रम को देखें (जहाँ हर वह कनेक्शन जो मौजूद था, अब टूट गया है, और हर टूटा हुआ कनेक्शन अब एक लिंक बन गया है)।

यह "सामान्यीकृत स्पेक्ट्रम" एक बहुत ही शक्तिशाली फिंगरप्रिंट है। यह घर के फर्श के नक्शे को देखने और साथ ही उस खाली प्लॉट के ब्लूप्रिंट को देखने जैसा है जिस पर वह खड़ा है। ज्यादातर समय, यह दो ग्राफों को अलग पहचानने के लिए पर्याप्त होता है। लेकिन कभी-कभी, कुछ "बहरूपिया" (imposter) ग्राफ अभी भी बच निकलते हैं।

बड़ा सवाल: यदि किसी ग्राफ के पास बहरूपिए हैं, तो कितने हो सकते हैं? क्या यह सिर्फ एक है? दस? दस लाख?

समाधान: "वॉक मैट्रिक्स" (Walk Matrix) और "स्मिथ नॉर्मल फॉर्म" (Smith Normal Form)

इस शोध पत्र के लेखक, मुहम्मद रज़ा और उनकी टीम ने इन बहरूपियों को खोजने के बजाय उन्हें गिनने का एक चतुर तरीका निकाला।

यहाँ उनका दृष्टिकोण दिया गया है, जिसे उपमाओं के माध्यम से समझाया गया है:

1. वॉक मैट्रिक्स: ग्राफ की "याददाश्त"

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

यदि ग्राफ "नियंत्रणीय" (controllable) है, तो यह याददाश्त अद्वितीय और शक्तिशाली होती है। इसका मतलब है कि ग्राफ की संरचना कठोर है और इसे नकली बनाना कठिन है।

2. स्मिथ नॉर्मल फॉर्म: "प्राइम कोड"

जब गणितज्ञ वॉक मैट्रिक्स को देखते हैं, तो वे इसे एक विशेष कोड में तोड़ सकते हैं जिसे स्मिथ नॉर्मल फॉर्म (SNF) कहा जाता है।
सोचिए कि SNF ग्राफ के DNA के प्राइम फैक्टराइजेशन (अभाज्य गुणनखंड) की तरह है। जिस तरह किसी भी संख्या को अभाज्य संख्याओं (जैसे $12 = 2 \times 2 \times 3$ ) में तोड़ा जा सकता है, उसी तरह वॉक मैट्रिक्स को "इनवेरिएंट फैक्टर्स" (invariant factors) की एक सूची में तोड़ा जा सकता है।
लेखक इस सूची के आखिरी नंबर पर ध्यान केंद्रित करते हैं। यह नंबर इस रहस्य को धारण करता है कि कितने बहरूपिए मौजूद हैं।

3. बहरूपिए का "स्तर" (Level)

एक ग्राफ को उसके बहरूपिए में बदलने के लिए, आपको एक विशेष गणितीय "चाबी" (मैट्रिक्स) की आवश्यकता होती है।
लेखक इस चाबी के स्तर (Level) को परिभाषित करते हैं। स्तर को उस "चाबी" के आकार या जटिलता के रूप में सोचें जिसकी आवश्यकता इस परिवर्तन को अनलॉक करने के लिए है।

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

बड़ी खोज (ऊपरी सीमा/Upper Bound)

टीम को ग्राफ का एक परिवार मिला है (मान लीजिए कि वे "Fn Family" हैं) जहाँ नियम बहुत सख्त हैं। इन ग्राफों के लिए, संभावित बहरूपियों की संख्या स्मिथ नॉर्मल फॉर्म के उस अंतिम नंबर के प्राइम फैक्टर्स (अभाज्य गुणनखंडों) द्वारा सीमित है।

साधारण अंग्रेजी में सूत्र:
यदि कोड का अंतिम नंबर इस तरह से अभाज्य गुणनखंडों में टूटता है:
$2^3 \times 3^2 \times 5^1$
(जिसका अर्थ है $2 \times 2 \times 2 \times 3 \times 3 \times 5$ )

बहरूपियों की संख्या की गणना करने के लिए, घातांकों (3, 2, और 1) को लिया जाता है, प्रत्येक में 1 जोड़ा जाता है, उन्हें गुणा किया जाता है, और फिर 1 घटाया जाता है (क्योंकि एक "चाबी" स्वयं ग्राफ है)।

$(3+1) \times (2+1) \times (1+1) - 1 = 4 \times 3 \times 2 - 1 = 23$ ।
तो, इस ग्राफ में अधिकतम 23 बहरूपिए हो सकते हैं।

यह क्यों मायने रखता है

यह एक सीमा है, अनुमान नहीं: इससे पहले, हमारे पास कोई सख्त सीमा नहीं थी कि एक ग्राफ में कितने बहरूपिए हो सकते हैं। अब, हमारे पास एक गणितीय "स्पीड लिमिट" है।
यह कई ग्राफों के लिए काम करता है: लेखकों ने हजारों यादृच्छिक ग्राफों पर इसका परीक्षण किया। उन्होंने पाया कि लगभग 39% यादृच्छिक ग्राफ इस विशेष "Fn Family" में आते हैं जहाँ यह नियम लागू होता है। यह ग्राफ की दुनिया का एक बहुत बड़ा हिस्सा है!
वास्तविक दुनिया का प्रमाण: उन्होंने 10 डॉट्स वाला एक विशिष्ट ग्राफ बनाया। उनके गणित ने भविष्यवाणी की कि इसमें अधिकतम 3 बहरूपिए हो सकते हैं। फिर उन्होंने उन्हें खोजने के लिए कंप्यूटर का उपयोग किया, और ठीक 3 ही मौजूद थे। गणित एकदम सटीक था।

सारांश

ग्राफ को एक अद्वितीय पहेली के रूप में सोचें।

पुराना दृष्टिकोण: "यदि टुकड़े एक जैसे दिखते हैं, तो यह वही पहेली है।" (कभी-कभी गलत)।
नया दृष्टिकोण: "यदि टुकड़े और बॉक्स का डिज़ाइन दोनों एक जैसे दिखते हैं, तो यह वही पहेली है।" (आमतौर पर सही)।
यह शोध पत्र: "यदि यह वही पहेली नहीं है, तो यहाँ बताया गया है कि कितने अलग-अलग पहेली हमें धोखा दे सकते हैं, और यहाँ बताया गया है कि केवल पहेली के 'प्राइम नंबर कोड' को देखकर उस संख्या की गणना कैसे की जाए।"

यह कार्य एक अस्पष्ट प्रश्न ("कितने मिलते-जुलते रूप हैं?") को एक सटीक गणना में बदल देता है, जिससे गणितज्ञों को नेटवर्क्स की छिपी हुई संरचना को समझने के लिए एक शक्तिशाली नया उपकरण मिलता है।

यहाँ रज़ा और अन्य द्वारा लिखित शोध पत्र "On the number of generalized cospectral mates of graphs" का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या विवरण (Problem Statement)

यह शोध पत्र स्पेक्ट्रल ग्राफ थ्योरी की एक शास्त्रीय समस्या के मात्रात्मक विस्तार को संबोधित करता है: यह निर्धारित करना कि कितने गैर-आइसोमॉर्फिक (non-isomorphic) ग्राफ एक ही सामान्यीकृत स्पेक्ट्रम (generalized spectrum) साझा करते हैं।

सामान्यीकृत स्पेक्ट्रम (Generalized Spectrum): इसे एक ग्राफ $G$ और उसके पूरक $\bar{G}$ के युग्म $(\text{Spec}(G), \text{Spec}(\bar{G}))$ के रूप में परिभाषित किया गया है।
सामान्यीकृत कोस्पेकट्रल मेट्स (Generalized Cospectral Mates): गैर-आइसोमॉर्फिक ग्राफों का एक सेट जो एक ही सामान्यीकृत स्पेक्ट्रम साझा करते हैं।
मुख्य प्रश्न: हालांकि यह ज्ञात है कि कुछ ग्राफ "अपने सामान्यीकृत स्पेक्ट्रम द्वारा निर्धारित" (DGS) होते हैं (अर्थात, उनके शून्य मेट्स होते हैं), यह शोध पत्र उन ग्राफों के लिए मेट्स की संख्या पर स्पष्ट ऊपरी सीमा (upper bounds) स्थापित करने का प्रयास करता है जो अद्वितीय रूप से निर्धारित नहीं हैं। पिछले कार्यों ने मेट्स खोजने के लिए एल्गोरिदम प्रदान किए थे, लेकिन व्यापक वर्गों के ग्राफों के लिए ऐसे मेट्स की संख्या पर सामान्य सैद्धांतिक सीमाएँ प्रदान करने में कमी थी।

2. कार्यप्रणाली (Methodology)

लेखक रैखिक बीजगणित (linear algebra), संख्या सिद्धांत (number theory), और कॉम्बिनेटरियल मैट्रिक्स थ्योरी (combinatorial matrix theory) के संयोजन का उपयोग करते हैं। दृष्टिकोण वॉक मैट्रिक्स (Walk Matrix) और इसके स्मिथ नॉर्मल फॉर्म (Smith Normal Form - SNF) पर अत्यधिक निर्भर है।

मुख्य परिभाषाएँ और उपकरण

वॉक मैट्रिक्स ( $W(G)$ ): एक $n \times n$ मैट्रिक्स जिसके कॉलम $e, A(G)e, \dots, A(G)^{n-1}e$ हैं, जहाँ $e$ ऑल-वन्स (all-ones) वेक्टर है। एक ग्राफ नियंत्रणीय (controllable) होता है यदि $W(G)$ गैर-एकल (non-singular) हो।
रैशनल ऑर्थोगोनल मैट्रिसेस (Rational Orthogonal Matrices): यदि दो ग्राफ $G$ और $H$ सामान्यीकृत कोस्पेकट्रल और नियंत्रणीय हैं, तो एक अद्वितीय नियमित रैशनल ऑर्थोगोनल मैट्रिक्स $Q$ (जहाँ $Qe=e $) मौजूद होता है ताकि$ Q^T A(G) Q = A(H)$ हो सके।
लेवल ( $\ell(Q)$ ): वह सबसे छोटा धनात्मक पूर्णांक $x$ जिससे $xQ$ एक इंटीग्रल मैट्रिक्स बन जाता है। यह एक महत्वपूर्ण अंकगणितीय पैरामीटर है।
स्मिथ नॉर्मल फॉर्म (SNF): एक इंटीग्रल मैट्रिक्स $M$ के लिए, SNF एक विकर्ण मैट्रिक्स $\text{diag}(d_1, \dots, d_n)$ है जहाँ $d_i | d_{i+1}$ । ये $d_i$ इनवेरिएंट फैक्टर्स (invariant factors) हैं।

सैद्धांतिक ढांचा (Theoretical Framework)

कार्यप्रणाली निम्नलिखित तार्किक चरणों में आगे बढ़ती है:

अंकगणितीय बाधाएं (Arithmetic Constraints): लेखक उन रैशनल ऑर्थोगोनल मैट्रिसेस $Q$ के अंकगणितीय गुणों का विश्लेषण करते हैं जो सामान्यीकृत कोस्पेकट्रल ग्राफों को जोड़ते हैं। वे लेवल $\ell(Q)$ पर विभाज्यता (divisibility) की शर्तों को प्राप्त करने के लिए वॉक मैट्रिक्स के SNF का उपयोग करते हैं।
परिमित क्षेत्रों (Finite Fields) पर रैंक विश्लेषण: वे $\mathbb{F}_p$ पर वॉक मैट्रिक्स की रैंक की जांच करते हैं। विशेष रूप से, वे दिखाते हैं कि कुछ ग्राफों के लिए, रैंक की बाधाएं स्केल किए गए मैट्रिक्स $\ell(Q)Q$ के कॉलम को $p^k$ मोड्यूलो एक निश्चित वेक्टर के अदिश गुणज (scalar multiples) होने के लिए मजबूर करती हैं।
लेवल के माध्यम से विशिष्टता (Uniqueness via Level): वे सिद्ध करते हैं कि यदि दो ग्राफ $H_1$ और $H_2$ , $G$ के सामान्यीकृत कोस्पेकट्रल हैं और उनके संगत मैट्रिक्स $Q_1, Q_2$ का समान लेवल है, तो $H_1$ और $H_2$ आइसोमॉर्फिक होने चाहिए। यह मेट्स की गिनती करने की समस्या को अनुमेय स्तरों (admissible levels) की संख्या गिनने में बदल देता है।
अनुमेय स्तरों को सीमित करना (Bounding Admissible Levels): वॉक मैट्रिक्स के अंतिम इनवेरिएंट फैक्टर, $d_n(W(G))$ , के अभाज्य गुणनखंड (prime factorization) का विश्लेषण करके, वे संभावित स्तरों की अधिकतम संख्या निर्धारित करते हैं।

3. मुख्य योगदान (Key Contributions)

A. परिवार $\mathcal{F}_n$ की परिभाषा

लेखक एक विशिष्ट नियंत्रणीय ग्राफों के परिवार $\mathcal{F}_n$ को परिभाषित करते हैं, जो उनके वॉक मैट्रिक्स के इनवेरिएंट फैक्टर्स पर विशिष्ट बाधाओं द्वारा अभिलक्षित है:
$d_{\lceil n/2 \rceil}(W(G)) = 1 \quad \text{और} \quad d_{n-1}(W(G)) = 2$
यह परिवार महत्वपूर्ण है क्योंकि यह पर्याप्त बड़ा है जिसमें कई रैंडम ग्राफ शामिल हैं, फिर भी इतना संरचित है कि सख्त अंकगणितीय सीमाएं लागू की जा सकें।

B. प्रमेय 1.1: लेवल विशिष्टता (Level Uniqueness)

कथन: किसी भी ग्राफ $G \in \mathcal{F}_n$ के लिए, यदि दो सामान्यीकृत कोस्पेकट्रल मेट्स $H_1$ और $H_2$ , रैशनल ऑर्थोगोनल मैट्रिसेस $Q_1$ और $Q_2$ के अनुरूप हैं जिनका समान लेवल है ( $\ell(Q_1) = \ell(Q_2)$ ), तो $H_1 \cong H_2$ ।
महत्व: यह रूपांतरण मैट्रिक्स के लेवल और मेट के आइसोमॉर्फिज्म क्लास के बीच एक एक-से-एक मैपिंग स्थापित करता है।

C. प्रमेय 1.2: स्पष्ट ऊपरी सीमा (Explicit Upper Bound)

कथन: यदि $G \in \mathcal{F}_n$ है और वॉक मैट्रिक्स के अंतिम इनवेरिएंट फैक्टर का अभाज्य गुणनखंड $d_n(W(G)) = \prod_{j=1}^m p_j^{k_j}$ है, तो $G$ के सामान्यीकृत कोस्पेकट्रल मेट्स की संख्या अधिक है:
$\left( \prod_{j=1}^m k_j \right) - 1$
व्युत्पत्ति: यह सीमा इनवेरिएंट फैक्टर्स के उन विभाजकों की संख्या गिनकर प्राप्त की जाती है जो परिमित क्षेत्रों पर रैंक बाधाओं को संतुष्ट करते हैं, इसमें ट्रिवियल केस (जहाँ लेवल 1 है, जो स्वयं ग्राफ को दर्शाता है) को छोड़कर शामिल है।

4. परिणाम और संख्यात्मक विश्लेषण (Results and Numerical Analysis)

टाइट उदाहरण (Tight Example): लेखकों ने $n=10$ $n = 10$ शीर्षों वाला एक विशिष्ट ग्राफ $G$ $G$ बनाया जो $\mathcal{F}_{10}$ $F_{10}$ में आता है।
- अंतिम इनवेरिएंट फैक्टर था $d_{10}(W(G)) = 19350 = 2^1 \cdot 3^2 \cdot 5^2 \cdot 43^1$ ।
- घातांक (exponents) हैं $k_1=1, k_2=2, k_3=2, k_4=1$ ।
- सैद्धांतिक ऊपरी सीमा है $(1 \times 2 \times 2 \times 1) - 1 = 3$ ।
- प्रायोगिक सत्यापन: एक ब्रूट-फोर्स सर्च ने पुष्टि की कि $G$ के ठीक 3 सामान्यीकृत कोस्पेकट्रल मेट्स ( $H_1, H_2, H_3$ ) हैं। संगत मैट्रिसेस के लेवल क्रमशः 3, 15 और 5 पाए गए, जो पुष्टि करते हैं कि वे भिन्न हैं और सैद्धांतिक भविष्यवाणी से मेल खाते हैं।
सांख्यिकीय व्यापकता (Statistical Prevalence): लेखकों ने विभिन्न $n$ $n$ (11 से 50 तक) के लिए $p=0.5$ $p = 0.5$ किनारे की संभावना के साथ 10,000 रैंडम ग्राफ उत्पन्न किए।
- उन्होंने पाया कि इनमें से लगभग 39% रैंडम ग्राफ परिवार $\mathcal{F}_n$ से संबंधित हैं।
- यह इंगित करता है कि व्युत्पन्न ऊपरी सीमा सरल ग्राफों के एक बड़े और गैर-तुच्छ (non-trivial) हिस्से के लिए लागू है।

5. महत्व और भविष्य की दिशाएं (Significance and Future Directions)

मात्रात्मक प्रगति (Quantitative Advancement): यह शोध पत्र "क्या एक ग्राफ DGS है?" के बाइनरी प्रश्न से आगे बढ़कर "एक ग्राफ के कितने मेट हो सकते हैं?" के मात्रात्मक प्रश्न की ओर बढ़ता है, जो एक ठोस, गणना योग्य ऊपरी सीमा प्रदान करता है।
व्यापक प्रयोज्यता (Broad Applicability): पिछले परिणामों के विपरीत जो केवल बिना मेट वाले ग्राफों पर लागू होते थे, यह कार्य उन ग्राफों के लिए सीमाएं प्रदान करता है जिनके पास मेट होते हैं।
पद्धतिगत नवाचार (Methodological Innovation): रैशनल ऑर्थोगोनल मैट्रिसेस पर स्मिथ नॉर्मल फॉर्म और मॉड्यूल अरिथमेटिक बाधाओं का उपयोग स्पेक्ट्रल ग्राफ थ्योरी के लिए एक शक्तिशाली नया टूलसेट प्रदान करता है, जो बीजगणितीय संख्या सिद्धांत (algebraic number theory) को सीधे ग्राफ आइसोमॉर्फिज्म समस्याओं से जोड़ता है।
भविष्य का कार्य: लेखक इनवेरिएंट फैक्टर्स के लिए बाधाओं को शिथिल करने का सुझाव देते हैं ताकि अधिक ग्राफों को कवर किया जा सके, अन्य मैट्रिसेस (जैसे साइनलेस लैप्लासियन, डिस्टेंस मैट्रिक्स) पर इन तकनीकों का विस्तार करना, और ऑल-वन्स वेक्टर $e$ के अलावा अन्य कंट्रोल वेक्टर्स की खोज करना।

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