रंगीन बहुपद

3 शीर्षों पर सभी गैर-समरूपी रेखांकन और उनके रंगीन बहुपद, शीर्ष से दक्षिणावर्त। स्वतंत्र 3-सेट: k³. एक किनारा और एक शीर्ष: k²(k – 1). 3-पथ: k(k – 1)². 3-क्लिक: k(k – 1)(k – 2).

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

इतिहास

जॉर्ज डेविड बिरखॉफ़ ने 1912 में रंगीन बहुपद की शुरुआत की, इसे चार रंग प्रमेय को साबित करने के प्रयास में केवल प्लेनर ग्राफ ़ के लिए परिभाषित किया। अगर $P(G,k)$ k रंगों के साथ G के उचित रंगों की संख्या को दर्शाता है तो चार रंग प्रमेय को दिखाकर स्थापित किया जा सकता है $P(G,4)>0$ सभी समतल रेखांकन के लिए जी। इस तरह उन्होंने गणितीय विश्लेषण और सार बीजगणित के शक्तिशाली उपकरणों को बहुपदों की जड़ों का अध्ययन करने के लिए मिश्रित रंग की समस्या को लागू करने की आशा की।

हस्लर व्हिटनी ने 1932 में प्लेनर मामले से सामान्य ग्राफ़ के लिए बिरखॉफ़ के बहुपद को सामान्यीकृत किया। 1968 में, रोनाल्ड सी। रीड ने पूछा कि कौन से बहुपद कुछ ग्राफ़ के रंगीन बहुपद हैं, एक प्रश्न जो खुला रहता है, और वर्णक्रमीय समकक्ष ग्राफ़ की अवधारणा पेश की। आज, रंगीन बहुपद बीजगणितीय ग्राफ सिद्धांत की केंद्रीय वस्तुओं में से एक हैं।

परिभाषा

के लिए k रंगों का उपयोग करते हुए 3 शीर्षों के साथ वर्टेक्स ग्राफ़ के सभी उचित शीर्ष रंग $k=0,1,2,3$. प्रत्येक ग्राफ का रंगीन बहुपद उचित रंगों की संख्या के माध्यम से प्रक्षेपित होता है।

ग्राफ G के लिए, $P(G,k)$ इसके (उचित) वर्टेक्स कलरिंग|वर्टेक्स के-कलरिंग्स की संख्या की गणना करता है।

अन्य आमतौर पर इस्तेमाल किए जाने वाले नोटेशन में शामिल हैं $P_{G}(k)$, $\chi _{G}(k)$, या $\pi _{G}(k)$. एक अद्वितीय बहुपद है $P(G,x)$ जिसका मूल्यांकन किसी भी पूर्णांक k ≥ 0 पर किया जाता है $P(G,k)$; इसे G का रंगीन बहुपद कहते हैं।

उदाहरण के लिए, पथ ग्राफ़ को रंगने के लिए $P_{3}$ k रंगों के साथ 3 शीर्षों पर, कोई भी पहले शीर्ष के लिए k रंगों में से कोई भी चुन सकता है, इनमें से कोई भी $k-1$ दूसरे शीर्ष के लिए शेष रंग, और अंत में तीसरे शीर्ष के लिए, इनमें से कोई भी $k-1$ रंग जो दूसरे शीर्ष की पसंद से भिन्न हैं। इसलिए, $P(P_{3},k)=k\cdot (k-1)\cdot (k-1)$ के-रंगों की संख्या है $P_{3}$. एक चर x (आवश्यक रूप से पूर्णांक नहीं) के लिए, हमारे पास इस प्रकार है $P(P_{3},x)=x(x-1)^{2}=x^{3}-2x^{2}+x$. (रंग जो केवल रंगों की अनुमति या जी के ग्राफ ऑटोमोर्फिज्म द्वारा भिन्न होते हैं, उन्हें अभी भी भिन्न के रूप में गिना जाता है।)

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

Main article: Deletion–contraction formula

तथ्य यह है कि k-colorings की संख्या k में एक बहुपद है जो 'विलोपन-संकुचन सूत्र|विलोपन-संकुचन पुनरावृत्ति' या 'मौलिक न्यूनीकरण प्रमेय' नामक पुनरावृत्ति संबंध से अनुसरण करता है। यह किनारे के संकुचन पर आधारित है: शीर्षों की एक जोड़ी के लिए $u$ और $v$ लेखाचित्र $G/uv$ दो शीर्षों को मिलाकर और उनके बीच के किनारों को हटाकर प्राप्त किया जाता है। अगर $u$ और $v$ जी में आसन्न हैं, चलो $G-uv$ किनारे को हटाकर प्राप्त ग्राफ को निरूपित करें $uv$. फिर इन ग्राफों के के-रंगों की संख्या संतुष्ट होती है:

$P(G,k)=P(G-uv,k)-P(G/uv,k)$

समान रूप से, अगर $u$ और $v$ G और में आसन्न नहीं हैं $G+uv$ किनारे के साथ ग्राफ है $uv$ जोड़ा, फिर

$P(G,k)=P(G+uv,k)+P(G/uv,k)$

यह अवलोकन से अनुसरण करता है कि G का प्रत्येक k-रंग या तो अलग-अलग रंग देता है $u$ और $v$, या समान रंग। पहले मामले में यह एक (उचित) के-रंग देता है $G+uv$, जबकि दूसरे मामले में यह रंग देता है $G/uv$. इसके विपरीत, जी के प्रत्येक के-रंग को विशिष्ट रूप से के-रंग से प्राप्त किया जा सकता है $G+uv$ या $G/uv$ (अगर $u$ और $v$ G में आसन्न नहीं हैं)।

इसलिए रंगीन बहुपद को पुनरावर्ती रूप से परिभाषित किया जा सकता है

$P(G,x)=x^{n}$ n शीर्षों पर किनारे रहित ग्राफ़ के लिए, और

$P(G,x)=P(G-uv,x)-P(G/uv,x)$ किनारे वाले ग्राफ G के लिए $uv$ (मनमाने ढंग से चुना गया)।

चूंकि एजलेस ग्राफ के के-रंगों की संख्या वास्तव में है $k^{n}$, यह किनारों की संख्या पर प्रेरण द्वारा अनुसरण करता है जो सभी जी के लिए बहुपद है $P(G,x)$ प्रत्येक पूर्णांक बिंदु x = k पर k-रंगों की संख्या के साथ मेल खाता है। विशेष रूप से, रंगीन बहुपद अंक के माध्यम से अधिकतम n पर डिग्री का अद्वितीय प्रक्षेपित बहुपद है

$\left\{(0,P(G,0)),(1,P(G,1)),\ldots ,(n,P(G,n))\right\}.$

सभी की जिज्ञासा जिसके बारे में अन्य ग्राफ अपरिवर्तनीय ने इस तरह की पुनरावृत्ति को संतुष्ट किया, ने उन्हें रंगीन बहुपद, टुट्टे बहुपद के द्विभाजित सामान्यीकरण की खोज करने के लिए प्रेरित किया। $T_{G}(x,y)$.

उदाहरण

Chromatic polynomials for certain graphs

Triangle $K_{3}$	$x(x-1)(x-2)$
Complete graph $K_{n}$	$x(x-1)(x-2)\cdots (x-(n-1))$
Edgeless graph ${\overline {K}}_{n}$	$x^{n}$
Path graph $P_{n}$	$x(x-1)^{n-1}$
Any tree on n vertices	$x(x-1)^{n-1}$
Cycle $C_{n}$	$(x-1)^{n}+(-1)^{n}(x-1)$
Petersen graph	$x(x-1)(x-2)\left(x^{7}-12x^{6}+67x^{5}-230x^{4}+529x^{3}-814x^{2}+775x-352\right)$

गुण

n शीर्षों पर निश्चित G के लिए, रंगीन बहुपद $P(G,x)$ पूर्णांक गुणांकों के साथ बिल्कुल n डिग्री का एक मोनिक बहुपद बहुपद है।

रंगीन बहुपद में जी की रंगीनता के बारे में कम से कम उतनी ही जानकारी शामिल होती है जितनी रंगीन संख्या होती है। दरअसल, रंगीन संख्या सबसे छोटी सकारात्मक पूर्णांक है जो रंगीन बहुपद का शून्य नहीं है,

$\chi (G)=\min\{k\in \mathbb {N} :P(G,k)>0\}.$

बहुपद का मूल्यांकन किया गया $-1$, वह है $P(G,-1)$, पैदावार $(-1)^{|V(G)|}$ जी के चक्रीय अभिविन्यास की संख्या का गुना। डेरिवेटिव का मूल्यांकन 1 पर किया गया, $P'(G,1)$ रंगीन अपरिवर्तनीय के बराबर है $\theta (G)$ हस्ताक्षर करने तक।

यदि G में n शीर्ष और c जुड़ा हुआ घटक है (ग्राफ़ सिद्धांत) $G_{1},\ldots ,G_{c}$, तब

• के गुणांक $x^{0},\ldots ,x^{c-1}$ शून्य हैं।
• के गुणांक $x^{c},\ldots ,x^{n}$ सभी गैर-शून्य हैं और संकेतों में वैकल्पिक हैं।
• का गुणांक $x^{n}$ 1 है (बहुपद एकात्मक बहुपद है)।
• का गुणांक $x^{n-1}$ है $-|E(G)|$.

हम एक साधारण ग्राफ G पर किनारों की संख्या पर प्रेरण के माध्यम से इसे साबित करते हैं $n$ शिखर और $k$ किनारों। कब $k=0$, जी एक खाली ग्राफ है। इसलिए प्रति परिभाषा $P(G,x)=x^{n}$. तो का गुणांक $x^{n-1}$ है $0$, जिसका अर्थ है कि खाली ग्राफ के लिए कथन सत्य है। कब $k=1$, जैसा कि G में केवल एक किनारा है, $P(G,x)=x^{n}-x^{n-1}$. इस प्रकार का गुणांक $x^{n-1}$ है $-1=-|E(G)|$. तो कथन k = 1 के लिए है। मजबूत प्रेरण का उपयोग करके मान लें कि कथन सत्य है $k=0,1,2,\ldots ,(k-1)$. जी के पास है $k$ किनारों। विलोपन-संकुचन सूत्र द्वारा|संकुचन-विलोपन सिद्धांत, <ब्लॉककोट>$P(G,x)=P(G-e,x)-P(G/e,x)$, चलो $P(G-e,x)=x^{n}-a_{n-1}x^{n-1}+a_{n-2}x^{n-2}-\cdots$, और $P(G/e,x)=x^{n-1}-b_{n-2}x^{n-2}+b_{n-3}x^{n-3}-\cdots$.
इसलिए $P(G,x)=x^{n}-(a_{n-1}+1)x^{n-1}+\cdots$.
चूंकि $G-e$ केवल एक किनारे e को हटाकर G से प्राप्त किया जाता है, $a_{n-1}=k-1$, इसलिए $a_{n-1}+1=k$ और इस प्रकार कथन k के लिए सत्य है।

• का गुणांक $x^{1}$ है $(-1)^{n-1}$ निर्दिष्ट, मनमाने ढंग से चुने गए शीर्ष पर अद्वितीय सिंक वाले एसाइक्लिक ओरिएंटेशन की संख्या का गुना।
• प्रत्येक रंगीन बहुपद के गुणांकों के निरपेक्ष मान एक लघुगणकीय अवतल अनुक्रम | लॉग-अवतल अनुक्रम बनाते हैं।
• $\scriptstyle P(G,x)=P(G_{1},x)P(G_{2},x)\cdots P(G_{c},x)$

अंतिम संपत्ति को इस तथ्य से सामान्यीकृत किया जाता है कि यदि जी एक क्लिक-सम|के-क्लिक-योग है $G_{1}$ और $G_{2}$ (अर्थात, k सिरों पर एक क्लिक पर दोनों को चिपकाकर प्राप्त किया गया एक ग्राफ), फिर

$P(G,x)={\frac {P(G_{1},x)P(G_{2},x)}{x(x-1)\cdots (x-k+1)}}.$

n शीर्षों वाला एक ग्राफ G एक वृक्ष है यदि और केवल यदि

$P(G,x)=x(x-1)^{n-1}.$

रंगीन तुल्यता

The three graphs with a chromatic polynomial equal to $(x-2)(x-1)^{3}x$.

दो ग्राफ़ों को वर्णिक रूप से समतुल्य कहा जाता है यदि उनके पास एक ही रंगीन बहुपद है। आइसोमॉर्फिक ग्राफ़ में समान रंगीन बहुपद होते हैं, लेकिन गैर-आइसोमॉर्फिक ग्राफ़ क्रोमेटिक रूप से समतुल्य हो सकते हैं। उदाहरण के लिए, n शीर्षों पर स्थित सभी वृक्षों में एक ही वर्णिक बहुपद होता है।

विशेष रूप से, $(x-1)^{3}x$ दोनों पंजे (ग्राफ सिद्धांत) और 4 कोने पर पथ ग्राफ का रंगीन बहुपद है।

एक ग्राफ क्रोमैटिक रूप से अद्वितीय होता है यदि यह समरूपता तक, इसके रंगीन बहुपद द्वारा निर्धारित किया जाता है। दूसरे शब्दों में, जी तब क्रोमेटिक रूप से अद्वितीय है $P(G,x)=P(H,x)$ इसका अर्थ यह होगा कि G और H तुल्याकारी हैं। सभी चक्र रेखांकन रंगीन अद्वितीय हैं।

रंगीन जड़ें

एक रंगीन बहुपद के फ़ंक्शन (या शून्य) की जड़, जिसे "क्रोमैटिक रूट" कहा जाता है, एक मान x है जहां $P(G,x)=0$. रंगीन जड़ों का बहुत अच्छी तरह से अध्ययन किया गया है, वास्तव में, रंगीन बहुपद को परिभाषित करने के लिए बिरखॉफ की मूल प्रेरणा यह दिखाने के लिए थी कि प्लानर ग्राफ के लिए, $P(G,x)>0$ x ≥ 4 के लिए। इससे चार रंगों की प्रमेय स्थापित हो जाती।

कोई भी ग्राफ 0-रंग का नहीं हो सकता, इसलिए 0 हमेशा एक रंगीन मूल होता है। केवल किनारे रहित ग्राफ़ 1-रंग के हो सकते हैं, इसलिए 1 कम से कम एक किनारे वाले प्रत्येक ग्राफ़ का एक रंगीन मूल है। दूसरी ओर, इन दो बिंदुओं को छोड़कर, किसी भी ग्राफ में 32/27 से कम या उसके बराबर वास्तविक संख्या में एक रंगीन जड़ नहीं हो सकती है। टुट्टे का एक परिणाम सुनहरा अनुपात को जोड़ता है $\phi$ रंगीन जड़ों के अध्ययन के साथ, यह दर्शाता है कि रंगीन जड़ें बहुत करीब मौजूद हैं $\phi ^{2}$: अगर $G_{n}$ तब एक गोले का समतलीय त्रिकोण है

$P(G_{n},\phi ^{2})\leq \phi ^{5-n}.$

जबकि वास्तविक रेखा में बड़े हिस्से होते हैं जिनमें किसी भी ग्राफ के लिए कोई रंगीन जड़ें नहीं होती हैं, जटिल विमान में हर बिंदु मनमाने ढंग से एक रंगीन जड़ के करीब होता है, जिसमें ग्राफ के एक अनंत परिवार मौजूद होते हैं जिनकी रंगीन जड़ें जटिल विमान में घनी होती हैं। .

सभी रंगों का उपयोग कर रंग

n शीर्षों पर एक ग्राफ G के लिए, मान लीजिए $e_{k}$ रंगों का नाम बदलने तक ठीक k रंगों का उपयोग करके रंगों की संख्या को निरूपित करें (इसलिए रंगों को अनुमति देकर एक दूसरे से प्राप्त किए जा सकने वाले रंगों को एक के रूप में गिना जाता है; G के ग्राफ ऑटोमोर्फिज़्म द्वारा प्राप्त रंगों को अभी भी अलग से गिना जाता है)। दूसरे शब्दों में, $e_{k}$ k (गैर-खाली) स्वतंत्र सेट (ग्राफ़ सिद्धांत) में वर्टेक्स सेट के एक सेट के विभाजन की संख्या की गणना करता है। तब $k!\cdot e_{k}$ ठीक k रंगों (अलग-अलग रंगों के साथ) का उपयोग करके रंगों की संख्या की गणना करता है। एक पूर्णांक x के लिए, G के सभी x-रंगों को एक पूर्णांक k ≤ x चुनकर, उपलब्ध x में से उपयोग किए जाने वाले k रंगों को चुनकर, और ठीक उन्हीं k (अलग-अलग) रंगों का उपयोग करके रंग भरकर विशिष्ट रूप से प्राप्त किया जा सकता है। इसलिए:

$P(G,x)=\sum _{k=0}^{x}{\binom {x}{k}}k!\cdot e_{k}=\sum _{k=0}^{x}(x)_{k}\cdot e_{k}$,

कहाँ $(x)_{k}=x(x-1)(x-2)\cdots (x-k+1)$ गिरते फैक्टोरियल को दर्शाता है। इस प्रकार संख्याएँ $e_{k}$ बहुपद के गुणांक हैं $P(G,x)$ आधार में $1,(x)_{1},(x)_{2},(x)_{3},\ldots$ गिरते फैक्टोरियल का।

होने देना $a_{k}$ का k-th गुणांक हो $P(G,x)$ मानक आधार पर $1,x,x^{2},x^{3},\ldots$, वह है:

$P(G,x)=\sum _{k=0}^{n}a_{k}x^{k}$

स्टर्लिंग संख्याएँ एक स्टर्लिंग संख्या देती हैं#मानक आधार और घटते क्रमगुणों के आधार के बीच आधार गुणांकों के परिवर्तन के रूप में। यह संकेत करता है:

$a_{k}=\sum _{j=0}^{n}(-1)^{j-k}{\begin{bmatrix}j\\k\end{bmatrix}}e_{j}$ और $e_{k}=\sum _{j=0}^{n}{\begin{Bmatrix}j\\k\end{Bmatrix}}a_{j}$.

वर्गीकरण

क्रोमैटिक बहुपद एक होमोलॉजी सिद्धांत द्वारा वर्गीकरण है जो खोवानोव होमोलॉजी से निकटता से संबंधित है।

एल्गोरिदम

Chromatic polynomial
Input	Graph G with n vertices.
Output	Coefficients of $P(G,x)$
Running time	$O(2^{n}n^{r})$ for some constant $r$
Complexity	#P-hard
Reduction from	#3SAT

#k-colorings
Input	Graph G with n vertices.
Output	$P(G,k)$
Running time	In P for $k=0,1,2$. $O(1.6262^{n})$ for $k=3$. Otherwise $O(2^{n}n^{r})$ for some constant $r$
Complexity	#P-hard unless $k=0,1,2$
Approximability	No FPRAS for $k>2$

रंगीन बहुपद से जुड़ी कम्प्यूटेशनल समस्याओं में शामिल हैं

• रंगीन बहुपद ढूँढना $P(G,x)$ किसी दिए गए ग्राफ G का;
• मूल्यांकन $P(G,x)$ दिए गए G के लिए एक निश्चित x पर।

पहली समस्या अधिक सामान्य है क्योंकि यदि हम के गुणांकों को जानते हैं $P(G,x)$ हम बहुपद समय में किसी भी बिंदु पर इसका मूल्यांकन कर सकते हैं क्योंकि डिग्री n है। दूसरे प्रकार की समस्या की कठिनाई x के मान पर दृढ़ता से निर्भर करती है और कम्प्यूटेशनल जटिलता सिद्धांत में इसका गहन अध्ययन किया गया है। जब x एक प्राकृतिक संख्या है, तो इस समस्या को सामान्य रूप से किसी दिए गए ग्राफ़ के x-रंगों की संख्या की गणना के रूप में देखा जाता है। उदाहरण के लिए, इसमें 3-रंगों की संख्या गिनने की समस्या '#3-रंग' शामिल है, गिनती की जटिलता के अध्ययन में एक विहित समस्या, गिनती वर्ग Sharp-P|#P के लिए पूर्ण।

कुशल एल्गोरिदम

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

बहुपद समय एल्गोरिदम व्यापक वर्गों के रेखांकन के लिए रंगीन बहुपद की गणना के लिए जाना जाता है, जिसमें कॉर्डल ग्राफ भी शामिल हैं। और घिरे गुट-चौड़ाई के रेखांकन। बाद वाले वर्ग में बाउंडेड ट्री-चौड़ाई के कोग्राफ और ग्राफ़ शामिल हैं, जैसे कि आउटरप्लानर ग्राफ़।

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

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

$\phi ^{n+m}=\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n+m}\in O\left(1.62^{n+m}\right),$

n शीर्षों और m किनारों वाले ग्राफ़ पर। संख्या के एक बहुपद कारक के भीतर विश्लेषण में सुधार किया जा सकता है $t(G)$ इनपुट ग्राफ के फैले हुए पेड़ (गणित) का। अभ्यास में, कुछ पुनरावर्ती कॉलों से बचने के लिए शाखा और बाध्य रणनीतियों और समरूपता अस्वीकृति को नियोजित किया जाता है, चलने का समय वर्टेक्स जोड़ी को चुनने के लिए उपयोग किए जाने वाले हेयुरिस्टिक पर निर्भर करता है।

घन विधि

ग्राफ़ रंगों पर एक प्राकृतिक ज्यामितीय परिप्रेक्ष्य है, यह देखते हुए कि प्रत्येक शीर्ष पर प्राकृतिक संख्याओं के असाइनमेंट के रूप में, एक ग्राफ़ रंग पूर्णांक जाली में एक वेक्टर है। चूंकि दो शिखर हैं $i$ और $j$ एक ही रंग दिया जा रहा है के बराबर है $i$वें और $j$कलरिंग वेक्टर में वां कोऑर्डिनेट बराबर होने पर, प्रत्येक किनारे को फॉर्म के हाइपरप्लेन से जोड़ा जा सकता है $\{x\in R^{d}:x_{i}=x_{j}\}$. किसी दिए गए ग्राफ़ के लिए ऐसे हाइपरप्लेन का संग्रह हाइपरप्लेन की ग्राफिक व्यवस्था कहलाता है। ग्राफ के उचित रंग वे जाली बिंदु हैं जो वर्जित हाइपरप्लेन से बचते हैं। के एक सेट तक सीमित करना $k$ रंग, जाली बिंदु घन में समाहित हैं $[0,k]^{n}$. इस संदर्भ में रंगीन बहुपद जाली बिंदुओं की संख्या की गणना करता है $[0,k]$-क्यूब जो ग्राफिक व्यवस्था से बचते हैं।

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

किसी दिए गए ग्राफ के 3-रंगों की संख्या की गणना करने की समस्या तीव्र-पी|#पी-पूर्ण समस्या का एक विहित उदाहरण है, इसलिए रंगीन बहुपद के गुणांकों की गणना करने की समस्या #पी-हार्ड है। इसी प्रकार मूल्यांकन करना $P(G,3)$ दिए गए G के लिए #P-पूर्ण है। दूसरी ओर, के लिए $k=0,1,2$ गणना करना आसान है $P(G,k)$, इसलिए संबंधित समस्याएँ बहुपद-समय संगणनीय हैं। पूर्णांकों के लिए $k>3$ समस्या #पी-हार्ड है, जो केस के समान स्थापित है $k=3$. दरअसल, यह पता चला है $P(G,x)$ तीन "आसान बिंदुओं" को छोड़कर सभी x (ऋणात्मक पूर्णांक और यहां तक ​​कि सभी जटिल संख्याओं सहित) के लिए #P-हार्ड है। इस प्रकार, #पी-कठोरता के दृष्टिकोण से, रंगीन बहुपद की गणना की जटिलता को पूरी तरह से समझा जाता है।

विस्तार में

$P(G,x)=a_{1}x+a_{2}x^{2}+\cdots +a_{n}x^{n},$

गुणांक $a_{n}$ हमेशा 1 के बराबर होता है, और गुणांक के कई अन्य गुण ज्ञात होते हैं। यह सवाल उठाता है कि क्या कुछ गुणांकों की गणना करना आसान है। हालाँकि कंप्यूटिंग की कम्प्यूटेशनल समस्या a_rएक निश्चित आर ≥ 1 के लिए और एक दिया गया ग्राफ जी #पी-हार्ड है, द्विपक्षीय प्लानर ग्राफ के लिए भी। कंप्यूटिंग के लिए कोई सन्निकटन एल्गोरिदम नहीं $P(G,x)$ तीन आसान बिंदुओं को छोड़कर किसी भी x के लिए जाने जाते हैं। पूर्णांक बिंदुओं पर $k=3,4,\ldots$, किसी दिए गए ग्राफ़ को के-रंगीन किया जा सकता है या नहीं, यह तय करने की संबंधित निर्णय समस्या एनपी कठिन है। इस तरह की समस्याओं को किसी बाउंडेड-एरर प्रोबेबिलिस्टिक एल्गोरिथम द्वारा किसी भी गुणक कारक के लिए अनुमानित नहीं किया जा सकता है जब तक कि एनपी = आरपी, क्योंकि कोई भी गुणक सन्निकटन 0 और 1 के मानों को अलग कर देगा, प्रभावी रूप से बाउंड-एरर प्रोबेबिलिस्टिक पॉलीनोमियल टाइम में निर्णय संस्करण को हल करेगा। विशेष रूप से, इसी धारणा के तहत, यह FPRAS | पूर्ण बहुपद समय यादृच्छिक सन्निकटन योजना (FPRAS) की संभावना को बाहर करता है। अन्य बिंदुओं के लिए, अधिक जटिल तर्कों की आवश्यकता है, और प्रश्न सक्रिय शोध का फोकस है। As of 2008, यह ज्ञात है कि कंप्यूटिंग के लिए कोई FPRAS नहीं है $P(G,x)$ किसी भी x > 2 के लिए, जब तक कि एनपी (जटिलता वर्ग)  = आरपी (जटिलता वर्ग) न हो।

संदर्भ

• Biggs, N. (1993), Algebraic Graph Theory, Cambridge University Press, ISBN 978-0-521-45897-9
• Chao, C.-Y.; Whitehead, E. G. (1978), "On chromatic equivalence of graphs", Theory and Applications of Graphs, Lecture Notes in Mathematics, vol. 642, Springer, pp. 121–131, ISBN 978-3-540-08666-6
• Dong, F. M.; Koh, K. M.; Teo, K. L. (2005), Chromatic polynomials and chromaticity of graphs, World Scientific Publishing Company, ISBN 978-981-256-317-0
• Ellis-Monaghan, Joanna A.; Merino, Criel (2011), "Graph polynomials and their applications I: The Tutte polynomial", in Dehmer, Matthias (ed.), Structural Analysis of Complex Networks, arXiv:0803.3079, doi:10.1007/978-0-8176-4789-6_9, ISBN 978-0-8176-4789-6, S2CID 585250
• Giménez, O.; Hliněný, P.; Noy, M. (2005), "Computing the Tutte polynomial on graphs of bounded clique-width", Proc. 31st Int. Worksh. Graph-Theoretic Concepts in Computer Science (WG 2005), Lecture Notes in Computer Science, vol. 3787, Springer-Verlag, pp. 59–68, CiteSeerX 10.1.1.353.6385, doi:10.1007/11604686_6, ISBN 978-3-540-31000-6
• Goldberg, L.A.; Jerrum, M. (2008), "Inapproximability of the Tutte polynomial", Information and Computation, 206 (7): 908, arXiv:cs/0605140, doi:10.1016/j.ic.2008.04.003, S2CID 53304001
• Helme-Guizon, Laure; Rong, Yongwu (2005), "A categorification of the chromatic polynomial", Algebraic & Geometric Topology, 5 (4): 1365–1388, arXiv:math/0412264, doi:10.2140/agt.2005.5.1365, S2CID 1339633
• Huh, June (2012), "Milnor numbers of projective hypersurfaces and the chromatic polynomial of graphs", Journal of the American Mathematical Society, 25 (3): 907–927, arXiv:1008.4749, doi:10.1090/S0894-0347-2012-00731-0, MR 2904577, S2CID 13523955
• Jackson, B. (1993), "A Zero-Free Interval for Chromatic Polynomials of Graphs", Combinatorics, Probability and Computing, 2 (3): 325–336, doi:10.1017/S0963548300000705, S2CID 39978844
• 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, S2CID 121454726
• Linial, N. (1986), "Hard enumeration problems in geometry and combinatorics", SIAM J. Algebr. Discrete Methods, 7 (2): 331–335, doi:10.1137/0607036
• Makowsky, J. A.; Rotics, U.; Averbouch, I.; Godlin, B. (2006), "Computing graph polynomials on graphs of bounded clique-width", Proc. 32nd Int. Worksh. Graph-Theoretic Concepts in Computer Science (WG 2006), Lecture Notes in Computer Science, vol. 4271, Springer-Verlag, pp. 191–204, CiteSeerX 10.1.1.76.2320, doi:10.1007/11917496_18, ISBN 978-3-540-48381-6
• Naor, J.; Naor, M.; Schaffer, A. (1987), "Fast parallel algorithms for chordal graphs", Proc. 19th ACM Symp. Theory of Computing (STOC '87), pp. 355–364, doi:10.1145/28395.28433, ISBN 978-0897912211, S2CID 12132229.
• Oxley, J. G.; Welsh, D. J. A. (2002), "Chromatic, flow and reliability polynomials: The complexity of their coefficients.", Combinatorics, Probability and Computing, 11 (4): 403–426, doi:10.1017/S0963548302005175, S2CID 14918970
• Pemmaraju, S.; Skiena, S. (2003), Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica, Cambridge University Press, section 7.4.2, ISBN 978-0-521-80686-2
• Read, R. C. (1968), "An introduction to chromatic polynomials" (PDF), Journal of Combinatorial Theory, 4: 52–71, doi:10.1016/S0021-9800(68)80087-0
• Sekine, Kyoko; Imai, Hiroshi; Tani, Seiichiro (1995), "Computing the Tutte polynomial of a graph of moderate size", in Staples, John; Eades, Peter; Katoh, Naoki; Moffat, Alistair (eds.), Algorithms and Computation, 6th International Symposium, ISAAC '95, Cairns, Australia, December 4–6, 1995, Proceedings, Lecture Notes in Computer Science, vol. 1004, Springer, pp. 224–233, doi:10.1007/BFb0015427
• Sokal, A. D. (2004), "Chromatic Roots are Dense in the Whole Complex Plane", Combinatorics, Probability and Computing, 13 (2): 221–261, arXiv:cond-mat/0012369, doi:10.1017/S0963548303006023, S2CID 5549332
• Stanley, R. P. (1973), "Acyclic orientations of graphs" (PDF), Discrete Math., 5 (2): 171–178, doi:10.1016/0012-365X(73)90108-8
• Voloshin, Vitaly I. (2002), Coloring Mixed Hypergraphs: Theory, Algorithms and Applications., American Mathematical Society, ISBN 978-0-8218-2812-0
• Wilf, H. S. (1986), Algorithms and Complexity, Prentice–Hall, ISBN 978-0-13-021973-2

बाहरी संबंध

• Weisstein, Eric W., "Chromatic polynomial", MathWorld
• PlanetMath Chromatic polynomial
• Code for computing Tutte, Chromatic and Flow Polynomials by Gary Haggard, David J. Pearce and Gordon Royle: [1]