একটি বিস্তৃত সাবগ্রাফ হল একটি সাবগ্রাফ যাতে মূল গ্রাফের সমস্ত শীর্ষবিন্দু রয়েছে। একটি স্প্যানিং ট্রি হল একটি বিস্তৃত সাবগ্রাফ যা প্রায়শই আগ্রহের বিষয়। একটি গ্রাফের একটি চক্র যেখানে গ্রাফের সমস্ত শীর্ষবিন্দু রয়েছে তাকে একটি বিস্তৃত চক্র বলা হবে।
কতটি স্প্যানিং সাবগ্রাফ আছে?
এখানে 2n প্ররোচিত সাবগ্রাফ রয়েছে (শীর্ষের সমস্ত উপসেট) এবং 2m বিস্তৃত সাবগ্রাফ (প্রান্তের সমস্ত উপসেট)।
আমি কীভাবে একটি বিস্তৃত সাবগ্রাফ খুঁজে পাব?
এবং একটি গ্রাফের স্প্যানিং সাবগ্রাফের সংজ্ঞা অনুসারে G হল একটি সাবগ্রাফ যা প্রান্ত মুছে ফেলার মাধ্যমে প্রাপ্ত হয় শুধুমাত্র। যদি আমরা এক প্রান্ত, দুই প্রান্ত, তিন প্রান্ত ইত্যাদি মুছে প্রান্তের উপসেট তৈরি করি। যেহেতু m প্রান্ত আছে তাই 2^m উপসেট আছে। তাই G এর 2^m স্প্যানিং সাবগ্রাফ রয়েছে৷
বিস্তৃত গাছ বলতে কী বোঝায়?
একটি গ্রাফের (G) বিস্তৃত গাছ হল G এর একটি উপসেট যা ন্যূনতম সংখ্যক প্রান্তব্যবহার করে এর সমস্ত শীর্ষবিন্দুকে কভার করে। একটি বিস্তৃত গাছের কিছু বৈশিষ্ট্য এই সংজ্ঞা থেকে অনুমান করা যেতে পারে: যেহেতু "একটি বিস্তৃত গাছ সমস্ত শীর্ষবিন্দুকে আবৃত করে", তাই এটি সংযোগ বিচ্ছিন্ন করা যাবে না।
স্প্যানিং গ্রাফ তত্ত্ব কি?
একটি বিস্তৃত গাছ হল গ্রাফ G-এর একটি উপসেট, যেটির সমস্ত শীর্ষবিন্দুকে ন্যূনতম সম্ভাব্য সংখ্যক প্রান্ত দিয়ে আচ্ছাদিত করা হয়েছে। তাই, একটি বিস্তৃত গাছের চক্র থাকে না এবং এটি সংযোগ বিচ্ছিন্ন করা যায় না.. এই সংজ্ঞা অনুসারে, আমরা একটি উপসংহার টানতে পারি যে প্রতিটি সংযুক্ত এবং অনির্দেশিত গ্রাফ G-এর অন্তত একটি স্প্যানিং ট্রি রয়েছে।
