क्रोमैटिक बहुपद: Difference between revisions

#k-colorings
#k-colorings
Input	Graph G with n vertices.
Output
Running time	In P for . for . Otherwise for some constant
Complexity	#P-hard unless
Approximability	No FPRAS for

Chromatic polynomial
Chromatic polynomial
Input	Graph G with n vertices.
Output	Coefficients of
Running time	for some constant
Complexity	#P-hard
Reduction from	#3SAT

Revision as of 13:30, 14 March 2023

3 शीर्षों पर सभी गैर-समरूपी रेखांकन और उनके रंगीन बहुपद, शीर्ष से दक्षिणावर्त। स्वतंत्र 3-सेट:

k 3

. एक किनारा और एक शीर्ष:

k 2 (k - 1)

. 3-पथ:

k (k - 1) 2

. 3-क्लिक:

k (k - 1)(k - 2)

.

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

इतिहास

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

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

परिभाषा

के रंगों का उपयोग करते हुए 3 शीर्षों के साथ वर्टेक्स ग्राफ के सभी उचित शीर्ष रंग

k=0,1,2,3

. प्रत्येक ग्राफ का रंगीन बहुपद उचित रंगों की संख्या के माध्यम से प्रक्षेपित होता है।

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

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

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

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)|}$ जी के चक्रीय अभिविन्यास की संख्या का गुना।^[4] डेरिवेटिव का मूल्यांकन 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}$ निर्दिष्ट, मनमाने ढंग से चुने गए शीर्ष पर अद्वितीय सिंक वाले एसाइक्लिक ओरिएंटेशन की संख्या का गुना।^[5]
प्रत्येक रंगीन बहुपद के गुणांक के पूर्ण मूल्य एक लघुगणक अवतल अनुक्रम | लॉग-अवतल अनुक्रम बनाते हैं।^[6]
$\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 तुल्याकारी हैं। सभी चक्र रेखांकन रंगीन अद्वितीय हैं।^[7]

रंगीन जड़ें

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

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

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

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

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

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}

.

वर्गीकरण

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

एल्गोरिदम

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

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

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

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

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

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