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

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

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

बाहरी संबंध

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