टुट्टे बहुपद: Difference between revisions
From Vigyanwiki
No edit summary |
m (16 revisions imported from alpha:टुट्टे_बहुपद) |
||
| (10 intermediate revisions by 2 users not shown) | |||
| Line 2: | Line 2: | ||
{{about|एक ग्राफ का पूर्ण बहुपद|मैट्रोइड का पूर्ण बहुपद|मैट्रोइड }} | {{about|एक ग्राफ का पूर्ण बहुपद|मैट्रोइड का पूर्ण बहुपद|मैट्रोइड }} | ||
[[Image:Tutte polynomial and chromatic polynomial of the Bull graph.jpg|thumb|upright=1.3|right|बहुपद <math>x^4+x^3+x^2y</math> [[बुल ग्राफ]] का टुट्टे बहुपद है। लाल रेखा विमान के साथ प्रतिच्छेदन को दर्शाती है <math>y=0</math>, रंगीन बहुपद के | [[Image:Tutte polynomial and chromatic polynomial of the Bull graph.jpg|thumb|upright=1.3|right|बहुपद <math>x^4+x^3+x^2y</math> [[बुल ग्राफ]] का टुट्टे बहुपद है। लाल रेखा विमान के साथ प्रतिच्छेदन को दर्शाती है <math>y=0</math>, रंगीन बहुपद के सामान्तर होती है।]]'''टुट्टे [[बहुपद]]''', जिसे '''द्विवर्णी''' या '''टुट्टे -व्हिटनी बहुपद''' भी कहा जाता है, ग्राफ बहुपद है। यह दो चरों वाला बहुपद है जो ग्राफ़ सिद्धांत में महत्वपूर्ण भूमिका निभाता है। यह प्रत्येक [[अप्रत्यक्ष ग्राफ|अदिष्ट आलेख]] <math>G</math> के लिए परिभाषित किया गया है और ग्राफ के संबंधो के बारे में जानकारी प्रदान करता है। इसे <math>T_G</math> द्वारा दर्शाया जाता है। | ||
इस बहुपद का महत्व इस बात से आता है कि यह <math>G</math> के बारे में | इस बहुपद का महत्व इस बात से समझ आता है कि यह <math>G</math> के बारे में जानकारी उत्पन्न करता है, यद्यपि मूल रूप से [[बीजगणितीय ग्राफ सिद्धांत]] में [[ग्राफ़ रंग]] और कहीं-शून्य प्रवाह से संबंधित गणना समस्याओं के सामान्यीकरण के रूप में अध्ययन किया गया है। इसमें अन्य विज्ञानों से अनेक प्रसिद्ध अन्य विशेषज्ञताएं सम्मलित हैं जैसे कि गुणांक सिद्धांत से [[जोन्स बहुपद]] और [[विभाजन फ़ंक्शन (सांख्यिकीय यांत्रिकी)|विभाजन फलन (सांख्यिकीय यांत्रिकी)]] [[सांख्यिकीय भौतिकी]] से [[पॉट्स मॉडल]] होता है। यह [[सैद्धांतिक कंप्यूटर विज्ञान]] में अनेक केंद्रीय [[कम्प्यूटेशनल समस्या]]ओं का स्रोत भी है। | ||
टुट्टे बहुपद की | टुट्टे बहुपद की अनेक परिभाषाएँ सामान्य मिलती है। यह सरल परिवर्तनों के अनुसार व्हिटनी के श्रेणी बहुपद, टुट्टे के स्वयं के '''द्विवर्णी बहुपद''' और फोर्टुइन-कास्टेलीन के [[यादृच्छिक क्लस्टर मॉडल]] के समान होता है। यह अनिवार्य रूप से [[matroid|मेट्रोइड]] के तत्काल सामान्यीकरण के साथ, किसी दिए गए आकार और जुड़े घटकों के किनारे समुच्चय की संख्या के लिए [[जनरेटिंग फ़ंक्शन|उत्पादन कारक फलन]] होता है। यह सबसे सामान्य ग्राफ अपरिवर्तनीय भी है जिसे विलोपन-संकुचन सूत्र पुनरावृत्ति द्वारा परिभाषित किया जा सकता है। ग्राफ सिद्धांत और मैट्रोइड सिद्धांत के बारे में अनेक पाठ्यपुस्तकें इसके लिए पूरे अध्याय समर्पित करती हैं।<ref>{{harvnb|Bollobás|1998|loc=chapter 10}}.</ref><ref>{{harvnb|Biggs|1993|loc=chapter 13}}.</ref><ref>{{harvnb|Godsil|Royle|2004|loc=chap. 15}}.</ref> | ||
==परिभाषाएँ== | ==परिभाषाएँ== | ||
अविरूपित ग्राफ (जिसे <math>G=(V,E)</math> द्वारा | अविरूपित ग्राफ (जिसे <math>G=(V,E)</math> द्वारा दर्शाया जा सकता है) टुट्टे बहुपद को इस प्रकार परिभाषित कर सकता है | ||
:<math>T_G(x,y)=\sum\nolimits_{A\subseteq E} (x-1)^{k(A)-k(E)}(y-1)^{k(A)+|A|-|V|},</math> | :<math>T_G(x,y)=\sum\nolimits_{A\subseteq E} (x-1)^{k(A)-k(E)}(y-1)^{k(A)+|A|-|V|},</math> | ||
यहाँ <math>k(A)</math> ग्राफ़ <math>(V,A)</math> के संबंधित घटकों की संख्या को दर्शाता है। इस परिभाषा में स्पष्ट है कि <math>T_G</math> विशेषतः परिभाषित होता है और | यहाँ <math>k(A)</math> ग्राफ़ <math>(V,A)</math> के संबंधित घटकों की संख्या को दर्शाता है। इस परिभाषा में स्पष्ट है कि <math>T_G</math> विशेषतः परिभाषित होता है और यहाँ <math>x</math> और <math>y</math>.बहुपद है। | ||
इस परिभाषा को थोड़ा अलग संकेतन का उपयोग करके दिया जा सकता है <math>r(A)=|V|-k(A)</math> ग्राफ़ <math>(V,A)</math> के | इस परिभाषा को थोड़ा अलग संकेतन का उपयोग करके दिया जा सकता है :<math>r(A)=|V|-k(A)</math> ग्राफ़ <math>(V,A)</math> के श्रेणी को दर्शाने के लिए उपयोग किया है। जिसमें संबंधित समस्त संचय के सभी दुघर्ण नहीं हैं, तब '''व्हिटनी श्रेणी''' उत्पन्न करने वाला फलन निम्नलिखित रूप में परिभाषित होता है: | ||
:<math>R_G(u,v)=\sum\nolimits_{A\subseteq E} u^{r(E)-r(A)} v^{|A|-r(A)}.</math> | :<math>R_G(u,v)=\sum\nolimits_{A\subseteq E} u^{r(E)-r(A)} v^{|A|-r(A)}.</math> | ||
चरों के साधारण परिवर्तन के अनुसार दोनों | चरों के साधारण परिवर्तन के अनुसार दोनों फलन समतुल्य हैं: | ||
:<math>T_G(x,y)=R_G(x-1,y-1).</math> | :<math>T_G(x,y)=R_G(x-1,y-1).</math> | ||
| Line 24: | Line 24: | ||
:<math>T_G(x,y)=(x-1)^{-k(G)} Q_G(x-1,y-1).</math> | :<math>T_G(x,y)=(x-1)^{-k(G)} Q_G(x-1,y-1).</math> | ||
टुट्टे की मूल परिभाषा <math>T_G</math> समान होती है | टुट्टे की मूल परिभाषा <math>T_G</math> समान होती है किन्तु कम आसान वक्तव्य के अनुसार उदाहरण के रूप में दिया जा सकता है। संबंधित G के लिए हम इसे हिंदी में इस प्रकार से अनुवादित करते हैं: | ||
:<math>T_G(x,y)=\sum\nolimits_{i,j} t_{ij} x^iy^j,</math> | :<math>T_G(x,y)=\sum\nolimits_{i,j} t_{ij} x^iy^j,</math> | ||
यहाँ <math>t_{ij}</math> आंतरिक गतिविधि के [[स्पैनिंग ट्री (गणित)]] की संख्या को दर्शाता है जो आंतरिक गतिविधि <math>i</math> और बाहरी गतिविधि <math>j</math> की संख्या होती है। | यहाँ <math>t_{ij}</math> आंतरिक गतिविधि के [[स्पैनिंग ट्री (गणित)|विस्तरित तरु(गणित)]] की संख्या को दर्शाता है जो आंतरिक गतिविधि <math>i</math> और बाहरी गतिविधि <math>j</math> की संख्या होती है। | ||
तीसरी परिभाषा विलयन-कंट्रैक्शन पुनरावृत्ति का उपयोग करती | तीसरी परिभाषा में हम विलयन-कंट्रैक्शन पुनरावृत्ति का उपयोग करती है। ग्राफ <math>G</math> का [[किनारे का संकुचन]] <math>G/uv</math> वह ग्राफ होता है जिसे शिखर <math>u</math> और <math>v</math> को एकीकृत करके प्राप्त किया जाता है और किनारा <math>uv</math> को हटा दिया जाता है। हम <math>G - uv</math> ग्राफ को वह ग्राफ कहते हैं जिसमें किनारा <math>uv</math> को सिर्फ हटाया गया होता है। फिर ट्यूट बहुपद को पुनरावृत्ति संबंध से परिभाषित किया जाता है | ||
:<math>T_G= T_{G-e}+T_{G/e},</math> | :<math>T_G= T_{G-e}+T_{G/e},</math> | ||
यदि <math>e</math> न | यदि <math>e</math> न तब [[लूप (ग्राफ सिद्धांत)]] है और न ही वेदी (ग्राफ सिद्धांत), इसके साथ: | ||
:<math>T_G(x,y)= x^i y^j, </math> | :<math>T_G(x,y)= x^i y^j, </math> | ||
यदि <math>G</math> | यदि <math>G</math> में <math>i</math> ब्रिज और <math>j</math> लूप होते हैं और कोई अन्य किनारा नहीं होता है। विशेष रूप से, <math>T_G=1</math> यदि <math>G</math> कोई किनारा नहीं है। | ||
विधि-तांत्रिकी के भौतिकी में {{harvtxt|फॉर्चिन |कास्टेलेन|1972}} द्वारा सांख्यिकीय यात्री मॉडल और समान विभाजन के उपयोग से और परिभाषा प्रदान करता है।<ref>{{harvnb|Sokal|2005}}.</ref> विभाजन सम क्रम कोईरा सम | |||
:<math>Z_G(q,w)=\sum\nolimits_{F\subseteq E}q^{k(F)}w^{|F|}</math> | :<math>Z_G(q,w)=\sum\nolimits_{F\subseteq E}q^{k(F)}w^{|F|}</math> | ||
टुट्टे बहुपद के समान है, परिवर्तन के | टुट्टे बहुपद के समान है, परिवर्तन के अनुसार <ref>{{harvnb|Sokal|2005|loc=eq. (2.26)}}.</ref> | ||
:<math>T_G(x, y)=(x-1)^{-k(E)}(y-1)^{-|V|} \cdot Z_G\Big((x-1)(y-1),\; y-1\Big).</math><br /> | :<math>T_G(x, y)=(x-1)^{-k(E)}(y-1)^{-|V|} \cdot Z_G\Big((x-1)(y-1),\; y-1\Big).</math><br /> | ||
===गुण=== | ===गुण=== | ||
टूटे बहुपद को संबंधित घटकों में विभाजित किया जा सकता है। यदि <math>G</math> | टूटे बहुपद को संबंधित घटकों में विभाजित किया जा सकता है। यदि <math>G</math> विभिन्न ग्राफ <math>H</math> और <math>H'</math> के अविभाज्य संघ का संयोजन है, तब | ||
: <math>T_G= T_H \cdot T_{H'}</math> | : <math>T_G= T_H \cdot T_{H'}</math> | ||
यदि <math>G</math> योजनात्मक है और <math>G^*</math> तब इसके दोहरे ग्राफ को दर्शाता है | यदि <math>G</math> योजनात्मक है और <math>G^*</math> तब इसके दोहरे ग्राफ को दर्शाता है | ||
: <math>T_G(x,y)= T_{G^*} (y,x)</math> | : <math>T_G(x,y)= T_{G^*} (y,x)</math> | ||
विशेष रूप से, | विशेष रूप से, योजनात्मक ग्राफ का रंगीन बहुपद उसके दोहरे का प्रवाह बहुपद होता है। टुट्टे ऐसे फलन को वी-फलन के रूप में संदर्भित करता है।<ref name="Tutte-2004" /> | ||
===उदाहरण=== | ===उदाहरण=== | ||
समरूपी ग्राफ़ में ही टुट्टे बहुपद होता है, किन्तु इसका विपरीत सत्य नहीं है। उदाहरण के लिए, <math>m</math> किनारे | समरूपी ग्राफ़ में ही टुट्टे बहुपद होता है, किन्तु इसका विपरीत सत्य नहीं है। उदाहरण के लिए, <math>m</math> किनारे प्रत्येक ट्री का टुट्टे बहुपद <math>x^m</math> होता है। | ||
टुट्टे बहुपदों को | टुट्टे बहुपदों को अधिकांशतः गुणांकों को सूचीबद्ध करके सारणीबद्ध रूप में दिया जाता है <math>t_{ij}</math> का <math>x^iy^j</math> पंक्ति में <math>i</math> और स्तंभ <math>j</math>. उदाहरण के लिए, [[पीटरसन ग्राफ]] का टुट्टे बहुपद, | ||
:<math>\begin{align} | :<math>\begin{align} | ||
| Line 64: | Line 64: | ||
&+10xy^4, | &+10xy^4, | ||
\end{align}</math> | \end{align}</math> | ||
निम्नलिखित तालिका में दिया गया है। | |||
{|class="wikitable" | {|class="wikitable" | ||
| Line 87: | Line 87: | ||
| 1 | | 1 | ||
|} | |} | ||
अन्य उदाहरण, | अन्य उदाहरण, अष्टफलक ग्राफ का टुट्टे बहुपद द्वारा दिया गया है | ||
:<math>\begin{align} | :<math>\begin{align} | ||
&12\,{y}^{2}{x}^{2}+11\,x+11\,y+40\,{y}^{3}+32\,{ | &12\,{y}^{2}{x}^{2}+11\,x+11\,y+40\,{y}^{3}+32\,{ | ||
| Line 99: | Line 99: | ||
==इतिहास== | ==इतिहास== | ||
विलोपन-संकुचन सूत्र में डब्ल्यू. टी. टुट्टे की रुचि ट्रिनिटी कॉलेज, कैम्ब्रिज में उनके स्नातक दिनों में | विलोपन-संकुचन सूत्र में डब्ल्यू. टी. टुट्टे की रुचि ट्रिनिटी कॉलेज, कैम्ब्रिज में उनके स्नातक दिनों में प्रारंभ हुई, जो मूल रूप से पूर्ण आयतबं और विस्तरित तरु (गणित) से प्रेरित थी। उन्होंने अधिकांशतः अपने शोध में सूत्र को क्रियान्वित किया और "आश्चर्यचकित हुए कि क्या ग्राफ़ के अन्य दिलचस्प ग्राफ़ इनवेरिएंट फलन , समरूपता के अनुसार अपरिवर्तनीय, समान रिकर्सन फ़ार्मुलों के साथ थे।"<ref name="Tutte-2004">{{harvnb|Tutte|2004}}.</ref> आर. एम. फोस्टर ने पहले ही देख लिया था कि [[रंगीन बहुपद]] ऐसा फलन है, और टुट्टे ने और अधिक खोजना प्रारंभ कर दिया। विलोपन-संकुचन पुनरावृत्ति को संतुष्ट करने वाले ग्राफ़ इनवेरिएंट के लिए उनकी मूल शब्दावली डब्ल्यू-फलन थी, और यदि घटकों पर गुणक है तब वी-फलन था। टुट्टे लिखते हैं, "अपने डब्ल्यू-फलन के साथ खेलते हुए मैंने दो-चर बहुपद प्राप्त किया, जिसमें से चर को शून्य के समान समुच्चय करके और संकेतबं को समायोजित करके या तब रंगीन बहुपद या प्रवाह-बहुपद प्राप्त किया जा सकता है।"<ref name="Tutte-2004"/>टुट्टे ने इस फलन को डाइक्रोमेट कहा, क्योंकि उन्होंने इसे दो चरों के लिए रंगीन बहुपद के सामान्यीकरण के रूप में देखा, किन्तु इसे सामान्यतः टुट्टे बहुपद के रूप में जाना जाता है। टुट्टे के शब्दों में, "यह [[हस्लर व्हिटनी]] के लिए अनुचित हो सकता है जो अनुरूप गुणांकों को दो चरों से जोड़ने की विचार किए बिना जानते थे और उनका उपयोग करते थे।" ("उल्लेखनीय भ्रम है"<ref>Welsh.</ref> टुट्टे द्वारा अलग-अलग पेपर में प्रस्तुत किए गए डाइक्रोमेट और डाइक्रोमैटिक बहुपद शब्दों के बारे में, और जो केवल थोड़ा अलग हैं।) मैट्रोइड्स के लिए टुट्टे बहुपद का सामान्यीकरण सबसे पहले [[हेनरी क्रैपो (गणितज्ञ)]] द्वारा प्रकाशित किया गया था, चूंकि यह टुट्टे की थीसिस में पहले से ही दिखाई देता है।<ref name="Farr 2007">{{harvnb|Farr|2007}}.</ref> | ||
बीजगणितीय ग्राफ सिद्धांत में काम से स्वतंत्र, पॉट्स ने 1952 में [[सांख्यिकीय यांत्रिकी]] में कुछ मॉडलों के विभाजन फलन (सांख्यिकीय यांत्रिकी) का अध्ययन प्रारंभ किया। फोर्टुइन और कस्टेलीन द्वारा काम<ref>{{harvnb|Fortuin|Kasteleyn|1972}}.</ref> यादृच्छिक क्लस्टर मॉडल पर, पॉट्स मॉडल का सामान्यीकरण, एकीकृत अभिव्यक्ति प्रदान करता है जो टुट्टे बहुपद से संबंध दिखाता है।<ref name="Farr 2007" /> | |||
==विशेषज्ञता== | === विशेषज्ञता === | ||
इस प्रकार विभिन्न बिंदुओं और रेखाओं पर <math>(x,y)</math>-समतल, टुट्टे बहुपद उन मात्राओं का मूल्यांकन करता है जिनका गणित और भौतिकी के विभिन्न क्षेत्रों में अपने आप में अध्ययन किया गया है। टुट्टे बहुपद की अपील का भाग उस एकीकृत ढांचे से आता है जो यह इन मात्राओं का विश्लेषण करने के लिए प्रदान करता है। | |||
===वर्णिक बहुपद=== | ===वर्णिक बहुपद=== | ||
{{Main|वर्णिक बहुपद}} | {{Main|वर्णिक बहुपद}} | ||
[[Image:Chromatic in the Tutte plane.jpg|thumb|right|टुट्टे तल में खींचा गया रंगीन बहुपद]] | [[Image:Chromatic in the Tutte plane.jpg|thumb|right|टुट्टे तल में खींचा गया रंगीन बहुपद]]जब <math>y=0</math> हो, टुट्टे बहुपद रंगीन बहुपद में पूर्णतः है, | ||
:<math>\chi_G(\lambda) = (-1)^{|V|-k(G)} \lambda^{k(G)} T_G(1-\lambda,0),</math> | :<math>\chi_G(\lambda) = (-1)^{|V|-k(G)} \lambda^{k(G)} T_G(1-\lambda,0),</math> | ||
यहाँ <math>k(G)</math> G के जुड़े घटकों की संख्या को दर्शाता है। | |||
पूर्णांक λ के लिए रंगीन बहुपद का मान <math>\chi_G(\lambda)</math> λ रंगों के | पूर्णांक λ के लिए रंगीन बहुपद का मान <math>\chi_G(\lambda)</math> λ रंगों के समुच्चय का उपयोग करके G के [[शीर्ष रंग]] की संख्या के समान है। यह स्पष्ट है कि <math>\chi_G(\lambda)</math> रंगों के समुच्चय पर निर्भर नहीं करता. जो कम स्पष्ट है वह यह है कि यह पूर्णांक गुणांक वाले बहुपद का λ पर मूल्यांकन है। इसे देखने के लिए, हम देखते हैं: | ||
# यदि G में n शीर्ष हैं और कोई किनारा नहीं है, | # यदि ''G'' में ''n'' शीर्ष हैं और कोई किनारा नहीं है, तब <math>\chi_G(\lambda) = \lambda^n</math>. | ||
# यदि G में लूप है ( शीर्ष को स्वयं से जोड़ने वाला किनारा), | # यदि ''G'' में लूप है ( शीर्ष को स्वयं से जोड़ने वाला किनारा), तब <math>\chi_G(\lambda) = 0</math>. | ||
# यदि | # यदि ''e'' किनारा है जो लूप नहीं है, तब | ||
::<math>\chi_G(\lambda) = \chi_{G - e}(\lambda) - \chi_{G/e}(\lambda).</math> | ::<math>\chi_G(\lambda) = \chi_{G - e}(\lambda) - \chi_{G/e}(\lambda).</math> | ||
उपरोक्त तीन स्थितियाँ हमें | उपरोक्त तीन स्थितियाँ हमें <math>\chi_G(\lambda)</math> गणना करने की अनुमति देती हैं, जहां हम धारा के इन्हें हटाने और संक्षेपण के क्रम को क्रियान्वित करते हैं; किन्तु वे कोई भी गारंटी नहीं देतीं हैं कि अलग गारंटी के क्रम हटाने और संक्षेपण ही मान तक पहुंचेंगे। गारंटी का कारण है कि <math>\chi_G(\lambda)</math> कुछ को गिनती करती है, पुनरावर्तन के अलग-अलग होने से अनुशासन से होता है। विशेष रूप से, इसमें एकत्रित होने से कुछ गिनती होती है, पुनरावर्तन से अलग होता है। | ||
:<math>T_G(2,0) = (-1)^{|V|} \chi_G(-1)</math> | :<math>T_G(2,0) = (-1)^{|V|} \chi_G(-1)</math> | ||
| Line 127: | Line 127: | ||
{{Main|जोन्स बहुपद}} | {{Main|जोन्स बहुपद}} | ||
[[Image:Jones in the Tutte plane.jpg|thumb|right|जोन्स बहुपद टुट्टे विमान में खींचा गया]]अतिपरवलय के साथ <math>xy=1</math>, समतलीय ग्राफ़ का टुट्टे बहुपद संबद्ध प्रत्यावर्ती गाँठ के जोन्स बहुपद में | [[Image:Jones in the Tutte plane.jpg|thumb|right|जोन्स बहुपद टुट्टे विमान में खींचा गया]]अतिपरवलय के साथ <math>xy=1</math>, समतलीय ग्राफ़ का टुट्टे बहुपद संबद्ध प्रत्यावर्ती गाँठ के जोन्स बहुपद में पूर्णतः होता है। | ||
===व्यक्तिगत अंक=== | ===व्यक्तिगत अंक=== | ||
| Line 135: | Line 135: | ||
====(1,1)==== | ====(1,1)==== | ||
<math>T_G(1,1)</math> फैले हुए जंगल की संख्या (बिना चक्र के किनारे उपसमुच्चय और | <math>T_G(1,1)</math> फैले हुए जंगल की संख्या (बिना चक्र के किनारे उपसमुच्चय और G के समान जुड़े हुए घटकों की संख्या) की गणना करें। यदि ग्राफ़ जुड़ा हुआ है, <math>T_G(1,1)</math> फैले हुए ट्री की संख्या गिनता है। | ||
====(1,2)==== | ====(1,2)==== | ||
<math>T_G(1,2)</math> फैले हुए सबग्राफ की संख्या की गणना करता है ( | <math>T_G(1,2)</math> फैले हुए सबग्राफ की संख्या की गणना करता है (G के समान कनेक्टेड घटकों के साथ किनारे उपसमुच्चय)। | ||
====(2,0)==== | ====(2,0)==== | ||
<math>T_G(2,0)</math> | <math>T_G(2,0)</math> G के चक्रीय प्रवणताों की संख्या की गणना करता है।<ref name="Welsh-1999">{{harvnb|Welsh|1999}}.</ref> | ||
'''(0,2)''' | |||
<math>T_G(0,2)</math> G के [[रॉबिन्स प्रमेय]] की संख्या की गणना करता है।<ref>{{harvnb|Las Vergnas|1980}}.</ref> | |||
<math>T_G(0,2)</math> | |||
'''(2,2)''' | |||
<math>T_G(2,2)</math> संख्या है <math>2^{|E|}</math> यहाँ <math>|E|</math> ग्राफ G के किनारों की संख्या है. | |||
<math>T_G(2,2)</math> संख्या है <math>2^{|E|}</math> | |||
====(0,−2)==== | ====(0,−2)==== | ||
यदि G 4-नियमित ग्राफ़ है, | यदि G 4-नियमित ग्राफ़ है, तब | ||
:<math>(-1)^{|V|+k(G)}T_G(0,-2)</math> यहां | :<math>(-1)^{|V|+k(G)}T_G(0,-2)</math> यहां G के [[यूलेरियन अभिविन्यास]] की संख्या गिना जाता है <math>k(G)</math> G से जुड़े घटकों की संख्या है.<ref name="Welsh-1999"/> | ||
'''(3,3)''' | |||
यदि G m×n [[ग्रिड ग्राफ]] है, तब <math>2 T_G(3,3)</math> [[ Tetromino |टेट्रोमिनो]] के साथ चौड़ाई 4 मीटर और ऊंचाई 4 N की आयत को टाइल करने के विधियों की संख्या गिना जाता है।<ref>{{harvnb|Korn|Pak|2004}}.</ref><ref>See {{harvnb|Korn|Pak|2003}} for combinatorial interpretations of many other points.</ref> | |||
यदि G m×n [[ग्रिड ग्राफ]] है, | |||
यदि G [[समतलीय ग्राफ]] है, तब <math>2 T_G(3,3)</math> G के औसत श्रेणी के ग्राफ में भारित यूलेरियन अभिविन्यासों के योग के समान है, जहां अभिविन्यास का वजन अभिविन्यास के काठी शीर्षों की संख्या से 2 है (अर्थात, घटना किनारों के साथ शीर्षों की संख्या चक्रीय रूप से अंदर, बाहर, बाहर क्रम में होती है) ).<ref>{{harvnb|Las Vergnas|1988}}.</ref> | |||
===पॉट्स और आइसिंग मॉडल=== | === पॉट्स और आइसिंग मॉडल === | ||
{{Main|आइसिंग मॉडल|पॉट्स मॉडल}} | {{Main|आइसिंग मॉडल|पॉट्स मॉडल}} | ||
[[Image:Potts and Ising in the Tutte plane.jpg|thumb|right|विभाजन इज़िंग मॉडल और टुट्टे विमान में तैयार किए गए 3- और 4-स्टेट पॉट्स मॉडल के लिए | [[Image:Potts and Ising in the Tutte plane.jpg|thumb|right|विभाजन इज़िंग मॉडल और टुट्टे विमान में तैयार किए गए 3- और 4-स्टेट पॉट्स मॉडल के लिए फलन करता है।]]xy-तल में अतिपरवलय को परिभाषित करें: | ||
:<math> H_2: \quad (x-1)(y-1)=2,</math> | :<math> H_2: \quad (x-1)(y-1)=2,</math> | ||
टुट्टे बहुपद विभाजन | टुट्टे बहुपद विभाजन फलन <math>Z(\cdot),</math> में पूर्णतः है, सांख्यिकीय भौतिकी में अध्ययन किए गए [[आइसिंग मॉडल]] विशेष रूप से, हाइपरबोला के साथ <math>H_2</math> दोनों समीकरण से संबंधित हैं:<ref>{{harvnb|Welsh|1993|p=62}}.</ref> | ||
:<math>Z(G) = 2\left(e^{-\alpha}\right)^{|E| - r(E)} \left(4 \sinh \alpha \right )^{r(E)} T_G \left (\coth \alpha, e^{2 \alpha} \right).</math> | :<math>Z(G) = 2\left(e^{-\alpha}\right)^{|E| - r(E)} \left(4 \sinh \alpha \right )^{r(E)} T_G \left (\coth \alpha, e^{2 \alpha} \right).</math> | ||
विशेष रूप से, | विशेष रूप से, | ||
| Line 177: | Line 177: | ||
:<math>H_q: \quad (x-1)(y-1)=q,</math> | :<math>H_q: \quad (x-1)(y-1)=q,</math> | ||
तब टुट्टे बहुपद | तब टुट्टे बहुपद q-स्थिति पॉट्स मॉडल के विभाजन फलन में पूर्णतः है। पॉट्स मॉडल के ढांचे <math>H_q</math>में विश्लेषण की गई विभिन्न भौतिक मात्राएं विशिष्ट भागों में परिवर्तित हो जाती हैं . | ||
{|class="wikitable" style="margin: 1em auto 1em auto" | {|class="wikitable" style="margin: 1em auto 1em auto" | ||
|+ पॉट्स मॉडल और टुट्टे विमान के | |||