Ore's theorem
ওরের উপপাদ্যটি 1960 সালে নরওয়েজিয়ান গণিতবিদ অয়েস্টাইন ওর দ্বারা প্রমাণিত গ্রাফ তত্ত্বের একটি ফলাফল। এটি একটি গ্রাফকে হ্যামিল্টনিয়ান হওয়ার জন্য যথেষ্ট শর্ত দেয়, মূলত উল্লেখ করে যে পর্যাপ্ত সংখ্যক প্রান্ত সহ একটি গ্রাফে অবশ্যই একটি হ্যামিল্টন চক্র থাকতে হবে। বিশেষত, উপপাদ্যটি অ-সংলগ্ন শীর্ষগুলির জোড়ার মাত্রার যোগফল বিবেচনা করেঃ যদি এই ধরনের প্রতিটি জোড়ের যোগফল কমপক্ষে গ্রাফের মোট শীর্ষগুলির সংখ্যার সমান হয়, তবে গ্রাফটি হ্যামিল্টনিয়ান হয়। আনুষ্ঠানিক বিবৃতি ধরা যাক শীর্ষগুলি সহ একটি (সীমাবদ্ধ এবং সহজ) গ্রাফ। আমরা একটি শীর্ষের মাত্রা দ্বারা নির্দেশ করি, অর্থাৎ। আপতিত প্রান্তের সংখ্যা। তারপর, ওরের উপপাদ্য বলে যে যদি হয় তবে হ্যামিল্টনিয়ান। প্রমাণ এটি দেখানোর সমতুল্য যে প্রতিটি অ-হ্যামিল্টনিয়ান গ্রাফ শর্ত মেনে চলে না। তদনুসারে, হ্যামিল্টনিয়ান নয় এমন শীর্ষে একটি গ্রাফ হতে দিন, এবং হ্যামিল্টনিয়ান চক্র তৈরি না করে এমন একবারে একটি প্রান্ত যোগ করে তৈরি করা যাক, যতক্ষণ না আর কোনও প্রান্ত যোগ করা যায় না। যে কোনও দুটি অ-সংলগ্ন শীর্ষ হতে দিন এবং হতে দিন। তারপরে প্রান্ত যোগ করলে কমপক্ষে একটি নতুন হ্যামিল্টনিয়ান চক্র তৈরি হবে এবং এই ধরনের চক্র ব্যতীত অন্য প্রান্তগুলিকে অবশ্যই এবং এর সাথে একটি হ্যামিল্টনিয়ান পথ তৈরি করতে হবে। পরিসীমার প্রতিটি সূচকের জন্য, থেকে এবং থেকে দুটি সম্ভাব্য প্রান্ত বিবেচনা করুন। এই দুটি প্রান্তের মধ্যে সর্বাধিক একটি প্রান্ত উপস্থিত থাকতে পারে, অন্যথায় চক্রটি হ্যামিল্টনিয়ান চক্র হবে। সুতরাং, মোট প্রান্তের সংখ্যা পছন্দের সংখ্যার সমান হয়, যা হল। অতএব, সম্পত্তি (঱্঱ং) মেনে চলে না, যার জন্য এই মোট প্রান্তের সংখ্যা () এর চেয়ে বেশি বা সমান হতে হবে। যেহেতু শীর্ষের ডিগ্রিগুলি সর্বাধিক ডিগ্রির সমান, তাই এটি অনুসরণ করে যে এটিও সম্পত্তি (঱্঱ং) মেনে চলে না। অ্যালগরিদম হ্যামিল্টনিয়ান চক্র নির্মাণের জন্য নিম্নলিখিত সহজ অ্যালগরিদমটি বর্ণনা করে যা একটি গ্রাফের সাথে মিলে যায়। গ্রাফের সংলগ্নতা উপেক্ষা করে একটি চক্রে নির্বিচারে শীর্ষগুলি সাজান। যদিও চক্রটিতে পরপর দুটি শীর্ষবিন্দু vi এবং vi + 1 রয়েছে যা গ্রাফের সংলগ্ন নয়, তবে নিম্নলিখিত দুটি পদক্ষেপ সম্পাদন করুনঃ একটি সূচক j অনুসন্ধান করুন যাতে চারটি শীর্ষবিন্দু vi, vi + 1, vj এবং vj + 1 সবই স্বতন্ত্র হয় এবং যাতে গ্রাফটিতে vi থেকে vj এবং vj + 1 থেকে vi + 1 পর্যন্ত প্রান্ত থাকে যা vi + 1 এবং vj (অন্তর্ভুক্ত) এর মধ্যে চক্রের অংশটিকে বিপরীত করে। প্রতিটি ধাপ গ্রাফের সংলগ্ন চক্রের ধারাবাহিক জোড়ার সংখ্যা এক বা দুটি জোড়া দ্বারা বৃদ্ধি করে (vj এবং vj + 1 ইতিমধ্যে সংলগ্ন কিনা তার উপর নির্ভর করে), তাই অ্যালগরিদম শেষ হওয়ার আগে বাইরের লুপটি কেবল সর্বাধিক n বার ঘটতে পারে, যেখানে n হল প্রদত্ত গ্রাফের শীর্ষগুলির সংখ্যা। উপপাদ্যটির প্রমাণের অনুরূপ একটি যুক্তি দ্বারা, পছন্দসই সূচক জে অবশ্যই বিদ্যমান থাকতে হবে, অন্যথায় অ-সংলগ্ন শীর্ষগুলি vi এবং vi + 1 এর মোট ডিগ্রি খুব কম হবে। আই এবং জে খুঁজে বের করা এবং চক্রের অংশটি বিপরীত করা, সবই ও (এন) সময়ে সম্পন্ন করা যেতে পারে। অতএব, অ্যালগরিদমের মোট সময় হল O (n2), যা ইনপুট গ্রাফের প্রান্তের সংখ্যার সাথে মিলে যায়। সম্পর্কিত ফলাফল ওরের উপপাদ্যটি ডিরাকের উপপাদ্যের একটি সাধারণীকরণ যে, যখন প্রতিটি শীর্ষে কমপক্ষে ডিগ্রি থাকে, তখন গ্রাফটি হ্যামিল্টনিয়ান হয়। কারণ, যদি একটি গ্রাফ ডিরাকের শর্ত পূরণ করে, তবে স্পষ্টতই প্রতিটি জোড়া শীর্ষে কমপক্ষে যোগ করা ডিগ্রি থাকে। ফলস্বরূপ, বন্ডী-চাভাতাল উপপাদ্য দ্বারা ওরের উপপাদ্যকে সাধারণীকরণ করা হয়। একটি গ্রাফের উপর একটি ক্লোজার অপারেশন সংজ্ঞায়িত করা যেতে পারে, যেখানে যখনই দুটি অ-সংলগ্ন শীর্ষে কমপক্ষে ডিগ্রি যোগ করা হয়, তখন একটি তাদের সংযুক্ত করে একটি প্রান্ত যোগ করে; যদি একটি গ্রাফ ওরের উপপাদ্যের শর্ত পূরণ করে, তবে তার ক্লোজার একটি সম্পূর্ণ গ্রাফ। বন্ডী-চাভাতাল উপপাদ্য বলে যে একটি গ্রাফ হ্যামিল্টনিয়ান হয় যদি এবং শুধুমাত্র যদি তার ক্লোজার হ্যামিল্টনিয়ান হয়; যেহেতু সম্পূর্ণ গ্রাফ হ্যামিল্টনিয়ান, তাই ওরের উপপাদ্যটি একটি তাৎক্ষণিক পরিণতি। ওরের উপপাদ্যের একটি সংস্করণ পাওয়া গেছে যা নির্দেশিত গ্রাফের ক্ষেত্রে প্রযোজ্য। ধরুন, একটি ডিগ্রাফ জি-এর বৈশিষ্ট্য হল যে, প্রতিটি দুটি শীর্ষে u এবং v-এর জন্য, হয় u থেকে v পর্যন্ত একটি প্রান্ত থাকে অথবা u-এর আউট ডিগ্রি এবং v-এর ইনডিগ্রি জি-তে শীর্ষের সংখ্যার সমান বা তার বেশি হয়। তারপর, উডালের উপপাদ্য অনুসারে, জি-তে একটি নির্দেশিত হ্যামিল্টনিয়ান চক্র রয়েছে। একটি প্রদত্ত অনির্দিষ্ট গ্রাফের প্রতিটি প্রান্তকে এক জোড়া নির্দেশিত প্রান্ত দ্বারা প্রতিস্থাপন করে উডাল থেকে আকরের উপপাদ্যটি পাওয়া যেতে পারে। একটি ঘনিষ্ঠভাবে সম্পর্কিত উপপাদ্য বলে যে একটি এন-ভার্টেক্স দৃঢ়ভাবে ডিগ্রাফকে এই বৈশিষ্ট্যের সাথে সংযুক্ত করে যে, প্রতিটি দুটি অ-সংলগ্ন শীর্ষ u এবং v-এর জন্য, u বা v-এর মোট প্রান্তের সংখ্যা কমপক্ষে 2n−1 হতে হবে। উপপাদ্যের ডিগ্রি অবস্থার ফলস্বরূপ হ্যামিল্টনিসিটির চেয়ে আরও শক্তিশালী উপসংহার দেওয়ার জন্য ওরের উপপাদ্যকেও শক্তিশালী করা যেতে পারে। বিশেষত, আকরের উপপাদ্যের শর্তগুলি সন্তুষ্ট করে এমন প্রতিটি গ্রাফ হয় একটি নিয়মিত সম্পূর্ণ দ্বিদলীয় গ্রাফ বা প্যানসাইক্লিক। রেফারেন্স। । । । । এক্সট্রিমাল গ্রাফ তত্ত্ব গ্রাফ তত্ত্বের উপপাদ্য হ্যামিল্টনিয়ান পথ এবং চক্রের প্রমাণ সম্বলিত নিবন্ধ