रेखांकन का शब्दकोषीय उत्पाद

आरेख का शब्दकोषीय उत्पाद.

शब्दकोषीय उत्पाद या आरेख संरचना, आरेख सिद्धांत में, दो आरेख 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.

बाहरी संबंध

• Weisstein, Eric W. "Graph Lexicographic Product". MathWorld.