Frucht's theorem
ফ্রুচ্টের উপপাদ্যটি বীজগাণিতিক গ্রাফ তত্ত্বের একটি উপপাদ্য যা 1936 সালে ডেনিস কনিগ দ্বারা অনুমান করা হয়েছিল এবং 1939 সালে রবার্ট ফ্রুচ্ট দ্বারা প্রমাণিত হয়েছিল। এটি বলে যে প্রতিটি সসীম গ্রুপ একটি সসীম অনির্দিষ্ট গ্রাফের প্রতিসাম্যের গ্রুপ। আরও দৃঢ়ভাবে, যে কোনও সসীম গ্রুপ জি-এর জন্য অসীমভাবে অনেক অ-আইসোমরফিক সরল সংযুক্ত গ্রাফ রয়েছে যাতে তাদের প্রত্যেকের অটোমরফিজম গ্রুপ জি-এর আইসোমরফিক হয়। প্রুফ ধারণা প্রমাণের মূল ধারণাটি পর্যবেক্ষণ করা হয় যে জি-এর কাইলি গ্রাফ, একে অপরের থেকে জি-এর জেনারেটরকে আলাদা করার জন্য তার প্রান্তে রঙ এবং অভিমুখের সংযোজন সহ, পছন্দসই অটোমরফিজম গ্রুপ রয়েছে। অতএব, যদি এই প্রান্তগুলির প্রতিটি একটি উপযুক্ত সাবগ্রাফ দ্বারা প্রতিস্থাপিত হয়, যাতে প্রতিটি প্রতিস্থাপন সাবগ্রাফ নিজেই অসমমিত হয় এবং দুটি প্রতিস্থাপন আইসোমরফিক হয় যদি এবং শুধুমাত্র যদি তারা একই রঙের প্রান্তগুলি প্রতিস্থাপন করে, তবে এই প্রতিস্থাপনগুলি সম্পাদন করে তৈরি অনির্দিষ্ট গ্রাফটিও তার প্রতিসাম্য গ্রুপ হিসাবে জি থাকবে। গ্রাফের আকার তিনটি ব্যতিক্রম ছাড়া-3,4 এবং 5 ক্রমের চক্রাকার গোষ্ঠী-প্রতিটি গোষ্ঠীকে একটি গ্রাফের প্রতিসাম্য হিসাবে উপস্থাপন করা যেতে পারে যার শীর্ষে মাত্র দুটি কক্ষপথ রয়েছে। অতএব, গ্রাফের শীর্ষগুলির সংখ্যা গ্রুপের ক্রমের সর্বাধিক দ্বিগুণ। ব্যতিক্রমগুলির একটি বৃহত্তর সেট সহ, বেশিরভাগ সীমাবদ্ধ গোষ্ঠীগুলিকে একটি শীর্ষ-ক্ষণস্থায়ী গ্রাফের প্রতিসাম্য হিসাবে উপস্থাপন করা যেতে পারে, যার মধ্যে গোষ্ঠীর ক্রমের সমান সংখ্যক শীর্ষ থাকে। গ্রাফের বিশেষ পরিবারগুলি ফ্রুক্টের উপপাদ্যের আরও শক্তিশালী সংস্করণ রয়েছে যা দেখায় যে গ্রাফের নির্দিষ্ট সীমাবদ্ধ পরিবারগুলিতে এখনও যে কোনও প্রতিসাম্য গোষ্ঠী উপলব্ধি করার জন্য পর্যাপ্ত গ্রাফ রয়েছে। ফ্রুক্ট প্রমাণ করেছেন যে প্রকৃতপক্ষে কাঙ্ক্ষিত বৈশিষ্ট্য সহ অনেকগুলি 3-নিয়মিত গ্রাফ বিদ্যমান; উদাহরণস্বরূপ, ফ্রুক্ট গ্রাফ, 12টি শীর্ষ এবং 18টি প্রান্ত সহ একটি 3-নিয়মিত গ্রাফের কোনও অ-তুচ্ছ প্রতিসাম্য নেই, যা তুচ্ছ গোষ্ঠীর জন্য এই ধরনের উপলব্ধি প্রদান করে। গের্ট সাবিডুসি দেখিয়েছেন যে, যে কোনও গোষ্ঠীকে গণনাযোগ্যভাবে অনেকগুলি স্বতন্ত্র কে-নিয়মিত গ্রাফ, কে-ভার্টেক্স-সংযুক্ত গ্রাফ বা কে-ক্রোমাটিক গ্রাফের প্রতিসাম্য গোষ্ঠী হিসাবে উপলব্ধি করা যেতে পারে, সমস্ত ধনাত্মক পূর্ণসংখ্যা মান কে-এর জন্য (নিয়মিত গ্রাফ এবং কে-ক্রোমাটিক গ্রাফের জন্য)। প্রতিটি গ্রাফকে তার প্রান্ত এবং শীর্ষগুলির আংশিক ক্রম থেকে পুনর্গঠন করা যেতে পারে, যে প্রতিটি সসীম আংশিক ক্রম বারখফের উপস্থাপনা উপপাদ্য দ্বারা একটি সসীম বিতরণমূলক জালের সমতুল্য, এটি অনুসরণ করে যে প্রতিটি সসীম গোষ্ঠীকে একটি বিতরণমূলক জালের প্রতিসাম্য হিসাবে উপলব্ধি করা যেতে পারে, এবং জালের গ্রাফ, একটি মধ্যমা গ্রাফ। প্রতিটি সসীম গোষ্ঠীকে একটি দৃঢ় নিয়মিত গ্রাফের প্রতিসাম্যের গোষ্ঠী হিসাবে উপলব্ধি করা সম্ভব। প্রতিটি সসীম গোষ্ঠীকে দুই নম্বরের পার্থক্যকারী গ্রাফের প্রতিসাম্য হিসাবেও উপলব্ধি করা যেতে পারেঃ একটি গ্রাফকে (অনুপযুক্তভাবে) দুটি রঙ দিয়ে রঙ করতে পারে যাতে গ্রাফের কোনও প্রতিসাম্য রঙ সংরক্ষণ না করে। যাইহোক, গ্রাফের কিছু গুরুত্বপূর্ণ শ্রেণী সমস্ত গোষ্ঠীকে তাদের প্রতিসাম্য হিসাবে উপলব্ধি করতে অক্ষম। ক্যামিল জর্ডান গাছের প্রতিসাম্য গোষ্ঠীগুলিকে তুচ্ছ গোষ্ঠী ধারণকারী সীমাবদ্ধ গোষ্ঠীগুলির ক্ষুদ্রতম সেট হিসাবে চিহ্নিত করেছিলেন এবং একে অপরের সাথে সরাসরি পণ্যগুলির অধীনে বন্ধ এবং প্রতিসাম্য গোষ্ঠীগুলির সাথে মালা পণ্যগুলির অধীনে বন্ধ; বিশেষত, ক্রম তিনটির চক্রীয় গোষ্ঠী কোনও গাছের প্রতিসাম্য গোষ্ঠী নয়। প্ল্যানার গ্রাফগুলি সমস্ত গোষ্ঠীকে তাদের প্রতিসাম্য হিসাবে উপলব্ধি করতে সক্ষম নয়; উদাহরণস্বরূপ, একমাত্র সীমাবদ্ধ সহজ গোষ্ঠী যা প্ল্যানার গ্রাফের প্রতিসাম্য, তা হল চক্রাকার গোষ্ঠী এবং বিকল্প গোষ্ঠী। আরও সাধারণভাবে, প্রতিটি ক্ষুদ্র-বদ্ধ গ্রাফ পরিবার তার গ্রাফের প্রতিসাম্য দ্বারা সমস্ত সীমাবদ্ধ গোষ্ঠীকে উপস্থাপন করতে অক্ষম। লাস্লো বাবাই আরও দৃঢ়ভাবে অনুমান করেন যে, প্রতিটি ক্ষুদ্র-আবদ্ধ পরিবার কেবলমাত্র সীমিতভাবে অনেক অ-চক্রীয় সীমাবদ্ধ সহজ গোষ্ঠীর প্রতিনিধিত্ব করতে পারে। অসীম গ্রাফ এবং গ্রুপ ইজবিকি 1959 সালে এই ফলাফলগুলি প্রসারিত করে এবং দেখায় যে কোনও সীমাবদ্ধ প্রতিসাম্য গ্রুপকে উপলব্ধি করার জন্য অগণিত অনেক অসীম গ্রাফ ছিল। পরিশেষে, জোহানেস ডি গ্রুট এবং সাবিডুসি 1959/1960-এ স্বাধীনভাবে প্রমাণ করেছিলেন যে যে কোনও গোষ্ঠীকে (গোষ্ঠীটি সীমাবদ্ধ বলে ধারণাটি বাদ দিয়ে, তবে পছন্দের স্বতঃসিদ্ধ অনুমানের সাথে) একটি অসীম গ্রাফের প্রতিসাম্যের গোষ্ঠী হিসাবে উপলব্ধি করা যেতে পারে। তথ্যসূত্র উৎস। । । । । । যেমনটি উল্লেখ করা হয়েছে। । । বীজগাণিতিক গ্রাফ তত্ত্ব গ্রাফ তত্ত্বের উপপাদ্য