বর্গমূলের জন্মদিনটা কবে? আমাদের মডারেটরদের দৃষ্টি আকর্ষন করছি। জন্মদিন কবে জানিয়ে দাও! সেদিন আমরা দু’টো কাজ করব। প্রথমটা হল, একটা দামড়া কেক নিয়ে হ্যাপিবার্থডেটুইউ শব্দে কিচিরমিচির করে কেক কাটব, এবং দ্বিতীয়টি হল, গ্রাফথিওরির হ্যান্ডশেকিং লেমা’র প্রুফ হাতে কলমে শিখে ফেলব। সবার কাজ হচ্ছে, নিজে কয়জনের সাথে সেই পার্টিতে হাত মেলালো, তার হিসেব রাখা। ব্যাপারটা ভাবতেই মজা লাগছে। ছেলেমেয়েরা হ্যান্ডশেক করেই সশব্দে ঘোষণা করছে “তেরো!” “…একুশ! “…চৌত্রিশ!” 😀

ধরাযাক, বর্গমূলের জন্মদিনে ৫০ জন মানুষ এসেছে। প্রত্যেকেই কারও না কারও সাথে হ্যান্ডশেক করেছে। কেউ করেছে ১ জনের সাথে, কেউ করেছে একচল্লিশ জনের সাথে। তো সবমিলিয়ে মোট কতগুলো হ্যান্ডশেক হয়েছে? এই উত্তরটাই দেবে হ্যান্ডশেকিং লেমা।

এই লেমা অনুযায়ী, প্রত্যেকে আলাদা আলাদা ভাবে যতগুলো হ্যান্ডশেক করেছে, তার যোগফল সম্মিলিত ভাবে মোট হ্যান্ডশেকের সংখ্যার দ্বিগুন।

প্রত্যেকটি মানুষকে একেকটা ভার্টেক্স এবং প্রত্যেকটি হ্যান্ডশেককে একেকটা এজ হিসেবে ভাবলে, বর্গমূলের জন্মদিনের গেটটুগেদারটাকে রাতারাতি একটা নিখুঁত আনডিরেক্টেড গ্রাফ হিসেবে চালিয়ে দেয়া যায়। বর্গমূলের $i$-তম সদস্য (বা ভার্টেক্স) যদি $k_i$ বার হ্যান্ডশেক করে, এবং সম্মিলিত ভাবে যদি মোট $m$ সংখ্যক হ্যান্ডশেক সম্পন্ন হয়, তাহলে আমরা গ্যারান্টি দিয়ে বলতে পারি,

\begin{eqnarray}
\sum_i k_i = 2m
\end{eqnarray}

যারা আগের পোস্ট গুলো পড়েছেন, তারা বুঝে ফেলেছেন যে আমি বলতে চাচ্ছি, একটা আনডিরেক্টেড নেটওয়ার্কে সবগুলো ভার্টেক্সের ডিগ্রীর সামেশন নিলে যে রেজাল্ট পাওয়া যাবে, সেটা হল সেই নেটওয়ার্কে সব এজের যোগফলের দ্বিগুণ। এটিই হ্যান্ডশেকিং লেমা।

প্রমাণটা মোটেও কঠিন নয়। একটা শিশু-নেটওয়ার্ক দিয়েই আগাই। গুনতে সুবিধা।

ছবির নেটওয়ার্কটিতে দ্যাখা যাচ্ছে, ভার্টেক্স ১ এর ডিগ্রী = $2$, এবং তা ভার্টেক্স-২ এবং ভার্টেক্স-৩ এর সাথে যুক্ত। তাহলে $k_1 = 2$. একই ভাবে, $k_2 = 2, k_3=2$. এখন আমরা সব $k_i$’কে যোগ করে দেব। যোগফল $6$.

কিন্তু আমরা যখন $k_1$ হিসেব করেছি, তখন ভার্টেক্স-১ থেকে ভার্টেক্স-২ পর্যন্ত এজ’টিকে একবার তো গুনেছিই, আবার যখন $k_2$ হিসেব করেছি, তখন ঐ একই এজ’কে আবার গুনেছি। সুতরাং, এভাবে যোগ করলে, প্রতিটি ভার্টেক্সকে আমরা দুই বার করে গুনছি। গ্রাফ যত দামড়া সাইজেরই হোকনা কেন, এই ঘটনা খুবই সত্য। তাই আসলে এজ’এর মোট সংখ্যা হবে এভাবে যোগ করে পাওয়া রেজাল্টকে ২ দিয়ে ভাগ। অর্থাৎ মোট এজের সংখ্যা যদি $m$ হয় তাহলে,

$$m = \frac{1}{2}(k_1+k_2+\ldots+k_n) $$

প্রুফ শেষ হয়ে গেল!  এই ছবির ক্ষেত্রে, $\frac{6}{2}=3$.

এই সিনারিওটা  আসলে এ্যাডজেসেন্সি ম্যাট্রিক্সের মধ্যেই জ্বলজ্বল করে। ছবির গ্রাফের এ্যাডজেসেন্সি ম্যাট্রিক্স হলঃ
\begin{eqnarray}
A =
\left(
\begin{matrix}
0 && 1 && 1 \\
1 && 0 && 1 \\
1 && 1 && 0
\end{matrix}
\right)
\end{eqnarray}

আগের কোন একটা পোস্ট থেকে আমরা জানি, এ্যাডজেসেন্সি ম্যাট্রিক্স $A$-এর $i$th Row-sum হচ্ছে ভার্টেক্স-$i$ এর ডিগ্রী। তাহলে সবগুলো রোও-সাম নিয়ে যোগ করে দিলে সব ভার্টেক্সের ডিগ্রী’র যোগফল পাওয়া যাবে।
\begin{eqnarray}
k_i &=& \sum_j A_{ij} \nonumber \\
\implies \sum_i k_i &=& \sum_i \sum_j A_{ij}
\end{eqnarray}

কিন্তু আগের পোস্টে আমরা এটাও দেখেছি যে আনডিরেক্টেড গ্রাফের ক্ষেত্রে এ্যাডজেসেন্সি ম্যাটরিক্সটা সিমেট্রিক। মানে, $i$ থেকে $j$’তে এজ থাকা মানেই $j$ থেকে $i$’তে এজ থাকা। সুতরাং $\sum_{i,j}A_{ij}$’তে আমরা প্রতিটি এজকে দুইবার কাউন্ট করছি। তাই মোট এজের সংখ্যা নিঃসন্দেহে

$$m = \frac{1}{2}\sum_{i,j}A_{ij}$$.

ব্যস! প্রমাণ হয়ে গেল!।

কো’নিগসবার্গের সপ্তসেতু
এবার একটু অন্য প্রসঙ্গে আসি। শুধু হ্যান্ডশেকিং লেমা দিয়ে পোস্ট লিখে পলায়নটা ফাঁকিবাজি মনে হচ্ছিল। তাই একটু অবকাশযাপনের উদ্দেশ্যে অষ্টাদশ শতাব্দি থেকে ঘুরে আসা যাক। এই ঘটনাটা অনেকেরই জানা। তবু আবার বলি আড্ডাবাজির খাতিরে।

প্রুশিয়ার কো’নিগসবার্গ শহরটি বেড়ে উঠেছিল প্রেগলিয়া নদীর চারপাশে। নদীর মাঝে ছিল একটা দ্বীপ, আর সেই দ্বীপের চারপাশের নদীর অন্য পাড়ে তিনটে ভুমি বা মেইনল্যান্ড। এই চার জায়গার মধ্যে যোগাযোগ রক্ষা করার জন্য দাঁড় করানো হয়েছিল সাতটি ব্রিজ। এই হচ্ছে ১৭৩৬ সালের কো’নিগসবার্গের গুগল-ম্যাপস। 😉

একসময় ব্রিজ গুলো নিয়ে একটা জটিল ধাঁধা তৈরি হল। ধরাযাক, আমাদের আরিফিন ডেঙ্গু থেকে উঠেই ব্রিজগুলো দিয়ে হাঁটাহাঁটি শুরু করে দিয়েছে। তাকে কন্ডিশন ধরিয়ে দেওয়া হল, “তোমাকে প্রতিটি ব্রিজে অন্তত একবার পা রাখতেই হবে। এবং একটি ব্রিজে একবারের বেশি পা রাখলেই মাইর! নদীটাও সাঁতরে বা নৌকায় করে পার হওয়া চলবেনা, কেবলমাত্র ব্রিজ দিয়েই পার হতে হবে। তবে, দ্বীপে বা তিনটি মেইনল্যান্ডেই তুমি বিভিন্ন ব্রিজ’দিয়ে যতবার খুশি আসতে-যেতে পারবে। তোমার কাজ হল, সব গুলো ভুমিতে অন্তত একবার করে পদধুলি দিয়ে আসা। যেই ভুমি থেকে শুরু করবে, সেখানেই এসে শেষ করতে হবে -এমন কোন কথা নেই। যেখান থেকে খুশি, হাঁটা শুরু কর!”

প্রশ্ন হল, এই শর্ত গুলো মেনে এরকম কতগুলো পথ আরিফিন বের করতে পারবে? আরিফিনের এই ব্রিজব্রাজন সেসময়ের ম্যাথম্যাটিশিয়ানদের মধ্যে বেশ আলোচিত হতে লাগল, কিন্তু কেউই কোন সলিউশন বের করতে পারলেন না। একসময় লিওনার্ড অয়লার এগিয়ে এলেন। অয়লারের হস্তক্ষেপ মানেই মোটামুটি যেকোন ম্যাথম্যাটিকাল সমস্যার সমাধান। তিনি খুবই সহজ একটা আর্গুমেন্ট দিয়ে প্রমান করে ফেললেন, এরকম কোন পথ আরিফিন আদৌ বের করতে পারবেনা! ইন ফ্যাক্ট, অয়লার এই কথাটা বলে গণিতের গ্রাফ-থিওরী শাখাটাই আবিষ্কার করে ফেললেন। এখন আর্গুমেন্টটা সহজ মনে হলেও, আঠারো শতকে মনে হয়না এটা সহজ ছিল।

যা হোক, অয়লারের নবউদ্ভাবিত গ্রাফ থিওরির চোখে প্রমানটার দিকে তাকালেই সব ফকফকা। প্রথমে দ্বীপ আর মেইনল্যান্ড গুলোকে চারটা ভার্টেক্স $A,B,C,D$ এবং ব্রিজগুলোকে সাতটা এজ ধরে নিলাম।

আগের পোস্টে অয়লারিয়ান পাথ ডিফাইন করেছিলাম। আবারও করছি।

ধরা যাক, একটা নেটওয়ার্কে এমন একটা পাথ আছে, যেটা অনুযায়ী ভ্রমণ করলে সবগুলো ভার্টেক্সেই যাওয়া যায়। তবে শর্ত হল, ভ্রমনের সময় একটা এজ অন্তত একবার, এবং কেবল মাত্র একবারই ভিজিটেড হয়। এরকম পাথের নাম রাখা হয়েছে অয়লারিয়ান পাথ। আমরা বুঝতে পারছি, আরিফিনকে ঐ শর্ত গুলো স্যাটিসফাই করতে হলে একটা অয়লারিয়ান পাথ খুঁজে বের করতে হবে।

ধরে নিচ্ছি, একটা নেটওয়ার্কে অয়লারিয়ান পাথ আছে। সেই অয়লারিয়ান পাথে ভ্রমনের মধ্যে যেসব ভার্টেক্স পড়বে, সেসব ভার্টেক্সকে যতবার খুশি ভিজিট করা যাবে, কিন্তু একই এজ দিয়ে না। অর্থাৎ, একটা ভার্টেক্স যদি আমাদের রাস্তায় একবার পড়ে যায়, তাহলে আমরা সেখানে একটা এজ দিয়ে ঢুকব, আরেকটা এজ দিয়ে বেরিয়ে যাব। অর্থাৎ ভার্টেক্সটির ডিগ্রী হবে = $2$. এই এজ দুটো আর কখনোই ব্যবহার করা যাবেনা। আবার এই ভার্টেক্সটিই যদি দুইবার ভিজিট করতে হয়, তাহলে দ্বিতীয়বার,সম্পুর্ন নতুন একটা এজ দিয়ে ঢুকব, এবং নতুন আরেকটা এজ দিয়ে বেরিয়ে যাব। ডিগ্রী হবে চার। যার অর্থ দাঁড়াচ্ছে, একটা ভার্টেক্সকে $\lambda$ বার ভিজিট করলে তার ডিগ্রী হবে $2\lambda$, যেটা একটা ইভেন নাম্বার।

মজার শুরু এখানেই। এবার বলুন দেখি, এরকম অয়লারিয়ান পাথ সমৃদ্ধ কোনো নেটওয়ার্কে কি একটাও ভার্টেক্স পাওয়া যাবেনা যার ডিগ্রী বেজোড় সংখ্যা?

যদি একটা ভার্টেক্সের ডিগ্রী বেজোড় সংখ্যা হয়, ধরা যাক তিন, তাহলে সেটার মানে কী দাঁড়ায়? প্রতিটি এজকে তো একবার ব্যবহার করতেই হবে অয়লারিয়ান পাথ হতে হলে। তাই তিনের মধ্যে দুটো এজ দিয়ে নিশ্চয়ই আমরা ভার্টেক্সটিতে ঢুকব-বেরুবো। অন্য এজটি দিয়ে হয় ঢুকব, নয়ত বেরুবো। অন্য সব বেজোড় সংখ্যা $2\lambda+1$-এর জন্যও তাহলে $2\lambda$ সংখ্যক এজ দিয়ে আমরা ঢুকব বেরুবো, এবং বাকি একটা এজ দিয়ে হয় ঢুকব, নয়ত বেরুবো।

এরকম দুটো পসিবলিটি কোন ভার্টেক্সের সাথে মেলে বলুন দেখি? নিশ্চিত ভাবেই ভার্টেক্স দুটি হচ্ছে স্টার্টিং আর এন্ডিং ভার্টেক্স। প্রথমটার বেজোড়তম এজটি দিয়ে বেরিয়ে যাত্রা শুরু করব, আর শেষটার বেজোড় তম এজটি দিয়ে ঢুকে যাত্রা শেষ করব।

তো, এই বেজোড় বা অড ডিগ্রী ওয়ালা কতগুলো ভার্টেক্স একটা অয়লারিয়ান পাথ সমৃদ্ধ নেটওয়ার্কে থাকতে পারে? উত্তর হল, সর্বোচ্চ দুটি (অথবা, স্টার্টিং আর এন্ডিং ভার্টেক্স একই হলে, একটিও না)।

কো’নিগসবার্গের সপ্তসেতুর দিকে তাকান, $A,B,C,D$-চারটি নোডের প্রতিটির ডিগ্রীই বেজোড়। তাই আমাদের নিবিষ্ট হন্টক আরিফিন নদীর এপারওপারে সবগুলো ভুমিতে পৌঁছানোর জন্য এমন কোন রাস্তা কখনোই খুঁজে পাবেনা যেটা অনুসরণ করে চললে প্রতিটি ব্রিজে অন্তত একবার এবং কেবল মাত্র একবারই তার পা পড়ে। সুতরাং, সে মাঠে নামলেই, মাইর!

অষ্টাদশ শতাব্দি থেকে বর্তমানে টাইমট্র্যাভেল করতে খানিক সময়  লাগছে। পরের পোস্ট পর্যন্ত শুভকামনা।

: -)

.

নেটওয়ার্ক উপাখ্যান সিরিজের পোস্ট গুলোঃ   ১   ২   ৩   ৪   ৫   ৬

Author: Galib Hassan

Mischief Managed.. 😉