रेखांकन का शब्दकोषीय उत्पाद: Difference between revisions
(Created page with "thumb|300px|ग्राफ़ का शब्दकोषीय उत्पाद.ग्राफ़ सिद्धांत म...") |
No edit summary |
||
| Line 1: | Line 1: | ||
[[Image:Graph-lexicographic-product.svg|thumb|300px| | [[Image:Graph-lexicographic-product.svg|thumb|300px|आरेख का शब्दकोषीय उत्पाद.]]'''शब्दकोषीय उत्पाद या आरेख संरचना''', आरेख सिद्धांत में, दो आरेख {{mvar|G}} और {{mvar|H}} को एक नए आरेख में मिलाया जाता है, जिसे {{math|''G'' ∙ ''H''}} के रूप में दर्शाया जाता है। यह संचालन निम्नलिखित रूप में परिभाषित होता है: | ||
* | * आरेख {{math|''G'' ∙ ''H''}} का शीर्ष समुच्चय {{math|''V(G)'' × ''V(H)''}}; का [[कार्तीय गुणन|कार्तीय]] उत्पाद होता है; और | ||
* | *आरेख {{math|''G'' ∙ ''H''}} में किसी भी दो शीर्ष {{math|(''u'',''v'')}} और {{math|(''x'',''y'')}} के बीच संबंधित होते हैं यदि और केवल यदि या तो {{mvar|u}} {{mvar|G}} में {{mvar|x}} के साथ संबंधित है,या यदि {{math|1=''u'' = ''x''}} है और {{mvar|v}} {{mvar|H}} में {{mvar|y}} के साथ संबंधित है। | ||
यदि दो आरेख के किनारे के संबंध आदेश संबंध होते हैं, तो उनके शब्दकोशीय संबंधी उत्पाद के संबंध को सम्मिलित करके प्राप्त संबंध [[शब्दकोषीय क्रम]] होता है। | |||
शब्दकोशीय संबंधी उत्पाद का पहला अध्ययन [[ क्रमपरिवर्तनशीलता |फीलिक्स हौसडोर्फ]] (1914) ने किया था। जैसा कि फाइगेनबाम और शेफर (1986) ने दिखाया, आरेख के शब्दकोशीय उत्पाद होने की पहचान करने की समस्या का ज्ञानी और आरेख समरूपता समस्या के जैसे समय के साथ संबंधित है। | |||
==गुण== | ==गुण== | ||
लेक्सिकोआरेख ़िक उत्पाद सामान्य रूप से [[ क्रमपरिवर्तनशीलता ]] में है: {{math|''G'' ∙ ''H'' ≠ ''H'' ∙ ''G''}}. हालाँकि यह असंयुक्त संघ के संबंध में एक वितरण को संतुष्ट करता है: {{math|1=(''A'' + ''B'') ∙ ''C'' = ''A'' ∙ ''C'' + ''B'' ∙ ''C''}}. | |||
इसके अलावा यह पूरक ( | इसके अलावा यह पूरक (आरेख ़ सिद्धांत) के संबंध में एक पहचान को संतुष्ट करता है: {{math|1=C(''G'' ∙ ''H'') = C(''G'') ∙ C(''H'')}}. विशेष रूप से, दो [[स्व-पूरक ग्राफ|स्व-पूरक आरेख]] ़ का शब्दकोषीय उत्पाद स्व-पूरक होता है। | ||
किसी शब्दकोषीय उत्पाद की [[स्वतंत्रता संख्या]] की गणना उसके कारकों से आसानी से की जा सकती है {{harv|Geller|Stahl|1975}}: | किसी शब्दकोषीय उत्पाद की [[स्वतंत्रता संख्या]] की गणना उसके कारकों से आसानी से की जा सकती है {{harv|Geller|Stahl|1975}}: | ||
| Line 20: | Line 21: | ||
:{{math|1=χ(''G'' ∙ ''H'') = χ<sub>b</sub>(''G'')}}, कहाँ {{math|1=''b'' = χ(''H'')}}. | :{{math|1=χ(''G'' ∙ ''H'') = χ<sub>b</sub>(''G'')}}, कहाँ {{math|1=''b'' = χ(''H'')}}. | ||
दो | दो आरेख ़ का शब्दकोषीय उत्पाद एक आदर्श आरेख ़ होता है यदि और केवल तभी जब दोनों कारक सही हों {{harv|Ravindra|Parthasarathy|1977}}. | ||
==संदर्भ== | ==संदर्भ== | ||
Revision as of 09:40, 12 August 2023
शब्दकोषीय उत्पाद या आरेख संरचना, आरेख सिद्धांत में, दो आरेख G और H को एक नए आरेख में मिलाया जाता है, जिसे G ∙ H के रूप में दर्शाया जाता है। यह संचालन निम्नलिखित रूप में परिभाषित होता है:
- आरेख G ∙ H का शीर्ष समुच्चय V(G) × V(H); का कार्तीय उत्पाद होता है; और
- आरेख G ∙ H में किसी भी दो शीर्ष (u,v) और (x,y) के बीच संबंधित होते हैं यदि और केवल यदि या तो u G में x के साथ संबंधित है,या यदि u = x है और v H में y के साथ संबंधित है।
यदि दो आरेख के किनारे के संबंध आदेश संबंध होते हैं, तो उनके शब्दकोशीय संबंधी उत्पाद के संबंध को सम्मिलित करके प्राप्त संबंध शब्दकोषीय क्रम होता है।
शब्दकोशीय संबंधी उत्पाद का पहला अध्ययन फीलिक्स हौसडोर्फ (1914) ने किया था। जैसा कि फाइगेनबाम और शेफर (1986) ने दिखाया, आरेख के शब्दकोशीय उत्पाद होने की पहचान करने की समस्या का ज्ञानी और आरेख समरूपता समस्या के जैसे समय के साथ संबंधित है।
गुण
लेक्सिकोआरेख ़िक उत्पाद सामान्य रूप से क्रमपरिवर्तनशीलता में है: G ∙ H ≠ H ∙ G. हालाँकि यह असंयुक्त संघ के संबंध में एक वितरण को संतुष्ट करता है: (A + B) ∙ C = A ∙ C + B ∙ C. इसके अलावा यह पूरक (आरेख ़ सिद्धांत) के संबंध में एक पहचान को संतुष्ट करता है: C(G ∙ H) = C(G) ∙ C(H). विशेष रूप से, दो स्व-पूरक आरेख ़ का शब्दकोषीय उत्पाद स्व-पूरक होता है।
किसी शब्दकोषीय उत्पाद की स्वतंत्रता संख्या की गणना उसके कारकों से आसानी से की जा सकती है (Geller & Stahl 1975):
- α(G ∙ H) = α(G)α(H).
किसी शब्दकोषीय उत्पाद की क्लिक संख्या भी गुणक होती है:
- ω(G ∙ H) = ω(G)ω(H).
किसी शब्दकोषीय उत्पाद की वर्णिक संख्या, G की भिन्नात्मक रंग#परिभाषाएँ|b-गुना वर्णिक संख्या के बराबर होती है, b के लिए, H की वर्णिक संख्या के बराबर होती है:
- χ(G ∙ H) = χb(G), कहाँ b = χ(H).
दो आरेख ़ का शब्दकोषीय उत्पाद एक आदर्श आरेख ़ होता है यदि और केवल तभी जब दोनों कारक सही हों (Ravindra & Parthasarathy 1977).
संदर्भ
- Feigenbaum, J.; Schäffer, A. A. (1986), "Recognizing composite graphs is equivalent to testing graph isomorphism", SIAM Journal on Computing, 15 (2): 619–627, doi:10.1137/0215045, MR 0837609.
- Geller, D.; Stahl, S. (1975), "The chromatic number and other functions of the lexicographic product", Journal of Combinatorial Theory, Series B, 19: 87–95, doi:10.1016/0095-8956(75)90076-3, MR 0392645.
- Hausdorff, F. (1914), Grundzüge der Mengenlehre, Leipzig
{{citation}}: CS1 maint: location missing publisher (link) - Imrich, Wilfried; Klavžar, Sandi (2000), Product Graphs: Structure and Recognition, Wiley, ISBN 0-471-37039-8
- Ravindra, G.; Parthasarathy, K. R. (1977), "Perfect product graphs", Discrete Mathematics, 20 (2): 177–186, doi:10.1016/0012-365X(77)90056-5, hdl:10338.dmlcz/102469, MR 0491304.
