बुल ग्राफ: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| Line 15: | Line 15: | ||
}} | }} | ||
ग्राफ़ सिद्धांत के | ग्राफ़ सिद्धांत के गणितीय क्षेत्र में, बुल ग्राफ़ 5 शीर्षों और 5 किनारों वाला [[समतलीय ग्राफ|समतलीय]] प्रकार का [[अप्रत्यक्ष ग्राफ]] है, जिसे दो असंयुक्त लटकन किनारों वाले त्रिकोण के रूप में दर्शाया जाता है।<ref>{{MathWorld|urlname=BullGraph|title=Bull Graph}}</ref> | ||
इस ग्राफ़ में वर्णिक संख्या 3, वर्णिक सूचकांक 3, त्रिज्या 2, व्यास 3 और परिधि (ग्राफ सिद्धांत) 3 है। यह [[स्व-पूरक ग्राफ]], [[ब्लॉक ग्राफ]], [[विभाजित ग्राफ]], [[अंतराल ग्राफ]], पंजा-मुक्त ग्राफ भी है। बुल ग्राफ़ 1-[[ के-वर्टेक्स-कनेक्टेड ग्राफ़ | के-वर्टेक्स-कनेक्टेड ग्राफ़]] और 1-[[ के-एज-कनेक्टेड ग्राफ़ | के-एज-कनेक्टेड ग्राफ़]] भी है। | |||
== बुल-मुक्त ग्राफ़ == | == बुल-मुक्त ग्राफ़ == | ||
ग्राफ | यदि ग्राफ में [[प्रेरित सबग्राफ]] के रूप में कोई बुल नहीं है तो ग्राफ बुल-मुक्त होता है। [[त्रिकोण-मुक्त ग्राफ़]], बुल-मुक्त प्रकार का ग्राफ़ हैं क्योंकि इस ग्राफ के प्रत्येक बुल में त्रिकोण होता है। सामान्य ग्राफ़ के लिए इसके प्रमाण को सिद्ध करने से बहुत पहले, '''मजबूत उत्तम ग्राफ़ प्रमेय''' को बैल-मुक्त ग्राफ़ के लिए सिद्ध किया गया था,<ref>{{citation|last1=Chvátal|first1=V.|author1-link=Václav Chvátal|last2=Sbihi|first2=N.|title=Bull-free Berge graphs are perfect|journal=[[Graphs and Combinatorics]]|volume=3|year=1987|pages=127–139|issue=1|doi=10.1007/BF01788536|s2cid=44570627}}.</ref> और बुल- मुक्त उत्तम ग्राफ़ के लिए बहुपद समय पहचान कलन विधि भी ज्ञात है।<ref>{{citation|last1=Reed|first1=B.|author1-link=Bruce Reed (mathematician)|last2=Sbihi|first2=N.|title=Recognizing bull-free perfect graphs|journal=[[Graphs and Combinatorics]]|volume=11|year=1995|pages=171–178|issue=2|doi=10.1007/BF01929485|s2cid=206808701}}.</ref> | ||
[[मारिया चुडनोव्स्की]] और [[शमूएल सफरा]] ने बुल- | [[मारिया चुडनोव्स्की]] और [[शमूएल सफरा]] ने बुल- मुक्त ग्राफ़ का अधिक सामान्यतः अध्ययन किया है, जिससे पता चलता है कि ऐसे किसी भी ग्राफ़ में या तो बड़ा समूह (ग्राफ़ सिद्धांत) या बड़ा [[स्वतंत्र सेट (ग्राफ़ सिद्धांत)]] होना चाहिए (अर्थात, एर्दो-हजनल अनुमान बुल ग्राफ के लिए मान्य है),<ref>{{citation|last1=Chudnovsky|first1=M.|author1-link=Maria Chudnovsky|last2=Safra|first2=S.|title=The Erdős–Hajnal conjecture for bull-free graphs|journal=[[Journal of Combinatorial Theory]]|series=Series B|volume=98|issue=6|year=2008|pages=1301–1310|doi=10.1016/j.jctb.2008.02.005|doi-access=free}}.</ref> और इन ग्राफ़ों के लिए सामान्य संरचना सिद्धांत विकसित करना चाहिए।<ref>{{citation|last=Chudnovsky|first=M.|authorlink=Maria Chudnovsky|year=2008|title=The structure of bull-free graphs. I. Three-edge paths with centers and anticenters|url=http://www.columbia.edu/~mc2775/bulls1.pdf}}.</ref><ref>{{citation|last=Chudnovsky|first=M.|authorlink=Maria Chudnovsky|year=2008|title=The structure of bull-free graphs. II. Elementary trigraphs|url=http://www.columbia.edu/~mc2775/bulls2.pdf}}.</ref><ref>{{citation|last=Chudnovsky|first=M.|authorlink=Maria Chudnovsky|year=2008|title=The structure of bull-free graphs. III. Global structure|url=http://www.columbia.edu/~mc2775/bulls3.pdf}}.</ref> | ||
== वर्णिक और चारित्रिक बहुपद == | == वर्णिक और चारित्रिक बहुपद == | ||
[[File:Chromatically equivalent graphs.svg|thumb|200px|[[रंगीन बहुपद]] के साथ तीन ग्राफ़ बराबर हैं <math>(x-2)(x-1)^3x</math>.]]बुल ग्राफ का रंगीन बहुपद है <math>(x-2)(x-1)^3x</math> | [[File:Chromatically equivalent graphs.svg|thumb|200px|[[रंगीन बहुपद]] के साथ तीन ग्राफ़ बराबर हैं <math>(x-2)(x-1)^3x</math>.]]बुल ग्राफ का रंगीन बहुपद है <math>(x-2)(x-1)^3x</math>। दो और अन्य ग्राफ़ गुणात्मक रूप से बुल ग्राफ़ के समतुल्य हैं। | ||
इसका अभिलक्षणिक बहुपद है <math>-x(x^2-x-3)(x^2+x-1)</math> | इसका अभिलक्षणिक बहुपद है <math>-x(x^2-x-3)(x^2+x-1)</math>। | ||
इसका टुट्टे बहुपद है <math>x^4+x^3+x^2y</math> | इसका टुट्टे बहुपद है <math>x^4+x^3+x^2y</math>। | ||
== संदर्भ == | == संदर्भ == | ||
{{reflist}} | {{reflist}} | ||
Revision as of 23:31, 19 July 2023
| Bull graph | |
|---|---|
 The bull graph | |
| Vertices | 5 |
| Edges | 5 |
| Radius | 2 |
| Diameter | 3 |
| Girth | 3 |
| Automorphisms | 2 (Z/2Z) |
| Chromatic number | 3 |
| Chromatic index | 3 |
| Properties | Planar Unit distance |
| Table of graphs and parameters | |
ग्राफ़ सिद्धांत के गणितीय क्षेत्र में, बुल ग्राफ़ 5 शीर्षों और 5 किनारों वाला समतलीय प्रकार का अप्रत्यक्ष ग्राफ है, जिसे दो असंयुक्त लटकन किनारों वाले त्रिकोण के रूप में दर्शाया जाता है।[1]
इस ग्राफ़ में वर्णिक संख्या 3, वर्णिक सूचकांक 3, त्रिज्या 2, व्यास 3 और परिधि (ग्राफ सिद्धांत) 3 है। यह स्व-पूरक ग्राफ, ब्लॉक ग्राफ, विभाजित ग्राफ, अंतराल ग्राफ, पंजा-मुक्त ग्राफ भी है। बुल ग्राफ़ 1- के-वर्टेक्स-कनेक्टेड ग्राफ़ और 1- के-एज-कनेक्टेड ग्राफ़ भी है।
बुल-मुक्त ग्राफ़
यदि ग्राफ में प्रेरित सबग्राफ के रूप में कोई बुल नहीं है तो ग्राफ बुल-मुक्त होता है। त्रिकोण-मुक्त ग्राफ़, बुल-मुक्त प्रकार का ग्राफ़ हैं क्योंकि इस ग्राफ के प्रत्येक बुल में त्रिकोण होता है। सामान्य ग्राफ़ के लिए इसके प्रमाण को सिद्ध करने से बहुत पहले, मजबूत उत्तम ग्राफ़ प्रमेय को बैल-मुक्त ग्राफ़ के लिए सिद्ध किया गया था,[2] और बुल- मुक्त उत्तम ग्राफ़ के लिए बहुपद समय पहचान कलन विधि भी ज्ञात है।[3]
मारिया चुडनोव्स्की और शमूएल सफरा ने बुल- मुक्त ग्राफ़ का अधिक सामान्यतः अध्ययन किया है, जिससे पता चलता है कि ऐसे किसी भी ग्राफ़ में या तो बड़ा समूह (ग्राफ़ सिद्धांत) या बड़ा स्वतंत्र सेट (ग्राफ़ सिद्धांत) होना चाहिए (अर्थात, एर्दो-हजनल अनुमान बुल ग्राफ के लिए मान्य है),[4] और इन ग्राफ़ों के लिए सामान्य संरचना सिद्धांत विकसित करना चाहिए।[5][6][7]
वर्णिक और चारित्रिक बहुपद
बुल ग्राफ का रंगीन बहुपद है । दो और अन्य ग्राफ़ गुणात्मक रूप से बुल ग्राफ़ के समतुल्य हैं।
इसका अभिलक्षणिक बहुपद है ।
इसका टुट्टे बहुपद है ।
संदर्भ
- ↑ Weisstein, Eric W. "Bull Graph". MathWorld.
- ↑ Chvátal, V.; Sbihi, N. (1987), "Bull-free Berge graphs are perfect", Graphs and Combinatorics, 3 (1): 127–139, doi:10.1007/BF01788536, S2CID 44570627.
- ↑ Reed, B.; Sbihi, N. (1995), "Recognizing bull-free perfect graphs", Graphs and Combinatorics, 11 (2): 171–178, doi:10.1007/BF01929485, S2CID 206808701.
- ↑ Chudnovsky, M.; Safra, S. (2008), "The Erdős–Hajnal conjecture for bull-free graphs", Journal of Combinatorial Theory, Series B, 98 (6): 1301–1310, doi:10.1016/j.jctb.2008.02.005.
- ↑ Chudnovsky, M. (2008), The structure of bull-free graphs. I. Three-edge paths with centers and anticenters (PDF).
- ↑ Chudnovsky, M. (2008), The structure of bull-free graphs. II. Elementary trigraphs (PDF).
- ↑ Chudnovsky, M. (2008), The structure of bull-free graphs. III. Global structure (PDF).
