Queen's graph
গণিতে, রানীর গ্রাফ হল একটি অনির্দিষ্ট গ্রাফ যা একটি দাবা বোর্ডে রানীর সমস্ত আইনি পদক্ষেপ-একটি দাবার টুকরো-উপস্থাপন করে। গ্রাফটিতে, প্রতিটি শীর্ষ একটি দাবা বোর্ডের একটি বর্গক্ষেত্রের প্রতিনিধিত্ব করে এবং প্রতিটি প্রান্ত একটি বৈধ পদক্ষেপ যা রানী করতে পারেন, অর্থাৎ, যে কোনও সংখ্যক বর্গক্ষেত্র দ্বারা অনুভূমিক, উল্লম্ব বা তির্যক পদক্ষেপ। যদি দাবা বোর্ডের মাত্রা থাকে, তবে প্ররোচিত গ্রাফটিকে রানীর গ্রাফ বলা হয়। গ্রাফের স্বাধীন সেটগুলি একাধিক রানীর বসতির সাথে মিলে যায় যেখানে কোনও দুই রানী একে অপরকে আক্রমণ করছে না। তাদের আটটি রানী ধাঁধার মধ্যে অধ্যয়ন করা হয়, যেখানে আটটি অ-আক্রমণকারী রানীকে একটি আদর্শ দাবা বোর্ডে রাখা হয়। প্রভাবশালী সেটগুলি রানীদের ব্যবস্থার প্রতিনিধিত্ব করে যেখানে প্রতিটি বর্গক্ষেত্র একজন রানী দ্বারা আক্রান্ত বা দখল করা হয়; পাঁচজন রানী, তবে কম নয়, দাবা বোর্ডে আধিপত্য বিস্তার করতে পারে। গ্রাফের রঙগুলি প্রতিটি বর্গক্ষেত্রকে রঙ করার উপায়গুলি উপস্থাপন করে যাতে একজন রানী একই রঙের যে কোনও দুটি বর্গক্ষেত্রের মধ্যে চলাচল করতে না পারে; একটি দাবা বোর্ডের জন্য কমপক্ষে এন রঙের প্রয়োজন হয়, তবে বোর্ডের জন্য 9 টি রঙের প্রয়োজন হয়। বৈশিষ্ট্য প্রতিটি রানীর গ্রাফের জন্য একটি হ্যামিল্টনিয়ান চক্র রয়েছে এবং গ্রাফগুলি দ্বি-সংযুক্ত থাকে (যদি কোনও একক শীর্ষ অপসারণ করা হয় তবে সেগুলি সংযুক্ত থাকে)। এবং রানীর গ্রাফের বিশেষ কেসগুলি সম্পূর্ণ। স্বাধীনতা গ্রাফের একটি স্বাধীন সেট একটি দাবা বোর্ডে বেশ কয়েকটি রানীর স্থাপনার সাথে মিলে যায় যাতে কোনও দুই রানী একে অপরকে আক্রমণ না করে। একটি দাবা বোর্ডে, বৃহত্তম স্বাধীন সেটটিতে সর্বাধিক n শীর্ষ থাকে, কারণ কোনও দুই রানী একই সারি বা কলামে থাকতে পারে না। এই ঊর্ধ্বসীমা n = 2 এবং n = 3 ব্যতীত সমস্ত n-এর জন্য অর্জন করা যেতে পারে। এন = 8-এর ক্ষেত্রে, এটি ঐতিহ্যবাহী আট রানীর ধাঁধা। আধিপত্য রানীর গ্রাফের একটি প্রভাবশালী সেট রানীদের বসানোর সাথে এমনভাবে মিলে যায় যে দাবা বোর্ডের প্রতিটি বর্গক্ষেত্র হয় রানী দ্বারা আক্রান্ত বা দখল করা হয়। একটি দাবা বোর্ডে, পাঁচজন রানী আধিপত্য বিস্তার করতে পারে এবং এটি সর্বনিম্ন সম্ভাব্য সংখ্যা (চারজন রানী কমপক্ষে দুটি বর্গক্ষেত্র আক্রমণ ছাড়াই রেখে যায়)। পাঁচটি রানীর 4,860 টি প্লেসমেন্ট রয়েছে, যার মধ্যে রানীরা নিয়ন্ত্রণ করে এমন সমস্ত বর্গক্ষেত্রও রয়েছে, অর্থাৎ। তারা একে অপরকে রক্ষা করার জন্য যথাক্রমে আক্রমণ করে। এই উপগোষ্ঠীতে, এমন অবস্থানও রয়েছে যেখানে রানীরা শুধুমাত্র প্রধান তির্যকের বর্গক্ষেত্র দখল করে (যেমন। a1 থেকে h8 পর্যন্ত), অথবা সবগুলি একটি উপ-তির্যকের উপর (যেমন। এ2 থেকে জি8)। একটি টরাস বা সিলিন্ডার দিয়ে অ-লুপিং আয়তক্ষেত্রাকার দাবা বোর্ড প্রতিস্থাপন করে গ্রাফ পরিবর্তন করা সর্বনিম্ন প্রভাবশালী সেটের আকারকে চারটিতে কমিয়ে দেয়। রানীর গ্রাফটি বোর্ডের কেন্দ্রে একক শীর্ষ দ্বারা প্রভাবিত হয়। রানীর গ্রাফের কেন্দ্রের শীর্ষটি 8টি শীর্ষ ছাড়া বাকি সবগুলির সংলগ্নঃ সেই শীর্ষগুলি যা নাইটের গ্রাফের কেন্দ্রের শীর্ষের সংলগ্ন। একটি রানীর গ্রাফের আধিপত্য সংখ্যা d (n) কে ক্ষুদ্রতম আধিপত্য সেটের আকার হিসাবে সংজ্ঞায়িত করুন এবং তির্যক আধিপত্য সংখ্যা dd (n) কে ক্ষুদ্রতম আধিপত্য সেটের আকার হিসাবে সংজ্ঞায়িত করুন যা দীর্ঘ তির্যকের একটি উপসেট। লক্ষ্য করুন যে সমস্ত n-এর জন্য সীমাটি প্রাপ্ত হয়, কিন্তু জন্য নয়। আধিপত্য সংখ্যাটি n-এ রৈখিক, যার দ্বারা প্রদত্ত সীমাঃ d (n)-এর প্রাথমিক মানগুলি হল 1,1,1,2,3,3,4,5,5,5। Kn কে এমন একটি উপসেটের সর্বোচ্চ আকার হিসাবে ধরা যাক যাতে প্রতিটি সংখ্যার একই সমতা থাকে এবং কোনও তিনটি সংখ্যা একটি গাণিতিক অগ্রগতি গঠন করে না (সেটটি "মধ্যবিন্দু-মুক্ত")। একটি রানীর গ্রাফের তির্যক আধিপত্য সংখ্যা হল। স্বাধীন আধিপত্য সংখ্যা আইডি (এন)-কে রানীর গ্রাফের ক্ষুদ্রতম স্বাধীন, প্রভাবশালী সেটের আকার হিসাবে সংজ্ঞায়িত করুন। এটা জানা যায়। রঙ করা রানীর গ্রাফের একটি রঙ প্রতিটি শীর্ষে রঙের একটি বরাদ্দ যাতে কোনও দুটি সংলগ্ন শীর্ষকে একই রঙ দেওয়া না হয়। উদাহরণস্বরূপ, যদি এ8 লাল রঙের হয় তবে এ-ফাইলের অন্য কোনও বর্গ, অষ্টম র্যাঙ্ক বা দীর্ঘ তির্যক লাল রঙের হতে পারে না, কারণ একজন রানী এ8 থেকে এই বর্গগুলির যে কোনও একটিতে যেতে পারে। গ্রাফের ক্রোমাটিক সংখ্যা হল সবচেয়ে কম সংখ্যক রঙ যা এটিকে রঙ করার জন্য ব্যবহার করা যেতে পারে। রানীর গ্রাফের ক্ষেত্রে, কমপক্ষে এন রঙের প্রয়োজন হয়, কারণ একটি র্যাঙ্ক বা ফাইলের প্রতিটি বর্গক্ষেত্রের জন্য আলাদা রঙের প্রয়োজন হয় (অর্থাৎ। সারি এবং কলামগুলি হল চক্র)। ক্রোমাটিক সংখ্যাটি ঠিক n হয় যদি (অর্থাৎ। n হল 6 এর গুণিতক থেকে এক গুণ বেশি বা এক গুণ কম)। একটি রানীর গ্রাফের ক্রোমাটিক সংখ্যা হল 9। অপ্রতিরোধ্য শীর্ষগুলির একটি সেট অপ্রতিরোধ্য হয় যদি সেট থেকে কোনও শীর্ষ অপসারণ সেটের আশেপাশের পরিবর্তন করে অর্থাৎ। প্রতিটি শীর্ষের জন্য, একটি সংলগ্ন শীর্ষ থাকে যা সেটের অন্য কোনও শীর্ষের সংলগ্ন নয়। এটি রানীদের একটি সেটের সাথে মিলে যায় যা প্রত্যেকে কমপক্ষে একটি বর্গক্ষেত্রকে অনন্যভাবে নিয়ন্ত্রণ করে। রানীর গ্রাফের একটি অপ্রয়োজনীয় সেটের সর্বাধিক আকারের আইআর (এন) চিহ্নিত করা কঠিন; পরিচিত মানগুলির মধ্যে রয়েছে অনুসরণ-ফাঁকি খেলা নিম্নলিখিত নিয়ম অনুসারে একটি রানীর গ্রাফের অনুসরণ-ফাঁকি খেলাটি বিবেচনা করুনঃ একটি সাদা রানী এক কোণে এবং বিপরীত কোণে একটি কালো রানী শুরু হয়। খেলোয়াড়দের বিকল্প পদক্ষেপ, যা রানীকে একটি সংলগ্ন শীর্ষে সরিয়ে নিয়ে যায় যা অতিক্রম না করে (অনুভূমিকভাবে, উল্লম্বভাবে বা তির্যকভাবে) বা বিপরীত রানীর সংলগ্ন একটি শীর্ষে অবতরণ না করে পৌঁছানো যায়। এই খেলাটি সাদা একটি জুটির কৌশলের মাধ্যমে জিততে পারে। আরও দেখুন কিংস গ্রাফ নাইটের গ্রাফ রুকের গ্রাফ বিশপের গ্রাফ রেফারেন্স গাণিতিক দাবা সমস্যা গ্রাফের প্যারামেট্রিক পরিবার