Ear decomposition
গ্রাফ তত্ত্বে, একটি অনির্দিষ্ট গ্রাফ জি-এর একটি কান হল একটি পথ পি যেখানে পথের দুটি শেষ বিন্দু মিলে যেতে পারে, তবে যেখানে অন্যথায় প্রান্ত বা শীর্ষগুলির কোনও পুনরাবৃত্তি অনুমোদিত নয়, তাই পি-এর প্রতিটি অভ্যন্তরীণ শীর্ষে জি-তে ডিগ্রি দুই থাকে। একটি অনির্দিষ্ট গ্রাফ জি-এর একটি কানের পচন হল কানের ক্রমানুসারে তার প্রান্তগুলির সেটের একটি বিভাজন, যাতে প্রতিটি কানের এক বা দুটি শেষ বিন্দু ক্রমানুসারে পূর্ববর্তী কানের অন্তর্গত হয় এবং যাতে প্রতিটি কানের অভ্যন্তরীণ শীর্ষগুলি কোনও পূর্ববর্তী কানের অন্তর্গত না হয়। উপরন্তু, বেশিরভাগ ক্ষেত্রে ক্রমের প্রথম কান অবশ্যই একটি চক্র হতে হবে। একটি খোলা কানের পচন বা একটি সঠিক কানের পচন হল একটি কানের পচন যেখানে প্রথমটির পরে প্রতিটি কানের দুটি প্রান্তবিন্দু একে অপরের থেকে আলাদা হয়। কানের পচনগুলি বেশ কয়েকটি গুরুত্বপূর্ণ গ্রাফ শ্রেণীকে চিহ্নিত করতে এবং দক্ষ গ্রাফ অ্যালগরিদমের অংশ হিসাবে ব্যবহার করা যেতে পারে। এগুলি গ্রাফ থেকে ম্যাট্রয়েড পর্যন্ত সাধারণীকরণ করা যেতে পারে। গ্রাফের শ্রেণীগুলির বৈশিষ্ট্য গ্রাফের বেশ কয়েকটি গুরুত্বপূর্ণ শ্রেণীকে নির্দিষ্ট ধরনের কানের পচনযুক্ত গ্রাফ হিসাবে চিহ্নিত করা যেতে পারে। গ্রাফ সংযোগ একটি গ্রাফ কে-ভার্টেক্স-সংযুক্ত হয় যদি কোনও (কে-1) শীর্ষ অপসারণ একটি সংযুক্ত সাবগ্রাফ ছেড়ে যায়, এবং কে-এজ-সংযুক্ত হয় যদি কোনও (কে-1) প্রান্ত অপসারণ একটি সংযুক্ত সাবগ্রাফ ছেড়ে যায়। নিম্নলিখিত ফলাফলটি নিম্নলিখিত কারণে হয়ঃ 2-ভার্টেক্স-সংযুক্ত একটি গ্রাফ যদি এবং শুধুমাত্র যদি এটির একটি খোলা কানের পচন থাকে। নিম্নলিখিত ফলাফলটি নিম্নলিখিত কারণে হয়ঃ একটি গ্রাফ 2-প্রান্ত-সংযুক্ত হয় যদি এবং শুধুমাত্র যদি এটি একটি কান পচন হয়। উভয় ক্ষেত্রেই কানের সংখ্যা অবশ্যই প্রদত্ত গ্রাফের সার্কিট র্যাঙ্কের সমান। রবিনস রবিন্স উপপাদ্য প্রমাণ করার জন্য একটি সরঞ্জাম হিসাবে 2-প্রান্ত-সংযুক্ত গ্রাফগুলির কানের পচন প্রবর্তন করেছিলেন, যে এগুলি ঠিক সেই গ্রাফগুলি যা একটি দৃঢ়ভাবে সংযুক্ত অভিযোজন দেওয়া যেতে পারে। কানের পচন নিয়ে হুইটনি এবং রবিন্সের অগ্রগামী কাজের কারণে, কানের পচনকে কখনও কখনও হুইটনি-রবিনস সংশ্লেষণও বলা হয়। একটি অ-বিচ্ছিন্ন কানের পচন হল একটি খোলা কানের পচন যাতে, শুধুমাত্র একটি ব্যতিক্রম ছাড়া প্রতিটি শীর্ষে v-এর জন্য, v-এর একটি প্রতিবেশী থাকে যার পচন প্রথম উপস্থিতিতে v-এর প্রথম উপস্থিতির তুলনায় পরবর্তী কানে হয়। এই ধরনের কানের পচন হুইটনির ফলাফলকে সাধারণীকরণ করতে ব্যবহার করা যেতে পারেঃ 3-ভার্টেক্স-সংযুক্ত একটি গ্রাফ যদি এবং শুধুমাত্র যদি G-এর একটি অ-পৃথক কানের পচন হয়। যদি এই ধরনের পচন বিদ্যমান থাকে, তবে এটি জি-এর একটি নির্দিষ্ট প্রান্ত ইউভি-র সাপেক্ষে এমনভাবে বেছে নেওয়া যেতে পারে যে ইউ প্রথম কানে থাকে, ভি হল শেষ কানে একাধিক প্রান্ত সহ নতুন শীর্ষ, এবং ইউভি একটি একক-প্রান্ত কান। এই ফলাফলটি প্রথম স্পষ্টভাবে বলা হয়েছিল, তবে বর্ণিত হিসাবে, এটি 1971 সালের পিএইচডি-র ফলাফলের সমতুল্য। লি মন্ডশেইনের থিসিস। সর্বাধিক সমতলীয় গ্রাফের অ-বিচ্ছিন্ন কানের পচনগুলির সাথে ঘনিষ্ঠভাবে সম্পর্কিত কাঠামো, যাকে ক্যানোনিকাল অর্ডারিং বলা হয়, গ্রাফ অঙ্কনের একটি আদর্শ সরঞ্জাম। নির্দেশিত গ্রাফের শক্তিশালী সংযোগ উপরের সংজ্ঞাগুলি নির্দেশিত গ্রাফের ক্ষেত্রেও প্রয়োগ করা যেতে পারে। একটি কান তখন একটি নির্দেশিত পথ হবে যেখানে সমস্ত অভ্যন্তরীণ শীর্ষে 1-এর সমান অনির্দিষ্ট এবং বহির্বিভাগ থাকবে। একটি নির্দেশিত গ্রাফ দৃঢ়ভাবে সংযুক্ত থাকে যদি এতে প্রতিটি শীর্ষ থেকে অন্য প্রতিটি শীর্ষে যাওয়ার একটি নির্দেশিত পথ থাকে। তারপর আমাদের নিম্নলিখিত উপপাদ্যটি রয়েছেঃ একটি নির্দেশিত গ্রাফ দৃঢ়ভাবে সংযুক্ত থাকে যদি এবং শুধুমাত্র যদি এটির একটি কানের পচন থাকে। ফ্যাক্টর-ক্রিটিক্যাল গ্রাফ একটি কানের পচন বিজোড় হয় যদি এর প্রতিটি কানে বিজোড় সংখ্যক প্রান্ত ব্যবহার করা হয়। একটি ফ্যাক্টর-ক্রিটিক্যাল গ্রাফ হল বিজোড় সংখ্যক শীর্ষ সহ একটি গ্রাফ, যেমন প্রতিটি শীর্ষে v-এর জন্য, যদি v গ্রাফ থেকে সরানো হয় তবে অবশিষ্ট শীর্ষগুলির একটি নিখুঁত মিল রয়েছে। পাওয়া গেছে যেঃ একটি গ্রাফ জি ফ্যাক্টর-সমালোচনামূলক যদি এবং শুধুমাত্র যদি জি-এর একটি বিজোড় কানের পচন থাকে। আরও সাধারণভাবে, এর ফলাফল যে কোনও গ্রাফ জি-তে সবচেয়ে কম জোড় কান সহ কানের পচন খুঁজে পাওয়া সম্ভব করে তোলে। সিরিজ-সমান্তরাল গ্রাফ একটি গাছের কানের পচন হল একটি সঠিক কানের পচন যেখানে প্রথম কানের একটি প্রান্ত থাকে এবং পরবর্তী প্রতিটি কানের জন্য একটি করে কান থাকে, যাতে উভয় প্রান্তবিন্দুতে থাকে। একটি নেস্টেড কানের পচন হল একটি গাছের কানের পচন যা প্রতিটি কানের মধ্যে, অন্যান্য কানের শেষ বিন্দুর জোড়া যা নেস্টেড ব্যবধানের একটি সেট গঠন করে। একটি সিরিজ-সমান্তরাল গ্রাফ হল দুটি মনোনীত টার্মিনাল এস এবং টি সহ একটি গ্রাফ যা দুটি উপায়ে ছোট সিরিজ-সমান্তরাল গ্রাফগুলিকে একত্রিত করে পুনরাবৃত্তিমূলকভাবে গঠন করা যেতে পারেঃ সিরিজ রচনা (একটি ছোট গ্রাফ থেকে একটি টার্মিনালকে অন্য ছোট গ্রাফ থেকে একটি টার্মিনাল দিয়ে চিহ্নিত করা, এবং অন্য দুটি টার্মিনালকে সম্মিলিত গ্রাফের টার্মিনাল হিসাবে রাখা) এবং সমান্তরাল রচনা (দুটি ছোট গ্রাফ থেকে উভয় জোড়া টার্মিনাল চিহ্নিত করা)। নিম্নলিখিত ফলাফলটি নিম্নলিখিত কারণে হয়ঃ একটি 2-ভার্টেক্স-সংযুক্ত গ্রাফ সিরিজ-সমান্তরাল হয় যদি এবং শুধুমাত্র যদি এটির একটি নেস্টেড কানের পচন থাকে। উপরন্তু, 2-ভার্টেক্স-সংযুক্ত সিরিজ-সমান্তরাল গ্রাফের যে কোনও খোলা কানের পচন অবশ্যই নেস্টেড হতে হবে। দুটি টার্মিনালের মধ্যে একটি পথ দিয়ে শুরু হওয়া খোলা কানের পচন ব্যবহার করে ফলাফলটি সিরিজ-সমান্তরাল গ্রাফগুলিতে প্রসারিত করা যেতে পারে যা 2-ভার্টেক্স-সংযুক্ত নয়। ম্যাট্রয়েড কানের পচনের ধারণাটি গ্রাফ থেকে ম্যাট্রয়েড পর্যন্ত প্রসারিত করা যেতে পারে। একটি ম্যাট্রয়েডের কানের পচনকে ম্যাট্রয়েডের সার্কিটগুলির একটি ক্রম হিসাবে সংজ্ঞায়িত করা হয়, যার দুটি বৈশিষ্ট্য রয়েছেঃ ক্রমের প্রতিটি সার্কিটের পূর্ববর্তী সার্কিটগুলির সাথে একটি অ-খালি ছেদ রয়েছে এবং ক্রমের প্রতিটি সার্কিট একটি সার্কিট হিসাবে রয়ে যায়, এমনকি যদি ক্রমের সমস্ত পূর্ববর্তী সার্কিট সংকুচিত হয়। গ্রাফ জি-এর গ্রাফিক ম্যাট্রয়েডে প্রয়োগ করা হলে, কানের পচনের এই সংজ্ঞাটি জি-এর সঠিক কানের পচনের সংজ্ঞার সাথে মিলে যায়ঃ প্রতিটি বর্তনীতে কমপক্ষে একটি প্রান্ত অন্তর্ভুক্ত থাকার প্রয়োজনীয়তার দ্বারা অনুপযুক্ত পচনের বিষয়টি বাদ দেওয়া হয় যা পূর্ববর্তী বর্তনীগুলির অন্তর্গত। এই সংজ্ঞাটি ব্যবহার করে, একটি ম্যাট্রয়েডকে ফ্যাক্টর-ক্রিটিকাল হিসাবে সংজ্ঞায়িত করা যেতে পারে যখন এটির একটি কানের পচন হয় যেখানে ক্রমের প্রতিটি বর্তনীতে বিজোড় সংখ্যক নতুন উপাদান থাকে। অ্যালগরিদম ধ্রুপদী কম্পিউটারে, 2-প্রান্ত-সংযুক্ত গ্রাফের কানের পচন এবং 2-ভার্টেক্স-সংযুক্ত গ্রাফের খোলা কানের পচন লোভী অ্যালগরিদম দ্বারা পাওয়া যেতে পারে যা প্রতিটি কানকে একবারে খুঁজে পায়। একটি সহজ লোভী পদ্ধতি যা একই সময়ে রৈখিক সময়ে (যদি বিদ্যমান থাকে) কানের পচন, খোলা কানের পচন, এস. টি-নম্বরিং এবং-ওরিয়েন্টেশন গণনা করে। এই পদ্ধতিটি একটি পাথ-জেনারেটিং নিয়ম দ্বারা চেইন ডিকম্পোসিশন নামে একটি বিশেষ কানের পচন গণনা করার উপর ভিত্তি করে। এটি দেখায় যে অ-বিচ্ছিন্ন কানের পচনও রৈখিক সময়ে তৈরি করা যেতে পারে। , এবং বিভিন্ন ধরনের কানের পচন গঠনের জন্য দক্ষ সমান্তরাল অ্যালগরিদম সরবরাহ করে। উদাহরণস্বরূপ, একটি 2-প্রান্ত-সংযুক্ত গ্রাফের কানের পচন খুঁজে পেতে, নিম্নলিখিত পদক্ষেপগুলি অনুসারে আয়ের অ্যালগরিদমঃ প্রদত্ত গ্রাফের একটি বিস্তৃত গাছ খুঁজে বের করুন এবং গাছের জন্য একটি মূল বেছে নিন। গাছের অংশ নয় এমন প্রতিটি প্রান্তের ইউভি-র জন্য, মূল এবং ইউ এবং ভি-এর সর্বনিম্ন সাধারণ পূর্বপুরুষের মধ্যে দূরত্ব নির্ধারণ করুন। গাছের অংশ হওয়া প্রতিটি প্রান্তের ইউভি-র জন্য, সংশ্লিষ্ট "মাস্টার এজ" খুঁজে বের করুন, একটি অ-গাছের প্রান্ত ডাব্লুএক্স যাতে গাছে ডাব্লুএক্স যোগ করে গঠিত চক্রটি ইউভি-র মধ্য দিয়ে যায় এবং এই ধরনের প্রান্তগুলির মধ্যে, ডাব্লু এবং এক্স-এর সর্বনিম্ন সাধারণ পূর্বপুরুষ থাকে যা মূলের যতটা সম্ভব কাছাকাছি থাকে (প্রান্ত সনাক্তকারী দ্বারা ভাঙা বন্ধন সহ)। প্রতিটি অ-গাছের প্রান্তের জন্য একটি কান তৈরি করুন, এটি এবং গাছের প্রান্তগুলি যার জন্য এটি মাস্টার, এবং কানগুলিকে মূল থেকে তাদের মাস্টার প্রান্তের দূরত্ব দ্বারা অর্ডার করুন (একই টাই-ব্রেকিং নিয়ম সহ)। এই অ্যালগরিদমগুলি অন্যান্য সমস্যার জন্য সাব-রুটিন হিসাবে ব্যবহার করা যেতে পারে যার মধ্যে রয়েছে সংযোগ পরীক্ষা করা, সিরিজ-সমান্তরাল গ্রাফগুলি সনাক্ত করা এবং গ্রাফের এস. টি-নম্বর তৈরি করা (প্ল্যানারিটি পরীক্ষায় একটি গুরুত্বপূর্ণ সাব-রুটিন)। একটি প্রদত্ত ম্যাট্রয়েডের একটি কানের পচন, প্রতিটি কানে ম্যাট্রয়েডের একই নির্দিষ্ট উপাদান থাকে এমন অতিরিক্ত সীমাবদ্ধতা সহ, ম্যাট্রয়েডের জন্য একটি স্বাধীন ওরাকলের অ্যাক্সেস দেওয়া বহুপদী সময়ে পাওয়া যেতে পারে। রেফারেন্স। । । । । । । । । । । । । । । । গ্রাফ তত্ত্ব ম্যাট্রয়েড তত্ত্বকে অবজেক্ট করে