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