टुट्टे बहुपद

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

बहुपद $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},$