Barnette's conjecture
বার্নেটের অনুমান গ্রাফ তত্ত্বের একটি অমীমাংসিত সমস্যা, যা গণিতের একটি শাখা, গ্রাফগুলিতে হ্যামিল্টনিয়ান চক্র সম্পর্কিত। ডেভিসের ক্যালিফোর্নিয়া বিশ্ববিদ্যালয়ের ইমেরিটাস অধ্যাপক ডেভিড ডব্লিউ বার্নেটের নামে এর নামকরণ করা হয়েছে; এতে বলা হয়েছে যে প্রতি শীর্ষে তিনটি প্রান্ত সহ প্রতিটি দ্বিদলীয় পলিহেড্রাল গ্রাফের একটি হ্যামিল্টনিয়ান চক্র থাকে। সংজ্ঞা একটি সমতলীয় গ্রাফ হল একটি অনির্দিষ্ট গ্রাফ যা কোনও ক্রসিং ছাড়াই ইউক্লিডীয় সমতলে এম্বেড করা যেতে পারে। একটি সমতলীয় গ্রাফকে পলিহেড্রাল বলা হয় যদি এবং শুধুমাত্র যদি এটি 3-ভার্টেক্স-সংযুক্ত থাকে, অর্থাৎ, যদি দুটি শীর্ষ না থাকে যার অপসারণ বাকি গ্রাফটিকে বিচ্ছিন্ন করে দেবে। একটি গ্রাফ দ্বিদলীয় হয় যদি এর শীর্ষগুলি দুটি ভিন্ন রঙে রঙ করা যায় যাতে প্রতিটি প্রান্তের প্রতিটি রঙের একটি শেষ বিন্দু থাকে। একটি গ্রাফ ঘন (বা 3-নিয়মিত) হয় যদি প্রতিটি শীর্ষ ঠিক তিনটি প্রান্তের শেষ বিন্দু হয়। পরিশেষে, একটি গ্রাফ হ্যামিল্টনিয়ান হয় যদি এমন একটি চক্র বিদ্যমান থাকে যা তার প্রতিটি শীর্ষের মধ্য দিয়ে ঠিক একবার অতিক্রম করে। বার্নেটের অনুমান অনুযায়ী প্রতিটি ঘন দ্বিদলীয় পলিহেড্রাল গ্রাফ হ্যামিল্টনিয়ান। স্টেনিৎজের উপপাদ্য অনুসারে, একটি সমতলীয় গ্রাফ একটি উত্তল পলিহেড্রনের প্রান্ত এবং শীর্ষগুলিকে প্রতিনিধিত্ব করে যদি এবং শুধুমাত্র যদি এটি পলিহেড্রাল হয়। একটি ত্রিমাত্রিক পলিহেড্রনের একটি ঘন গ্রাফ থাকে যদি এবং শুধুমাত্র যদি এটি একটি সাধারণ পলিহেড্রন হয়। এবং, একটি প্ল্যানার গ্রাফ দ্বিদলীয় হয় যদি এবং শুধুমাত্র যদি, গ্রাফের একটি প্ল্যানার এম্বেডিংয়ে, সমস্ত মুখের চক্রের দৈর্ঘ্য জোড় হয়। অতএব, বার্নেটের অনুমানটি সমতুল্য আকারে বলা যেতে পারেঃ ধরুন যে একটি ত্রিমাত্রিক সরল উত্তল পলিহেড্রনের প্রতিটি মুখে জোড় সংখ্যক প্রান্ত রয়েছে। তারপর, অনুমান অনুসারে, পলিহেড্রনের গ্রাফের একটি হ্যামিল্টনিয়ান চক্র রয়েছে। ইতিহাস অনুমান করেছিল যে প্রতিটি ঘন পলিহেড্রাল গ্রাফ হ্যামিল্টনিয়ান; এটি টেইটের অনুমান হিসাবে পরিচিত হয়েছিল। এটি দ্বারা অস্বীকার করা হয়েছিল, যিনি 46টি শীর্ষ সহ একটি পাল্টা উদাহরণ তৈরি করেছিলেন; অন্যান্য গবেষকরা পরে আরও ছোট পাল্টা উদাহরণ খুঁজে পেয়েছিলেন। যাইহোক, এই পরিচিত পাল্টা উদাহরণগুলির কোনওটিই দ্বিদলীয় নয়। টুট নিজেই অনুমান করেছিলেন যে প্রতিটি ঘন 3-সংযুক্ত দ্বিদলীয় গ্রাফ হ্যামিল্টনিয়ান, তবে একটি পাল্টা উদাহরণ, হর্টন গ্রাফ আবিষ্কারের মাধ্যমে এটি মিথ্যা বলে প্রমাণিত হয়েছিল। প্রতিটি দ্বিদলীয় ঘন পলিহেড্রন হ্যামিল্টনিয়ান, বা সমতুল্যভাবে, যে টেইটের অনুমানের প্রতিটি বিপরীত উদাহরণ অ-দ্বিদলীয় বলে উল্লেখ করে টেইট এবং টুটের অনুমানের একটি দুর্বল সংমিশ্রণের প্রস্তাব করেছিলেন। সমতুল্য রূপগুলি দেখায় যে বার্নেটের অনুমানটি একটি উপরিতলের শক্তিশালী বিবৃতির সমতুল্য, যে একটি দ্বিদলীয় ঘন পলিহেড্রনের একই মুখের প্রতি দুটি প্রান্ত ই এবং এফ-এর জন্য একটি হ্যামিল্টনিয়ান চক্র বিদ্যমান যা ই ধারণ করে তবে এফ ধারণ করে না। স্পষ্টতই, যদি এই বিবৃতিটি সত্য হয়, তবে প্রতিটি দ্বিদলীয় ঘন পলিহেড্রনে একটি হ্যামিল্টনিয়ান চক্র থাকেঃ কেবল ইচ্ছাকৃতভাবে ই এবং এফ নির্বাচন করুন। অন্য দিকে, কেলম্যান দেখিয়েছেন যে একটি পাল্টা উদাহরণ মূল বার্নেট অনুমানের পাল্টা উদাহরণে রূপান্তরিত হতে পারে। বার্নেটের অনুমানটি এই বিবৃতির সমতুল্য যে প্রতিটি ঘন দ্বিদলীয় পলিহেড্রাল গ্রাফের দ্বৈতের শীর্ষগুলিকে দুটি উপসেটে বিভক্ত করা যেতে পারে যার প্ররোচিত উপগ্রাফগুলি গাছ। দ্বৈত আলেখ্যচিত্রে এই ধরনের বিভাজন দ্বারা প্ররোচিত কাটা প্রাথমিক আলেখ্যে হ্যামিল্টনিয়ান চক্রের সাথে মিলে যায়। আংশিক ফলাফল যদিও বার্নেটের অনুমানের সত্যতা অজানা রয়ে গেছে, গণনামূলক পরীক্ষাগুলি দেখিয়েছে যে 86 টিরও কম শীর্ষে কোনও পাল্টা উদাহরণ নেই। যদি বার্নেটের অনুমানটি মিথ্যা প্রমাণিত হয়, তবে একটি দ্বিদলীয় ঘন পলিহেড্রন হ্যামিল্টনিয়ান কিনা তা পরীক্ষা করার জন্য এটি এনপি-সম্পূর্ণ হিসাবে দেখানো যেতে পারে। যদি একটি সমতলীয় গ্রাফ দ্বিদলীয় এবং ঘন হয় তবে কেবল সংযোগ 2-এর হয়, তবে এটি অ-হ্যামিল্টনীয় হতে পারে এবং এই গ্রাফগুলির জন্য হ্যামিল্টনিসিটি পরীক্ষা করা এনপি-সম্পূর্ণ। আরেকটি ফলাফল পাওয়া গেছেঃ যদি দ্বৈত গ্রাফটি নীল, লাল এবং সবুজ রঙের সাথে শীর্ষ-রঙের হতে পারে যাতে প্রতিটি লাল-সবুজ চক্রে ডিগ্রি 4 এর একটি শীর্ষ থাকে, তবে প্রাথমিক গ্রাফটি হ্যামিল্টনিয়ান। সম্পর্কিত সমস্যা বার্নেটের একটি সম্পর্কিত অনুমান বলে যে প্রতিটি ঘন পলিহেড্রাল গ্রাফ যেখানে সমস্ত মুখের ছয় বা তার কম প্রান্ত থাকে তা হ্যামিল্টনিয়ান। গণনামূলক পরীক্ষাগুলি দেখিয়েছে যে, যদি একটি বিপরীত উদাহরণ বিদ্যমান থাকে তবে এটির 177 টিরও বেশি শীর্ষ থাকতে হবে। অনুমানটি দ্বারা প্রমাণিত হয়েছিল। এই দুটি অনুমানের ছেদ হবে যে প্রতিটি দ্বিদলীয় ঘন পলিহেড্রাল গ্রাফ যেখানে সমস্ত মুখের চার বা ছয়টি প্রান্ত রয়েছে তা হ্যামিল্টনিয়ান। এটি সত্য বলে প্রমাণিত হয়েছে। নোটস রেফারেন্স; সায়েন্টিফিক পেপার্স-এ পুনঃমুদ্রিত, খণ্ড। দ্বিতীয়, পিপি। 85-98 বাহ্যিক লিঙ্কগুলি ওপেন প্রবলেম গার্ডেনে বার্নেটের অনুমান, রবার্ট সামাল, 2007। অনুমান গ্রাফ তত্ত্বে অমীমাংসিত সমস্যা প্ল্যানার গ্রাফ হ্যামিল্টনিয়ান পথ এবং চক্র