विंडमिल ग्राफ: Difference between revisions

From Vigyanwiki
(Created page with "{{short description|Graph family made by joining complete graphs at a universal node}} {{infobox graph | name = Windmill graph | image = Image:Windmill graph Wd(5,4).svg|2...")
 
No edit summary
 
(17 intermediate revisions by 3 users not shown)
Line 1: Line 1:
{{short description|Graph family made by joining complete graphs at a universal node}}
{{infobox graph
{{infobox graph
  | name = Windmill graph
  | name = Windmill graph
Line 16: Line 15:
}}
}}


[[ ग्राफ सिद्धांत ]] के गणित क्षेत्र में, विंडमिल ग्राफ {{math|Wd(''k'',''n'')}} के लिए निर्मित एक [[अप्रत्यक्ष ग्राफ]] है {{math|''k'' ≥ 2}} और {{math|''n'' ≥ 2}} में शामिल होने से {{mvar|n}} पूरे ग्राफ की प्रतियां {{mvar|K{{sub|k}}}} एक साझा सार्वभौमिक शीर्ष पर। अर्थात्, यह इन पूर्ण रेखांकन का एक गुट-योग|1-समूह-योग है।<ref>{{cite journal |last=Gallian |first=J. A. | author-link = Joseph Gallian |title=ग्राफ लेबलिंग का एक गतिशील सर्वेक्षण|journal=Electronic Journal of Combinatorics |volume=DS6 |pages=1–58 |date=3 January 2007 |url=http://www.combinatorics.org/Surveys/ds6.pdf|mr=1668059 }}</ref>
[[ ग्राफ सिद्धांत |ग्राफ सिद्धांत]] के गणित क्षेत्र में '''विंडमिल ग्राफ''' Wd(''k'',''n'') एक अप्रत्यक्ष ग्राफ है। जिसे ''k'' ≥ 2 और ''n'' ≥ 2 के लिए एक वितरित यूनिवर्सल वर्टेक्स पर पूर्ण ग्राफ K<sub>k</sub> की n प्रतियों में सम्मिलित करके बनाया गया है अर्थात् यह इन पूर्ण ग्राफ़ों का 1-क्लिक-योग है।<ref>{{cite journal |last=Gallian |first=J. A. | author-link = Joseph Gallian |title=ग्राफ लेबलिंग का एक गतिशील सर्वेक्षण|journal=Electronic Journal of Combinatorics |volume=DS6 |pages=1–58 |date=3 January 2007 |url=http://www.combinatorics.org/Surveys/ds6.pdf|mr=1668059 }}</ref>




== गुण ==
यह है {{math|''n''(''k'' – 1) + 1}} शिखर और {{math|''nk''(''k'' − 1)/2}} किनारों,<ref>{{MathWorld|urlname=WindmillGraph|title=Windmill Graph}}</ref> परिधि 3 (यदि {{math|''k'' > 2}}), त्रिज्या 1 और व्यास 2।
इसका [[के-वर्टेक्स-कनेक्टेड ग्राफ]] 1 है क्योंकि इसका केंद्रीय शीर्ष एक आर्टिक्यूलेशन पॉइंट है; हालाँकि, पूर्ण रेखांकन की तरह जिससे यह बनता है, यह है {{math|(''k'' – 1)}}-एज-कनेक्टेड। यह [[तुच्छ रूप से सही ग्राफ]] और एक [[ब्लॉक ग्राफ]] है।


== विशेष मामले ==
'''<u><big>विशेषताएं-</big></u>'''
निर्माण द्वारा, पवनचक्की ग्राफ {{math|Wd(3,''n'')}} [[दोस्ती का ग्राफ]] है {{mvar|F{{sub|n}}}}, पवनचक्की ग्राफ {{math|Wd(2,''n'')}} तारा है (ग्राफ सिद्धांत) {{mvar|S{{sub|n}}}} और पवनचक्की ग्राफ {{math|Wd(3,2)}} [[तितली ग्राफ]] है।
 
इसमें n(k – 1) + 1 कोने और nk(k − 1)/2 किनारों, परिधि 3 (यदि k > 2), त्रिज्या 1 और व्यास 2 है।<ref>{{MathWorld|urlname=WindmillGraph|title=Windmill Graph}}</ref> इसका [[के-वर्टेक्स-कनेक्टेड ग्राफ|वर्टेक्स-कनेक्टेड ग्राफ]] 1 है क्योंकि इसका केंद्रीय शीर्ष एक आर्टिक्यूलेशन बिन्दु स्थित है। चूंकि पूर्ण रेखांकन के समान, जिससे इसका निर्माण किया जाता है, यह (k – 1)-एज-कनेक्टेड है। यह [[तुच्छ रूप से सही ग्राफ|तुच्छ रूप से परिपूर्ण ग्राफ]] और एक [[ब्लॉक ग्राफ]] है।
 
== विशेष स्थितियां ==
इनके निर्माण के द्वारा पवनचक्की ग्राफ Wd(3,n) [[दोस्ती का ग्राफ|मित्रता ग्राफ]] Fn है। पवनचक्की ग्राफ Wd(2,n) स्टार ग्राफ Sn है और पवनचक्की ग्राफ Wd(3,2) [[तितली ग्राफ|बटरफ्लाई ग्राफ]] है।  


== लेबलिंग और रंग ==
== लेबलिंग और रंग ==
पवनचक्की ग्राफ में [[रंगीन संख्या]] होती है {{mvar|k}} और [[रंगीन सूचकांक]] {{math|''n''(''k'' – 1)}}. इसका [[रंगीन बहुपद]] पूरे ग्राफ के रंगीन बहुपद से निकाला जा सकता है और इसके बराबर है
पवनचक्की ग्राफ में [[रंगीन संख्या]] k और [[रंगीन सूचकांक]] n(k - 1) है। इसका [[रंगीन बहुपद]] सम्पूर्ण ग्राफ के रंगीन बहुपद से निकाला जा सकता है और इसके बराबर है। 
:<math>x\prod_{i=1}^{k-1}(x-i)^n.</math>
:<math>x\prod_{i=1}^{k-1}(x-i)^n.</math>
पवनचक्की ग्राफ {{math|Wd(''k'',''n'')}} अगर [[ग्रेसफुल लेबलिंग]] साबित नहीं हुई है {{math|''k'' > 5}}.<ref>{{cite journal |first=K. M. |last=Koh |first2=D. G. |last2=Rogers |first3=H. K. |last3=Teo |first4=K. Y. |last4=Yap |title=Graceful graphs: some further results and problems |journal= Congressus Numerantium |volume=29 |pages=559–571 |year=1980 |mr=0608456}}</ref> 1979 में, बरमोंड ने अनुमान लगाया है {{math|Wd(4,''n'')}} सबके लिए कृपालु है {{math|''n'' ≥ 4}}.<ref>{{cite book |first=J.-C. |last=Bermond |chapter=Graceful graphs, radio antennae and French windmills |editor-first=Robin J. |editor-last=Wilson |editor-link=Robin Wilson (mathematician) |title= Graph theory and combinatorics (Proc. Conf., Open Univ., Milton Keynes, 1978) |chapter-url=https://books.google.com/books?id=7-_uAAAAMAAJ |year=1979 |publisher=Pitman |pages=18–37 |series=Research notes in mathematics | volume=34 |isbn=978-0273084358 |oclc=757210583|mr=0587620}}</ref> पूर्ण अंतर परिवारों के साथ एक तुल्यता के माध्यम से, यह साबित हो गया है {{math|''n'' ≤ 1000}}.
पवनचक्की ग्राफ {{math|Wd(''k'',''n'')}} यदि [[ग्रेसफुल लेबलिंग]] {{math|''k'' > 5}} नहीं हुई है।<ref>{{cite journal |first=K. M. |last=Koh |first2=D. G. |last2=Rogers |first3=H. K. |last3=Teo |first4=K. Y. |last4=Yap |title=Graceful graphs: some further results and problems |journal= Congressus Numerantium |volume=29 |pages=559–571 |year=1980 |mr=0608456}}</ref> 1979 में, बरमोंड ने अनुमान लगाया कि Wd(4,n) सभी n ≥ 4 के लिए अनुकूल है।<ref>{{cite book |first=J.-C. |last=Bermond |chapter=Graceful graphs, radio antennae and French windmills |editor-first=Robin J. |editor-last=Wilson |editor-link=Robin Wilson (mathematician) |title= Graph theory and combinatorics (Proc. Conf., Open Univ., Milton Keynes, 1978) |chapter-url=https://books.google.com/books?id=7-_uAAAAMAAJ |year=1979 |publisher=Pitman |pages=18–37 |series=Research notes in mathematics | volume=34 |isbn=978-0273084358 |oclc=757210583|mr=0587620}}</ref> पूर्ण अंतर परिवारों के साथ एक तुल्यता के माध्यम से यह n ≤ 1000 के लिए प्रमाणित किया गया है।<ref>{{cite journal |first=G. |last=Ge |first2=Y. |last2=Miao |first3=X. |last3=Sun |title=परफेक्ट डिफरेंस फैमिली, परफेक्ट डिफरेंस मैट्रिसेस और संबंधित कॉम्बिनेटरियल स्ट्रक्चर|journal=Journal of Combinatorial Designs |volume=18 |issue=6 |pages=415–449 |year=2010 |doi=10.1002/jcd.20259 |mr=2743134 }}</ref>
<ref>{{cite journal |first=G. |last=Ge |first2=Y. |last2=Miao |first3=X. |last3=Sun |title=परफेक्ट डिफरेंस फैमिली, परफेक्ट डिफरेंस मैट्रिसेस और संबंधित कॉम्बिनेटरियल स्ट्रक्चर|journal=Journal of Combinatorial Designs |volume=18 |issue=6 |pages=415–449 |year=2010 |doi=10.1002/jcd.20259 |mr=2743134 }}</ref>
 
बरमोंड, [[एंटोन कोटज़िग]] और टर्जन ने यह साबित कर दिया {{math|Wd(''k'',''n'')}} कृपालु नहीं है जब {{math|1=''k'' = 4}} और {{math|1=''n'' = 2}} या {{math|1=''n'' = 3}}, और जब {{math|1=''k'' = 5}} और {{math|1=''n'' = 2}}.<ref>{{cite book |first=J.-C. |last=Bermond |first2=A. |last2=Kotzig|author2-link= Anton Kotzig |first3=J. |last3=Turgeon |chapter=On a combinatorial problem of antennas in radioastronomy |editor-first=A. |editor-last=Hajnal |editor2-first=Vera T. |editor2-last=Sos |title=Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. I |chapter-url=https://books.google.com/books?id=OPtUvQEACAAJ |year=1978 |publisher=North-Holland |volume=18 |series=Colloquia mathematica Societatis János Bolyai |isbn=978-0-444-85095-9 |pages=135–149 |mr=0519261}}</ref> पवनचक्की {{math|Wd(3,''n'')}} कृपालु है अगर और केवल अगर {{math|''n'' ≡ 0 (mod 4)}} या {{math|''n'' ≡ 1 (mod 4)}}.<ref>{{cite book |first=J.-C. |last=Bermond |first2=A. E. |last2=Brouwer |author2-link= Andries Brouwer |first3=A. |last3=Germa |chapter=Systèmes de triplets et différences associées |title= Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976) |chapter-url=https://books.google.com/books?id=0u3uAAAAMAAJ |year=1978 |publisher=Éditions du Centre national de la recherche scientifique |isbn=978-2-222-02070-7 |volume=260 |series=Colloques internationaux du Centre National de la Recherche Scientifique |pages=35–38|mr=0539936}}</ref>
बरमोंड, [[एंटोन कोटज़िग]] और टर्जन ने सिद्ध किया कि जब k = 4 और n = 2 या n = 3 और जब k = 5 और n = 2 होता है। तो Wd(k,n) सुंदर नहीं होता है।<ref>{{cite book |first=J.-C. |last=Bermond |first2=A. |last2=Kotzig|author2-link= Anton Kotzig |first3=J. |last3=Turgeon |chapter=On a combinatorial problem of antennas in radioastronomy |editor-first=A. |editor-last=Hajnal |editor2-first=Vera T. |editor2-last=Sos |title=Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. I |chapter-url=https://books.google.com/books?id=OPtUvQEACAAJ |year=1978 |publisher=North-Holland |volume=18 |series=Colloquia mathematica Societatis János Bolyai |isbn=978-0-444-85095-9 |pages=135–149 |mr=0519261}}</ref> वह पवनचक्की Wd(3,n) सुंदर है। यदि और केवल यदि n ≡ 0 (mod 4) या n ≡ 1 (mod 4)<ref>{{cite book |first=J.-C. |last=Bermond |first2=A. E. |last2=Brouwer |author2-link= Andries Brouwer |first3=A. |last3=Germa |chapter=Systèmes de triplets et différences associées |title= Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976) |chapter-url=https://books.google.com/books?id=0u3uAAAAMAAJ |year=1978 |publisher=Éditions du Centre national de la recherche scientifique |isbn=978-2-222-02070-7 |volume=260 |series=Colloques internationaux du Centre National de la Recherche Scientifique |pages=35–38|mr=0539936}}</ref>
 




== गैलरी ==
== गैलरी ==


[[Image:Windmill graphs.svg|thumb|550px|center|छोटे पवनचक्की रेखांकन।]]
[[Image:Windmill graphs.svg|thumb|550px|center|छोटे पवनचक्की का रेखांकन।]]
{{-}}
 
== संदर्भ ==
== संदर्भ ==
{{reflist}}
{{reflist}}
[[Category: रेखांकन के पैरामीट्रिक परिवार]] [[Category: बिल्कुल सही रेखांकन]]


[[Category: Machine Translated Page]]
[[Category:Created On 28/02/2023]]
[[Category:Created On 28/02/2023]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Templates Vigyan Ready]]
[[Category:बिल्कुल सही रेखांकन]]
[[Category:रेखांकन के पैरामीट्रिक परिवार]]

Latest revision as of 10:38, 4 May 2023

Windmill graph
Windmill graph Wd(5,4).svg
The Windmill graph Wd(5,4).
Verticesn(k – 1) + 1
Edgesnk(k − 1)/2
Radius1
Diameter2
Girth3 if k > 2
Chromatic numberk
Chromatic indexn(k – 1)
NotationWd(k,n)
Table of graphs and parameters

ग्राफ सिद्धांत के गणित क्षेत्र में विंडमिल ग्राफ Wd(k,n) एक अप्रत्यक्ष ग्राफ है। जिसे k ≥ 2 और n ≥ 2 के लिए एक वितरित यूनिवर्सल वर्टेक्स पर पूर्ण ग्राफ Kk की n प्रतियों में सम्मिलित करके बनाया गया है अर्थात् यह इन पूर्ण ग्राफ़ों का 1-क्लिक-योग है।[1]


विशेषताएं-

इसमें n(k – 1) + 1 कोने और nk(k − 1)/2 किनारों, परिधि 3 (यदि k > 2), त्रिज्या 1 और व्यास 2 है।[2] इसका वर्टेक्स-कनेक्टेड ग्राफ 1 है क्योंकि इसका केंद्रीय शीर्ष एक आर्टिक्यूलेशन बिन्दु स्थित है। चूंकि पूर्ण रेखांकन के समान, जिससे इसका निर्माण किया जाता है, यह (k – 1)-एज-कनेक्टेड है। यह तुच्छ रूप से परिपूर्ण ग्राफ और एक ब्लॉक ग्राफ है।

विशेष स्थितियां

इनके निर्माण के द्वारा पवनचक्की ग्राफ Wd(3,n) मित्रता ग्राफ Fn है। पवनचक्की ग्राफ Wd(2,n) स्टार ग्राफ Sn है और पवनचक्की ग्राफ Wd(3,2) बटरफ्लाई ग्राफ है।

लेबलिंग और रंग

पवनचक्की ग्राफ में रंगीन संख्या k और रंगीन सूचकांक n(k - 1) है। इसका रंगीन बहुपद सम्पूर्ण ग्राफ के रंगीन बहुपद से निकाला जा सकता है और इसके बराबर है।

पवनचक्की ग्राफ Wd(k,n) यदि ग्रेसफुल लेबलिंग k > 5 नहीं हुई है।[3] 1979 में, बरमोंड ने अनुमान लगाया कि Wd(4,n) सभी n ≥ 4 के लिए अनुकूल है।[4] पूर्ण अंतर परिवारों के साथ एक तुल्यता के माध्यम से यह n ≤ 1000 के लिए प्रमाणित किया गया है।[5]

बरमोंड, एंटोन कोटज़िग और टर्जन ने सिद्ध किया कि जब k = 4 और n = 2 या n = 3 और जब k = 5 और n = 2 होता है। तो Wd(k,n) सुंदर नहीं होता है।[6] वह पवनचक्की Wd(3,n) सुंदर है। यदि और केवल यदि n ≡ 0 (mod 4) या n ≡ 1 (mod 4)[7]


गैलरी

छोटे पवनचक्की का रेखांकन।

संदर्भ

  1. Gallian, J. A. (3 January 2007). "ग्राफ लेबलिंग का एक गतिशील सर्वेक्षण" (PDF). Electronic Journal of Combinatorics. DS6: 1–58. MR 1668059.
  2. Weisstein, Eric W. "Windmill Graph". MathWorld.
  3. Koh, K. M.; Rogers, D. G.; Teo, H. K.; Yap, K. Y. (1980). "Graceful graphs: some further results and problems". Congressus Numerantium. 29: 559–571. MR 0608456.
  4. Bermond, J.-C. (1979). "Graceful graphs, radio antennae and French windmills". In Wilson, Robin J. (ed.). Graph theory and combinatorics (Proc. Conf., Open Univ., Milton Keynes, 1978). Research notes in mathematics. Vol. 34. Pitman. pp. 18–37. ISBN 978-0273084358. MR 0587620. OCLC 757210583.
  5. Ge, G.; Miao, Y.; Sun, X. (2010). "परफेक्ट डिफरेंस फैमिली, परफेक्ट डिफरेंस मैट्रिसेस और संबंधित कॉम्बिनेटरियल स्ट्रक्चर". Journal of Combinatorial Designs. 18 (6): 415–449. doi:10.1002/jcd.20259. MR 2743134.
  6. Bermond, J.-C.; Kotzig, A.; Turgeon, J. (1978). "On a combinatorial problem of antennas in radioastronomy". In Hajnal, A.; Sos, Vera T. (eds.). Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. I. Colloquia mathematica Societatis János Bolyai. Vol. 18. North-Holland. pp. 135–149. ISBN 978-0-444-85095-9. MR 0519261.
  7. Bermond, J.-C.; Brouwer, A. E.; Germa, A. (1978). "Systèmes de triplets et différences associées". Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976). Colloques internationaux du Centre National de la Recherche Scientifique. Vol. 260. Éditions du Centre national de la recherche scientifique. pp. 35–38. ISBN 978-2-222-02070-7. MR 0539936.