ग्राफ़ के कार्तीय उत्पाद: Difference between revisions

Revision as of 11:21, 16 May 2023

रेखांकन का कार्तीय उत्पाद।

ग्राफ़ सिद्धांत में, कार्तीय गुणन G □ H ग्राफ़ G और H एक ऐसा ग्राफ़ है जो::

G □ H का शीर्ष समुच्चय कार्तीय गुणनफल V(G) × V(H) है; और
G □ H में दो शीर्ष (u,u' ) और (v,v' ) आसन्न हैं यदि और केवल यदि या तो
- u = v और u', H में v' के सन्निकट है, या
- u' = v' और u, G में v के सन्निकट है।

ग्राफ़ के कार्तीय उत्पाद को कभी-कभी ग्राफ़ का बॉक्स उत्पाद कहा जाता है [हैरी 1969]।

संचालन साहचर्य है, रेखांकन के रूप में $(F □ G) □ H$ और $F □ (G □ H)$ स्वाभाविक रूप से ग्राफ समरूपता हैं। संक्रिया क्रमविनिमेय है, रेखांकन के समरूपता तुल्यता वर्ग पर एक संक्रिया के रूप में, और अधिक दृढ़ता से रेखांकन $G □ H$ और $H □ G$ प्राकृतिक समरूपतावाद हैं, लेकिन यह ग्राफ लेबलिंग पर एक संचालन के रूप में क्रमविनिमेय नहीं है।

अंकन $G \times H$ का उपयोग अक्सर ग्राफ़ के कार्तीय उत्पादों के लिए किया जाता है, लेकिन अब इसे ग्राफ़ के प्रदिश उत्पाद के रूप में जाने वाले अन्य निर्माण के लिए अधिक सामान्यतः उपयोग किया जाता है। चौकोर प्रतीक कार्तीय उत्पाद के लिए एक सहज और स्पष्ट संकेतन के रूप में अभिप्रेत है, क्योंकि यह दो किनारों के कार्तीय उत्पाद से उत्पन्न चार किनारों को दृष्टिगत रूप से दिखाता है।^[1]

उदाहरण

दो किनारों का कार्तीय उत्पाद चार शीर्षों पर एक चक्र ग्राफ है: K₂ $□$ K₂ = C₄.
K₂ का कार्तीय उत्पाद और एक पथ ग्राफ एक सीढ़ी ग्राफ है।
दो पथ ग्राफ़ का कार्तीय उत्पाद एक जालक(ग्रिड) ग्राफ है।
n किनारों का कार्तीय उत्पाद एक अतिविम है:

(K_{2})^{\square n}=Q_{n}.

इस प्रकार, दो अतिविम ग्राफ का कार्तीय उत्पाद एक और अतिविम है: Q_i□Q_j = Q_i+j.

दो माध्यिका ग्राफ का कार्तीय गुणनफल एक अन्य माध्यिका ग्राफ है।
एन-प्रिज्म (ज्यामिति) के कोने और किनारों का ग्राफ कार्तीय उत्पाद ग्राफK₂□C_n है।
रूक का ग्राफ दो पूर्ण ग्राफों का कार्तीय उत्पाद है।

गुण

यदि जुड़ा हुआ ग्राफ एक कार्तीय उत्पाद है, तो इसे प्रमुख कारकों के उत्पाद के रूप में विशिष्ट रूप से गुणनखंडित किया जा सकता है, ऐसे ग्राफ़ जिन्हें ग्राफ़ के उत्पादों के रूप में स्वयं विघटित नहीं किया जा सकता है।^[2] हालाँकि, इमरिच & कलवज़ार (2000) एक असंगत किए गए ग्राफ़ का वर्णन करें जिसे प्रधान ग्राफ़ के कार्तीय उत्पाद के रूप में दो अलग-अलग तरीकों से व्यक्त किया जा सकता है:

(K_{1}+K_{2}+K_{2}^{2})\mathbin {\square } (K_{1}+K_{2}^{3})=(K_{1}+K_{2}^{2}+K_{2}^{4})\mathbin {\square } (K_{1}+K_{2}),

जहां धन चिह्न(प्लस साइन) असंयुक्त संघ को दर्शाता है और उपरिलेख कार्तीय उत्पादों पर घातांक को दर्शाता है।

एक कार्तीय उत्पाद शीर्ष-सकर्मक ग्राफ है यदि और केवल यदि इसके प्रत्येक कारक हैं।^[3] एक कार्तीय उत्पाद द्विदलीय ग्राफ है यदि और केवल यदि इसके प्रत्येक कारक हैं। अधिक सामान्यतः, कार्तीय उत्पाद की रंगीन संख्या समीकरण को संतुष्ट करती है:

\chi (G\mathbin {\square } H)=\max\{\chi (G),\chi (H)\}.

^[4]

हेडेनीमी का अनुमान रेखांकन के टेंसर उत्पाद के लिए संबंधित समानता बताता है। कार्तीय उत्पाद की स्वतंत्रता संख्या इतनी आसानी से गणना नहीं की जाती है, लेकिन के रूप में वाइजिंग (1963) ने दिखाया कि यह असमानताओं को संतुष्ट करता है:

\alpha (G)\alpha (H)+\min\{|V(G)|-\alpha (G),|V(H)|-\alpha (H)\}\leq \alpha (G\mathbin {\square } H)\leq \min\{\alpha (G)|V(H)|,\alpha (H)|V(G)|\}.

वाइजिंग अनुमान कहता है कि कार्तीय उत्पाद की प्रभुत्व संख्या असमानता को संतुष्ट करती है:

\gamma (G\mathbin {\square } H)\geq \gamma (G)\gamma (H).

यूनिट दूरी ग्राफ़ का कार्तीय उत्पाद एक और यूनिट दूरी ग्राफ़ है।^[5]

कार्तीय उत्पाद रेखांकन को रैखिक समय में कुशलता से पहचाना जा सकता है।^[6]

बीजगणितीय ग्राफ सिद्धांत

कार्तीय ग्राफ उत्पाद का विश्लेषण करने के लिए बीजगणितीय ग्राफ सिद्धांत का उपयोग किया जा सकता है। यदि ग्राफ $G_{1}$ है $n_{1}$ शिखर और $n_{1}\times n_{1}$ सहखंडज मैट्रिक्स $\mathbf {A} _{1}$ , और ग्राफ $G_{2}$ है $n_{2}$ शिखर और $n_{2}\times n_{2}$ सहखंडज मैट्रिक्स $\mathbf {A} _{2}$ , तो दोनों ग्राफों के कार्तीय उत्पाद के आसन्न मैट्रिक्स द्वारा दिया गया है।

\mathbf {A} _{1\mathbin {\square } 2}=\mathbf {A} _{1}\otimes \mathbf {I} _{n_{2}}+\mathbf {I} _{n_{1}}\otimes \mathbf {A} _{2}

,

जहाँ $\otimes$ मैट्रिसेस के क्रोनकर उत्पाद को दर्शाता है और $\mathbf {I} _{n}$ दर्शाता है $n\times n$ तत्समक आव्यूह।^[7] कार्तीय ग्राफ उत्पाद का आसन्न मैट्रिक्स इसलिए कारकों के आसन्न मैट्रिक्स का क्रोनकर योग है।

श्रेणी सिद्धांत

एक ग्राफ़ को एक श्रेणी (गणित) के रूप में देखना, जिसकी वस्तुएँ कोने हैं और जिनकी आकृतियाँ ग्राफ़ में पथ हैं, ग्राफ़ का कार्तीय उत्पाद से मेल खाता है अजीब प्रदिश उत्पाद श्रेणियों की। ग्राफ़ का कार्तीय उत्पाद दो ग्राफ़ उत्पादों में से एक है जो ग्राफ़ और ग्राफ़ समरूपता की श्रेणी को एक सममित बंद मोनोइडल श्रेणी में बदल देता है (केवल सममित मोनोइडल के विपरीत), दूसरा ग्राफ़ का टेंसर उत्पाद है।^[8] आंतरिक होम $[G,H]$ ग्राफ़ के कार्तीय उत्पाद के लिए ग्राफ़ समरूपताएँ हैं $G$ को $H$ शीर्ष के रूप में और अप्राकृतिक परिवर्तन उनके बीच किनारों के रूप में है।^[8]

इतिहास

इमरिच & कलवज़ार (2000) के अनुसार ग्राफ़ के कार्तीय उत्पाद को 1912 में अल्फ्रेड नॉर्थ व्हाइटहेड और बर्ट्रेंड रसेल द्वारा परिभाषित किया गया था। उन्हें बार-बार बाद में फिर से खोजा गया, विशेष रूप से गर्ट सबिदुस्सी (1960) द्वारा।

↑ Hahn & Sabidussi (1997).
↑ Sabidussi (1960); Vizing (1963).
↑ Imrich & Klavžar (2000), Theorem 4.19.
↑ Sabidussi (1957).
↑ Horvat & Pisanski (2010).
↑ Imrich & Peterin (2007). For earlier polynomial time algorithms see Feigenbaum, Hershberger & Schäffer (1985) and Aurenhammer, Hagauer & Imrich (1992).
↑ Kaveh & Rahami (2005).
↑ ^8.0 ^8.1 Weber 2013.

संदर्भ

Aurenhammer, F.; Hagauer, J.; Imrich, W. (1992), "Cartesian graph factorization at logarithmic cost per edge", Computational Complexity, 2 (4): 331–349, doi:10.1007/BF01200428, MR 1215316.
Feigenbaum, Joan; Hershberger, John; Schäffer, Alejandro A. (1985), "A polynomial time algorithm for finding the prime factors of Cartesian-product graphs", Discrete Applied Mathematics, 12 (2): 123–138, doi:10.1016/0166-218X(85)90066-6, MR 0808453.
Hahn, Geňa; Sabidussi, Gert (1997), Graph symmetry: algebraic methods and applications, NATO Advanced Science Institutes Series, vol. 497, Springer, p. 116, ISBN 978-0-7923-4668-5.
Horvat, Boris; Pisanski, Tomaž (2010), "Products of unit distance graphs", Discrete Mathematics, 310 (12): 1783–1792, doi:10.1016/j.disc.2009.11.035, MR 2610282.
Imrich, Wilfried; Klavžar, Sandi (2000), Product Graphs: Structure and Recognition, Wiley, ISBN 0-471-37039-8.
Imrich, Wilfried; Klavžar, Sandi; Rall, Douglas F. (2008), Graphs and their Cartesian Products, A. K. Peters, ISBN 1-56881-429-1.
Imrich, Wilfried; Peterin, Iztok (2007), "Recognizing Cartesian products in linear time", Discrete Mathematics, 307 (3–5): 472–483, doi:10.1016/j.disc.2005.09.038, MR 2287488.
Kaveh, A.; Rahami, H. (2005), "A unified method for eigendecomposition of graph products", Communications in Numerical Methods in Engineering with Biomedical Applications, 21 (7): 377–388, doi:10.1002/cnm.753, MR 2151527.
Sabidussi, G. (1957), "Graphs with given group and given graph-theoretical properties", Canadian Journal of Mathematics, 9: 515–525, doi:10.4153/CJM-1957-060-7, MR 0094810.
Sabidussi, G. (1960), "Graph multiplication", Mathematische Zeitschrift, 72: 446–457, doi:10.1007/BF01162967, hdl:10338.dmlcz/102459, MR 0209177.
Vizing, V. G. (1963), "The Cartesian product of graphs", Vycisl. Sistemy, 9: 30–43, MR 0209178.
Weber, Mark (2013), "Free products of higher operad algebras", TAC, 28 (2): 24–65.

बाहरी संबंध

Weisstein, Eric W. "Graph Cartesian Product". MathWorld.

[FOOTNOTEHahnSabidussi1997-1] Hahn & Sabidussi (1997).

[2] Sabidussi (1960); Vizing (1963).

[3] Imrich & Klavžar (2000), Theorem 4.19.

[FOOTNOTESabidussi1957-4] Sabidussi (1957).

[FOOTNOTEHorvatPisanski2010-5] Horvat & Pisanski (2010).

[6] Imrich & Peterin (2007). For earlier polynomial time algorithms see Feigenbaum, Hershberger & Schäffer (1985) and Aurenhammer, Hagauer & Imrich (1992).

[FOOTNOTEKavehRahami2005-7] Kaveh & Rahami (2005).

[FOOTNOTEWeber2013-8] 8.0 ^8.1 Weber 2013.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

@@ Line 1: / Line 1: @@
 {{short description|Operation in graph theory}}
-[[File:Graph-Cartesian-product.svg|thumb|upright=1.35|रेखांकन का कार्टेशियन उत्पाद।]][[ग्राफ सिद्धांत]] में, कार्टेशियन उत्पाद {{math|''G'' □ ''H''}ग्राफ का } (असतत गणित)। {{mvar|G}} और {{mvar|H}} ऐसा ग्राफ है कि:
+[[File:Graph-Cartesian-product.svg|thumb|upright=1.35|रेखांकन का कार्तीय उत्पाद।]]ग्राफ़ सिद्धांत में, कार्तीय गुणन G □ H ग्राफ़ G और H एक ऐसा ग्राफ़ है जो::
-* [[ शीर्ष (ग्राफ सिद्धांत) ]] का सेट {{math|''G'' □ ''H''}} कार्टेशियन उत्पाद है {{math|''V''(''G'') × ''V''(''H'')}}; और
+* G □ H का शीर्ष समुच्चय कार्तीय गुणनफल V(G) × V(H) है; और
-* दो शिखर {{math|(''u'',''u' '')}} और {{math|(''v'',''v' '')}} में सटे हुए हैं {{math|''G'' □ ''H''}} [[अगर और केवल अगर]] या तो
+* G □ H में दो शीर्ष (u,u' ) और (v,v' ) आसन्न हैं यदि और केवल यदि या तो
-** {{math|1=''u'' = ''v''}} और {{mvar|u'}} लगी हुई है {{mvar|v'}} में {{mvar|H}}, या
+** u = v और u', H में v' के सन्निकट है, या
-**  {{math|1=''u' '' = ''v' ''}} और {{mvar|u}} लगी हुई है {{mvar|v}} में {{mvar|G}}.
+**  u' = v' और u, G में v के सन्निकट है।
 ग्राफ़ के कार्तीय उत्पाद को कभी-कभी ग्राफ़ का बॉक्स उत्पाद कहा जाता है [हैरी 1969]।
-ऑपरेशन साहचर्य है, रेखांकन के रूप में  {{math|(''F'' □ ''G'') □ ''H''}} और {{math|''F'' □ (''G'' □ ''H'')}} स्वाभाविक रूप से [[ग्राफ समरूपता]] हैं।
+संचालन साहचर्य है, रेखांकन के रूप में  {{math|(''F'' □ ''G'') □ ''H''}} और {{math|''F'' □ (''G'' □ ''H'')}} स्वाभाविक रूप से [[ग्राफ समरूपता]] हैं।
-संक्रिया क्रम[[विनिमेय]] है, रेखांकन के समरूपता [[तुल्यता वर्ग]] पर एक संक्रिया के रूप में, और अधिक दृढ़ता से रेखांकन {{math|''G'' □ ''H''}} और {{math|''H'' □ ''G''}} [[प्राकृतिक समरूपता]]वाद हैं, लेकिन यह [[ग्राफ लेबलिंग]] पर एक ऑपरेशन के रूप में क्रमविनिमेय नहीं है।
+संक्रिया क्रम[[विनिमेय]] है, रेखांकन के समरूपता [[तुल्यता वर्ग]] पर एक संक्रिया के रूप में, और अधिक दृढ़ता से रेखांकन {{math|''G'' □ ''H''}} और {{math|''H'' □ ''G''}} [[प्राकृतिक समरूपता]]वाद हैं, लेकिन यह [[ग्राफ लेबलिंग]] पर एक संचालन के रूप में क्रमविनिमेय नहीं है।
-अंकन {{math|''G'' × ''H''}} का उपयोग अक्सर ग्राफ़ के कार्टेशियन उत्पादों के लिए किया जाता है, लेकिन अब इसे ग्राफ़ के टेन्सर उत्पाद के रूप में जाने वाले अन्य निर्माण के लिए अधिक सामान्यतः उपयोग किया जाता है। चौकोर प्रतीक कार्तीय उत्पाद के लिए एक सहज और स्पष्ट संकेतन के रूप में अभिप्रेत है, क्योंकि यह दो किनारों के कार्टेशियन उत्पाद से उत्पन्न चार किनारों को नेत्रहीन रूप से दिखाता है।{{sfnp|Hahn|Sabidussi|1997}}
+अंकन {{math|''G'' × ''H''}} का उपयोग अक्सर ग्राफ़ के कार्तीय उत्पादों के लिए किया जाता है, लेकिन अब इसे ग्राफ़ के प्रदिश उत्पाद के रूप में जाने वाले अन्य निर्माण के लिए अधिक सामान्यतः उपयोग किया जाता है। चौकोर प्रतीक कार्तीय उत्पाद के लिए एक सहज और स्पष्ट संकेतन के रूप में अभिप्रेत है, क्योंकि यह दो किनारों के कार्तीय उत्पाद से उत्पन्न चार किनारों को दृष्टिगत रूप से दिखाता है।{{sfnp|Hahn|Sabidussi|1997}}
 == उदाहरण ==
-* दो किनारों का कार्तीय उत्पाद चार शीर्षों पर एक [[चक्र ग्राफ]] है: K<sub>2</sub>{{math|□}}क<sub>2</sub> = सी<sub>4</sub>.
+* दो किनारों का कार्तीय उत्पाद चार शीर्षों पर एक [[चक्र ग्राफ]] है: K<sub>2</sub>{{math|□}}K<sub>2</sub> = C<sub>4</sub>.
-* K का कार्टेशियन उत्पाद<sub>2</sub> और एक [[पथ ग्राफ]] एक सीढ़ी ग्राफ है।
+* K<sub>2</sub> का कार्तीय उत्पाद और एक [[पथ ग्राफ]] एक सीढ़ी ग्राफ है।
-* दो पथ ग्राफ़ का कार्टेशियन उत्पाद एक [[ग्रिड ग्राफ]]़ है।
+* दो पथ ग्राफ़ का कार्तीय उत्पाद एक [[Index.php?title=जालक(ग्रिड) ग्राफ|जालक(ग्रिड) ग्राफ]] है।
-* एन किनारों का कार्टेशियन उत्पाद एक हाइपरक्यूब है:
+* n किनारों का कार्तीय उत्पाद एक अतिविम है:
 :: <math>(K_2)^{\square n} = Q_n.</math>
-: इस प्रकार, दो [[हाइपरक्यूब ग्राफ]] का कार्टेशियन उत्पाद एक और हाइपरक्यूब है: क्यू<sub>i</sub>{{math|□}}क्यू<sub>j</sub> = क्यू<sub>i+j</sub>.
+: इस प्रकार, दो [[हाइपरक्यूब ग्राफ|अतिविम ग्राफ]] का कार्तीय उत्पाद एक और अतिविम है: Q<sub>i</sub>□Q<sub>j</sub> = Q<sub>i+j</sub>.
-* दो [[माध्यिका ग्राफ]]ों का कार्तीय गुणनफल एक अन्य माध्यिका ग्राफ है।
+* दो [[माध्यिका ग्राफ]] का कार्तीय गुणनफल एक अन्य माध्यिका ग्राफ है।
-* एन-[[प्रिज्म (ज्यामिति)]] के कोने और किनारों का ग्राफ कार्तीय उत्पाद ग्राफ के है<sub>2</sub>{{math|□}}सी<sub>n</sub>.
+* एन-[[प्रिज्म (ज्यामिति)]] के कोने और किनारों का ग्राफ कार्तीय उत्पाद ग्राफK<sub>2</sub>□C<sub>n</sub> है।
-* हाथी का ग्राफ दो पूर्ण ग्राफों का कार्टेशियन उत्पाद है।
+*रूक का ग्राफ दो पूर्ण ग्राफों का कार्तीय उत्पाद है।
 == गुण ==
-यदि एक कनेक्टेड ग्राफ एक कार्टेशियन उत्पाद है, तो इसे प्रमुख कारकों के उत्पाद के रूप में विशिष्ट रूप से गुणनखंडित किया जा सकता है, ऐसे ग्राफ़ जिन्हें ग्राफ़ के उत्पादों के रूप में स्वयं विघटित नहीं किया जा सकता है।<ref>{{harvtxt|Sabidussi|1960}}; {{harvtxt|Vizing|1963}}.</ref> हालाँकि, {{harvtxt|Imrich|Klavžar|2000}} एक डिस्कनेक्ट किए गए ग्राफ़ का वर्णन करें जिसे प्राइम ग्राफ़ के कार्टेशियन उत्पाद के रूप में दो अलग-अलग तरीकों से व्यक्त किया जा सकता है:
+यदि जुड़ा हुआ ग्राफ एक कार्तीय उत्पाद है, तो इसे प्रमुख कारकों के उत्पाद के रूप में विशिष्ट रूप से गुणनखंडित किया जा सकता है, ऐसे ग्राफ़ जिन्हें ग्राफ़ के उत्पादों के रूप में स्वयं विघटित नहीं किया जा सकता है।<ref>{{harvtxt|Sabidussi|1960}}; {{harvtxt|Vizing|1963}}.</ref> हालाँकि, {{harvtxt|इमरिच|कलवज़ार|2000}} एक असंगत किए गए ग्राफ़ का वर्णन करें जिसे प्रधान ग्राफ़ के कार्तीय उत्पाद के रूप में दो अलग-अलग तरीकों से व्यक्त किया जा सकता है:
 :<math>(K_1 + K_2 + K_2^2) \mathbin{\square} (K_1 + K_2^3) = (K_1 + K_2^2 + K_2^4) \mathbin{\square} (K_1 + K_2),</math>
-जहां धन चिह्न असंयुक्त संघ को दर्शाता है और सुपरस्क्रिप्ट कार्टेशियन उत्पादों पर घातांक को दर्शाता है।
+जहां धन चिह्न(प्लस साइन) असंयुक्त संघ को दर्शाता है और उपरिलेख कार्तीय उत्पादों पर घातांक को दर्शाता है।
-एक कार्टेशियन उत्पाद [[शीर्ष-सकर्मक ग्राफ]] है यदि और केवल यदि इसके प्रत्येक कारक हैं।<ref>{{harvtxt|Imrich|Klavžar|2000}}, Theorem&nbsp;4.19.</ref>
+एक कार्तीय उत्पाद [[शीर्ष-सकर्मक ग्राफ]] है यदि और केवल यदि इसके प्रत्येक कारक हैं।<ref>{{harvtxt|Imrich|Klavžar|2000}}, Theorem&nbsp;4.19.</ref>
-एक कार्टेशियन उत्पाद द्विदलीय ग्राफ है यदि और केवल यदि इसके प्रत्येक कारक हैं। अधिक सामान्यतः, कार्तीय उत्पाद की [[रंगीन संख्या]] समीकरण को संतुष्ट करती है
+एक कार्तीय उत्पाद द्विदलीय ग्राफ है यदि और केवल यदि इसके प्रत्येक कारक हैं। अधिक सामान्यतः, कार्तीय उत्पाद की [[रंगीन संख्या]] समीकरण को संतुष्ट करती है:
 :<math>\chi (G \mathbin{\square} H) = \max \{ \chi (G), \chi (H) \}.</math> {{sfnp|Sabidussi|1957}}
-[[Hedetniemi अनुमान]] रेखांकन के टेंसर उत्पाद के लिए संबंधित समानता बताता है। कार्तीय उत्पाद की स्वतंत्रता संख्या इतनी आसानी से गणना नहीं की जाती है, लेकिन के रूप में {{harvtxt|Vizing|1963}} ने दिखाया कि यह असमानताओं को संतुष्ट करता है
+[[Index.php?title=हेडेनीमी का अनुमान|हेडेनीमी का अनुमान]] रेखांकन के टेंसर उत्पाद के लिए संबंधित समानता बताता है। कार्तीय उत्पाद की स्वतंत्रता संख्या इतनी आसानी से गणना नहीं की जाती है, लेकिन के रूप में {{harvtxt|वाइजिंग|1963}} ने दिखाया कि यह असमानताओं को संतुष्ट करता है:
 :<math>\alpha (G) \alpha (H) + \min \{ |V(G)| -\alpha (G), |V(H)| - \alpha (H) \} \le \alpha (G \mathbin{\square} H) \le \min \{ \alpha (G) |V(H)|, \alpha (H) |V(G)| \}.</math>
-वाइजिंग अनुमान कहता है कि कार्तीय उत्पाद की [[प्रभुत्व संख्या]] असमानता को संतुष्ट करती है
+वाइजिंग अनुमान कहता है कि कार्तीय उत्पाद की [[प्रभुत्व संख्या]] असमानता को संतुष्ट करती है:
 :<math>\gamma (G \mathbin{\square} H) \ge \gamma (G) \gamma (H).</math>
-यूनिट दूरी ग्राफ़ का कार्टेशियन उत्पाद एक और यूनिट दूरी ग्राफ़ है।{{sfnp|Horvat|Pisanski|2010}}
+यूनिट दूरी ग्राफ़ का कार्तीय उत्पाद एक और यूनिट दूरी ग्राफ़ है।{{sfnp|Horvat|Pisanski|2010}}
 कार्तीय उत्पाद रेखांकन को [[रैखिक समय]] में कुशलता से पहचाना जा सकता है।<ref>{{harvtxt|Imrich|Peterin|2007}}. For earlier [[polynomial time]] algorithms see {{harvtxt|Feigenbaum|Hershberger|Schäffer|1985}} and {{harvtxt|Aurenhammer|Hagauer|Imrich|1992}}.</ref>
@@ Line 41: / Line 41: @@
 == [[बीजगणितीय ग्राफ सिद्धांत]] ==
-कार्टेशियन ग्राफ उत्पाद का विश्लेषण करने के लिए बीजगणितीय ग्राफ सिद्धांत का उपयोग किया जा सकता है।
+कार्तीय ग्राफ उत्पाद का विश्लेषण करने के लिए बीजगणितीय ग्राफ सिद्धांत का उपयोग किया जा सकता है।
-यदि ग्राफ <math>G_1</math> है <math>n_1</math> शिखर और <math>n_1\times n_1</math> [[सहखंडज मैट्रिक्स]] <math>\mathbf A_1</math>, और ग्राफ <math>G_2</math> है <math>n_2</math> शिखर और <math>n_2\times n_2</math> सहखंडज मैट्रिक्स <math>\mathbf A_2</math>, तो दोनों ग्राफों के कार्टेशियन उत्पाद के आसन्न मैट्रिक्स द्वारा दिया गया है
+यदि ग्राफ <math>G_1</math> है <math>n_1</math> शिखर और <math>n_1\times n_1</math> [[सहखंडज मैट्रिक्स]] <math>\mathbf A_1</math>, और ग्राफ <math>G_2</math> है <math>n_2</math> शिखर और <math>n_2\times n_2</math> सहखंडज मैट्रिक्स <math>\mathbf A_2</math>, तो दोनों ग्राफों के कार्तीय उत्पाद के आसन्न मैट्रिक्स द्वारा दिया गया है।
 : <math>\mathbf A_{1\mathbin{\square} 2} = \mathbf A_1 \otimes \mathbf I_{n_2} + \mathbf I_{n_1} \otimes \mathbf A_2</math>,
-कहाँ <math>\otimes</math> मैट्रिसेस के [[क्रोनकर उत्पाद]] को दर्शाता है और <math>\mathbf I_n</math> दर्शाता है <math>n\times n</math> [[शिनाख्त सांचा]]।{{sfnp|Kaveh|Rahami|2005}} कार्तीय ग्राफ उत्पाद का आसन्न मैट्रिक्स इसलिए कारकों के आसन्न मैट्रिक्स का क्रोनकर योग है।
+जहाँ <math>\otimes</math> मैट्रिसेस के [[क्रोनकर उत्पाद]] को दर्शाता है और <math>\mathbf I_n</math> दर्शाता है <math>n\times n</math> [[Index.php?title=तत्समक आव्यूह|तत्समक आव्यूह]]।{{sfnp|Kaveh|Rahami|2005}} कार्तीय ग्राफ उत्पाद का आसन्न मैट्रिक्स इसलिए कारकों के आसन्न मैट्रिक्स का क्रोनकर योग है।
 == श्रेणी सिद्धांत ==
-एक ग्राफ़ को एक [[श्रेणी (गणित)]] के रूप में देखना, जिसकी वस्तुएँ कोने हैं और जिनकी आकृतियाँ ग्राफ़ में पथ हैं, ग्राफ़ का कार्टेशियन उत्पाद [https://ncatlab.org/nlab/show/funny+tensor+product से मेल खाता है अजीब टेन्सर उत्पाद] श्रेणियों की। ग्राफ़ का कार्तीय उत्पाद दो ग्राफ़ उत्पादों में से एक है जो ग्राफ़ और ग्राफ़ समरूपता की श्रेणी को एक [[सममित मोनोइडल श्रेणी]] [[बंद मोनोइडल श्रेणी]] में बदल देता है (केवल सममित मोनोइडल के विपरीत), दूसरा ग्राफ़ का टेंसर उत्पाद है।{{sfn|Weber|2013}} आंतरिक होम <math>[G, H]</math> ग्राफ़ के कार्टेशियन उत्पाद के लिए ग्राफ़ समरूपताएँ हैं <math>G</math> को <math>H</math> शीर्ष के रूप में और [https://ncatlab.org/nlab/show/unnatural+transformation अप्राकृतिक परिवर्तन] उनके बीच किनारों के रूप में।{{sfn|Weber|2013}}
+एक ग्राफ़ को एक [[श्रेणी (गणित)]] के रूप में देखना, जिसकी वस्तुएँ कोने हैं और जिनकी आकृतियाँ ग्राफ़ में पथ हैं, ग्राफ़ का कार्तीय उत्पाद [https://ncatlab.org/nlab/show/funny+tensor+product से मेल खाता है अजीब प्रदिश उत्पाद] श्रेणियों की। ग्राफ़ का कार्तीय उत्पाद दो ग्राफ़ उत्पादों में से एक है जो ग्राफ़ और ग्राफ़ समरूपता की श्रेणी को एक [[Index.php?title=सममित|सममित]] [[बंद मोनोइडल श्रेणी]] में बदल देता है (केवल सममित मोनोइडल के विपरीत), दूसरा ग्राफ़ का टेंसर उत्पाद है।{{sfn|Weber|2013}} आंतरिक होम <math>[G, H]</math> ग्राफ़ के कार्तीय उत्पाद के लिए ग्राफ़ समरूपताएँ हैं <math>G</math> को <math>H</math> शीर्ष के रूप में और [https://ncatlab.org/nlab/show/unnatural+transformation अप्राकृतिक परिवर्तन] उनके बीच किनारों के रूप में है।{{sfn|Weber|2013}}
 == इतिहास ==
-के अनुसार {{harvtxt|Imrich|Klavžar|2000}}, ग्राफ़ के कार्तीय उत्पाद को 1912 में [[अल्फ्रेड नॉर्थ व्हाइटहेड]] और [[बर्ट्रेंड रसेल]] द्वारा परिभाषित किया गया था। उन्हें बार-बार बाद में फिर से खोजा गया, विशेष रूप से द्वारा {{harvs|first=Gert|last=Sabidussi|authorlink=Gert Sabidussi|year=1960|txt}}.
+{{harvtxt|इमरिच|कलवज़ार|2000}} के अनुसार ग्राफ़ के कार्तीय उत्पाद को 1912 में [[अल्फ्रेड नॉर्थ व्हाइटहेड]] और [[बर्ट्रेंड रसेल]] द्वारा परिभाषित किया गया था। उन्हें बार-बार बाद में फिर से खोजा गया, विशेष रूप से {{harvs|first=गर्ट|last=सबिदुस्सी|authorlink=गर्ट सबिदुस्सी|year=1960|txt}} द्वारा।
 ==टिप्पणियाँ==

Anonymous

Search

ग्राफ़ के कार्तीय उत्पाद: Difference between revisions

Namespaces

More

Page actions

Revision as of 11:21, 16 May 2023

Contents

उदाहरण

गुण

बीजगणितीय ग्राफ सिद्धांत

श्रेणी सिद्धांत

इतिहास

टिप्पणियाँ

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

ग्राफ़ के कार्तीय उत्पाद: Difference between revisions

Revision as of 11:21, 16 May 2023

उदाहरण

गुण

बीजगणितीय ग्राफ सिद्धांत

श्रेणी सिद्धांत

इतिहास

टिप्पणियाँ

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories