Bishop's graph
গণিতে, একজন বিশপের গ্রাফ হল এমন একটি গ্রাফ যা একটি দাবা বোর্ডে বিশপের দাবা অংশের সমস্ত আইনি পদক্ষেপের প্রতিনিধিত্ব করে। প্রতিটি শীর্ষ দাবা বোর্ডে একটি বর্গক্ষেত্রের প্রতিনিধিত্ব করে এবং প্রতিটি প্রান্ত বিশপের একটি আইনি পদক্ষেপের প্রতিনিধিত্ব করে; অর্থাৎ, দুটি শীর্ষের (বর্গক্ষেত্র) মধ্যে একটি প্রান্ত থাকে যদি তারা একটি সাধারণ তির্যক দখল করে। যখন দাবা বোর্ডের মাত্রা থাকে, তখন প্ররোচিত গ্রাফটিকে বিশপের গ্রাফ বলা হয়। বৈশিষ্ট্য দাবা বোর্ডে দুটি রঙের বর্গ রয়েছে, যেমন লাল এবং কালো, যেমন অনুভূমিকভাবে বা উল্লম্বভাবে সংলগ্ন বর্গগুলির বিপরীত রঙ রয়েছে, যা বোঝায় যে বিশপের গ্রাফের দুটি সংযুক্ত উপাদান রয়েছে, যার শীর্ষ সেটগুলি যথাক্রমে লাল এবং কালো বর্গক্ষেত্র। কারণটি হল যে বিশপের তির্যক পদক্ষেপগুলি এটিকে রঙ পরিবর্তন করতে দেয় না, তবে এক বা একাধিক পদক্ষেপের মাধ্যমে একজন বিশপ যে কোনও বর্গক্ষেত্র থেকে একই রঙের অন্য যে কোনও জায়গায় যেতে পারেন। দুটি উপাদান আইসোমরফিক হয় যদি বোর্ডের জোড় দৈর্ঘ্যের একটি দিক থাকে, তবে উভয় পক্ষই বিজোড় হলে তা হয় না। বিশপের গ্রাফের একটি উপাদানকে হীরার উপর রুকের গ্রাফ হিসাবে বিবেচনা করা যেতে পারে যদি মূল বোর্ডটি বর্গাকার হয় এবং এর দিকগুলি বিজোড় দৈর্ঘ্যের হয়, কারণ যদি লাল বর্গগুলি (বলুন) 45 ডিগ্রি ঘোরানো হয়, তবে বিশপের পদক্ষেপগুলি অনুভূমিক এবং উল্লম্ব হয়ে যায়, ঠিক রুকের মতো। একটি বর্গক্ষেত্রকে একজন বিশপের দ্বারা আক্রান্ত বলা হয় যদি বিশপ ঠিক এক পদক্ষেপে সেই বর্গক্ষেত্রে পৌঁছতে পারেন। একটি প্রভাবশালী সেট হল বিশপদের এমন একটি ব্যবস্থা যাতে প্রতিটি চত্বর সেই বিশপদের মধ্যে একজনের দ্বারা আক্রান্ত বা দখল করা হয়। একটি স্বাধীন প্রভাবশালী সেট হল একটি প্রভাবশালী সেট যেখানে কোনও বিশপ অন্য কাউকে আক্রমণ করে না। সাইড এন-এর একটি বর্গাকার বোর্ডে আধিপত্য বিস্তারের জন্য ন্যূনতম সংখ্যক বিশপের প্রয়োজন হয় ঠিক এন, এবং এটিই সবচেয়ে কম সংখ্যক বিশপ যারা একটি স্বাধীন প্রভাবশালী সেট গঠন করতে পারে। বিপরীতে, একটি মোট আধিপত্য সেট, যা একটি প্রভাবশালী সেট, যার জন্য বিশপদের দখলে থাকা সহ প্রতিটি বর্গক্ষেত্র বিশপদের মধ্যে একজনের দ্বারা আক্রান্ত হয়, তার জন্য আরও বিশপের প্রয়োজন হয়; পাশের বর্গ বোর্ডে n ≤ 3, মোট আধিপত্য সেটের সর্বনিম্ন আকার ন্যূনতম প্রভাবশালী সেটের চেয়ে প্রায় 1/3 বড়। তথ্যসূত্র গ্রাফ তত্ত্ব গাণিতিক দাবা সমস্যা দাবা-সম্পর্কিত তালিকা