Queen's graph
गणित में, एक रानी का ग्राफ एक दिशाहीन ग्राफ है जो एक शतरंज की बिसात पर रानी की सभी कानूनी चालों-एक शतरंज के टुकड़े-का प्रतिनिधित्व करता है। ग्राफ में, प्रत्येक शीर्ष एक शतरंज की बिसात पर एक वर्ग का प्रतिनिधित्व करता है, और प्रत्येक किनारा एक कानूनी चाल है जो रानी किसी भी संख्या में वर्गों द्वारा क्षैतिज, ऊर्ध्वाधर या विकर्ण चाल कर सकती है। यदि शतरंज की बिसात के आयाम हैं, तो प्रेरित ग्राफ को रानी का ग्राफ कहा जाता है। ग्राफ के स्वतंत्र सेट कई रानियों के प्लेसमेंट के अनुरूप होते हैं जहां कोई दो रानियाँ एक-दूसरे पर हमला नहीं कर रही होती हैं। उनका अध्ययन आठ रानियों की पहेली में किया जाता है, जहाँ आठ गैर-हमलावर रानियों को एक मानक शतरंज की बिसात पर रखा जाता है। हावी सेट रानियों की व्यवस्था का प्रतिनिधित्व करते हैं जहाँ हर वर्ग पर एक रानी द्वारा हमला किया जाता है या कब्जा कर लिया जाता है; पाँच रानियाँ, लेकिन कम नहीं, शतरंज की बिसात पर हावी हो सकती हैं। ग्राफ के रंग प्रत्येक वर्ग को रंगने के तरीकों का प्रतिनिधित्व करते हैं ताकि एक रानी एक ही रंग के किसी भी दो वर्गों के बीच न चल सके; एक शतरंज की बिसात के लिए कम से कम एन रंगों की आवश्यकता होती है, लेकिन बोर्ड के लिए 9 रंगों की आवश्यकता होती है। गुण प्रत्येक रानी के ग्राफ के लिए एक हैमिल्टनियन चक्र होता है, और ग्राफ द्वि-संयोजित होते हैं (यदि किसी एक शीर्ष को हटा दिया जाता है तो वे जुड़े रहते हैं)। और रानी के ग्राफ के विशेष मामले पूरे हो गए हैं। स्वतंत्रता ग्राफ का एक स्वतंत्र सेट एक शतरंज की बिसात पर कई रानियों की नियुक्ति से मेल खाता है जैसे कि कोई भी दो रानियाँ एक दूसरे पर हमला नहीं कर रही हों। एक शतरंजपट में, सबसे बड़े स्वतंत्र सेट में अधिकतम n शीर्ष होते हैं, क्योंकि कोई भी दो रानियाँ एक ही पंक्ति या स्तंभ में नहीं हो सकती हैं। यह ऊपरी सीमा n = 2 और n = 3 को छोड़कर सभी n के लिए प्राप्त की जा सकती है। एन = 8 के मामले में, यह पारंपरिक आठ रानियों की पहेली है। प्रभुत्व रानी के ग्राफ का एक प्रमुख सेट रानियों की नियुक्ति से मेल खाता है जैसे कि शतरंज की बिसात पर प्रत्येक वर्ग पर या तो हमला किया जाता है या एक रानी द्वारा कब्जा कर लिया जाता है। एक शतरंज की बिसात पर, पाँच रानियाँ हावी हो सकती हैं, और यह न्यूनतम संभव संख्या है (चार रानियाँ कम से कम दो वर्गों को बिना हमला किए छोड़ देती हैं)। पाँच रानियों के 4,860 ऐसे प्लेसमेंट हैं, जिनमें वे भी शामिल हैं जहाँ रानियाँ सभी अधिकृत चौराहों को नियंत्रित करती हैं, अर्थात। वे एक दूसरे की रक्षा करने के लिए क्रमशः हमला करते हैं। इस उपसमूह में, ऐसी स्थितियाँ भी हैं जहाँ रानियाँ केवल मुख्य विकर्ण पर वर्गों पर कब्जा करती हैं (जैसे। a1 से h8 तक), या सब एक उप-विकर्ण पर (जैसे। ए2 से जी8 तक)। गैर-लूपिंग आयताकार शतरंजपट को टोरस या सिलेंडर से बदलकर ग्राफ को संशोधित करने से न्यूनतम हावी सेट आकार चार हो जाता है। रानी के ग्राफ पर बोर्ड के केंद्र में एकल शीर्ष का प्रभुत्व है। रानी के ग्राफ का केंद्र शीर्ष 8 शीर्षों को छोड़कर सभी से सटा हुआ हैः वे शीर्ष जो नाइट के ग्राफ के केंद्र शीर्ष से सटे हैं। प्रभुत्व संख्या एक रानी के ग्राफ की प्रभुत्व संख्या d (n) को सबसे छोटे प्रभुत्व वाले सेट के आकार के रूप में परिभाषित करती है, और विकर्ण प्रभुत्व संख्या dd (n) को सबसे छोटे प्रभुत्व वाले सेट के आकार के रूप में परिभाषित करती है जो लंबे विकर्ण का एक उपसमुच्चय है। ध्यान दें कि सभी एन के लिए सीमा प्राप्त की जाती है, लेकिन के लिए नहीं। वर्चस्व संख्या n में रैखिक है, जिसके द्वारा दी गई सीमाएँ हैंः d (n) के प्रारंभिक मान 1,1,1,2,3,3,4,5,5,5 हैं। मान लीजिए कि Kn एक उपसमुच्चय का अधिकतम आकार है कि प्रत्येक संख्या में समान समानता हो और कोई भी तीन संख्याएँ एक अंकगणितीय प्रगति नहीं बनाती हैं (समुच्चय "मध्य-बिंदु-मुक्त" है)। रानी के ग्राफ की विकर्ण वर्चस्व संख्या है। स्वतंत्र वर्चस्व संख्या आईडी (एन) को रानी के ग्राफ में सबसे छोटे स्वतंत्र, प्रमुख सेट के आकार के रूप में परिभाषित करें। यह ज्ञात है। रंग रानी के ग्राफ का रंग प्रत्येक शीर्ष पर रंगों का एक असाइनमेंट है जैसे कि किसी भी दो आसन्न शीर्षों को एक ही रंग नहीं दिया जाता है। उदाहरण के लिए, यदि ए8 लाल रंग का है तो ए-फाइल, आठवीं श्रेणी या लंबे विकर्ण पर कोई अन्य वर्ग लाल रंग का नहीं हो सकता है, क्योंकि एक रानी ए8 से इनमें से किसी भी वर्ग में जा सकती है। ग्राफ की वर्णात्मक संख्या रंगों की सबसे छोटी संख्या है जिसका उपयोग इसे रंगने के लिए किया जा सकता है। रानी के ग्राफ के मामले में, कम से कम एन रंगों की आवश्यकता होती है, क्योंकि एक रैंक या फ़ाइल में प्रत्येक वर्ग को एक अलग रंग (यानी। पंक्तियाँ और स्तंभ गुट हैं)। वर्णात्मक संख्या बिल्कुल n है यदि (अर्थात। एन 6 के गुणज से एक अधिक या एक कम है)। रानी के ग्राफ की वर्णात्मक संख्या 9 है। इरेडंडेंस शीर्षों का एक समूह अपरिवर्तनीय है यदि सेट से किसी भी शीर्ष को हटाने से सेट के पड़ोस में परिवर्तन होता है अर्थात। प्रत्येक शीर्ष के लिए, एक आसन्न शीर्ष होता है जो समूह में किसी अन्य शीर्ष के निकट नहीं होता है। यह रानियों के एक समूह से मेल खाता है जो प्रत्येक विशिष्ट रूप से कम से कम एक वर्ग को नियंत्रित करता है। रानी के ग्राफ पर एक अपरिवर्तनीय सेट के अधिकतम आकार आई. आर. (एन) को चिह्नित करना मुश्किल है; ज्ञात मूल्यों में खोज-चोरी का खेल शामिल है रानी के ग्राफ पर पीछा-चोरी के खेल पर विचार करें जो निम्नलिखित नियमों के अनुसार खेला जाता हैः एक सफेद रानी एक कोने में शुरू होती है और दूसरी कोने में एक काली रानी। खिलाड़ी वैकल्पिक चाल चलाते हैं, जिसमें रानी को एक आसन्न शीर्ष पर ले जाना शामिल होता है जिसे (क्षैतिज, ऊर्ध्वाधर या विकर्ण रूप से) पार किए बिना या विपरीत रानी से सटे शीर्ष पर उतरे बिना पहुँचा जा सकता है। यह खेल सफेद द्वारा जोड़ी बनाने की रणनीति के साथ जीता जा सकता है। किंग्स ग्राफ नाइट का ग्राफ रुक का ग्राफ बिशप का ग्राफ संदर्भ गणितीय शतरंज समस्याएं ग्राफ के पैरामीट्रिक परिवार भी देखें।