Tutte theorem
গ্রাফ তত্ত্বের গাণিতিক শাখায় উইলিয়াম থমাস টুটের নামে নামকরণ করা টুট উপপাদ্যটি নিখুঁত মিল সহ সীমাবদ্ধ অনির্দিষ্ট গ্রাফের একটি বৈশিষ্ট্য। এটি হলের বিবাহ উপপাদ্যের দ্বিদলীয় থেকে নির্বিচারে গ্রাফের একটি সাধারণীকরণ। এটি টুটে-বর্জ সূত্রের একটি বিশেষ উদাহরণ। অন্তর্দৃষ্টি লক্ষ্য হল এমন সমস্ত গ্রাফকে চিহ্নিত করা যার একটি নিখুঁত মিল নেই। নিখুঁত মিল ছাড়াই একটি গ্রাফের সবচেয়ে সুস্পষ্ট কেস দিয়ে শুরু করুনঃ বিজোড় সংখ্যক শীর্ষ সহ একটি গ্রাফ। এই ধরনের আলেখ্যে, যে কোনও মিল থাকা অন্তত একটি অতুলনীয় শীর্ষস্থান রেখে যায়, তাই এটি নিখুঁত হতে পারে না। সামান্য বেশি সাধারণ ক্ষেত্রে একটি সংযোগ বিচ্ছিন্ন গ্রাফ হয় যেখানে এক বা একাধিক উপাদানের বিজোড় সংখ্যক শীর্ষ থাকে (এমনকি শীর্ষগুলির মোট সংখ্যা জোড় হলেও)। আসুন আমরা এই ধরনের উপাদানগুলিকে বিজোড় উপাদান বলি। যে কোনও মিলনের ক্ষেত্রে, প্রতিটি শীর্ষ শুধুমাত্র একই উপাদানের শীর্ষগুলির সাথে মিলিত হতে পারে। অতএব, যে কোনও মিল প্রতিটি বিজোড় উপাদানের মধ্যে কমপক্ষে একটি অতুলনীয় শীর্ষ রেখে যায়, তাই এটি নিখুঁত হতে পারে না। এরপরে, একটি গ্রাফ জি-কে এমনভাবে বিবেচনা করুন যাতে, আমরা যদি জি থেকে শীর্ষ ইউ এবং তার সংলগ্ন প্রান্তগুলি সরিয়ে ফেলি, তবে অবশিষ্ট গ্রাফটিতে (চিহ্নিত) দুই বা ততোধিক বিজোড় উপাদান থাকে। উপরের মতো, প্রতিটি বিজোড় উপাদানের মধ্যে যে কোনও মিল রেখে যায়, কমপক্ষে একটি শীর্ষ যা একই উপাদানের অন্যান্য শীর্ষগুলির সাথে তুলনাহীন। এই ধরনের একটি শীর্ষ শুধুমাত্র u এর সাথে মিলে যেতে পারে। কিন্তু যেহেতু দুটি বা ততোধিক অতুলনীয় শীর্ষ রয়েছে এবং তাদের মধ্যে কেবল একটিই ইউ-এর সাথে মিলিত হতে পারে, তাই কমপক্ষে অন্য একটি শীর্ষটি অতুলনীয় থাকে, তাই মিলটি নিখুঁত নয়। পরিশেষে, শীর্ষগুলির একটি সেট সহ একটি গ্রাফ জি বিবেচনা করুন যাতে, আমরা যদি জি থেকে শীর্ষগুলি এবং তাদের সংলগ্ন সমস্ত প্রান্তগুলি সরিয়ে ফেলি, তবে অবশিষ্ট গ্রাফটিতে (চিহ্নিত) বিজোড় উপাদানগুলির চেয়ে বেশি থাকে। উপরে যেমন ব্যাখ্যা করা হয়েছে, যে কোনও মিল থাকা প্রতিটি বিজোড় অংশে কমপক্ষে একটি অতুলনীয় শীর্ষ রেখে যায় এবং এগুলি কেবল এর শীর্ষগুলির সাথে মিলিত হতে পারে-তবে এই সমস্ত অতুলনীয় শীর্ষগুলির জন্য পর্যাপ্ত শীর্ষ নেই, তাই মিলটি নিখুঁত নয়। আমরা একটি প্রয়োজনীয় শর্তে পৌঁছেছিঃ যদি জি-এর একটি নিখুঁত মিল থাকে, তবে জি-এর প্রতিটি শীর্ষ উপসেটের জন্য, গ্রাফটিতে সর্বাধিক বিজোড় উপাদান রয়েছে। টুটের উপপাদ্য বলে যে এই শর্তটি নিখুঁত মিলনের অস্তিত্বের জন্য প্রয়োজনীয় এবং যথেষ্ট উভয়ই। টুট্টের উপপাদ্য একটি গ্রাফের একটি নিখুঁত মিল রয়েছে যদি এবং কেবলমাত্র প্রতিটি উপসেটের জন্য, উপগ্রাফটিতে সর্বাধিক বিজোড় উপাদান থাকে (সংযুক্ত উপাদানগুলির একটি বিজোড় সংখ্যক শীর্ষ থাকে)। প্রমাণ প্রথমে আমরা শর্তটি লিখিঃ যেখানে দ্বারা প্ররোচিত সাবগ্রাফের বিজোড় উপাদানগুলির সংখ্যা বোঝায়। এর প্রয়োজনীয়তাঃ এই দিকটি ইতিমধ্যে নীচের ইনটুইশন বিভাগে আলোচনা করা হয়েছিল, তবে আসুন এখানে প্রমাণটি সংক্ষিপ্ত করা যাক। একটি নিখুঁত মিল সহ একটি গ্রাফ বিবেচনা করুন। এর একটি নির্বিচারে উপসেট হতে দিন। মুছে ফেলুন। ধরা যাক একটি নির্বিচারে বিজোড় উপাদান। যেহেতু একটি নিখুঁত মিল ছিল, তাই কমপক্ষে একটি শীর্ষ অবশ্যই একটি শীর্ষের সাথে মিলিত হতে হবে। অতএব, প্রতিটি বিজোড় উপাদানের অন্তত একটি শীর্ষ থাকে যা একটি শীর্ষের সাথে মিলে যায়। যেহেতু প্রতিটি শীর্ষে সর্বাধিক একটি সংযুক্ত উপাদানের সাথে এই সম্পর্ক থাকতে পারে (কারণ এটি একটি নিখুঁত মিলনের মধ্যে সর্বাধিক একবার মিলে যায়)। এর পর্যাপ্ততাঃ ধরা যাক একটি নির্বিচারে গ্রাফ যার কোনও নিখুঁত মিল নেই। আমরা একজন তথাকথিত টুটে লঙ্ঘনকারীকে খুঁজে পাব, অর্থাৎ এর একটি উপসেট। আমরা ধরে নিতে পারি যে এটি প্রান্ত-সর্বাধিক, অর্থাৎ, ইতিমধ্যে উপস্থিত নয় এমন প্রতিটি প্রান্তের জন্য একটি নিখুঁত মিল রয়েছে। প্রকৃতপক্ষে, যদি আমরা প্রান্ত-সর্বাধিক আলেখ্যে একটি টুট লঙ্ঘনকারী খুঁজে পাই, তবে প্রতিটি বিস্তৃত উপ-আলেখ্যেও এটি একটি টুট লঙ্ঘনকারী, কারণ এর প্রতিটি বিজোড় উপাদান সম্ভবত আরও বেশি উপাদানে বিভক্ত হবে যার মধ্যে অন্তত একটি আবার বিজোড় হবে। আমরা ডিগ্রি সহ শীর্ষগুলির সেট হিসাবে সংজ্ঞায়িত করি। প্রথমে আমরা সেই বিষয়টি বিবেচনা করি যেখানে এর সমস্ত উপাদান সম্পূর্ণ গ্রাফ। তারপর একটি টুট লঙ্ঘনকারী হতে হবে, কারণ যদি, তাহলে আমরা প্রতিটি বিজোড় উপাদান থেকে একটি শীর্ষকে একটি শীর্ষের সাথে মিলিয়ে এবং অন্যান্য সমস্ত শীর্ষকে জোড়া দিয়ে একটি নিখুঁত মিল খুঁজে পেতে পারি (এটি বিজোড় না হলে কাজ করবে, তবে এটি একটি টুট লঙ্ঘনকারী)। এখন ধরুন এটি একটি উপাদান এবং এর মতো শীর্ষ। একটি সংক্ষিপ্ততম পথের প্রথম শীর্ষগুলি ধরা যাক। এটি নিশ্চিত করে যে এবং। যেহেতু, এরকম একটি শীর্ষ রয়েছে। এর প্রান্ত-সর্বাধিকতা থেকে, আমরা একটি নিখুঁত মিল এবং একটি নিখুঁত মিল হিসাবে সংজ্ঞায়িত করি। সেটা অবশ্যই লক্ষ্য করুন। ধরা যাক যে সর্বাধিক পথটি একটি প্রান্ত থেকে শুরু হয় এবং যার প্রান্তগুলি এবং এর মধ্যে পরিবর্তিত হয়। কিভাবে শেষ করা যায়? যদি না আমরা 'বিশেষ' শীর্ষে পৌঁছাই যেমন বা, আমরা সর্বদা চালিয়ে যেতে পারিঃ দ্বারা-মিলে যায়, তাই এর প্রথম প্রান্তটি নেই, তাই দ্বিতীয় শীর্ষটি একটি ভিন্ন প্রান্ত দ্বারা মিলে যায় এবং আমরা এই পদ্ধতিতে চালিয়ে যাই। এর শেষ শীর্ষকে নির্দেশ করা যাক। যদি এর শেষ প্রান্তটি থাকে, তবে তা হতে হবে, কারণ অন্যথায় আমরা একটি প্রান্ত দিয়ে চালিয়ে যেতে পারি (এমনকি পৌঁছনো বা)। এই ক্ষেত্রে আমরা সংজ্ঞায়িত করি। যদি এর শেষ প্রান্তটি থাকে, তবে অবশ্যই অনুরূপ কারণে এবং আমরা সংজ্ঞায়িত করি। এখন প্রতিটি প্রান্তের সাথে জোড় দৈর্ঘ্যের একটি চক্র। আমরা এখন সংজ্ঞায়িত করতে পারি (যেখানে প্রতিসম পার্থক্য) এবং আমরা একটি নিখুঁত মিল, একটি দ্বন্দ্ব পেতে পারি। টুটে-বার্জ সূত্রের সমতুল্যতা টুটে-বার্জ সূত্রটি বলে যে একটি গ্রাফের সর্বাধিক মিলনের আকার সমান। সমতুল্যভাবে, সর্বাধিক মিলযুক্ত শীর্ষগুলির সংখ্যা সমান হয়। এই সূত্রটি টুট্টের উপপাদ্য থেকে অনুসরণ করা হয়েছে, সেই পর্যবেক্ষণের সাথে যার আকারের মিল রয়েছে যদি এবং শুধুমাত্র যদি নতুন শীর্ষ যোগ করে প্রাপ্ত গ্রাফ, প্রতিটি মূল শীর্ষের সাথে যুক্ত, একটি নিখুঁত মিল থাকে। যেহেতু যে কোনও সেট যা একাধিক উপাদানে বিভক্ত হয় তাতে অবশ্যই সমস্ত নতুন শীর্ষ থাকতে হবে, (*) যদি এবং শুধুমাত্র যদি সন্তুষ্ট হয়। অসীম গ্রাফগুলিতে সংযুক্ত অসীম গ্রাফগুলির জন্য যা স্থানীয়ভাবে সীমাবদ্ধ (প্রতিটি শীর্ষে সীমাবদ্ধ ডিগ্রি থাকে), টুটের শর্তের একটি সাধারণীকরণ ধারণ করেঃ এই ধরনের গ্রাফগুলির নিখুঁত মিল থাকে যদি এবং শুধুমাত্র যদি কোনও সীমাবদ্ধ উপসেট না থাকে, যার অপসারণ উপসেটটির আকারের চেয়ে বড় সংখ্যক সীমাবদ্ধ বিজোড় উপাদান তৈরি করে। এছাড়াও দেখুন বাইপারটাইট ম্যাচিং হলের বিবাহ উপপাদ্য পিটারসেনের উপপাদ্য নোটস রেফারেন্স ম্যাচিং (গ্রাফ তত্ত্ব) গ্রাফ তত্ত্বের উপপাদ্য প্রমাণ সম্বলিত নিবন্ধ