Schnyder's theorem
গ্রাফ তত্ত্বে, স্নাইডারের উপপাদ্য হল প্ল্যানার গ্রাফগুলির একটি বৈশিষ্ট্য যা তাদের আপতন অবস্থানের ক্রম মাত্রার পরিপ্রেক্ষিতে। ওয়াল্টার শ্নাইডারের নামে এর নামকরণ করা হয়েছে, যিনি 1989 সালে এর প্রমাণ প্রকাশ করেছিলেন। ভার্টেক্স সেট এবং এজ সেট সহ একটি অনির্দিষ্ট গ্রাফের আপতন অবস্থান হল উচ্চতা 2-এর আংশিকভাবে ক্রমযুক্ত সেট যা তার উপাদান হিসাবে রয়েছে। এই আংশিক ক্রমে, একটি ক্রম সম্পর্ক রয়েছে যখন একটি শীর্ষ, একটি প্রান্ত, এবং এর দুটি শেষ বিন্দুর মধ্যে একটি। একটি আংশিক ক্রমের ক্রমের মাত্রা হল মোট ক্রমের ক্ষুদ্রতম সংখ্যা যার ছেদ প্রদত্ত আংশিক ক্রম; এই ধরনের ক্রমের সেটকে আংশিক ক্রমের রিয়েলাইজার বলা হয়। শ্নাইডারের উপপাদ্য বলে যে একটি গ্রাফ সমতল হয় যদি এবং শুধুমাত্র যদি এর ক্রমের মাত্রা সর্বাধিক তিন হয়। সম্প্রসারণ এই উপপাদ্যটি উচ্চতার মাত্রার উপর একটি শক্ত সীমানা দ্বারা সাধারণীকরণ করা হয়েছে-একটি উত্তল পলিহেড্রনের শীর্ষ, প্রান্ত এবং মুখ থেকে অনুরূপভাবে গঠিত তিনটি আংশিকভাবে ক্রমযুক্ত সেট, বা আরও সাধারণভাবে একটি এমবেডেড প্ল্যানার গ্রাফেরঃ উভয় ক্ষেত্রেই, পজিটের ক্রম মাত্রা সর্বাধিক চারটি হয়। যাইহোক, এই ফলাফলটি উচ্চ-মাত্রিক উত্তল পলিটোপগুলিতে সাধারণীকরণ করা যায় না, কারণ চার-মাত্রিক পলিটোপ রয়েছে যার মুখের জালগুলির সীমাহীন ক্রমের মাত্রা রয়েছে। আরও সাধারণভাবে, বিমূর্ত সরল জটিলতাগুলির জন্য, জটিলটির মুখের অবস্থানের ক্রম মাত্রা সর্বাধিক, যেখানে একটি ইউক্লিডীয় স্থানের সর্বনিম্ন মাত্রা যেখানে জটিলটির জ্যামিতিক উপলব্ধি রয়েছে। অন্যান্য গ্রাফ যেমন শ্নাইডার পর্যবেক্ষণ করেছেন, একটি গ্রাফ জি-এর আপতন অবস্থানের ক্রম মাত্রা দুই থাকে যদি এবং শুধুমাত্র যদি গ্রাফটি একটি পথ বা একটি পথের উপগ্রাফ হয়। কারণ, যখন কোনও আপতন অবস্থানের ক্রমের মাত্রা দুই হয়, তখন তার একমাত্র সম্ভাব্য অনুধাবনকারী দুটি মোট ক্রম নিয়ে গঠিত যা (যখন গ্রাফের শীর্ষে সীমাবদ্ধ থাকে) একে অপরের বিপরীত হয়। অন্য যে কোনও দুটি অর্ডারে একটি ছেদ থাকবে যার মধ্যে দুটি শীর্ষের মধ্যে একটি অর্ডার সম্পর্ক অন্তর্ভুক্ত থাকবে, যা আপতন অবস্থানের জন্য অনুমোদিত নয়। শীর্ষে এই দুটি ক্রমের জন্য, পরপর শীর্ষগুলির মধ্যে একটি প্রান্ত দুটি প্রান্তের শেষ বিন্দুর পরে অবিলম্বে স্থাপন করে ক্রমানুসারে অন্তর্ভুক্ত করা যেতে পারে, তবে অন্য কোনও প্রান্ত অন্তর্ভুক্ত করা যাবে না। যদি একটি গ্রাফকে চারটি রঙে রঙ করা যায়, তবে তার আপতন অবস্থানের ক্রম মাত্রা সর্বাধিক চারটি। n শীর্ষে একটি সম্পূর্ণ গ্রাফের আপতন অবস্থানের ক্রম মাত্রা রয়েছে। রেফারেন্স। । । । । । গ্রাফ তত্ত্বে ক্রম তত্ত্ব প্ল্যানার গ্রাফ উপপাদ্য