टुट्टे बहुपद

This article is about एक ग्राफ का पूर्ण बहुपद. For मैट्रोइड का पूर्ण बहुपद, see मैट्रोइड.

File:Tutte polynomial and chromatic polynomial of the Bull graph.jpg

बहुपद $x^{4}+x^{3}+x^{2}y$ बुल ग्राफ का टुट्टे बहुपद है। लाल रेखा विमान के साथ प्रतिच्छेदन को दर्शाती है $y=0$, रंगीन बहुपद के सामान्तर होती है।

टुट्टे बहुपद, जिसे द्विवर्णी या टुट्टे -व्हिटनी बहुपद भी कहा जाता है, ग्राफ बहुपद है। यह दो चरों वाला बहुपद है जो ग्राफ़ सिद्धांत में महत्वपूर्ण भूमिका निभाता है। यह प्रत्येक अदिष्‍ट आलेख $G$ के लिए परिभाषित किया गया है और ग्राफ के संबंधो के बारे में जानकारी प्रदान करता है। इसे $T_{G}$ द्वारा दर्शाया जाता है।

इस बहुपद का महत्व इस बात से समझ आता है कि यह $G$ के बारे में जानकारी उत्पन्न करता है, यद्यपि मूल रूप से बीजगणितीय ग्राफ सिद्धांत में ग्राफ़ रंग और कहीं-शून्य प्रवाह से संबंधित गणना समस्याओं के सामान्यीकरण के रूप में अध्ययन किया गया है। इसमें अन्य विज्ञानों से अनेक प्रसिद्ध अन्य विशेषज्ञताएं सम्मलित हैं जैसे कि गुणांक सिद्धांत से जोन्स बहुपद और विभाजन फलन (सांख्यिकीय यांत्रिकी) सांख्यिकीय भौतिकी से पॉट्स मॉडल होता है। यह सैद्धांतिक कंप्यूटर विज्ञान में अनेक केंद्रीय कम्प्यूटेशनल समस्याओं का स्रोत भी है।

टुट्टे बहुपद की अनेक परिभाषाएँ सामान्य मिलती है। यह सरल परिवर्तनों के अनुसार व्हिटनी के श्रेणी बहुपद, टुट्टे के स्वयं के द्विवर्णी बहुपद और फोर्टुइन-कास्टेलीन के यादृच्छिक क्लस्टर मॉडल के समान होता है। यह अनिवार्य रूप से मेट्रोइड के तत्काल सामान्यीकरण के साथ, किसी दिए गए आकार और जुड़े घटकों के किनारे समुच्चय की संख्या के लिए उत्पादन कारक फलन होता है। यह सबसे सामान्य ग्राफ अपरिवर्तनीय भी है जिसे विलोपन-संकुचन सूत्र पुनरावृत्ति द्वारा परिभाषित किया जा सकता है। ग्राफ सिद्धांत और मैट्रोइड सिद्धांत के बारे में अनेक पाठ्यपुस्तकें इसके लिए पूरे अध्याय समर्पित करती हैं।

परिभाषाएँ

अविरूपित ग्राफ (जिसे $G=(V,E)$ द्वारा दिया जा सकता है) टुट्टे बहुपद को इस प्रकार परिभाषित कर सकता है

$T_{G}(x,y)=\sum \nolimits _{A\subseteq E}(x-1)^{k(A)-k(E)}(y-1)^{k(A)+|A|-|V|},$

यहाँ $k(A)$ ग्राफ़ $(V,A)$ के संबंधित घटकों की संख्या को दर्शाता है। इस परिभाषा में स्पष्ट है कि $T_{G}$ विशेषतः परिभाषित होता है और यहाँ $x$ और $y$.बहुपद है।

इस परिभाषा को थोड़ा अलग संकेतन का उपयोग करके दिया जा सकता है :$r(A)=|V|-k(A)$ ग्राफ़ $(V,A)$ के श्रेणी को दर्शाने के लिए उपयोग किया है। जिसमें संबंधित समस्त संचय के सभी दुघर्ण नहीं हैं, तब व्हिटनी श्रेणी उत्पन्न करने वाला फलन निम्नलिखित रूप में परिभाषित होता है:

$R_{G}(u,v)=\sum \nolimits _{A\subseteq E}u^{r(E)-r(A)}v^{|A|-r(A)}.$

चरों के साधारण परिवर्तन के अनुसार दोनों फलन समतुल्य हैं:

$T_{G}(x,y)=R_{G}(x-1,y-1).$

टुट्टे का द्विवर्णीय बहुपद $Q_{G}$ और सरल परिवर्तन के परिणामस्वरूप होता है:

$T_{G}(x,y)=(x-1)^{-k(G)}Q_{G}(x-1,y-1).$

टुट्टे की मूल परिभाषा $T_{G}$ समान होती है किन्तु कम आसान वक्तव्य के अनुसार उदाहरण के रूप में दिया जा सकता है। संबंधित G के लिए हम इसे हिंदी में इस प्रकार से अनुवादित करते हैं:

$T_{G}(x,y)=\sum \nolimits _{i,j}t_{ij}x^{i}y^{j},$

यहाँ $t_{ij}$ आंतरिक गतिविधि के विस्तरित तरु(गणित) की संख्या को दर्शाता है जो आंतरिक गतिविधि $i$ और बाहरी गतिविधि $j$ की संख्या होती है।

तीसरी परिभाषा में हम विलयन-कंट्रैक्शन पुनरावृत्ति का उपयोग करती है। ग्राफ $G$ का किनारे का संकुचन $G/uv$ वह ग्राफ होता है जिसे शिखर $u$ और $v$ को एकीकृत करके प्राप्त किया जाता है और किनारा $uv$ को हटा दिया जाता है। हम $G-uv$ ग्राफ को वह ग्राफ कहते हैं जिसमें किनारा $uv$ को सिर्फ हटाया गया होता है। फिर ट्यूट बहुपद को पुनरावृत्ति संबंध से परिभाषित किया जाता है

$T_{G}=T_{G-e}+T_{G/e},$

यदि $e$ न तब लूप (ग्राफ सिद्धांत) है और न ही वेदी (ग्राफ सिद्धांत), इसके साथ:

$T_{G}(x,y)=x^{i}y^{j},$

यदि $G$ में $i$ ब्रिज और $j$ लूप होते हैं और कोई अन्य किनारा नहीं होता है। विशेष रूप से, $T_{G}=1$ यदि $G$ कोई किनारा नहीं है।

विधि-तांत्रिकी के भौतिकी में फॉर्चिन & कास्टेलेन (1972) द्वारा सांख्यिकीय यात्री मॉडल और समान विभाजन के उपयोग से और परिभाषा प्रदान करता है। विभाजन सम क्रम कोईरा सम

$Z_{G}(q,w)=\sum \nolimits _{F\subseteq E}q^{k(F)}w^{|F|}$

टुट्टे बहुपद के समान है, परिवर्तन के अनुसार

$T_{G}(x,y)=(x-1)^{-k(E)}(y-1)^{-|V|}\cdot Z_{G}{\Big (}(x-1)(y-1),\;y-1{\Big )}.$

गुण

टूटे बहुपद को संबंधित घटकों में विभाजित किया जा सकता है। यदि $G$ अलग-अलग ग्राफ $H$ और $H'$ के अविभाज्य संघ का संयोजन है, तब

$T_{G}=T_{H}\cdot T_{H'}$

यदि $G$ योजनात्मक है और $G^{*}$ तब इसके दोहरे ग्राफ को दर्शाता है

$T_{G}(x,y)=T_{G^{*}}(y,x)$

विशेष रूप से, योजनात्मक ग्राफ का रंगीन बहुपद उसके दोहरे का प्रवाह बहुपद होता है। टुट्टे ऐसे फलन को वी-फलन के रूप में संदर्भित करता है।

उदाहरण

समरूपी ग्राफ़ में ही टुट्टे बहुपद होता है, किन्तु इसका विपरीत सत्य नहीं है। उदाहरण के लिए, $m$ किनारे प्रत्येक ट्री का टुट्टे बहुपद $x^{m}$ होता है।

टुट्टे बहुपदों को अधिकांशतः गुणांकों को सूचीबद्ध करके सारणीबद्ध रूप में दिया जाता है $t_{ij}$ का $x^{i}y^{j}$ पंक्ति में $i$ और स्तंभ $j$. उदाहरण के लिए, पीटरसन ग्राफ का टुट्टे बहुपद,

${\begin{aligned}36x&+120x^{2}+180x^{3}+170x^{4}+114x^{5}+56x^{6}+21x^{7}+6x^{8}+x^{9}\\&+36y+84y^{2}+75y^{3}+35y^{4}+9y^{5}+y^{6}\\&+168xy+240x^{2}y+170x^{3}y+70x^{4}y+12x^{5}y\\&+171xy^{2}+105x^{2}y^{2}+30x^{3}y^{2}\\&+65xy^{3}+15x^{2}y^{3}\\&+10xy^{4},\end{aligned}}$

निम्नलिखित तालिका में दिया गया है।

0	36	84	75	35	9	1
36	168	171	65	10
120	240	105	15
180	170	30
170	70
114	12
56
21
6
1

अन्य उदाहरण, अष्टफलक ग्राफ का टुट्टे बहुपद द्वारा दिया गया है

${\begin{aligned}&12\,{y}^{2}{x}^{2}+11\,x+11\,y+40\,{y}^{3}+32\,{y}^{2}+46\,yx+24\,x{y}^{3}+52\,x{y}^{2}\\&+25\,{x}^{2}+29\,{y}^{4}+15\,{y}^{5}+5\,{y}^{6}+6\,{y}^{4}x\\&+39\,y{x}^{2}+20\,{x}^{3}+{y}^{7}+8\,y{x}^{3}+7\,{x}^{4}+{x}^{5}\end{aligned}}$

इतिहास

विलोपन-संकुचन सूत्र में डब्ल्यू. टी. टुट्टे की रुचि ट्रिनिटी कॉलेज, कैम्ब्रिज में उनके स्नातक दिनों में प्रारंभ हुई, जो मूल रूप से पूर्ण आयतबं और विस्तरित तरु (गणित) से प्रेरित थी। उन्होंने अधिकांशतः अपने शोध में सूत्र को क्रियान्वित किया और "आश्चर्यचकित हुए कि क्या ग्राफ़ के अन्य दिलचस्प ग्राफ़ इनवेरिएंट फलन , समरूपता के अनुसार अपरिवर्तनीय, समान रिकर्सन फ़ार्मुलों के साथ थे।" आर. एम. फोस्टर ने पहले ही देख लिया था कि रंगीन बहुपद ऐसा फलन है, और टुट्टे ने और अधिक खोजना प्रारंभ कर दिया। विलोपन-संकुचन पुनरावृत्ति को संतुष्ट करने वाले ग्राफ़ इनवेरिएंट के लिए उनकी मूल शब्दावली डब्ल्यू-फलन थी, और यदि घटकों पर गुणक है तब वी-फलन था। टुट्टे लिखते हैं, "अपने डब्ल्यू-फलन के साथ खेलते हुए मैंने दो-चर बहुपद प्राप्त किया, जिसमें से चर को शून्य के समान समुच्चय करके और संकेतबं को समायोजित करके या तब रंगीन बहुपद या प्रवाह-बहुपद प्राप्त किया जा सकता है।"टुट्टे ने इस फलन को डाइक्रोमेट कहा, क्योंकि उन्होंने इसे दो चरों के लिए रंगीन बहुपद के सामान्यीकरण के रूप में देखा, किन्तु इसे सामान्यतः टुट्टे बहुपद के रूप में जाना जाता है। टुट्टे के शब्दों में, "यह हस्लर व्हिटनी के लिए अनुचित हो सकता है जो अनुरूप गुणांकों को दो चरों से जोड़ने की विचार किए बिना जानते थे और उनका उपयोग करते थे।" ("उल्लेखनीय भ्रम है" टुट्टे द्वारा अलग-अलग पेपर में प्रस्तुत किए गए डाइक्रोमेट और डाइक्रोमैटिक बहुपद शब्दों के बारे में, और जो केवल थोड़ा अलग हैं।) मैट्रोइड्स के लिए टुट्टे बहुपद का सामान्यीकरण सबसे पहले हेनरी क्रैपो (गणितज्ञ) द्वारा प्रकाशित किया गया था, चूंकि यह टुट्टे की थीसिस में पहले से ही दिखाई देता है।

बीजगणितीय ग्राफ सिद्धांत में काम से स्वतंत्र, पॉट्स ने 1952 में सांख्यिकीय यांत्रिकी में कुछ मॉडलों के विभाजन फलन (सांख्यिकीय यांत्रिकी) का अध्ययन प्रारंभ किया। फोर्टुइन और कस्टेलीन द्वारा काम यादृच्छिक क्लस्टर मॉडल पर, पॉट्स मॉडल का सामान्यीकरण, एकीकृत अभिव्यक्ति प्रदान करता है जो टुट्टे बहुपद से संबंध दिखाता है।

विशेषज्ञता

इस प्रकार विभिन्न बिंदुओं और रेखाओं पर $(x,y)$-समतल, टुट्टे बहुपद उन मात्राओं का मूल्यांकन करता है जिनका गणित और भौतिकी के विभिन्न क्षेत्रों में अपने आप में अध्ययन किया गया है। टुट्टे बहुपद की अपील का भाग उस एकीकृत ढांचे से आता है जो यह इन मात्राओं का विश्लेषण करने के लिए प्रदान करता है।

वर्णिक बहुपद

Main article: वर्णिक बहुपद

File:Chromatic in the Tutte plane.jpg

टुट्टे तल में खींचा गया रंगीन बहुपद

जब $y=0$ हो, टुट्टे बहुपद रंगीन बहुपद में कुशल है,

$\chi _{G}(\lambda )=(-1)^{|V|-k(G)}\lambda ^{k(G)}T_{G}(1-\lambda ,0),$

यहाँ $k(G)$ G के जुड़े घटकों की संख्या को दर्शाता है।

पूर्णांक λ के लिए रंगीन बहुपद का मान $\chi _{G}(\lambda )$ λ रंगों के समुच्चय का उपयोग करके G के शीर्ष रंग की संख्या के समान है। यह स्पष्ट है कि $\chi _{G}(\lambda )$ रंगों के समुच्चय पर निर्भर नहीं करता. जो कम स्पष्ट है वह यह है कि यह पूर्णांक गुणांक वाले बहुपद का λ पर मूल्यांकन है। इसे देखने के लिए, हम देखते हैं:

1. यदि G में n शीर्ष हैं और कोई किनारा नहीं है, तब $\chi _{G}(\lambda )=\lambda ^{n}$.
2. यदि G में लूप है ( शीर्ष को स्वयं से जोड़ने वाला किनारा), तब $\chi _{G}(\lambda )=0$.
3. यदि e किनारा है जो लूप नहीं है, तब

$\chi _{G}(\lambda )=\chi _{G-e}(\lambda )-\chi _{G/e}(\lambda ).$

उपरोक्त तीन स्थितियाँ हमें $\chi _{G}(\lambda )$ गणना करने की अनुमति देती हैं, जहां हम धारा के इन्हें हटाने और संक्षेपण के क्रम को क्रियान्वित करते हैं; लेकिन वे कोई भी गारंटी नहीं देतीं हैं कि अलग गारंटी के क्रम हटाने और संक्षेपण ही मान तक पहुंचेंगे। गारंटी का कारण है कि $\chi _{G}(\lambda )$ कुछ को गिनती करती है, पुनरावर्तन के अलग-अलग होने से अनुशासन से। विशेष रूप से, इसमें एकत्रित होने से कुछ गिनती होती है, पुनरावर्तन से अलग।

$T_{G}(2,0)=(-1)^{|V|}\chi _{G}(-1)$

चक्रीय अभिविन्यासों की संख्या देता है।

जोन्स बहुपद

Main article: जोन्स बहुपद

File:Jones in the Tutte plane.jpg

जोन्स बहुपद टुट्टे विमान में खींचा गया

अतिपरवलय के साथ $xy=1$, समतलीय ग्राफ़ का टुट्टे बहुपद संबद्ध प्रत्यावर्ती गाँठ के जोन्स बहुपद में कुशल होता है।

व्यक्तिगत अंक

(2,1)

$T_{G}(2,1)$ वृक्षों की संख्या (ग्राफ सिद्धांत) की गणना करता है, अर्थात, चक्रीय किनारे उपसमुच्चय की संख्या।

(1,1)

$T_{G}(1,1)$ फैले हुए जंगल की संख्या (बिना चक्र के किनारे उपसमुच्चय और G के समान जुड़े हुए घटकों की संख्या) की गणना करें। यदि ग्राफ़ जुड़ा हुआ है, $T_{G}(1,1)$ फैले हुए ट्री की संख्या गिनता है।

(1,2)

$T_{G}(1,2)$ फैले हुए सबग्राफ की संख्या की गणना करता है (G के समान कनेक्टेड घटकों के साथ किनारे उपसमुच्चय)।

(2,0)

$T_{G}(2,0)$ G के चक्रीय प्रवणताों की संख्या की गणना करता है।

(0,2)

$T_{G}(0,2)$ G के रॉबिन्स प्रमेय की संख्या की गणना करता है।

(2,2)

$T_{G}(2,2)$ संख्या है $2^{|E|}$ यहाँ $|E|$ ग्राफ G के किनारों की संख्या है.

(0,−2)

यदि G 4-नियमित ग्राफ़ है, तब

$(-1)^{|V|+k(G)}T_{G}(0,-2)$ यहां G के यूलेरियन अभिविन्यास की संख्या गिना जाता है $k(G)$ G से जुड़े घटकों की संख्या है.

(3,3)

यदि G m×n ग्रिड ग्राफ है, तब $2T_{G}(3,3)$ टेट्रोमिनो के साथ चौड़ाई 4 मीटर और ऊंचाई 4 N की आयत को टाइल करने के विधियों की संख्या गिना जाता है।

यदि G समतलीय ग्राफ है, तब $2T_{G}(3,3)$ G के औसत श्रेणी के ग्राफ में भारित यूलेरियन अभिविन्यासों के योग के समान है, जहां अभिविन्यास का वजन अभिविन्यास के काठी शीर्षों की संख्या से 2 है (अर्थात, घटना किनारों के साथ शीर्षों की संख्या चक्रीय रूप से अंदर, बाहर, बाहर क्रम में होती है) ).

पॉट्स और आइसिंग मॉडल

Main articles: आइसिंग मॉडल and पॉट्स मॉडल

File:Potts and Ising in the Tutte plane.jpg

विभाजन इज़िंग मॉडल और टुट्टे विमान में तैयार किए गए 3- और 4-स्टेट पॉट्स मॉडल के लिए फलन करता है।

xy-तल में अतिपरवलय को परिभाषित करें:

$H_{2}:\quad (x-1)(y-1)=2,$

टुट्टे बहुपद विभाजन फलन $Z(\cdot ),$ में कुशल है, सांख्यिकीय भौतिकी में अध्ययन किए गए आइसिंग मॉडल विशेष रूप से, हाइपरबोला के साथ $H_{2}$ दोनों समीकरण से संबंधित हैं:

$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).$

विशेष रूप से,

$(\coth \alpha -1)\left(e^{2\alpha }-1\right)=2$

सभी जटिल α के लिए।

अधिक सामान्यतः, यदि किसी धनात्मक पूर्णांक q के लिए, हम अतिपरवलय को परिभाषित करते हैं:

$H_{q}:\quad (x-1)(y-1)=q,$

तब टुट्टे बहुपद q-स्थिति पॉट्स मॉडल के विभाजन फलन में कुशल है। पॉट्स मॉडल के ढांचे $H_{q}$में विश्लेषण की गई विभिन्न भौतिक मात्राएं विशिष्ट भागों में परिवर्तित हो जाती हैं .

पॉट्स मॉडल और टुट्टे विमान के मध्य पत्राचार

पॉट्स मॉडल	टुट्टे बहुपद
लौहचुंबकीय	$H_{q}$ की धनात्मक शाखा
प्रति-लौहचुंबकीय	$H_{q}$ with $y>0$ की ऋणात्मक शाखा
उच्च तापमान	$H_{q}$ to $y=1$ का स्पर्शोन्मुख
निम्न तापमान लौहचुंबकीय	$H_{q}$ की धनात्मक शाखा $x=1$ स्पर्शोन्मुख
शून्य तापमान प्रतिलौहचुंबकीय	ग्राफ़ q-रंग, i.e., $x=1-q,y=0$

प्रवाह बहुपद

Main article: कहीं नहीं-शून्य प्रवाह

File:Flow in the Tutte plane.jpg

टुट्टे तल में खींचा गया प्रवाह बहुपद

इस प्रकार टुट्टे बहुपद कॉम्बिनेटरिक्स में $x=0$ पर अध्ययन किए गए प्रवाह बहुपद में कुशल है। कनेक्टेड और अप्रत्यक्ष ग्राफ़ G और पूर्णांक k के लिए, कहीं-शून्य k-प्रवाह "प्रवाह" मानों का मूल्यांकन है $1,2,\dots ,k-1$ G के इच्छानुसार से अभिविन्यास के किनारों पर इस प्रकार कि प्रत्येक शीर्ष पर प्रवेश करने और छोड़ने वाला कुल प्रवाह सर्वांगसम मॉड्यूलो k है। प्रवाह बहुपद $C_{G}(k)$ कहीं नहीं-शून्य के-प्रवाह की संख्या को दर्शाता है। यह मान रंगीन बहुपद के साथ घनिष्ठ रूप से जुड़ा हुआ है, वास्तव में, यदि G समतलीय ग्राफ है, तब G का रंगीन बहुपद इसके दोहरे ग्राफ के प्रवाह बहुपद के समान है $G^{*}$ इस अर्थ में कि प्रमेय (टुट्टे बहुपद )है।

$C_{G}(k)=k^{-1}\chi _{G^{*}}(k).$

टुट्टे बहुपद का संबंध इस प्रकार दिया गया है:

$C_{G}(k)=(-1)^{|E|-|V|+k(G)}T_{G}(0,1-k).$

विश्वसनीयता बहुपद

Main article: कनेक्टिविटी (ग्राफ सिद्धांत)

File:Reliability in the Tutte plane.jpg

टुट्टे विमान में विश्वसनीयता बहुपद खींचा गया

इस प्रकार टुट्टे बहुपद नेटवर्क सिद्धांत में $x=1$ पर अध्ययन किए गए सभी-टर्मिनल विश्वसनीयता बहुपद में कुशल है। कनेक्टेड ग्राफ़ G के लिए प्रायिकता p के साथ प्रत्येक किनारे को हटा दें; यह यादृच्छिक किनारे विफलताओं के अधीन नेटवर्क मॉडल करता है। तब विश्वसनीयता बहुपद फलन है $R_{G}(p)$, पी में बहुपद, जो संभावना देता है कि किनारों के विफल होने के पश्चात् G में शीर्षों की प्रत्येक जोड़ी जुड़ी रहती है। टुट्टे बहुपद का संबंध किसके द्वारा दिया गया है?

$R_{G}(p)=(1-p)^{|V|-k(G)}p^{|E|-|V|+k(G)}T_{G}\left(1,{\tfrac {1}{p}}\right).$

द्विवर्णी बहुपद

टुट्टे ने रंगीन बहुपद, ग्राफ के द्विवर्णी बहुपद, के निकट 2-चर सामान्यीकरण को भी परिभाषित किया है।

यह

$Q_{G}(u,v)=\sum \nolimits _{A\subseteq E}u^{k(A)}v^{|A|-|V|+k(A)},$

यहाँ $k(A)$ फैले हुए सबग्राफ (वी,ए) के जुड़े घटक (ग्राफ सिद्धांत) की संख्या है। यह 'को श्रेणी-न्युलिटी बहुपद' से संबंधित है

$Q_{G}(u,v)=u^{k(G)}\,R_{G}(u,v).$

द्विवर्णीय बहुपद मैट्रोइड्स के लिए सामान्यीकरण नहीं करता है क्योंकि k(A) मैट्रोइड गुण नहीं है: ही मैट्रोइड के साथ अलग-अलग ग्राफ़ में अलग-अलग संख्या में जुड़े घटक हो सकते हैं।

संबंधित बहुपद

मार्टिन बहुपद

मार्टिन बहुपद $m_{\vec {G}}(x)$ उन्मुख 4-नियमित ग्राफ़ का ${\vec {G}}$ 1977 में पियरे मार्टिन द्वारा परिभाषित किया गया था। उन्होंने दिखाया कि यदि G समतल ग्राफ है और ${\vec {G}}_{m}$ तब इसका औसत श्रेणी का ग्राफ निर्देशित औसत ग्राफ है

$T_{G}(x,x)=m_{{\vec {G}}_{m}}(x).$

कलन (कलन)

विलोपन-संकुचन

Main article: विलोपन-संकुचन सूत्र

Error creating thumbnail:

विलोपन-संकुचन एल्गोरिथ्म हीरे के ग्राफ पर क्रियान्वित होता है। बाएं बच्चे में लाल किनारे हट जाते हैं और दाएं बच्चे में सिकुड़ जाते हैं। परिणामी बहुपद पत्तियों पर एकपदी का योग है, $x^{3}+2x^{2}+y^{2}+2xy+x+y$. पर आधारित Welsh & Merino (2000).

टुट्टे बहुपद के लिए विलोपन-संकुचन पुनरावृत्ति,

$T_{G}(x,y)=T_{G\setminus e}(x,y)+T_{G/e}(x,y),\qquad e{\text{ not a loop nor a bridge.}}$

किसी दिए गए ग्राफ़ के लिए गणना करने के लिए तुरंत पुनरावर्ती कलन उत्पन्न करता है: जब तक आप किनारा E पा सकते हैं जो लूप (ग्राफ़ सिद्धांत) या ब्रिज (ग्राफ़ सिद्धांत) नहीं है, उस किनारे को हटा दिए जाने पर टुट्टे बहुपद की पुनरावर्ती गणना करें, और जब वह किनारा संकुचन होता है। फिर ग्राफ़ के लिए समग्र टुट्टे बहुपद प्राप्त करने के लिए दो उप-परिणामों को साथ जोड़ दिया जाता है।

आधार स्थिति एकपदी है $x^{m}y^{n}$ यहाँ m पुलों की संख्या है, और n लूपों की संख्या है।

बहुपद कारक के भीतर, इस एल्गोरिथ्म के चलने का समय t शीर्ष n की संख्या और ग्राफ़ के किनारों m की संख्या के संदर्भ में व्यक्त किया जा सकता है,

$t(n+m)=t(n+m-1)+t(n+m-2),$

पुनरावृत्ति संबंध जो समाधान के साथ फाइबोनैचि संख्याओं के रूप में मापता है

$t(n+m)=\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n+m}=O\left(1.6180^{n+m}\right).$

विश्लेषण को संख्या के बहुपद कारक के भीतर बेहतर बनाया जा सकता है $\tau (G)$ इनपुट ग्राफ़ के विस्तरित तरु (गणित) का। विरल ग्राफ के लिए $m=O(n)$ यह चलने का समय है $\exp(O(n))$. डिग्री k के नियमित ग्राफ के लिए, फैले हुए ट्री की संख्या को सीमित किया जा सकता है

$\tau (G)=O\left(\nu _{k}^{n}n^{-1}\log n\right),$

यहाँ

$\nu _{k}={\frac {(k-1)^{k-1}}{(k^{2}-2k)^{{\frac {k}{2}}-1}}}.$

इसलिए विलोपन-संकुचन एल्गोरिथ्म इस सीमा के बहुपद कारक के भीतर चलता है।

उदाहरण के लिए:

$\nu _{5}\approx 4.4066.$

व्यावहारिक रूप से, ग्राफ समरूपता परीक्षण का उपयोग कुछ पुनरावर्ती कॉलों से बचने के लिए किया जाता है। यह दृष्टिकोण उन ग्राफ़ों के लिए अच्छा काम करता है जो काफी विरल हैं और अनेक समरूपताएँ प्रदर्शित करते हैं; कलन का प्रदर्शन किनारा E को चुनने के लिए उपयोग किए जाने वाले अनुमान पर निर्भर करता है।

गाऊसी उन्मूलन

कुछ प्रतिबंधित उदाहरणों में, टुट्टे बहुपद की गणना बहुपद समय में की जा सकती है, अंततः क्योंकि गाऊसी उन्मूलन कुशलतापूर्वक आव्यूह संचालन निर्धारक और पफैफ़ियन की गणना करता है। ये कलन स्वयं बीजगणितीय ग्राफ सिद्धांत और सांख्यिकीय यांत्रिकी से महत्वपूर्ण परिणाम हैं।

$T_{G}(1,1)$ संख्या के समान है $\tau (G)$ जुड़े हुए ग्राफ़ के विस्तरित तरु (गणित) का। यह है लाप्लासियन आव्यूह G के अधिकतम प्रमुख सबआव्यूह के निर्धारक के रूप में बहुपद समय में गणना योग्य, बीजगणितीय ग्राफ सिद्धांत में प्रारंभिक परिणाम जिसे किरचॉफ के आव्यूह-ट्री प्रमेय के रूप में जाना जाता है। इसी प्रकार, साइकिल स्थान का आयाम $T_{G}(-1,-1)$ गॉसियन विलोपन द्वारा बहुपद समय में गणना की जा सकती है।

समतलीय ग्राफ़ के लिए, आइसिंग मॉडल का विभाजन फलन , अर्थात, हाइपरबोला पर टुट्टे बहुपद $H_{2}$, को प्फॉफियन के रूप में व्यक्त किया जा सकता है और FKT एल्गोरिथ्म के माध्यम से कुशलतापूर्वक गणना की जा सकती है। यह विचार माइकल फिशर, पीटर कस्टेली द्वारा और हेरोल्ड नेविल वेज़िले टेम्परले द्वारा समतल जाली मॉडल (भौतिकी) के डोमिनोज़ टाइलिंग कवर की संख्या की गणना करने के लिए विकसित किया गया था।

मार्कोव श्रृंखला मोंटे कार्लो

मार्कोव श्रृंखला मोंटे कार्लो विधि का उपयोग करके, टुट्टे बहुपद को इच्छानुसार से धनात्मक शाखा $H_{2}$ के साथ अनुमानित किया जा सकता है, समकक्ष, लौहचुंबकीय आइसिंग मॉडल का विभाजन फलन है । यह आइसिंग मॉडल और ग्राफ में मिलान (ग्राफ सिद्धांत) की गणना की समस्या के मध्य घनिष्ठ संबंध का लाभ उठाता है। इस प्रतिष्ठित परिणाम के पीछे जेरम और सिंक्लेयर का विचार था मार्कोव श्रृंखला स्थापित करना है जिसके राज्य इनपुट ग्राफ़ से मेल खाते हैं। बदलावों को यादृच्छिक रूप से किनारों को चुनकर और तदनुसार मिलान को संशोधित करके परिभाषित किया जाता है। परिणामी मार्कोव श्रृंखला तेG से मिश्रित हो रही है और "पर्याप्त यादृच्छिक" मिलान की ओर ले जाती है, जिसका उपयोग यादृच्छिक नमूने का उपयोग करके विभाजन फलन को पुनर्प्राप्त करने के लिए किया जा सकता है। परिणामी कलन पूरी प्रकार से बहुपद-समय यादृच्छिक सन्निकटन योजना (एफपीआरएएस) है।

कम्प्यूटेशनल जटिलता

टुट्टे बहुपद के साथ अनेक कम्प्यूटेशनल समस्याएं जुड़ी हुई हैं। सबसे सीधा है

इनपुट

ग्राफ $G$;आउटपुट: के गुणांक $T_{G}$विशेष रूप से, आउटपुट मूल्यांकन की अनुमति देता है $T_{G}(-2,0)$ जो G के 3-रंगों की संख्या की गणना करने के समान है। यह पश्चात् वाला प्रश्न #पी-पूर्ण है, यहां तक ​​​​कि जब समतल ग्राफ़ के परिवार तक सीमित है, तब टुट्टे बहुपद के गुणांक की गणना करने की समस्या किसी दिए गए ग्राफ़ के लिए #पी-हार्ड है, यहां तक ​​कि समतल ग्राफ़ के लिए भी होती है।

टुट्टे नामक समस्याओं के परिवार पर अधिक ध्यान दिया गया है$(x,y)$ प्रत्येक जटिल जोड़ी के लिए परिभाषित $(x,y)$:

इनपुट: ग्राफ $G$

आउटपुट: का मान $T_{G}(x,y)$

इन समस्याओं की कठोरता निर्देशांक के साथ बदलती रहती है $(x,y)$.

सटीक गणना

File:Tractable points of the Tutte polynomial in the real plane.svg

टुट्टे विमान. हर बिंदु $(x,y)$ वास्तविक स्तर पर यह कम्प्यूटेशनल समस्या से मेल खाता है $T_{G}(x,y)$. किसी भी लाल बिंदु पर, समस्या बहुपद-समय गणना योग्य है; किसी भी नीले बिंदु पर, समस्या सामान्य रूप से #P-कठिन है, किन्तु समतलीय ग्राफ़ के लिए बहुपद-समय गणना योग्य है; और श्वेत क्षेत्रों में किसी भी बिंदु पर, समस्या द्विदलीय तलीय ग्राफ़ के लिए भी #पी-हार्ड है।

यदि x और y दोनों गैर-ऋणात्मक पूर्णांक हैं, तब समस्या $T_{G}(x,y)$ #पी से संबंधित है। सामान्य पूर्णांक युग्मों के लिए, टुट्टे बहुपद में ऋणात्मक पद होते हैं, जो समस्या को जटिलता वर्ग GapP में रखता है, घटाव के अनुसार #पी को विवृत करता है। तर्कसंगत निर्देशांक को समायोजित करने के लिए $(x,y)$, कोई #पी के तर्कसंगत एनालॉग को परिभाषित कर सकता है।

बिल्कुल कंप्यूटिंग की कम्प्यूटेशनल जटिलता $T_{G}(x,y)$ किसी के लिए दो वर्गों में से में आता है $x,y\in \mathbb {C}$. जब तक समस्या #पी-कठिन नहीं है $(x,y)$ अतिपरवलय पर स्थित है $H_{1}$ या बिंदुओं में से है

$\left\{(1,1),(-1,-1),(0,-1),(-1,0),(i,-i),(-i,i),\left(j,j^{2}\right),\left(j^{2},j\right)\right\},\qquad j=e^{\frac {2\pi i}{3}}.$

किन स्थितियों में यह बहुपद समय में गणना योग्य है। यदि समस्या समतलीय ग्राफ़ के वर्ग तक ही सीमित है, तब हाइपरबोला पर बिंदु $H_{2}$ बहुपद-समय भी गणना योग्य बनें। अन्य सभी बिंदु #पी-कठोर बने रहते हैं, यहां तक ​​कि द्विदलीय समतलीय ग्राफ़ के लिए भी। समतलर ग्राफ़ के लिए द्विभाजन पर अपने पेपर में, वर्टिगन का प्रमाणित है (अपने निष्कर्ष में) कि वही परिणाम तब होता है जब अधिकतम तीन शीर्ष डिग्री वाले ग्राफ़ तक सीमित हो, बिंदु को छोड़कर $T_{G}(0,-2)$, जो कहीं नहीं गिना जाता-शून्य Z₃-प्रवाह और बहुपद समय में गणना योग्य है।

इन परिणामों में अनेक उल्लेखनीय विशेष स्थितियों में सम्मलित हैं। उदाहरण के लिए, आइसिंग मॉडल के विभाजन फलन की गणना करने की समस्या सामान्य रूप से #पी-कठिन है, भले ही ऑनसेगर और फिशर के प्रसिद्ध कलन इसे समतलर लैटिस के लिए हल करते हैं। साथ ही, जोन्स बहुपद की गणना करना #P-कठिन है। अंत में, समतलीय ग्राफ़ के चार-रंगों की संख्या की गणना करना #पी-पूर्ण है, भले ही चार रंग प्रमेय द्वारा निर्णय समस्या तुच्छ है। इसके विपरीत, यह देखना आसान है कि समतलीय ग्राफ़ के लिए तीन-रंगों की संख्या की गणना #पी-पूर्ण है क्योंकि निर्णय समस्या को पारसी कटौती के माध्यम से एनपी-पूर्ण माना जाता है।

अनुमान

वह प्रश्न जो अच्छे सन्निकटन कलन को स्वीकार करता है, का बहुत अच्छी प्रकार से अध्ययन किया गया है। उन बिंदुओं के अतिरिक्त जिनकी गणना बहुपद समय में सटीक रूप से की जा सकती है, एकमात्र सन्निकटन एल्गोरिथ्म के लिए जाना जाता है $T_{G}(x,y)$ जेरम और सिंक्लेयर का एफपीआरएएस है, जो "आइज़िंग" हाइपरबोला पर बिंदुओं के लिए काम करता है $H_{2}$ y > 0 के लिए। यदि इनपुट ग्राफ़ डिग्री के साथ सघन उदाहरणों तक सीमित हैं $\Omega (n)$, यदि x ≥ 1, y ≥ 1 है तब FPRAS है।

यद्यपि स्थिति सटीक गणना के लिए उतनी अच्छी प्रकार से समझी नहीं गई है, विमान के बड़े क्षेत्रों का अनुमान लगाना कठिन माना जाता है।

यह भी देखें

• बोल्लोबास-रिओर्डन बहुपद
• टुट्टे-ग्रोथेंडिक इनवेरिएंट टुट्टे बहुपद का कोई मूल्यांकन है

संदर्भ

• Alon, N.; Frieze, A.; Welsh, D. J. A. (1995), "Polynomial time randomized approximation schemes for Tutte-Gröthendieck invariants: The dense case", Random Structures and Algorithms, 6 (4): 459–478, doi:10.1002/rsa.3240060409.
• Annan, J. D. (1994), "A Randomised Approximation Algorithm for Counting the Number of Forests in Dense Graphs", Combinatorics, Probability and Computing, 3 (3): 273–283, doi:10.1017/S0963548300001188.
• Biggs, Norman (1993), Algebraic Graph Theory (2nd ed.), Cambridge University Press, ISBN 0-521-45897-8.
• Björklund, Andreas; Husfeldt, Thore; Kaski, Petteri; Koivisto, Mikko (2008), "Computing the Tutte polynomial in vertex-exponential time", Proc. of the 47th annual IEEE Symposium on Foundations of Computer Science (FOCS 2008), pp. 677–686, arXiv:0711.2585, doi:10.1109/FOCS.2008.40, ISBN 978-0-7695-3436-7.
• Bollobás, Béla (1998), Modern Graph Theory, Springer, ISBN 978-0-387-98491-9.
• Chung, Fan; Yau, S.-T. (1999), "Coverings, heat kernels and spanning trees", Electronic Journal of Combinatorics, 6: R12, MR 1667452.
• Crapo, Henry H. (1969), "The Tutte polynomial", Aequationes Mathematicae, 3 (3): 211–229, doi:10.1007/bf01817442.
• Farr, Graham E. (2007), "Tutte-Whitney polynomials: some history and generalizations", in Grimmett, Geoffrey; McDiarmid, Colin (eds.), Combinatorics, complexity, and chance. A tribute to Dominic Welsh, Oxford Lecture Series in Mathematics and its Applications, vol. 34, Oxford University Press, pp. 28–52, ISBN 978-0-19-857127-8, Zbl 1124.05020.
• Fortuin, Cees M.; Kasteleyn, Pieter W. (1972), "On the random-cluster model: I. Introduction and relation to other models", Physica, Elsevier, 57 (4): 536–564, Bibcode:1972Phy....57..536F, doi:10.1016/0031-8914(72)90045-6, ISSN 0031-8914.
• Godsil, Chris; Royle, Gordon (2004), Algebraic Graph Theory, Springer, ISBN 978-0-387-95220-8.
• Goldberg, Leslie Ann; Jerrum, Mark (2008), "Inapproximability of the Tutte polynomial", Information and Computation, 206 (7): 908–929, arXiv:cs/0605140, doi:10.1016/j.ic.2008.04.003.
• Haggard, Gary; Pearce, David J.; Royle, Gordon (2010), "Computing Tutte polynomials", ACM Transactions on Mathematical Software, 37 (3): Art. 24, 17, doi:10.1145/1824801.1824802, MR 2738228.
• Jaeger, F.; Vertigan, D. L.; Welsh, D. J. A. (1990), "On the computational complexity of the Jones and Tutte polynomials", Mathematical Proceedings of the Cambridge Philosophical Society, 108 (1): 35–53, Bibcode:1990MPCPS.108...35J, doi:10.1017/S0305004100068936.
• Jerrum, Mark; Sinclair, Alistair (1993), "Polynomial-time approximation algorithms for the Ising model" (PDF), SIAM Journal on Computing, 22 (5): 1087–1116, doi:10.1137/0222066.
• Korn, Michael; Pak, Igor (2003), Combinatorial evaluations of the Tutte polynomial (PDF) (preprint).
• Korn, Michael; Pak, Igor (2004), "Tilings of rectangles with T-tetrominoes", Theoretical Computer Science, 319 (1–3): 3–27, doi:10.1016/j.tcs.2004.02.023.
• Las Vergnas, Michel (1980), "Convexity in oriented matroids", Journal of Combinatorial Theory, Series B, 29 (2): 231–243, doi:10.1016/0095-8956(80)90082-9, ISSN 0095-8956, MR 0586435.
• Las Vergnas, Michel (1988), "On the evaluation at (3, 3) of the Tutte polynomial of a graph", Journal of Combinatorial Theory, Series B, 45 (3): 367–372, doi:10.1016/0095-8956(88)90079-2, ISSN 0095-8956.
• Martin, Pierre (1977), Enumérations Eulériennes dans les multigraphes et invariants de Tutte-Grothendieck [Eulerian Enumerations in multigraphs and Tutte-Grothendieck invariants] (Ph.D. thesis) (in French), Joseph Fourier University{{citation}}: CS1 maint: unrecognized language (link).
• Pearce, David J.; Haggard, Gary; Royle, Gordon (2010), "Edge-selection heuristics for computing Tutte polynomials" (PDF), Chicago Journal of Theoretical Computer Science: Article 6, 14, MR 2659710.
• Sekine, Kyoko; Imai, Hiroshi; Tani, Seiichiro (1995), "Computing the Tutte polynomial of a graph of moderate size", Algorithms and computations (Cairns, 1995), Lecture Notes in Computer Science, vol. 1004, Springer, pp. 224–233, doi:10.1007/BFb0015427, MR 1400247.
• Sokal, Alan D. (2005), "The multivariate Tutte polynomial (alias Potts model) for graphs and matroids", in Webb, Bridget S. (ed.), Surveys in Combinatorics, London Mathematical Society Lecture Note Series, vol. 327, Cambridge University Press, pp. 173–226, arXiv:math/0503607, doi:10.1017/CBO9780511734885.009.
• Tutte, W. T. (2001), Graph Theory, Cambridge University Press, ISBN 978-0521794893.
• Tutte, W. T. (2004), "Graph-polynomials", Advances in Applied Mathematics, 32 (1–2): 5–9, doi:10.1016/S0196-8858(03)00041-1.
• Vertigan, D. L.; Welsh, D. J. A. (1992), "The Computational Complexity of the Tutte Plane: the Bipartite Case", Combinatorics, Probability and Computing, 1 (2): 181–187, doi:10.1017/S0963548300000195.
• Vertigan, Dirk (2005), "The Computational Complexity of Tutte Invariants for Planar Graphs", SIAM Journal on Computing, 35 (3): 690–712, doi:10.1137/S0097539704446797.
• Welsh, D. J. A. (1976), Matroid Theory, Academic Press, ISBN 012744050X.
• Welsh, Dominic (1993), Complexity: Knots, Colourings and Counting, London Mathematical Society Lecture Note Series, Cambridge University Press, ISBN 978-0521457408.
• Welsh, Dominic (1999), "The Tutte polynomial", Random Structures & Algorithms, Wiley, 15 (3–4): 210–228, doi:10.1002/(SICI)1098-2418(199910/12)15:3/4<210::AID-RSA2>3.0.CO;2-R, ISSN 1042-9832.
• Welsh, D. J. A.; Merino, C. (2000), "The Potts model and the Tutte polynomial", Journal of Mathematical Physics, 41 (3): 1127–1152, Bibcode:2000JMP....41.1127W, doi:10.1063/1.533181.
• Wilf, Herbert S. (1986), Algorithms and complexity (PDF), Prentice Hall, ISBN 0-13-021973-8, MR 0897317.

बाहरी संबंध

• "Tutte polynomial", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• Weisstein, Eric W. "Tutte polynomial". MathWorld.
• PlanetMath Chromatic polynomial
• Steven R. Pagano: Matroids and Signed Graphs
• Sandra Kingan: Matroid theory. Many links.
• Code for computing Tutte, Chromatic and Flow Polynomials by Gary Haggard, David J. Pearce and Gordon Royle: [1]