Erdős–Gallai theorem
এরদোস-গাল্লাই উপপাদ্যটি গ্রাফ তত্ত্বের একটি ফলাফল, যা সমন্বিত গণিতের একটি শাখা। এটি গ্রাফ উপলব্ধি সমস্যা সমাধানের জন্য দুটি পরিচিত পদ্ধতির মধ্যে একটি প্রদান করে, অর্থাৎ। এটি একটি সহজ গ্রাফের ডিগ্রি সিকোয়েন্স হওয়ার জন্য প্রাকৃতিক সংখ্যার একটি সীমাবদ্ধ ক্রমের জন্য একটি প্রয়োজনীয় এবং পর্যাপ্ত শর্ত দেয়। এই শর্তগুলি মেনে চলা একটি ক্রমকে "গ্রাফিক" বলা হয়। এই উপপাদ্যটি 1960 সালে পল এরদোস এবং টিবোর গ্যালাই দ্বারা প্রকাশিত হয়েছিল, যার নামে এর নামকরণ করা হয়েছে। বিবৃতি অ-ঋণাত্মক পূর্ণসংখ্যার একটি ক্রমকে n শীর্ষে একটি সীমাবদ্ধ সহজ গ্রাফের ডিগ্রি ক্রম হিসাবে উপস্থাপন করা যেতে পারে যদি এবং শুধুমাত্র যদি জোড় হয় এবং প্রতিটি ইন ধরে রাখে। প্রমাণ এটি দেখানো কঠিন নয় যে সংখ্যার একটি ক্রম গ্রাফিক হওয়ার জন্য এরদোস-গাল্লাই উপপাদ্যের শর্তগুলি প্রয়োজনীয়। ডিগ্রির সমষ্টি সম হওয়ার প্রয়োজনীয়তা হ 'ল হ্যান্ডশেকিং লেম্মা, যা ইউলার ইতিমধ্যে কনিসবার্গের সেতুর উপর তাঁর 1736 সালের গবেষণাপত্রে ব্যবহার করেছেন। বৃহত্তম ডিগ্রির যোগফল এবং অবশিষ্ট ডিগ্রির যোগফলের মধ্যে অসমতা দ্বিগুণ গণনা দ্বারা প্রতিষ্ঠিত করা যেতে পারেঃ বাম দিকটি সর্বোচ্চ-ডিগ্রি শীর্ষগুলির মধ্যে প্রান্ত-ভার্টেক্স সংলগ্নতার সংখ্যা দেয়, এই ধরনের প্রতিটি সংলগ্নতা অবশ্যই এক বা দুটি উচ্চ-ডিগ্রি প্রান্তবিন্দু সহ একটি প্রান্তে থাকতে হবে, ডানদিকের শব্দটি প্রান্ত-ভার্টেক্স সংলগ্নতার সর্বাধিক সম্ভাব্য সংখ্যা দেয় যেখানে উভয় প্রান্তবিন্দুতে উচ্চ ডিগ্রি থাকে এবং ডানদিকের উপরের সীমানায় অবশিষ্ট পদটি ঠিক একটি উচ্চ ডিগ্রি প্রান্তবিন্দুযুক্ত প্রান্তের সংখ্যা দেয়। সুতরাং, প্রমাণের আরও কঠিন অংশটি দেখানো হয় যে, এই শর্তগুলি মেনে চলা সংখ্যার যে কোনও ক্রমের জন্য একটি গ্রাফ বিদ্যমান যার জন্য এটি ডিগ্রি ক্রম। এর মূল প্রমাণ দীর্ঘ এবং জড়িত ছিল। নেটওয়ার্ক প্রবাহের ধারণার উপর ভিত্তি করে ক্লড বার্জের একটি সংক্ষিপ্ত প্রমাণ উদ্ধৃত করেছেন। চৌদুম পরিবর্তে ডিগ্রির যোগফলের উপর গাণিতিক প্রবর্তন দ্বারা একটি প্রমাণ প্রদান করেনঃ তিনি একটি সংখ্যার প্রথম সূচক হতে দেন যার জন্য (বা সমস্ত সমান হলে উপান্ত সংখ্যা), একটি কেস বিশ্লেষণ ব্যবহার করে দেখান যে ক্রমের শেষ সংখ্যা থেকে একটি বিয়োগ করে গঠিত ক্রমটি আবার গ্রাফিক হয়, এবং দুটি অবস্থানের মধ্যে একটি প্রান্ত যোগ করে মূল ক্রমের প্রতিনিধিত্বকারী একটি গ্রাফ তৈরি করে যেখান থেকে একটি বিয়োগ করা হয়েছিল। "অবাস্তবকরণ"-এর একটি ক্রম বিবেচনা করুন, গ্রাফ যার ডিগ্রিগুলি প্রদত্ত ডিগ্রি সিকোয়েন্স দ্বারা সীমাবদ্ধ। তারা দেখায় যে, যদি জি একটি অবাস্তবকরণ হয়, এবং আই জি-তে একটি শীর্ষের ক্ষুদ্রতম সূচক যার ডিগ্রি ডি-এর সমান না হয়, তবে জি-কে এমনভাবে সংশোধন করা যেতে পারে যা আরেকটি অবাস্তবকরণ তৈরি করে, ক্রমের পূর্ববর্তী শীর্ষগুলির ডিগ্রি পরিবর্তন না করে শীর্ষ আই-এর ডিগ্রি বৃদ্ধি করে। এই ধরনের পুনরাবৃত্ত পদক্ষেপগুলি অবশ্যই উপপাদ্যটি প্রমাণ করে প্রদত্ত ক্রমটির উপলব্ধিতে পৌঁছাতে হবে। পূর্ণসংখ্যা বিভাজনের সাথে সম্পর্ক এরদোস-গাল্লাই উপপাদ্য এবং পূর্ণসংখ্যা বিভাজনের তত্ত্বের মধ্যে ঘনিষ্ঠ সংযোগ বর্ণনা করে। ধরা যাক; তারপর সাজানো পূর্ণসংখ্যার ক্রমগুলি এর পার্টিশন হিসাবে ব্যাখ্যা করা যেতে পারে। তাদের উপসর্গ যোগফলের বড়করণের অধীনে, পার্টিশনগুলি একটি জাল গঠন করে, যেখানে একটি পৃথক পার্টিশন এবং পার্টিশন ক্রমানুসারে নীচের আরেকটি পার্টিশনের মধ্যে ন্যূনতম পরিবর্তন হল একটি সংখ্যা থেকে একটি বিয়োগ করা এবং এটিকে এমন একটি সংখ্যায় যোগ করা যা কমপক্ষে দুটি দ্বারা ছোট (শূন্য হতে পারে)। আইগনার এবং ট্রাইশ যেমন দেখান, এই অপারেশনটি গ্রাফিক হওয়ার বৈশিষ্ট্য সংরক্ষণ করে, তাই এরদোস-গাল্লাই উপপাদ্য প্রমাণ করার জন্য এই মেজরাইজেশন ক্রমে সর্বাধিক গ্রাফিক সিকোয়েন্সগুলি চিহ্নিত করা যথেষ্ট। তারা সংশ্লিষ্ট বিভাজনের ফেরার্স চিত্রের পরিপ্রেক্ষিতে এই ধরনের একটি বৈশিষ্ট্য প্রদান করে এবং দেখায় যে এটি এরদোস-গাল্লাই উপপাদ্যের সমতুল্য। অন্যান্য ধরনের গ্রাফের জন্য গ্রাফিক সিকোয়েন্স অনুরূপ উপপাদ্যগুলি সহজ নির্দেশিত গ্রাফের ডিগ্রি সিকোয়েন্স, লুপ সহ সহজ নির্দেশিত গ্রাফ এবং সহজ দ্বিদলীয় গ্রাফ বর্ণনা করে। প্রথম সমস্যাটি ফুলকারসন-চেন-অ্যানস্টি উপপাদ্য দ্বারা চিহ্নিত করা হয়। পরের দুটি ঘটনা, যা সমতুল্য, গেল-রাইজার উপপাদ্য দ্বারা চিহ্নিত করা হয়। আরও শক্তিশালী সংস্করণ প্রমাণ করে যে, সঙ্গে এবং পক্ষে এই বৈষম্য বিবেচনা করাই যথেষ্ট। বিপরীত প্রবাহে গ্রাফের জন্য বৈষম্যের সেটকে সীমাবদ্ধ করুন। যদি একটি জোড়-সমষ্টিগত ধনাত্মক ক্রম d-এর সর্বাধিক এবং সর্বনিম্ন (এবং দৈর্ঘ্য বৃহত্তম প্রবেশের চেয়ে বেশি) ছাড়া অন্য কোনও পুনরাবৃত্তি এন্ট্রি না থাকে, তবে এটি শুধুমাত্র তম বৈষম্য পরীক্ষা করার জন্য যথেষ্ট, যেখানে। সাধারণীকরণ অ-ঋণাত্মক পূর্ণসংখ্যার একটি সীমাবদ্ধ ক্রম যা যদি জোড় হয় তবে গ্রাফিক হয় এবং এমন একটি ক্রম বিদ্যমান যা গ্রাফিক এবং বড় হয়। এই ফলাফলটি দ্বারা দেওয়া হয়েছিল। এটি পুনরায় উদ্ভাবন করেন এবং আরও সরাসরি প্রমাণ দেন। এছাড়াও হ্যাভেল-হাকিমি অ্যালগরিদম রেফারেন্স দেখুন। । গ্যালাই উপপাদ্য গ্রাফ তত্ত্বের উপপাদ্য