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

[[Image:Graph-lexicographic-product.svg|thumb|300px|ग्राफ़ का शब्दकोषीय उत्पाद.]]ग्राफ़ सिद्धांत में, लेक्सिकोग्राफ़िक उत्पाद या (ग्राफ़) रचना {{math|''G'' ∙ ''H''}} ग्राफ़ का {{mvar|G}} और {{mvar|H}} एक ग्राफ़ ऐसा है
* का शीर्ष सेट {{math|''G'' ∙ ''H''}} [[कार्तीय गुणन]]फल है {{math|''V(G)'' × ''V(H)''}}; और
* कोई भी दो शीर्ष {{math|(''u'',''v'')}} और {{math|(''x'',''y'')}} में आसन्न हैं {{math|''G'' ∙ ''H''}} यदि और केवल यदि दोनों में से कोई एक {{mvar|u}} के साथ सटा हुआ है {{mvar|x}} में {{mvar|G}} या {{math|1=''u'' = ''x''}} और {{mvar|v}} के साथ सटा हुआ है {{mvar|y}} में{{mvar|H}}.

यदि दो ग्राफ़ के किनारे संबंध क्रम सिद्धांत हैं, तो उनके लेक्सिकोग्राफ़िक उत्पाद का किनारा संबंध संबंधित [[शब्दकोषीय क्रम]] है।

लेक्सिकोग्राफ़िक उत्पाद का अध्ययन सबसे पहले किसके द्वारा किया गया था {{harvs|first=Felix|last=Hausdorff|authorlink=Felix Hausdorff|year=1914|txt}}. जैसा {{harvtxt|Feigenbaum|Schäffer|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}}:
:{{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=''b'' = χ(''H'')}}.

दो ग्राफ़ का शब्दकोषीय उत्पाद एक आदर्श ग्राफ़ होता है यदि और केवल तभी जब दोनों कारक सही हों {{harv|Ravindra|Parthasarathy|1977}}.

==संदर्भ==
*{{citation
  | last1 = Feigenbaum | first1 =  J. | last2 = Schäffer | first2 = A. A.
  | year = 1986
  | title = Recognizing composite graphs is equivalent to testing graph isomorphism
  | journal = [[SIAM Journal on Computing]]
  | volume = 15
  | pages = 619–627
  | mr = 0837609
  | doi = 10.1137/0215045
  | issue = 2}}.
*{{citation
  | last1 = Geller | first1 = D. | last2 = Stahl | first2 = S.
  | title = The chromatic number and other functions of the lexicographic product
  | journal = [[Journal of Combinatorial Theory]] | series = Series B
  | volume = 19
  | year = 1975
  | pages = 87–95
  | mr = 0392645
  | doi = 10.1016/0095-8956(75)90076-3| doi-access = free
  }}.
*{{citation
  | last = Hausdorff | first = F.
  | authorlink = Felix Hausdorff
  | title = Grundzüge der Mengenlehre
  | year = 1914
  | location = Leipzig}}
*{{citation
  | last1 = Imrich | first1 = Wilfried | last2 = Klavžar | first2 = Sandi
  | title = Product Graphs: Structure and Recognition
  | publisher = Wiley
  | year = 2000
  | isbn = 0-471-37039-8}}
*{{citation
 | last1 = Ravindra | first1 = G.
 | last2 = Parthasarathy | first2 = K. R.
 | doi = 10.1016/0012-365X(77)90056-5
 | issue = 2
 | journal = Discrete Mathematics
 | mr = 0491304
 | pages = 177–186
 | title = Perfect product graphs
 | volume = 20
 | year = 1977| hdl = 10338.dmlcz/102469
 | hdl-access = free
 }}.


== बाहरी संबंध ==
*{{mathworld | title = Graph Lexicographic Product | urlname = GraphLexicographicProduct}}
[[Category: ग्राफ़ उत्पाद]] 



[[Category: Machine Translated Page]]
[[Category:Created On 09/08/2023]]