ইনসিডেন্স ম্যাট্রিক্স (Incidence Matrix)
ইনসিডেন্স ম্যাট্রিক্স হল একটি গ্রাফ রিপ্রেজেন্টেশন পদ্ধতি যা গ্রাফের ভেরটেক্স এবং এজের মধ্যে সম্পর্ককে নির্দেশ করে। এটি গ্রাফের নোড এবং তাদের সাথে সংশ্লিষ্ট এজগুলির মধ্যে সম্পর্ককে একটি ম্যাট্রিক্স ফর্মে উপস্থাপন করে।
গঠন
- ইনসিডেন্স ম্যাট্রিক্স একটি ম্যাট্রিক্স, যেখানে হল ভেরটেক্সের সংখ্যা এবং হল এজের সংখ্যা।
- প্রতিটি সারি একটি ভেরটেক্সকে নির্দেশ করে এবং প্রতিটি কলাম একটি এজকে নির্দেশ করে।
- একটি ডাইরেক্টেড গ্রাফের জন্য, ইনসিডেন্স ম্যাট্রিক্সের কোষের মান হবে:
- যদি ভেরটেক্সটি এজের প্রারম্ভ নোড হয়।
- যদি ভেরটেক্সটি এজের শেষ নোড হয়।
- যদি ভেরটেক্সটি এজের সাথে সম্পর্কিত না হয়।
- একটি আনডাইরেক্টেড গ্রাফের জন্য, ইনসিডেন্স ম্যাট্রিক্সের কোষের মান হবে:
- যদি ভেরটেক্সটি এজের সাথে সম্পর্কিত হয়।
- অন্যথায়।
উদাহরণ
ধরি, আমাদের একটি গ্রাফ আছে যার ভেরটেক্স A, B, C, D এবং এজ E1 (A-B), E2 (A-C), E3 (B-D)।
ইনসিডেন্স ম্যাট্রিক্স হবে (ডাইরেক্টেড গ্রাফের জন্য):
এখানে:
- E1 এজ A থেকে B এর দিকে যায়, তাই A এর জন্য 1 এবং B এর জন্য -1।
- E2 এজ A থেকে C এর দিকে যায়, তাই A এর জন্য 1 এবং C এর জন্য -1।
- E3 এজ B থেকে D এর দিকে যায়, তাই B এর জন্য -1 এবং D এর জন্য 1।
ইনসিডেন্স ম্যাট্রিক্স (আনডাইরেক্টেড গ্রাফের জন্য):
এখানে:
- E1 এজ A এবং B এর মধ্যে রয়েছে, তাই A এবং B উভয়ের জন্য 1।
- E2 এজ A এবং C এর মধ্যে রয়েছে, তাই A এবং C উভয়ের জন্য 1।
- E3 এজ B এবং D এর মধ্যে রয়েছে, তাই B এবং D উভয়ের জন্য 1।
সুবিধা
- এজ-ভিত্তিক সম্পর্ক: ইনসিডেন্স ম্যাট্রিক্স ব্যবহার করে ভেরটেক্স এবং এজের মধ্যে সম্পর্ক সহজে বোঝা যায়।
- অ্যালগরিদমের জন্য উপযোগী: এটি গ্রাফের বিভিন্ন অ্যালগরিদম, যেমন ফ্লো নেটওয়ার্ক অ্যালগরিদম বা গ্রাফ ট্রাভার্সাল অ্যালগরিদমে সহায়ক।
- স্পষ্ট গঠন: ম্যাট্রিক্সের আকার গ্রাফের ভেরটেক্স এবং এজের সংখ্যা অনুযায়ী নির্ধারিত হয়, যা সহজবোধ্য।
অসুবিধা
- স্থান সংকুলান: ইনসিডেন্স ম্যাট্রিক্সের স্থান ব্যবহার (O(V * E)) হতে পারে, যা বড় গ্রাফের জন্য অযৌক্তিক হতে পারে।
- ডেটা অ্যাক্সেস: নির্দিষ্ট ভেরটেক্সের সাথে সংযুক্ত এজ খুঁজে বের করতে O(E) সময় লাগতে পারে।
সারসংক্ষেপ
ইনসিডেন্স ম্যাট্রিক্স হল একটি কার্যকরী গ্রাফ রিপ্রেজেন্টেশন পদ্ধতি, যা ভেরটেক্স এবং এজের মধ্যে সম্পর্ককে নির্দেশ করে। এটি এজ-ভিত্তিক সম্পর্ক বোঝাতে সহায়ক এবং বিভিন্ন অ্যালগরিদমের জন্য উপযোগী। তবে, এটি অনেক ক্ষেত্রেই স্থান সংকুলান করে এবং ডেটা অ্যাক্সেসে কিছু সীমাবদ্ধতা রয়েছে।
Content added By
Read more
