टुट्टे बहुपद

This article is about the Tutte polynomial of a graph. For the Tutte polynomial of a matroid, see Matroid.

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

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

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

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

परिभाषाएँ

<ब्लॉककोट>परिभाषा. एक अप्रत्यक्ष ग्राफ़ के लिए $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/uv$ ग्राफ का $G$ शीर्षों को मिलाने से प्राप्त ग्राफ़ है $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$ कोई किनारा नहीं है.

सांख्यिकीय यांत्रिकी के कारण यादृच्छिक क्लस्टर मॉडल Fortuin & Kasteleyn (1972) एक और समकक्ष परिभाषा प्रदान करता है। बँटवारा योग

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

के बराबर है $T_{G}$ परिवर्तन के तहत

$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: Chromatic polynomial

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

पर $y=0$, टुटे बहुपद रंगीन बहुपद में माहिर है,

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

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

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

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

$\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: Jones polynomial

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

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

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

(2,1)

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

(1,1)

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

(1,2)

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

(2,0)

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

(0,2)

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

(2,2)

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

(0,−2)

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

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

(3,3)

यदि G m×n ग्रिड ग्राफ़ है, तो $2T_{G}(3,3)$ Tetromino | टी-टेट्रोमिनो के साथ चौड़ाई 4 मीटर और ऊंचाई 4 एन की एक आयत को टाइल करने के तरीकों की संख्या गिना जाता है। यदि G एक समतलीय ग्राफ है, तो $2T_{G}(3,3)$ जी के एक औसत दर्जे के ग्राफ में भारित यूलेरियन अभिविन्यासों के योग के बराबर है, जहां एक अभिविन्यास का वजन अभिविन्यास के काठी शीर्षों की संख्या से 2 है (अर्थात, घटना किनारों के साथ शीर्षों की संख्या चक्रीय रूप से अंदर, बाहर, बाहर क्रम में होती है) ).

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

Main articles: Ising model and Potts model

विभाजन इज़िंग मॉडल और टुट्टे विमान में तैयार किए गए 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,$

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

Correspondences between the Potts model and the Tutte plane

Potts model	Tutte polynomial
Ferromagnetic	Positive branch of $H_{q}$
Antiferromagnetic	Negative branch of $H_{q}$ with $y>0$
High temperature	Asymptote of $H_{q}$ to $y=1$
Low temperature ferromagnetic	Positive branch of $H_{q}$ asymptotic to $x=1$
Zero temperature antiferromagnetic	Graph q-colouring, i.e., $x=1-q,y=0$

प्रवाह बहुपद

Main article: Nowhere-zero flow

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

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

<ब्लॉककोट>प्रमेय (टुट्टे)।

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

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

$C_{G}(k)=(-1)^{|E|-|V|+k(G)}T_{G}(0,1-k).$</ब्लॉककोट>

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

Main article: Connectivity (graph theory)

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

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

$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: Deletion–contraction formula

विलोपन-संकुचन एल्गोरिथ्म हीरे के ग्राफ पर लागू होता है। बाएं बच्चे में लाल किनारे हट जाते हैं और दाएं बच्चे में सिकुड़ जाते हैं। परिणामी बहुपद पत्तियों पर एकपदी का योग है, $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.}}$

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

आधार मामला एकपदी है $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.$

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

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

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

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

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

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

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

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

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

इनपुट

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

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

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

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

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

सटीक गणना

टुट्टे विमान. हर बिंदु $(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]