Bishop's graph
ریاضی میں، بشپ کا گراف ایک گراف ہے جو شطرنج کے ٹکڑے کی تمام قانونی چالوں کی نمائندگی کرتا ہے۔ ہر ورٹیکس شطرنج بورڈ پر ایک مربع کی نمائندگی کرتا ہے اور ہر کنارے بشپ کی قانونی حرکت کی نمائندگی کرتا ہے۔ یعنی، دو عمودی (مربع) کے درمیان ایک کنارے ہوتا ہے اگر وہ ایک مشترکہ اخترن پر قابض ہوں۔ جب شطرنج بورڈ کے طول و عرض ہوتے ہیں، تو انڈیوسڈ گراف کو بشپ گراف کہا جاتا ہے۔ خصوصیات حقیقت یہ ہے کہ شطرنج بورڈ میں دو رنگوں کے مربع ہوتے ہیں، جیسے کہ سرخ اور سیاہ، جیسے کہ افقی یا عمودی طور پر ملحقہ مربع مخالف رنگ کے ہوتے ہیں، اس سے یہ ظاہر ہوتا ہے کہ بشپ کے گراف میں دو جڑے ہوئے اجزاء ہوتے ہیں، جن کے ورٹیکس سیٹ بالترتیب سرخ اور سیاہ مربع ہوتے ہیں۔ وجہ یہ ہے کہ بشپ کی اخترن حرکتیں اسے رنگ تبدیل کرنے کی اجازت نہیں دیتی ہیں، لیکن ایک یا ایک سے زیادہ چالوں سے ایک بشپ کسی بھی مربع سے اسی رنگ کے کسی دوسرے حصے میں جا سکتا ہے۔ دونوں اجزاء آئسومورفک ہوتے ہیں اگر بورڈ کی لمبائی یکساں ہو، لیکن اس صورت میں نہیں جب دونوں اطراف عجیب ہوں۔ بشپ کے گراف کے ایک جزو کو ہیرے پر روک کے گراف کے طور پر سمجھا جا سکتا ہے اگر اصل بورڈ مربع ہے اور اس کے اطراف عجیب لمبائی کے ہیں، کیونکہ اگر سرخ مربع (جیسے) 45 ڈگری مڑے ہوئے ہیں، تو بشپ کی حرکتیں افقی اور عمودی ہو جاتی ہیں، بالکل روک کی طرح۔ اگر بشپ بالکل ایک حرکت میں اس چوک تک پہنچ سکتا ہے تو کہا جاتا ہے کہ ایک چوک پر بشپ حملہ کرتا ہے۔ غالب سیٹ بشپوں کا ایک ایسا انتظام ہے جس میں ہر چوک پر ان بشپوں میں سے ایک حملہ کرتا ہے یا اس پر قبضہ کرتا ہے۔ ایک آزاد غالب سیٹ ایک غالب سیٹ ہے جس میں کوئی بشپ کسی دوسرے پر حملہ نہیں کرتا ہے۔ سائیڈ n کے مربع بورڈ پر غلبہ حاصل کرنے کے لیے درکار بشپوں کی کم از کم تعداد بالکل n ہے، اور یہ بشپوں کی سب سے چھوٹی تعداد بھی ہے جو ایک آزاد غالب سیٹ تشکیل دے سکتی ہے۔ اس کے برعکس، ایک کل غلبہ سیٹ، جو ایک غالب سیٹ ہے جس کے لیے ہر مربع، بشمول بشپوں کے زیر قبضہ افراد، پر بشپوں میں سے ایک حملہ کرتا ہے، اس کے لیے زیادہ بشپوں کی ضرورت ہوتی ہے۔ طرف کے مربع بورڈ n ≤ 3 پر، کل غالب سیٹ کا کم سے کم سائز کم سے کم غالب سیٹ سے تقریبا 1/3 بڑا ہوتا ہے۔ حوالہ جات گراف تھیوری ریاضیاتی شطرنج کے مسائل شطرنج سے متعلق فہرستیں