आसन्नता आव्यूह कैलकुलेटर (Adjacency Matrix Calculator)

कोर सूची → आसन्नता आव्यूह · कोटि अनुक्रम · घनत्व · संबद्ध घटक · आव्यूह घात A² A³

इनपुट (Input):
प्रकार (Type):

विभाजक (Separators): A-B A B A,B A->B। तीर (->) दिष्ट कोर (directed edge) को दर्शाता है।

त्वरित उदाहरण (Quick Examples)

आसन्नता आव्यूह (Adjacency Matrix) क्या है?

एक आसन्नता आव्यूह (Adjacency Matrix) एक वर्ग n×n आव्यूह A होता है जिसका उपयोग n शीर्षों (vertices) वाले ग्राफ G = (V, E) को दर्शाने के लिए किया जाता है। यदि शीर्ष i से शीर्ष j तक एक कोर (edge) है, तो प्रविष्टि A[i][j] = 1 होती है, और अन्यथा 0 होती है। भारित ग्राफों (weighted graphs) के लिए, प्रविष्टि 1 के स्थान पर कोर भार (edge weight) को संग्रहीत करती है। कंप्यूटर विज्ञान में ग्राफ को दर्शाने के दो पारंपरिक तरीकों में से एक आसन्नता आव्यूह है — दूसरा आसन्नता सूची (adjacency list) है।

नेटवर्क विश्लेषण, सोशल नेटवर्क मॉडलिंग, रूटिंग एल्गोरिदम और कंप्यूटर विज्ञान में रैखिक बीजगणित के अनुप्रयोगों के लिए आसन्नता आव्यूह अत्यंत महत्वपूर्ण है। यह O(1) समय में कोरों के अस्तित्व की जाँच करने की सुविधा देता है और वॉक की संख्या की गणना, त्रिकोणों का पता लगाने और संबद्ध घटकों को खोजने जैसी शक्तिशाली बीजगणितीय तकनीकों को सक्षम बनाता है।

इस कैलकुलेटर का उपयोग कैसे करें

तीन इनपुट मोड उपलब्ध हैं:

  • कोर सूची (Edge List) (डिफ़ॉल्ट) — शीर्षों के जोड़े दर्ज करें, प्रत्येक पंक्ति में एक। समर्थित विभाजक: A-B, A B, A,B, A->B। दिष्ट कोर दर्शाने के लिए -> का उपयोग करें।
  • आव्यूह ग्रिड (Matrix Grid) — सीधे 0/1 ग्रिड भरें। आकार 2-8 चुनें और नीले हेडर कक्षों में शीर्ष लेबलों को अनुकूलित करें।
  • आसन्नता सूची (Adj. List) — इसे शीर्ष: पड़ोसी1, पड़ोसी2, ... प्रारूप में दर्ज करें।

अदिष्ट (Undirected) या दिष्ट (Directed) का चयन करें, फिर गणना करें पर क्लिक करें। यह टूल आसन्नता आव्यूह, आसन्नता सूची, कोर सूची, कोटि तालिका, ग्राफ घनत्व, संबद्धता, आव्यूह घात A² और A³, और एक इंटरैक्टिव ग्राफ विज़ुअलाइज़ेशन प्रदान करता है। एडवांस्ड टैब में पथ अस्तित्व जाँचकर्ता भी शामिल है।

मुख्य सूत्र

शीर्ष कोटि (Vertex Degree)

अदिष्ट (Undirected): deg(v) = Σⱼ A[v][j] (पंक्ति योग = कॉलम योग) दिष्ट (Directed): out-deg(v) = Σⱼ A[v][j] (पंक्ति योग - बाह्य-कोटि) in-deg(v) = Σᵢ A[i][v] (कॉलम योग - अंतः-कोटि)

ग्राफ घनत्व (Graph Density)

अदिष्ट (Undirected): D = 2|E| / (n(n−1)) दिष्ट (Directed): D = |E| / (n(n−1)) D = 0 → रिक्त ग्राफ (कोई कोर नहीं) D = 1 → पूर्ण ग्राफ (सभी शीर्ष परस्पर संबद्ध)

आव्यूह घात और वॉक संख्या (Walk Counts)

A^k [i][j] = शीर्ष i से j तक ठीक k लंबाई के वॉक (walks) की संख्या A¹[i][j] → प्रत्यक्ष कोर A²[i][j] → एक मध्यवर्ती शीर्ष के माध्यम से वॉक A³[i][j] → दो मध्यवर्ती शीर्षों के माध्यम से वॉक त्रिकोण (अदिष्ट) = trace(A³) / 6 A² का विकर्ण (अदिष्ट) = प्रत्येक शीर्ष की कोटि (degree)

सममितीय गुण (Symmetry Property)

A सममित है ⟺ सभी i, j के लिए A[i][j] = A[j][i] सममित आव्यूह ⟺ अदिष्ट ग्राफ (A = Aᵀ)

हल किए गए उदाहरण (Worked Examples)

उदाहरण 1 — त्रिकोण ग्राफ K₃ (अदिष्ट)

शीर्ष: A, B, C. कोर: A–B, B–C, A–C.

  1. शीर्ष अनुक्रमित करें: A=0, B=1, C=2. एक 3×3 शून्य आव्यूह से शुरू करें।
  2. कोर A–B: A[0][1] = A[1][0] = 1
  3. कोर B–C: A[1][2] = A[2][1] = 1
  4. कोर A–C: A[0][2] = A[2][0] = 1
  5. सभी कोटियाँ = 2. घनत्व = 2×3 / (3×2) = 1.0 → यह एक पूर्ण ग्राफ K₃ है।
ABC
A011
B101
C110

उदाहरण 2 — दिष्ट चक्र (3 शीर्ष)

शीर्ष: 1, 2, 3. कोर: 1→2, 2→3, 3→1.

  1. A[0][1] = 1, A[1][2] = 1, A[2][0] = 1. अन्य सभी प्रविष्टियाँ = 0.
  2. आव्यूह सममित नहीं है। प्रत्येक शीर्ष: बाह्य-कोटि = 1, अंतः-कोटि = 1.
  3. घनत्व = 3 / (3×2) = 0.50 (आधे दिष्ट जोड़े जुड़े हुए हैं)।
123
1010
2001
3100

उदाहरण 3 — A² वॉक संख्या पढ़ना

ऊपर दिए गए त्रिकोण K₃ के लिए, A²[A][A] = A[A][B]×A[B][A] + A[A][C]×A[C][A] = 1+1 = 2। इसका मतलब है कि A से वापस A तक लंबाई 2 के 2 वॉक (A→B→A और A→C→A) हैं। अदिष्ट ग्राफ के लिए A² का मुख्य विकर्ण हमेशा शीर्षों की कोटियों के बराबर होता है।

अक्सर पूछे जाने वाले प्रश्न (FAQ)

आसन्नता आव्यूह (Adjacency Matrix) क्या है?
आसन्नता आव्यूह (Adjacency Matrix) एक वर्ग n×n आव्यूह A होता है जहाँ प्रविष्टि A[i][j] = 1 होती है यदि शीर्ष i से शीर्ष j तक एक कोर है, और अन्यथा 0 होती है। यह दो प्राथमिक ग्राफ निरूपणों में से एक है। अदिष्ट ग्राफ हमेशा सममित आव्यूह (A = Aᵀ) बनाते हैं, जबकि दिष्ट ग्राफ असममित आव्यूह बना सकते हैं। सघन ग्राफ के लिए यह आदर्श है क्योंकि यह O(n²) मेमोरी का उपयोग करता है।
कोर सूची (Edge list) से आसन्नता आव्यूह कैसे बनाया जाता है?
प्रत्येक अद्वितीय शीर्ष को एक अनुक्रमिक सूचकांक (index) दें। शून्य से भरा एक n×n आव्यूह बनाएं। सूची में प्रत्येक कोर (u, v) के लिए, A[index(u)][index(v)] = 1 सेट करें। यदि ग्राफ अदिष्ट है, तो समरूपता के लिए A[index(v)][index(u)] = 1 भी सेट करें। यह कैलकुलेटर इन सभी चरणों को स्वचालित रूप से निष्पादित करता है।
दिष्ट और अदिष्ट आसन्नता आव्यूह में क्या अंतर है?
अदिष्ट ग्राफ में कोर (u, v) और (v, u) एक ही होते हैं, इसलिए आव्यूह मुख्य विकर्ण के सापेक्ष हमेशा सममित होता है। दिष्ट ग्राफ (digraph) में A[i][j] = 1 का अर्थ है कि i से j तक दिष्ट कोर है; A[j][i] का मान 0 हो सकता है। दिष्ट ग्राफ के लिए पंक्ति का योग बाह्य-कोटि और कॉलम का योग अंतः-कोटि दर्शाता है।
वर्ग आसन्नता आव्यूह A² क्या दर्शाता है?
प्रविष्टि A²[i][j] शीर्ष i से शीर्ष j तक ठीक 2 लंबाई वाले वॉक (walks) की संख्या को गिनता है। सामान्य तौर पर, A^k[i][j] लंबाई k के वॉक की संख्या होती है। अदिष्ट ग्राफ के लिए, A² का विकर्ण प्रत्येक शीर्ष की कोटि (degree) को दर्शाता है। A³ के ट्रेस को 6 से विभाजित करने पर ग्राफ में त्रिकोणों की संख्या प्राप्त होती है।
आसन्नता आव्यूह से शीर्ष की कोटि (degree) कैसे ज्ञात की जाती है?
अदिष्ट ग्राफ के लिए, deg(v) = पंक्ति v का योग होता है। दिष्ट ग्राफ के लिए, out-deg(v) = पंक्ति v का योग (v से निकलने वाले कोर) और in-deg(v) = कॉलम v का योग (v में प्रवेश करने वाले कोर) होता है। यह कैलकुलेटर प्रत्येक शीर्ष की इन सभी कोटियों की गणना करता है।
ग्राफ घनत्व (Graph Density) क्या है और इसकी गणना कैसे की जाती है?
घनत्व यह मापता है कि अधिकतम संभावित कोरों की तुलना में वास्तव में कितने कोर मौजूद हैं। अदिष्ट ग्राफ के लिए: D = 2m / (n(n−1)) और दिष्ट ग्राफ के लिए: D = m / (n(n−1)), जहाँ m कोरों की संख्या है और n शीर्षों की संख्या है। D = 0 का अर्थ है रिक्त ग्राफ और D = 1 का अर्थ है पूर्ण ग्राफ।
आसन्नता आव्यूह का उपयोग करके ग्राफ संबद्धता की जाँच कैसे करें?
किसी भी शीर्ष से BFS या DFS आरंभ करें, और आव्यूह का उपयोग करके संबद्ध पड़ोसियों पर जाएँ। यदि एक ही ट्रैवर्सल में सभी n शीर्षों पर पहुँचा जा सकता है, तो ग्राफ संबद्ध (connected) है। यदि एकाधिक BFS/DFS रनों की आवश्यकता होती है, तो वे अलग-अलग घटकों (components) का प्रतिनिधित्व करते हैं।
मुझे आव्यूह के स्थान पर आसन्नता सूची (adjacency list) का उपयोग कब करना चाहिए?
आसन्नता आव्यूह का उपयोग तब करें जब ग्राफ सघन हो (m ≈ n²) या आपको O(1) में कोरों के अस्तित्व की त्वरित जाँच करनी हो। आसन्नता सूची का उपयोग तब करें जब ग्राफ विरल हो (m ≪ n²) ताकि अत्यधिक मेमोरी (O(n²)) नष्ट होने से बचा जा सके, क्योंकि सूची केवल O(n + m) मेमोरी का उपयोग करती है।

संबंधित कैलकुलेटर

आव्यूह कैलकुलेटर (Matrix Calculator)

आव्यूह जोड़, गुणा, व्युत्क्रम और सारणिक

प्रायिकता कैलकुलेटर (Probability Calculator)

द्विपद, सामान्य वितरण और संचय (combinations)

विशेषताएं (Features)

  • ✓ संबद्ध घटक गणना
  • ✓ आव्यूह घात A² और A³
  • ✓ ग्राफ विज़ुअलाइज़ेशन (SVG)
  • ✓ डिग्री अनुक्रम विश्लेषण