रेखांकन का शब्दकोषीय उत्पाद
ग्राफ़ सिद्धांत में, लेक्सिकोग्राफ़िक उत्पाद या (ग्राफ़) रचना G ∙ H ग्राफ़ का G और H एक ग्राफ़ ऐसा है
- का शीर्ष सेट G ∙ H कार्तीय गुणनफल है V(G) × V(H); और
- कोई भी दो शीर्ष (u,v) और (x,y) में आसन्न हैं G ∙ H यदि और केवल यदि दोनों में से कोई एक u के साथ सटा हुआ है x में G या u = x और v के साथ सटा हुआ है y मेंH.
यदि दो ग्राफ़ के किनारे संबंध क्रम सिद्धांत हैं, तो उनके लेक्सिकोग्राफ़िक उत्पाद का किनारा संबंध संबंधित शब्दकोषीय क्रम है।
लेक्सिकोग्राफ़िक उत्पाद का अध्ययन सबसे पहले किसके द्वारा किया गया था Felix Hausdorff (1914). जैसा Feigenbaum & Schäffer (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.
