बुल ग्राफ: Difference between revisions

From Vigyanwiki
(Created page with "{{Infobox graph | name = Bull graph | image = 170px | image_caption = The bull graph | namesake = | vertices = 5 | edges = 5 | automorphis...")
 
No edit summary
Line 15: Line 15:
}}
}}


ग्राफ़ सिद्धांत के गणित क्षेत्र में, बुल ग्राफ़ 5 शीर्षों और 5 किनारों वाला एक [[समतलीय ग्राफ]]़ [[अप्रत्यक्ष ग्राफ]]़ है, जो दो असंयुक्त लटकन किनारों वाले त्रिकोण के रूप में होता है।<ref>{{MathWorld|urlname=BullGraph|title=Bull Graph}}</ref>
ग्राफ़ सिद्धांत के गणित क्षेत्र में, बुल ग्राफ़ 5 शीर्षों और 5 किनारों वाला [[समतलीय ग्राफ]]़ [[अप्रत्यक्ष ग्राफ]]़ है, जो दो असंयुक्त लटकन किनारों वाले त्रिकोण के रूप में होता है।<ref>{{MathWorld|urlname=BullGraph|title=Bull Graph}}</ref>
इसमें वर्णिक संख्या 3, वर्णिक सूचकांक 3, त्रिज्या 2, व्यास 3 और परिधि (ग्राफ सिद्धांत) 3 है। यह एक [[स्व-पूरक ग्राफ]], एक [[ब्लॉक ग्राफ]], एक [[विभाजित ग्राफ]], एक [[अंतराल ग्राफ]], एक पंजा-मुक्त ग्राफ भी है। एक 1-[[ के-वर्टेक्स-कनेक्टेड ग्राफ़ ]]|वर्टेक्स-कनेक्टेड ग्राफ और एक 1-[[ के-एज-कनेक्टेड ग्राफ़ ]]|एज-कनेक्टेड ग्राफ।
 
इसमें वर्णिक संख्या 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=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>
 


[[मारिया चुडनोव्स्की]] और [[शमूएल सफरा]] ने बुल-फ्री ग्राफ़ का अधिक सामान्यतः अध्ययन किया है, जिससे पता चलता है कि ऐसे किसी भी ग्राफ़ में या तो बड़ा क्लिक (ग्राफ़ सिद्धांत) या बड़ा [[स्वतंत्र सेट (ग्राफ़ सिद्धांत)]] होना चाहिए (अर्थात, एर्दो-हजनल अनुमान इसके लिए मान्य है) बुल ग्राफ),<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 21:05, 19 July 2023

Bull graph
Bull graph.circo.svg
The bull graph
Vertices5
Edges5
Radius2
Diameter3
Girth3
Automorphisms2 (Z/2Z)
Chromatic number3
Chromatic index3
PropertiesPlanar
Unit distance
Table of graphs and parameters

ग्राफ़ सिद्धांत के गणित क्षेत्र में, बुल ग्राफ़ 5 शीर्षों और 5 किनारों वाला समतलीय ग्राफ़ अप्रत्यक्ष ग्राफ़ है, जो दो असंयुक्त लटकन किनारों वाले त्रिकोण के रूप में होता है।[1]

इसमें वर्णिक संख्या 3, वर्णिक सूचकांक 3, त्रिज्या 2, व्यास 3 और परिधि (ग्राफ सिद्धांत) 3 है। यह स्व-पूरक ग्राफ, ब्लॉक ग्राफ, विभाजित ग्राफ, अंतराल ग्राफ, पंजा-मुक्त ग्राफ भी है। 1- के-वर्टेक्स-कनेक्टेड ग्राफ़ और 1- के-एज-कनेक्टेड ग्राफ़

बुल-मुक्त ग्राफ़

ग्राफ बुल-मुक्त है यदि इसमें प्रेरित सबग्राफ के रूप में कोई बुल नहीं है। त्रिकोण-मुक्त ग्राफ़ बैल-मुक्त ग्राफ़ हैं, क्योंकि प्रत्येक बैल में त्रिकोण होता है। सामान्य ग्राफ़ के लिए इसके प्रमाण से बहुत पहले मजबूत परफेक्ट ग्राफ़ प्रमेय को बैल-मुक्त ग्राफ़ के लिए सिद्ध किया गया था,[2] और बुल-फ्री परफेक्ट ग्राफ़ के लिए बहुपद समय पहचान एल्गोरिथ्म ज्ञात है।[3]

मारिया चुडनोव्स्की और शमूएल सफरा ने बुल-फ्री ग्राफ़ का अधिक सामान्यतः अध्ययन किया है, जिससे पता चलता है कि ऐसे किसी भी ग्राफ़ में या तो बड़ा क्लिक (ग्राफ़ सिद्धांत) या बड़ा स्वतंत्र सेट (ग्राफ़ सिद्धांत) होना चाहिए (अर्थात, एर्दो-हजनल अनुमान इसके लिए मान्य है) बुल ग्राफ),[4] और इन ग्राफ़ों के लिए सामान्य संरचना सिद्धांत विकसित करना।[5][6][7]

वर्णिक और चारित्रिक बहुपद

रंगीन बहुपद के साथ तीन ग्राफ़ बराबर हैं .

बुल ग्राफ का रंगीन बहुपद है . दो अन्य ग्राफ़ गुणात्मक रूप से बुल ग्राफ़ के समतुल्य हैं।

इसका अभिलक्षणिक बहुपद है .

इसका टुट्टे बहुपद है .

संदर्भ

  1. ↑ Weisstein, Eric W. "Bull Graph". MathWorld.
  2. ↑ 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.
  3. ↑ Reed, B.; Sbihi, N. (1995), "Recognizing bull-free perfect graphs", Graphs and Combinatorics, 11 (2): 171–178, doi:10.1007/BF01929485, S2CID 206808701.
  4. ↑ 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.
  5. ↑ Chudnovsky, M. (2008), The structure of bull-free graphs. I. Three-edge paths with centers and anticenters (PDF).
  6. ↑ Chudnovsky, M. (2008), The structure of bull-free graphs. II. Elementary trigraphs (PDF).
  7. ↑ Chudnovsky, M. (2008), The structure of bull-free graphs. III. Global structure (PDF).
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=बुल_ग्राफ&oldid=225037’