পাথ লেংথের কথা সবার মনে আছে নিশ্চয়ই? একটা নোড থেকে আরেকটা নোডে যাওয়ার রাস্তায় যত গুলো এজ পার হতে হবে, সেই সংখ্যাটাই পাথ লেংথ। এবার গতদিনের আঁকা ডিরেক্টেড নেটওয়ার্কটার দিকে আবার একটু তাকানো যাক।
এই নেটওয়ার্কটিতে ভার্টেক্স ৪ থেকে ২ -এ যেতে কতগুলি পথ আছে? আমার মনে হয়, তিনটিঃ
– একটা হল, ৪,১,২। যেহেতু এই রাস্তায় দুটো এজ পার হতে হয়, তাই এই পথটির লেংথ = $2$.
– আরেকটা পথ, ৪,৫,১,২। এবার এজ ব্যবহার করেছি তিনটে। তাই এই পথের লেংথ = $3$.
– আরেকটা পথই বাকি। ৪,২। এই পথের লেংথ = $1$.
এদের মধ্যে জিওডেসিক কোনটা? অবশ্যই ৪,২ পথটি। কারন এই পথের লেংথ সবচে ছোট।
এখন যদি প্রশ্ন করা হয়, যেকোন ভার্টেক্স $i$ থেকে $j$ পর্যন্ত কতগুলো পথে পৌঁছানো সম্ভব, এবং তাদের মধ্যে জিওডেসিক কোনটি – তাহলে কি আমরা মাথায় হাত দেব?
মোটেই না! এ্যাডজেসেন্সি ম্যাট্রিক্স থাকতে মাথায় হাত? প্রশ্নই আসেনা। নেটওয়ার্কটির এ্যাডজেসেন্সি ম্যাট্রিক্সের দিকে তাকাচ্ছিঃ
এখান থেকে পাথ-লেংথ কিভাবে বের হবে?
এক কাজ করি। ম্যাট্রিক্সটাকে স্কয়্যার করে দিই।
\begin{eqnarray}
A^2 = A\cdot A
&=&
\left(
\begin{matrix}
0 && 0 && 0 && 1 && 1 \\
1 && 0 && 1 && 1 && 0 \\
0 && 0 && 0 && 0 && 0 \\
0 && 0 && 0 && 0 && 0 \\
0 && 0 && 0 && 1 && 0
\end{matrix}
\right)
\cdot
\left(
\begin{matrix}
0 && 0 && 0 && 1 && 1 \\
1 && 0 && 1 && 1 && 0 \\
0 && 0 && 0 && 0 && 0 \\
0 && 0 && 0 && 0 && 0 \\
0 && 0 && 0 && 1 && 0
\end{matrix}
\right) \nonumber \\ \\
\therefore \quad A^2 \quad &=& \left(
\begin{matrix}
0 && 0 && 0 && 1 && 0 \\
0 && 0 && 0 && 1 && 1 \\
0 && 0 && 0 && 0 && 0 \\
0 && 0 && 0 && 0 && 0 \\
0 && 0 && 0 && 0 && 0
\end{matrix}
\right) \nonumber \\
\end{eqnarray}
স্কয়্যার করা হয়ে গেল। পুরানো গল্পে ফেরা যাক। আমরা ভার্টেক্স ৪ থেকে ২ -এ যাবার রাস্তা খুঁজছিলাম। এবার $A^2$ ম্যাট্রিক্সের ২ নম্বর রোও এবং ৪ নম্বর কলাম কী বলছে দেখুন তো? দেখা যাচ্ছে, $[A^2]_{24} = 1$. মজার ব্যাপার হচ্ছে, এই $1$-টাই নির্দেশ করছে যে, ভার্টেক্স-৪ থেকে ভার্টেক্স-২ পর্যন্ত $2$ লেংথের পথের সংখ্যা = $1$. ব্যাপারটা ভাক্কাবাজি মনে হলে আসুন $A$-এর কাঁধে কিউব চড়িয়ে দেই।
\begin{eqnarray}
A^3 \quad
= \left(
\begin{matrix}
0 && 0 && 0 && 0 && 0 \\
0 && 0 && 0 && 1 && 0 \\
0 && 0 && 0 && 0 && 0 \\
0 && 0 && 0 && 0 && 0 \\
0 && 0 && 0 && 0 && 0
\end{matrix}
\right)
\end{eqnarray}
$A$-এর কাঁধে পাওয়ার যখন $3$ তুললাম, তখন ম্যাট্রিক্সটির মধ্যে একটিই মাত্র নন-জিরো এন্ট্রি দ্যাখা যাচ্ছে, সেটা হল, $[A^3]_{24}$. তাহলে কি এই $1$ -নির্দেশ করছে $3$ লেংথের পাথের সংখ্যা = $1$? নিশ্চয়ই! ছবি থেকেও আমরা তাই দেখতে পাচ্ছি। তিন-লেংথের কেবল মাত্র একটাই পথ, এবং সেটা ভার্টেক্স ৪ থেকে ২ -এ।
নেটওয়ার্কটিতে $4$-লেংথের কোন পথ নেই। তাহলে কি প্রিতিটি $[A^4]_{ij}=0$ হবে? করে দ্যাখা যাকঃ
\begin{eqnarray}
A^4 \quad
= \left(
\begin{matrix}
0 && 0 && 0 && 0 && 0 \\
0 && 0 && 0 && 0 && 0 \\
0 && 0 && 0 && 0 && 0 \\
0 && 0 && 0 && 0 && 0 \\
0 && 0 && 0 && 0 && 0
\end{matrix}
\right)
\end{eqnarray}
ব্যাপারটা মজার না? আসলে এই ঘটনাটা একটা জেনারেল রেজাল্ট। একটা নেটওয়ার্কে এ্যাডজেসেন্সি ম্যাট্রিক্স $A$ এবং যেকোন $r\in \mathbb{N}$ এর জন্য $[A^r]_{ij}$ হচ্ছে ভার্টেক্স $j$ থেকে $i$-এ $r$-লেংথের পথের সংখ্যা।
আনডিরেক্টেড গ্রাফের ক্ষেত্রে জিনিসটা কেমন যেন ভজঘট পাকিয়ে যায়। আমি স্ট্যাকএক্সচেইঞ্জে প্রশ্ন করেছিলাম, যে আনডিরেক্টেড গ্রাফের ক্ষেত্রে এই নিয়মটা কাজ করেনা কেন। উত্তর এল, উপরের নিয়মে আসলে $r$-লেংথের “Walk” বের হয়, “path” নয়। বিড়ম্বনাটা দুটো সংজ্ঞা দিয়ে ক্লিয়ার করছি।
হ্যামিল্টনিয়ান পাথ
যেই পাথে ভ্রমন করলে কোন একটা ভার্টেক্স একবারের বেশি ভিজিটেড হয়না, সেটা হ্যামিল্টনিয়ান পাথ।
অয়লারিয়ান পাথ
যেই পাথে ভ্রমন করলে, কোন একটা এজ একবারের বেশি ভিজিটেড হয়না, সেটা অয়লারিয়ান পাথ।
আমার বিড়ম্বনাটা যেখানে দাঁড়িয়েছিল সেটা হল, স্ট্যাকএক্সচেইঞ্জের লোকজন Path বলতে শুধু হ্যামিল্টনিয়ান বা Eularian Path বোঝাচ্ছিল। আর Walk বলতে যেকোন পাথ বোঝাচ্ছিল, যেক্ষেত্রে একটা ভার্টেক্স বা এজ এক বা তারচে’ বেশি সংখকবার ভিজিটেড হতে পারে।
নাহ, ঘুম চলে এল। লেখা এলোমেলো হয়ে যাচ্ছে। এই থিওরি থেকে জিওডেসিক কিভাবে বের করা যায় সেটা ভেবে বের করে ফেলুন।
আমি ঘুম বিরতি নিচ্ছি।
: -)
নেটওয়ার্ক উপাখ্যান সিরিজের পোস্ট গুলোঃ ১ ২ ৩ ৪ ৫ ৬
Author: Galib Hassan
Mischief Managed.. 😉
সাম্প্রতিক মন্তব্য