আগের পোস্টে নেটওয়ার্ক সায়েন্সের খুব বেসিক কিছু ধারনা আলোচনা করতে করতে আমরা বুঝতে পেরেছি, জিনিসটাকে ওভাবে এগিয়ে নিয়ে যাওয়াটা একটু বোরিং। আজকের ম্যাজিক দিয়ে সেই বোরডমটা কেটে যাবে। নিচের পিচ্চি নেটওয়ার্কটার দিকে তাকান।
গত পোস্ট থেকে আমরা জেনেছি, নেটওয়ার্কটিতে
– ভার্টেক্স বা নোডের সংখ্যা $n = 5$,
– এজের সংখ্যা $m=6$.
এবার এমন একটা স্কয়্যার ম্যাট্রিক্স চিন্তা করা যাক, যেটার সাইজ $n\times n$. অর্থাৎ আমাদের এই ক্ষেত্রে $5\times 5$. ম্যাট্রিক্সের নাম রাখলাম $A$. যদি আমাদের নেটওয়ার্কের ভার্টেক্স-$i$ এবং ভার্টেক্স-$j$ এর মধ্যে একটা এজ থাকে, তাহলে এই ম্যাট্রিক্সের $i$-তম রোও এবং $j$-তম কলামে আমরা একটা $1$ বসিয়ে দেব। আর যদি এজ না থাকে, তাহলে বসাব $0$. ব্যস! হয়ে গেল এ্যাডজেসেন্সি ম্যাট্রিক্স!
আমাদের নেটওয়ার্কের $A$ তাহলে দেখতে কেমন হবে? ভার্টেক্স ১ এবং ২ এর মধ্যে একটা এজ আছে। তাহলে ম্যাট্রিক্স $A$-এর ১ম রোও এবং ২য় কলামে একটি $1$ বসবে। আবার ভার্টেক্স ১ থেকে ৩ -এ কোন এজ নেই। তাহলে ১ম রোও এবং ৩য় কলামে বসবে $0$. অর্থাৎ
$$A_{12} = 1, \quad A_{13} = 0 \quad \ldots$$
ইত্যাদি। আমরা প্রথাগত নিয়মেই ইনডেক্সিং করছি। অর্থাৎ $A_{ij}$ -এর $i$ হল রোও-ইনডেক্স, আর $j$ হল কলাম-ইন্ডেক্স।
আমাদের নেটওয়ার্কের সব জানা অজানা তথ্য আমরা এই এ্যাডজেন্সি ম্যাট্রিক্সের ভেতরে এনকোড করে ফেলেছি। আমরা ধীরে ধীরে জানব। তবে কিছু রহস্য এখনি উন্মোচন করে ফেলি।
ডিগ্রী
আগের পোস্ট থেকে আমরা জানি, ভার্টেক্স ৪ -এর ডিগ্রী, $k_4 = 3$. কারন ভার্টেক্স ৪ এর সাথে তিনটে এজ যুক্ত। এ্যাডজেসেন্সি ম্যাট্রিক্স এটা নিয়ে কী বলে? ভার্টেক্স ৪ এর জন্য $A$ এর চার-নম্বর রোও বরাবর এন্ট্রি গুলো যোগ করে দিনতো? রেজাল্ট তিন। তারমানে $A$-এর i’th Row-sum হচ্ছে নেটওয়ার্কটির $i$-তম ভার্টেক্সের ডিগ্রী!
\begin{eqnarray}
k_i = \sum_j A_{ij}
\end{eqnarray}
মনে করিয়ে দেই, কোন ম্যাট্রিক্সের রোও বরাবর সামেশন চাইলে তার একটা রোও’কে ফিক্স করে সব কলামের ওপর সামেশন রান করতে হয়। অর্থাত আমাদের ভার্টেক্স ৪ এর ক্ষেত্রে সেটা হয়েছে
$$A_{41}+A_{42}+A_{43}+A_{44}+A_{45}$$
তাই সামেশনের ইনডেক্সটা $j$.
আনডিরেক্টেড গ্রাফ
আমাদের নেটওয়ার্কের ক্ষেত্রে $A$ ম্যাট্রিক্সটি সিমেট্রিক। অর্থাৎ সে নিজেই তার ট্রান্সপোজ।
\begin{eqnarray}
A = A^T
\end{eqnarray}
এটার কারন হল, $i$ থেকে $j$ ‘তে একটা এজ আছে মানেই তো $j$ থেকে $i$ ‘তে একটা এজ আছে। নো সারপ্রাইজ। এই ধরনের গ্রাফ গুলোকে বলা হয় আনডিরেক্টেড গ্রাফ।
ডিরেক্টেড গ্রাফ
আমাদের নেটওয়ার্কের এজ গুলোতে কিছু ডিরেকশন জুরে দেই।
লক্ষ্য করুন, এখন ভার্টেক্স ৪ থেকে ১ -এ যাওয়ার রাস্তা আছে। কিন্তু ১ থেকে ৪ -এ যাওয়ার কোন রাস্তা নেই। এই ধরনের গ্রাফ গুলোকে বলে ডিরেক্টেড গ্রাফ। এদের ক্ষেত্রে ডিগ্রী’র ডেফিনিশনও তাই অন্য রকম।
ইন-ডিগ্রী, আউট ডিগ্রী
ডিরেক্টেড গ্রাফে একটা ভার্টেক্সের সাথে কানেক্টেড এজ গুলোর মধ্যে যত গুলো এজ তার দিকে তীর চিহ্ন তাক করে বসে থাকে, সেই সংখ্যা হচ্ছে ইন-ডিগ্রী। সোজা কথা, ভার্টেক্সটির দিকে ইনওয়ার্ড এজের সংখ্যা হল ইন-ডিগ্রী। একই ভাবে ভার্টেক্সটি থেকে অউটওয়ার্ড এজের সংখ্যা হচ্ছে আউট-ডিগ্রী। এগুলোকে যথাক্রমে $k_i^{in}$ এবং $k_i^{out}$ দিয়ে লেখা হয়। যেমন আমাদের ডিরেক্টেড নেটওয়ার্কটিতে ভার্টেক্স ১ এর ক্ষেত্রে,
$$k_1^{in} = 2, \quad k_1^{out}=1 $$
ইত্যাদি।
ডিরেক্টেড গ্রাফের এ্যাডজেসেন্সি ম্যাট্রিক্স
ডিরেক্টেড গ্রাফের ক্ষেত্রে যেহেতু $i$ থেকে $j$ এর লিঙ্ক মানেই $j$ থেকে $i$ -এর লিঙ্ক নয়, তাই তার এ্যাডজেসেন্সি ম্যাট্রিক্সটিও সিমেট্রিক নয়। এই ক্ষেত্রে $A$ ‘কে আমরা তৈরি করব একটু অন্য ভাবে। যদি $j$ থেকে $i$ -এর দিকে একটা এজ থাকে, তাহলে আমরা $A_{ij} = 1$ বসাব। আর $j$ থেকে $i$-এর দিকে কোন এজ না থাকে, তাহলে $A_{ij}=0$ বসাব।
তাহলে এই ক্ষেত্রে ম্যাট্রিস্ক $A$ দাঁড়াবে নিচের ছবির মত। 
এবার যদি আমি $A$ -এর $i$’তম রোও বরাবর সামেশন চালিয়ে দেই, তাহলে কি কোন ডিগ্রী পাব? নিশ্চয়ই পাব! নেটওয়ার্কটির দিকে তাকান এবং ভার্টেক্স ৪ কথা ভাবুন। তার ইন-ডিগ্রী শুন্য। কিন্তু আউট-ডিগ্রী তিন। এ্যাডজেসেন্সি ম্যাট্রিক্স কী বলছে? চতুর্থ রোও বরাবর সামেশন = শুন্য, এবং চতুর্থ কলাম বরাবর সামেশন = তিন! ব্যস, হয়ে গেল ডিগ্রীর রহস্য ভেদ।
\begin{eqnarray}
k_i^{in} = \sum_j A_{ij}, \qquad
k_j^{out} = \sum_i A_{ij}, \qquad
\end{eqnarray}
$k^{out}$-এর ক্ষেত্রে সামেশনটা কিন্তু একটা কলাম-সাম। তাই সামেশনের ইনডেক্সটা $i$.
স্বভাবতই দেখা যাচ্ছে, এক্ষেত্রে এ্যাডজেসেন্সি ম্যাট্রিক্সটি সিমেট্রিক নয়। এই কারনে ডিরেক্টেড নেটওয়ার্ক সবসময়ই একটু কমপ্লিকেটেড।
একটু একটু করেই গল্প চলুক। পরের পোস্টে পাথ লেংথ নিয়ে ফিরছি।
: -)
.
নেটওয়ার্ক উপাখ্যান সিরিজের পোস্ট গুলোঃ ১ ২ ৩ ৪ ৫ ৬
Author: Galib Hassan
Mischief Managed.. 😉
সাম্প্রতিক মন্তব্য