Graph pebbling
গ্রাফ পেবলিং হল একটি গাণিতিক খেলা যা প্রতিটি শীর্ষে শূন্য বা তার বেশি নুড়ি সহ একটি গ্রাফের উপর খেলা হয়। 'গেম প্লে' পেবলিং চালের একটি সিরিজ নিয়ে গঠিত। একটি গ্রাফের উপর একটি পেবলিং মুভ কমপক্ষে দুটি পেবল সহ একটি শীর্ষ নির্বাচন করে, এটি থেকে দুটি পেবল সরিয়ে এবং একটি সংলগ্ন শীর্ষে যোগ করে (দ্বিতীয় সরানো পেবলটি খেলা থেকে ফেলে দেওয়া হয়)। π (G), একটি গ্রাফ G-এর পেবলিং সংখ্যা, হল সর্বনিম্ন প্রাকৃতিক সংখ্যা n যা নিম্নলিখিত শর্তটি পূরণ করেঃ গ্রাফের যে কোনও লক্ষ্য বা 'মূল' শীর্ষ এবং গ্রাফের n পেবলের যে কোনও প্রাথমিক বিন্যাসের পরিপ্রেক্ষিতে, পেবলিং পদক্ষেপের একটি সিরিজের পরে, একটি নতুন বিন্যাসে পৌঁছানো সম্ভব, যেখানে মনোনীত মূল শীর্ষে এক বা একাধিক পেবল রয়েছে। উদাহরণস্বরূপ, 2টি শীর্ষ এবং 1টি প্রান্ত যুক্ত একটি গ্রাফে পেবলিং সংখ্যা হল 2। গ্রাফের শীর্ষে দুটি নুড়ি যতই থাকুক না কেন, গ্রাফের যে কোনও শীর্ষে একটি নুড়ি সরানো সর্বদা সম্ভব। গ্রাফ পেবলিংয়ের কেন্দ্রীয় প্রশ্নগুলির মধ্যে একটি হল প্রদত্ত গ্রাফ জি-এর জন্য π (জি)-এর মান। পেবলিংয়ের অন্যান্য বিষয়গুলির মধ্যে রয়েছে কভার পেবলিং, সর্বোত্তম পেবলিং, আধিপত্য কভার পেবলিং, সীমানা এবং পেবলিং সংখ্যার জন্য থ্রেশহোল্ড, পাশাপাশি গভীর গ্রাফ। π (G)-একটি গ্রাফের পেবলিং সংখ্যা পেবলিং খেলার প্রথম প্রস্তাব করেছিলেন লাগারিয়াস এবং সাক্স, সংখ্যা তত্ত্বের একটি নির্দিষ্ট সমস্যা সমাধানের হাতিয়ার হিসাবে। 1989 সালে এফ. আর. কে. চুং সাহিত্যে ধারণাটি প্রবর্তন করেন এবং পেবলিং সংখ্যা, π (G) সংজ্ঞায়িত করেন। n শীর্ষে একটি সম্পূর্ণ গ্রাফের জন্য পেবলিং সংখ্যাটি সহজেই n হিসাবে যাচাই করা যায়ঃ যদি আমাদের গ্রাফটি রাখার জন্য (n−1) নুড়ি থাকত, তবে আমরা লক্ষ্য ব্যতীত প্রতিটি শীর্ষে একটি নুড়ি রাখতে পারতাম। যেহেতু কোনও শীর্ষে দুই বা ততোধিক নুড়ি থাকে না, তাই কোনও নড়াচড়া সম্ভব নয়, তাই লক্ষ্যে একটি নুড়ি স্থাপন করা অসম্ভব। সুতরাং, পেবলিং সংখ্যাটি অবশ্যই n-1 এর চেয়ে বড় হতে হবে। n নুড়ি দেওয়া হলে, দুটি সম্ভাব্য কেস রয়েছে। যদি প্রতিটি শীর্ষে একটি নুড়ি থাকে, তবে কোনও পদক্ষেপের প্রয়োজন হয় না। যদি কোনও শীর্ষ খালি থাকে, তবে কমপক্ষে অন্য একটি শীর্ষে অবশ্যই দুটি নুড়ি থাকতে হবে এবং একটি নুড়ি বাঁধার পদক্ষেপ সম্পূর্ণ গ্রাফের যে কোনও লক্ষ্য শীর্ষে একটি নুড়ি যুক্ত করার অনুমতি দেয়। π (G) গ্রাফের পরিবারের জন্য পেবলিং সংখ্যাটি নিম্নলিখিত গ্রাফের পরিবারের জন্য পরিচিতঃ, যেখানে n শীর্ষে একটি সম্পূর্ণ গ্রাফ রয়েছে। , যেখানে n শীর্ষে একটি পাথ গ্রাফ রয়েছে। , যেখানে n শীর্ষে একটি চাকা গ্রাফ রয়েছে। গ্রাহামের পেবলিং অনুমান রোনাল্ড গ্রাহামকে এই অনুমানের জন্য কৃতিত্ব দেয় যে গ্রাফের একটি কার্টেসিয়ান পণ্যের পেবলিং সংখ্যা পণ্যের উপাদানগুলির পেবলিং সংখ্যার গুণফলের সর্বাধিক সমান। এটি গ্রাহামের পেবলিং কনজেকচার নামে পরিচিত। , এটি অমীমাংসিত রয়ে গেছে, যদিও বিশেষ ক্ষেত্রে জানা যায়। γ (G)-একটি গ্রাফ ক্রাল এট আল-এর প্রচ্ছদ পেবলিং সংখ্যা। প্রচ্ছদ পেবলিংয়ের ধারণাটি প্রবর্তন করে। γ (G), একটি গ্রাফের প্রচ্ছদ নুড়ি সংখ্যা হল নুড়ি পাথরের ন্যূনতম সংখ্যা যাতে নুড়ি পাথরের যে কোনও প্রাথমিক বিন্যাস থেকে, নুড়ি পাথরের একাধিক পদক্ষেপের পরে, গ্রাফটি আবৃত থাকেঃ প্রতিটি শীর্ষে কমপক্ষে একটি নুড়ি পাথর থাকে। স্ট্যাকিং উপপাদ্য নামে একটি ফলাফল যে কোনও গ্রাফের জন্য প্রচ্ছদ পেবলিং সংখ্যা খুঁজে পায়। স্ট্যাকিং উপপাদ্য স্ট্যাকিং উপপাদ্য অনুসারে, নুড়িগুলির প্রাথমিক বিন্যাস যার জন্য সর্বাধিক নুড়িগুলির সমাধান করা প্রয়োজন তখন ঘটে যখন সমস্ত নুড়িগুলি একটি একক শীর্ষে স্থাপন করা হয়। এই পর্যবেক্ষণের উপর ভিত্তি করে, জি-তে প্রতিটি শীর্ষ v-এর জন্য সংজ্ঞায়িত করুন, যেখানে d (u, v) u থেকে v-এর দূরত্ব নির্দেশ করে। γ (G) গ্রাফের পরিবারের জন্য প্রচ্ছদ পেবলিং সংখ্যাটি নিম্নলিখিত গ্রাফের পরিবারের জন্য পরিচিতঃ, যেখানে n শীর্ষে একটি সম্পূর্ণ গ্রাফ রয়েছে। , যেখানে n শীর্ষে একটি পথ রয়েছে। , যেখানে n শীর্ষে একটি চাকা গ্রাফ রয়েছে। আরও দেখুন পেবল গেম প্রুফ অফ স্পেস রেফারেন্স আরও পড়া গ্রাফ অপরিবর্তনীয়