Bishop's graph
गणित में, एक बिशप का ग्राफ एक ग्राफ है जो शतरंज के टुकड़े की सभी कानूनी चालों का प्रतिनिधित्व करता है। प्रत्येक शीर्ष शतरंज की बिसात पर एक वर्ग का प्रतिनिधित्व करता है और प्रत्येक किनारा बिशप की एक कानूनी चाल का प्रतिनिधित्व करता है; यानी, दो शीर्षों (वर्गों) के बीच एक किनारा होता है यदि वे एक सामान्य विकर्ण पर कब्जा करते हैं। जब शतरंज की बिसात के आयाम होते हैं, तो प्रेरित ग्राफ को बिशप ग्राफ कहा जाता है। गुण तथ्य यह है कि शतरंज की बिसात में दो रंगों के वर्ग होते हैं, मान लीजिए कि लाल और काले, जैसे कि क्षैतिज या ऊर्ध्वाधर रूप से आस-पास के वर्गों में विपरीत रंग होते हैं, इसका मतलब है कि बिशप के ग्राफ में दो जुड़े हुए घटक होते हैं, जिनके शीर्ष समूह क्रमशः लाल और काले वर्ग होते हैं। इसका कारण यह है कि बिशप की विकर्ण चालें इसे रंग बदलने की अनुमति नहीं देती हैं, लेकिन एक या एक से अधिक चालों से एक बिशप किसी भी वर्ग से उसी रंग के किसी भी अन्य में जा सकता है। दोनों घटक समरूपी होते हैं यदि बोर्ड की एक तरफ की लंबाई सम होती है, लेकिन तब नहीं जब दोनों तरफ विषम हों। बिशप के ग्राफ के एक घटक को हीरे पर एक रुक के ग्राफ के रूप में माना जा सकता है यदि मूल बोर्ड वर्गाकार है और इसके किनारे विषम लंबाई के हैं, क्योंकि यदि लाल वर्ग (मान लीजिए) 45 डिग्री मुड़े हुए हैं, तो बिशप की चालें क्षैतिज और ऊर्ध्वाधर हो जाती हैं, जैसे कि रुक की। कहा जाता है कि एक वर्ग पर एक बिशप द्वारा हमला किया जाता है यदि बिशप ठीक एक चाल में उस वर्ग तक पहुँच सकता है। एक प्रमुख समूह बिशपों की एक ऐसी व्यवस्था है कि प्रत्येक वर्ग पर उन बिशपों में से एक द्वारा हमला किया जाता है या उस पर कब्जा कर लिया जाता है। एक स्वतंत्र हावी समूह एक हावी समूह है जिसमें कोई भी बिशप किसी अन्य पर हमला नहीं करता है। पक्ष एन के वर्गाकार बोर्ड पर हावी होने के लिए आवश्यक बिशपों की न्यूनतम संख्या बिल्कुल एन है, और यह बिशपों की सबसे छोटी संख्या भी है जो एक स्वतंत्र हावी समूह बना सकते हैं। इसके विपरीत, एक कुल वर्चस्व सेट, जो एक हावी सेट है, जिसके लिए बिशप द्वारा कब्जा किए गए लोगों सहित प्रत्येक वर्ग पर बिशपों में से एक द्वारा हमला किया जाता है, के लिए अधिक बिशप की आवश्यकता होती है; पक्ष के वर्ग बोर्ड पर n ≤ 3, कुल प्रभुत्व वाले सेट का सबसे कम आकार न्यूनतम प्रभुत्व वाले सेट से लगभग 1/3 बड़ा होता है। संदर्भ ग्राफ सिद्धांत गणितीय शतरंज की समस्याएं शतरंज से संबंधित सूचियाँ