रेखांकन का शब्दकोषीय उत्पाद: Difference between revisions
From Vigyanwiki
(Created page with "thumb|300px|ग्राफ़ का शब्दकोषीय उत्पाद.ग्राफ़ सिद्धांत म...") |
m (5 revisions imported from alpha:रेखांकन_का_शब्दकोषीय_उत्पाद) |
||
| (4 intermediate revisions by 2 users not shown) | |||
| 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'')}}। विशेष रूप से, दो [[स्व-पूरक ग्राफ|स्व-पूरक आरेख]] का शब्दकोषीय उत्पाद स्व-पूरक होता है। | |||
इसके | |||
किसी शब्दकोषीय उत्पाद की [[स्वतंत्रता संख्या]] की गणना उसके कारकों से आसानी से की जा सकती है | किसी शब्दकोषीय उत्पाद की [[स्वतंत्रता संख्या]] की गणना उसके कारकों से आसानी से की जा सकती है गेलर एवं स्टाल 1975: | ||
:{{math|1=α(''G'' ∙ ''H'') = α(''G'')α(''H'')}}. | :{{math|1=α(''G'' ∙ ''H'') = α(''G'')α(''H'')}}. | ||
| Line 17: | Line 17: | ||
:{{math|1=ω(''G'' ∙ ''H'') = ω(''G'')ω(''H'')}}. | :{{math|1=ω(''G'' ∙ ''H'') = ω(''G'')ω(''H'')}}. | ||
किसी शब्दकोषीय उत्पाद की वर्णिक | किसी शब्दकोषीय उत्पाद की वर्णिक शब्दकोषीय उत्पाद का वर्णिक नंबर G के b--गुणा वर्णिक नंबर के बराबर होता है, जहाँ b H के वर्णिक नंबर के समान होता है | ||
:{{math|1=χ(''G'' ∙ ''H'') = χ<sub>b</sub>(''G'')}}, | :{{math|1=χ(''G'' ∙ ''H'') = χ<sub>b</sub>(''G'')}},जहाँ {{math|1=''b'' = χ(''H'')}}. | ||
दो | दो आरेख का शब्दकोषीय उत्पाद एक आदर्श आरेख होता है यदि और केवल तभी जब दोनों कारक सही हों {{harv|(रवींद्र|पार्थसारथी |1977)}}. | ||
==संदर्भ== | ==संदर्भ== | ||
| Line 78: | Line 78: | ||
[[Category: Machine Translated Page]] | [[Category: Machine Translated Page]] | ||
[[Category:Created On 09/08/2023]] | [[Category:Created On 09/08/2023]] | ||
[[Category:Vigyan Ready]] | |||
Latest revision as of 07:37, 28 September 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)। विशेष रूप से, दो स्व-पूरक आरेख का शब्दकोषीय उत्पाद स्व-पूरक होता है।
किसी शब्दकोषीय उत्पाद की स्वतंत्रता संख्या की गणना उसके कारकों से आसानी से की जा सकती है गेलर एवं स्टाल 1975:
- α(G ∙ H) = α(G)α(H).
किसी शब्दकोषीय उत्पाद की क्लिक संख्या भी गुणक होती है:
- ω(G ∙ H) = ω(G)ω(H).
किसी शब्दकोषीय उत्पाद की वर्णिक शब्दकोषीय उत्पाद का वर्णिक नंबर G के b--गुणा वर्णिक नंबर के बराबर होता है, जहाँ b H के वर्णिक नंबर के समान होता है
- χ(G ∙ H) = χb(G),जहाँ b = χ(H).
दो आरेख का शब्दकोषीय उत्पाद एक आदर्श आरेख होता है यदि और केवल तभी जब दोनों कारक सही हों ((रवींद्र, पार्थसारथी & 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.
