Heawood conjecture
গ্রাফ তত্ত্বে, হিউড অনুমান বা রিঙ্গেল-ইয়ংস উপপাদ্য একটি প্রদত্ত বংশের পৃষ্ঠে গ্রাফের রঙের জন্য প্রয়োজনীয় রঙের সংখ্যার জন্য একটি নিম্ন সীমা দেয়। 0, 1, 2, 3, 4, 5, 6, 7,. গণের পৃষ্ঠতলের জন্য প্রয়োজনীয় রঙের সংখ্যা হল 4,7,8,9,10,11,12,, ক্রোমাটিক সংখ্যা বা হিউড সংখ্যা। অনুমানটি 1890 সালে পার্সি জন হিউড দ্বারা প্রণয়ন করা হয়েছিল এবং 1968 সালে গেরহার্ড রিঙ্গেল এবং টেড ইয়ংস দ্বারা প্রমাণিত হয়েছিল। একটি ক্ষেত্রে, অ-অভিমুখী ক্লেইন বোতল, সাধারণ সূত্রের ব্যতিক্রম হিসাবে প্রমাণিত হয়েছিল। সমতল বা গোলকের জন্য প্রয়োজনীয় রঙের সংখ্যা খুঁজে বের করার অনেক পুরনো সমস্যার জন্য একটি সম্পূর্ণ ভিন্ন পদ্ধতির প্রয়োজন ছিল, যা 1976 সালে হ্যাকেন এবং অ্যাপেল দ্বারা চার রঙের উপপাদ্য হিসাবে সমাধান করা হয়েছিল। গোলকের উপর নীচের সীমাটি সহজ, যেখানে উচ্চতর গণের জন্য উপরের সীমাটি সহজ এবং হিউডের মূল ছোট কাগজে প্রমাণিত হয়েছিল যেখানে অনুমানটি ছিল। অন্য কথায়, রিঙ্গেল, ইয়াংগস এবং অন্যান্যদের প্রতিটি গণের জন্য চরম উদাহরণ তৈরি করতে হয়েছিল জি = 1,2,3,। যদি g = 12s + k হয়, তবে k = 0,1,2,3,4,5,6,7,8,9,10,11 অনুসারে জেনেরাটি 12টি ক্ষেত্রে পড়ে। সহজ করার জন্য, ধরুন যে কেস k প্রতিষ্ঠিত হয়েছে যদি 12s + k ফর্মের শুধুমাত্র একটি সীমাবদ্ধ সংখ্যক g সন্দেহের মধ্যে থাকে। তারপর যে বছরগুলিতে বারোটি মামলার নিষ্পত্তি হয় এবং যাদের দ্বারা নিম্নলিখিতগুলি করা হয়ঃ 1954, রিঙ্গেলঃ কেস 5,1961, রিঙ্গেলঃ কেস 3,7,10 1963, টেরি, ওয়েলচ, ইয়ংসঃ কেস 0,4 1964, গাস্টিন, ইয়ংসঃ কেস 1 1965, গাস্টিনঃ কেস 9 1966, ইয়ংসঃ কেস 6 1967, রিঙ্গেল, ইয়ংসঃ কেস 2,8,11 শেষ সাতটি বিক্ষিপ্ত ব্যতিক্রম নিম্নরূপ নিষ্পত্তি করা হয়েছিলঃ 1967, মায়ারঃ কেস 18,20,23 1968, রিঙ্গেল, ইয়ংসঃ কেস 30,35,47,59, এবং অনুমান প্রমাণিত হয়েছিল। আনুষ্ঠানিক বিবৃতি পার্সি জন হিউড 1890 সালে অনুমান করেছিলেন যে একটি প্রদত্ত গণের জন্য জি> 0, সেই গণের একটি অভিমুখী পৃষ্ঠের উপর আঁকা সমস্ত গ্রাফকে রঙ করার জন্য প্রয়োজনীয় ন্যূনতম রঙের সংখ্যা (বা পৃষ্ঠের যে কোনও বিভাজনের অঞ্চলগুলিকে কেবল সংযুক্ত অঞ্চলে রঙ করার সমতুল্য) দ্বারা দেওয়া হয় যেখানে মেঝের কার্যকারিতা রয়েছে। কুলটিকে অয়লার বৈশিষ্ট্য দ্বারা প্রতিস্থাপিত করে, আমরা একটি সূত্র পাই যা ওরিয়েন্টেবল এবং নন-ওরিয়েন্টেবল উভয় ক্ষেত্রেই অন্তর্ভুক্ত করে, এই সম্পর্কটি, যেমন রিঙ্গেল এবং ইয়ংস দেখিয়েছেন, ক্লেইন বোতল ব্যতীত সমস্ত পৃষ্ঠের জন্য। ফিলিপ ফ্রাঙ্কলিন (1930) প্রমাণ করেছিলেন যে ক্লেইন বোতলে সূত্র দ্বারা ভবিষ্যদ্বাণী করা 7টির পরিবর্তে সর্বাধিক 6টি রঙের প্রয়োজন। ক্লেইন বোতলের উপর ফ্রাঙ্কলিনের গ্রাফটি এমনভাবে আঁকা যেতে পারে যা ছয়টি পারস্পরিক-সংলগ্ন অঞ্চল গঠন করে, যা দেখায় যে এই বন্ধনটি শক্ত। হেউডের মূল ছোট কাগজে প্রমাণিত উপরের সীমাটি একটি লোভী রঙিন অ্যালগরিদমের উপর ভিত্তি করে তৈরি। অয়লার বৈশিষ্ট্যটি ব্যবহার করে, কেউ দেখাতে পারে যে প্রদত্ত পৃষ্ঠে এম্বেড করা প্রতিটি গ্রাফের অবশ্যই প্রদত্ত সীমার চেয়ে কমপক্ষে একটি ডিগ্রি কম থাকতে হবে। যদি কেউ এই শীর্ষস্থানটি সরিয়ে দেয় এবং গ্রাফের বাকি অংশকে রঙ দেয়, তবে অপসারিত শীর্ষে অল্প সংখ্যক প্রান্ত নিশ্চিত করে যে এটি আবার গ্রাফে যোগ করা যেতে পারে এবং সীমার বাইরে প্রয়োজনীয় রঙের সংখ্যা না বাড়িয়ে রঙ করা যেতে পারে। অন্য দিকে, প্রমাণটি আরও কঠিন, এবং এটি দেখানো জড়িত যে প্রতিটি ক্ষেত্রে (ক্লেইন বোতল ব্যতীত) প্রদত্ত রঙের সংখ্যার সমান সংখ্যক শীর্ষ সহ একটি সম্পূর্ণ গ্রাফ পৃষ্ঠে এম্বেড করা যেতে পারে। উদাহরণ টরাসের g = 1, তাই χ = 0। অতএব, সূত্রটি যেমন বলে, অঞ্চলগুলিতে টরাসের যে কোনও উপবিভাগ সর্বাধিক সাতটি রঙ ব্যবহার করে রঙ করা যেতে পারে। চিত্রটি তোরাসের একটি উপবিভাগ দেখায় যেখানে সাতটি অঞ্চলের প্রত্যেকটি একে অপরের অঞ্চলের সংলগ্ন; এই উপবিভাগটি দেখায় যে এই ক্ষেত্রে রঙের সংখ্যার উপর সাতটির সীমা শক্ত। এই মহকুমার সীমানা টোরাসের উপর হিউড গ্রাফের একটি এম্বেডিং গঠন করে। তথ্যসূত্র বাহ্যিক যোগসূত্র গ্রাফ কালারিং টপোলজিক্যাল গ্রাফ তত্ত্ব প্রমাণিত হয়েছে এমন অনুমান গ্রাফ তত্ত্বের উপপাদ্য