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