কানেক্টিভিটি, ডিস্ট্যান্স এবং স্প্যানিং ট্রি

স্প্যানিং ট্রি

একটি সহজ সংজ্ঞা হল: একটি ট্রি হল একটি কানেক্টেড গ্রাফ যাতে কোনো সাইকেল নেই, যেখানে একটি সাইকেল আমাদের একটি নোড থেকে নিজে আসলো যেতে দেয় কোনো এজ রিপিট ছাড়া।

একটি কানেক্টেড গ্রাফ G-এর জন্য একটি স্প্যানিং ট্রি হল একটি ট্রি যেটি G-এর সব ভার্টেক্স ধারণ করে।

স্প্যানিং ট্রি প্রায়:internet রাউটিং অ্যালগরিদমে ব্যবহৃত হয়। ইন্টারনেটে, কম্পিউটার (নোড) প্রায় অনেক রিডান্ডান্ট ফিজিক্যাল কানেকশন দিয়ে কানেক্টেড থাকে।

এক গ্রাফে মোট স্প্যানিং ট্রির সংখ্যা। যদি একটি গ্রাফ n সংখ্যক ভার্টেক্সের সাথে একটি কমপ্লিট গ্রাফ হয়, তবে মোট স্প্যানিং ট্রির সংখ্যা nⁿ⁻² হবে।

যেখানে n হল গ্রাফে নোডের সংখ্যা। কমপ্লিট গ্রাফে, কাজটি n নোডের সাথে আলাদা-अলাদা লেবেলড ট্রি গণনার সমান, যার জন্য কেইলির সূত্র প্রযোজ্য।

কানেক্টিভিটি

গণিত এবং কম্পিউটার সায়েন্সে, কানেক্টিভিটি গ্রাফ থিয়রির মূল ধারণাগুলোর একটা।

এই বলতে পারে নোড বা এজের ন্যূনতম সংখ্যা কত যা বাদ দিলে বাকি নোডগুলো আলাদা-अলাদা সাবগ্রাফে ভাগ হয়ে যায়।

এটি নেটওয়ærk ফ্লো সমস্যার থিয়রির সাথে ঘনিষ্ঠভাবে জড়িত।

ড্যাশড এজটি সরিয়ে দিলে এই গ্রাফ ডিসকানেক্টেড হয়ে যায়।

ভার্টেক্স কানেক্টিভিটি। একটি গ্রাফের ভার্টেক্স কানেক্টিভিটি হল সেই ন্যূনতম সংখ্যক নোড যাদের ডিলিট করলে গ্রাফটি ডিসকানেক্টেড হয়ে যায়।

ভার্টেক্স কানেক্টিভিটিকে কখনো "পয়েন্ট কানেক্টিভিটি" বা সহজে "কানেক্টিভিটি" বলা হয়।

এজ কানেক্টিভিটি। যে ন্যূনতম সংখ্যক এজ গ্রাফ থেকে বাদ দিলে সেটি ডিসকানেক্টেড হয়ে যায়, সেটিও লাইন কানেক্টিভিটি হিসেবে জানা যায়।

একটি ডিসকানেক্টেড গ্রাফের এজ কানেক্টিভিটি ০, আর একটি ব্রিজযুক্ত কানেক্টেড গ্রাফের এজ কানেক্টিভিটি ১।

ডিস্ট্যান্স

দুই নোডের মধ্যকার দূরত্ব লোয়েস্ট কমন एন্সেস্টার (LCA) দিয়ে ক্যালকুলেট করা যায়। সূত্র নিচে:

Dist(d1, d2) = Dist(root, d1) + Dist(root, d2) - 2*Dist(root, lca) 
// 'd1' এবং 'd2' হল দুটি দিয়ে গিয়ে কী
// 'root' হল দিয়ে দিয়ে বাইনারি ট্রির রুট
// 'lca' হল d1 এবং d2-এর লোয়েস্ট কমন এন্সেস্টার
// Dist(d1, d2) হল d1 এবং d2-এর মধ্যকার দূরত্ব