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