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

From Vigyanwiki
No edit summary
No edit summary
Line 1: Line 1:
{{Infobox graph
{{Infobox graph
  | name = Bull graph
  | name = बुल ग्राफ
  | image = [[File:Bull graph.circo.svg|170px]]
  | image = [[File:Bull graph.circo.svg|170px]]
  | image_caption = The bull graph
  | image_caption = बुल ग्राफ
  | namesake =
  | namesake =
  | vertices = 5
  | vertices = 5
Line 12: Line 12:
  | chromatic_number = 3
  | chromatic_number = 3
  | chromatic_index = 3
  | chromatic_index = 3
  | properties = [[planar graph|Planar]]<br />[[unit distance graph|Unit distance]]
  | properties = [[तलीय ग्राफ|तलीय]]<br />[[इकाई दूरी ग्राफ|इकाई दूरी]]
}}
}}


Line 20: Line 20:


== बुल-मुक्त ग्राफ़ ==
== बुल-मुक्त ग्राफ़ ==
यदि ग्राफ में [[प्रेरित सबग्राफ]] के रूप में कोई बुल नहीं है तो ग्राफ बुल-मुक्त होता है। [[त्रिकोण-मुक्त ग्राफ़]], बुल-मुक्त प्रकार का ग्राफ़ हैं क्योंकि इस ग्राफ के प्रत्येक बुल में त्रिकोण होता है। सामान्य ग्राफ़ के लिए इसके प्रमाण को सिद्ध करने से बहुत पहले, '''मजबूत उत्तम ग्राफ़ प्रमेय''' को बुल-मुक्त ग्राफ़ के लिए सिद्ध किया गया था,<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(x^2-x-3)(x^2+x-1)</math> इसका अभिलक्षणिक बहुपद है।
<math>(x-2)(x-1)^3x</math>


<math>x^4+x^3+x^2y</math> इसका सभी बहुपद है।
इसके अलावा और दो ग्राफ भी बुल ग्राफ के रंगीय समरूप हैं।
 
इसका लक्षण बहुपद निम्नलिखित है:
 
<math>-x(x^2-x-3)(x^2+x-1)</math>
 
इसका सभी बहुपद निम्नलिखित है:
 
<math>x^4+x^3+x^2y</math>  
== संदर्भ ==
== संदर्भ ==
{{reflist}}
{{reflist}}

Revision as of 06:45, 20 July 2023

बुल ग्राफ
Bull graph.circo.svg
बुल ग्राफ
Vertices5
Edges5
Radius2
Diameter3
Girth3
Automorphisms2 (Z/2Z)
Chromatic number3
Chromatic index3
Propertiesतलीय
इकाई दूरी
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=225042’