গ্রাফ থিওরি (পর্ব ৪)
প্রোগ্রামিং — ১
গ্রাফের বন-জঙ্গল
আমরা ধীরে ধীরে গ্রাফের ভেতর ঢুকতে শুরু করেছি। এবার কিছু সিরিয়াস লেখাপড়ার প্রস্তুতি নেয়া যেতে পারে। নিচের ছবিটি খেয়াল করা যাক তাহলে,
উপরের ছবিতে বেশ লম্বা-চওড়া একটা গ্রাফ দেখা যাচ্ছে। গ্রাফের নাম দেয়া হয়েছে G। এই গ্রাফে অনেকগুলো এজ আছে কিন্তু আমরা শুধু দুটি এজের নাম এখানে উল্লেখ করেছি। কারণ এরা বিশেষ এজ। আমরা যদি p বা e এজটি সরিয়ে ফেলি তাহলে গ্রাফটি আর connected থাকেনা, নিচের চিত্রের মতো disconnected graph পাওয়া যায়।
p এজটি সরিয়ে দেয়ার ফলে দুটি বিচ্ছিন্ন অংশ তৈরি হয়েছে যাকে আমরা রঙিন এলাকা দিয়ে ঘিরে দেখিয়েছি। এখানে আমরা দুটো এলাকা পেয়েছি। এদেরকে component বলে। এটা প্রকাশ করার নিয়ম হচ্ছে, C(G) = 2, মানে হচ্ছে যে G গ্রাফের component দুটি। পাশের ছবিতে e এজ সরিয়ে নিয়েও একইভাবে দুটি component পাওয়া গেছে। এই বিষয়টিকে অন্যভাবেও প্রকাশ করা যায়। G\p বা G\e (এটার উচ্চারণ হচ্ছে ‘জি ব্যাকস্ল্যাস উমুক’) এর component দুটি।
আরেকটা উদাহরণ দেখবো,
ছবি ২৮ এর G গ্রাফটি disconnected। এই গ্রাফের component আমরা দেখতে পাচ্ছি ২ টি। কিন্তু e এজটি সরিয়ে নেয়ার পর component হয়ে গেলো ৩ টি।
ছবি ২৬ এর গ্রাফটি connected graph। connected graph এর component সংখ্যা সবসময় ১ টি হয়। এরপর আমরা ছবি ২৭ এ দেখলাম বিশেষ কোন এজ সরিয়ে নিলে component বেড়ে যাচ্ছে। পরবর্তীতে ছবি ২৮ এ এসে disconnected graph এর ক্ষেত্রেও আমরা এই অবস্থা দেখলাম।
যে এজ সরিয়ে নিলে গ্রাফে component সংখ্যা বেড়ে যায় তাকে Bridge edge বলে।
কোন চক্র বা cycle এর এজগুলো কখনও bridge edge হতে পারেনা, কারণ বোঝার জন্য নিচের ছবিটি খেয়াল করি,
উপরের ছবির গ্রাফের যেকোন একটি এজ সরিয়ে নিলে কি এটার component বেড়ে যাবে বলে তোমার মনে হয়? মোটেও না, চেষ্টা করে দেখতে পারো। গ্রাফটি connected আছে, যেকোন একটি এজ সরিয়ে নিলেও তাই থাকবে।
এখন আমরা মহাগুরুত্বপূর্ণ একটি বিষয় নিয়ে পড়াশোনা করবো, সেটা হচ্ছে ট্রি। ট্রি মানে গাছ, সবাই জানে। কিন্তু তারপরেও আমরা এটিকে ট্রি নামেই ডাকবো। তাহলে শুরু করা যাক।
যে গ্রাফে কোন চক্র বা cycle থাকেনা তাকে চক্রবিহীন গ্রাফ বা acyclic graph বলে। তোমাদের নিশ্চয়ই মনে আছে যে, connected গ্রাফ কি বস্তু!! কোন গ্রাফে যদি এই দুটি বৈশিষ্ট্য (acyclic ও connected) থাকে তবে সেই গ্রাফকে আমরা ট্রি বলবো। কিছুক্ষণ আগেই আমরা দেখেছি যে cycle এর কোন এজ bridge হতে পারেনা। তাহলে কি আমরা বলতে পারি না যে, acyclic graph এর এজগুলো অবশ্যই bridge হবে যদি সেই গ্রাফটি connected হয়? হ্যা পারি।
তাহলে ট্রি এর একটি বিকল্প সংজ্ঞা হতে পারে এরকম, “একটি যুক্ত (connected) গ্রাফের সবগুলো এজ bridge হলে তাকে ট্রি বলে।”
এবার আমরা ট্রি এর কিছু উদাহরণ দেখে ফেলি,
উপরের ছবির (১) নং গ্রাফটি একটি path, বুঝতে নিশ্চয়ই কষ্ট হচ্ছে না। দুনিয়ার সকল path হচ্ছে ট্রি। (২) ও (৩) নং গ্রাফ আসলে একই, একটু ভিন্নভাবে আঁকা হয়েছে আরকি। তোমাদের কি মনে পড়ছে যে, এদেরকে complete bipartite graph বা star নামে ডাকা হয়? এরাও এক ধরনের ট্রি। আরও কিছু উদাহরণ দেখা যেতে পারে,
উপরের ছবির (১) নং গ্রাফটি দেখে কি কিছু মনে পড়ছে? ওই যে অনেকগুলো পা ওয়ালা এক ধরনের পোকা আছে না, শুঁয়াপোকা। ওরকম লাগছেনা? কাছাকাছি তো লাগছে, তাই এই ট্রি এর নাম হচ্ছে শুঁয়াপোকা গ্রাফ বা caterpillar। তুমি যদি (১) নং গ্রাফের উপর-নিচের এজগুলো সরিয়ে ফেলো তাহলে একটা path বাকি থাকে, একে গ্রাফের spine বলা হয়, মেরুদন্ড আরকি। আর পাশেরটা তো double star।
এখন একটা প্রশ্নের উত্তর দাও তো, তোমাকে যদি আমি তিনটি নোড দিয়ে বলি “ট্রি আঁকো”। তাহলে কি করবা? নিচের ছবিটি খেয়াল করি,
উপরের ছবির (১) ও (২) নং গ্রাফ হুবহু একই, একটু খেয়াল করে দেখলেই বোঝা যাবে। তাহলে আমরা বলতে পারি, তিনটি নোড দিয়ে আসলে তিনটি (২, ৩, ৪ নং) ভিন্ন ভিন্ন ট্রি আঁকা সম্ভব। তুমি এদের চেয়ে আলাদা ট্রি আঁকার চেষ্টা করে দেখতে পারো, কিন্তু সেটা সম্ভব না। আসলে তিনটি নোড দিয়ে তিনটির বেশি আলাদা ট্রি আঁকা সম্ভব না। তাহলে মনের মধ্যে প্রশ্ন চলে আসে, ৫টি নোড দিয়ে কতগুলো আলাদা আলাদা ট্রি আঁকা সম্ভব? উপরের ছবির মতো সবগুলো আঁকা শুরু করলে তো দিন শেষ হয়ে যাবে।
n সংখ্যক নোড দিয়ে আলাদা আলাদা কতগুলো ট্রি আঁকা যায় তার একটি সূত্র আছে। এই সূত্রটি আবিষ্কার করেছিলেন বিখ্যাত গণিতবিদ আর্থার ক্যালে (Arthur Cayley)। সূত্রের আলোচনায় যাওয়ার আগে এই ভদ্রলোকের কিছু গল্প বলা যাক।
বেশ অল্প বয়সে (১৭ বছর) এই জনাব ক্যামব্রিজ বিশ্ববিদ্যালয়ে ভর্তি হন। সেখানে তিনি লেখাপড়ায় বেশ সুনাম কুড়ান। কিন্তু তিনি বিশুদ্ধ গণিত নিয়ে পড়াশোনা শেষ করে টাকা-পয়সা আয়ের সুবিধা করতে পারছিলেন না। দিয়ে বাবাজি করলেন কি, ২৫ বছর বয়সে Lincoln’s Inn এ ভর্তি হয়ে গেলেন। এটা হচ্ছে সেই বিশ্ববিখ্যাত প্রতিষ্ঠান যেখান থেকে আরও অনেক দেশের মতো আমাদের দেশের কিছু বিখ্যাত উকিল ব্যারিস্টারি পাশ করে এসেছেন। যাই হোক এখান থেকে লেখাপড়া করে তিনি ১৪ বছর ওকালতিও করেন। কিন্তু গণিতের নেশা উনার তখনও কাটেনি, তাই ৪২ বছর বয়সে উনি যখন ক্যামব্রিজে গণিতের প্রফেসর হওয়ার সুযোগ পেলেন তখন আবার দৌড় দিলেন। যদিও সেখানে ওকালতির মতো আয় রোজগারের সুযোগ ছিলনা।
আচ্ছা গল্প তো হলো, এই ভদ্রলোক যে সূত্র দিয়েছিলেন সেটা হলো, n সংখ্যক নোড দিয়ে একই গ্রাফের আলাদা আলাদা nⁿ⁻ ² সংখ্যক ট্রি আঁকা যায়। ছবি ৩২ এ আমরা তিনটি নোড দিয়ে তিনটি আলাদা ট্রি এঁকেছিলাম। উপরের সূত্রে n এর মান ৩ বসিয়ে দেখো, দেখবা সূত্র ঠিকই আছে। সূত্রের প্রমাণের দিকে আপাতত না যাই।
জঙ্গল তৈরি হয় অনেকগুলো গাছ নিয়ে, আবার একটি গাছের অনেকগুলো ডালপালার একদম শেষে থাকে পাতা। আচ্ছা তোমরাকে একটা প্রশ্ন করি। পাতাকে যদি একটি নোড ধরি, তাহলে এই নোডের এজ কয়টা থাকে? চোখ বন্ধ করে একটু কল্পনা করার চেষ্টা করো তো। পাতার পর কিন্তু আর কিছু নাই। পাতার এজ কিন্তু একটা। নিচের ছবিটি খেয়াল করলেই বোঝা যাবে।
গাণিতিকভাবে লিখলে, যদি কোন ট্রিকে T দ্বারা এবং এই ট্রি এর কোন নোডকে v দ্বারা প্রকাশ করা হয় অর্থাৎ v ∈ V(T), তাহলে deg(v)=1 হলে v কে আমরা লিফ (leaf) বা পাতা বলবো।
ছবি ৩২ এ খেয়াল করি আবার, ওই ট্রিতে তিনটি নোড ছিল এবং তাতে লিফ আছে ২টি। যদি ২টি নোডবিশিষ্ট ট্রি আঁকতে চাই,
এই গ্রাফেও খেয়াল করো, ২টি লিফ আছে। তারমানে দাঁড়ায় যে, পৃথিবীর যেকোন ট্রিতে (যদি তাতে কমপক্ষে ২টি নোড থাকে আরকি) কমপক্ষে ২টি লিফ থাকবে। গাণিতিকভাবে, যদি |V(T)|≥ 2 হয় তাহলে ওই ট্রিতে কমপক্ষে ২টি লিফ থাকবে। ছবি ৩০ ও ৩১ এ বেশ কয়েকটি ট্রি এর উদাহরণ আছে, ওগুলোর ক্ষেত্রে খেয়াল করলেও দেখবে যে প্রতিটি ট্রিতেই কমপক্ষে ২টি লিফ থাকে।
ট্রি এর একটি বিশেষ বৈশিষ্ট্য হচ্ছে, এতে যতগুলো নোড থাকবে তার চেয়ে একটি এজ কম থাকবে।
অর্থাৎ |E(T)| = |V(T)|–1.
সব গাণিতিক সূত্রেরই প্রমাণ আছে, তবে আমরা আমাদের আলোচনা যতটুকু সহজ রাখা যায় সেই চেষ্টা করবো। তাই আমরা প্রমাণের দিকে যাবোনা, প্রতিযোগিতামূলক প্রোগ্রামিং এ ভালো করা বা সফটওয়্যার ইঞ্জিনিয়ার হিসেবে চাকরি পাওয়ার চেষ্টা থাকবে আমাদের।
এবার আমরা জঙ্গল বা Forest নিয়ে কথা বলবো। নিচের ছবিটি খেয়াল করি,
উপরের ছবিতে একটাই গ্রাফ আছে, তিনটা না। এটি একটি disconnected graph যার component সংখ্যা তিন এবং প্রতিটি component এক একটি ট্রি। এ ধরনের গ্রাফকে forest বলে। এই component গুলোকে জোড়া লাগানোর জন্য কটা এজ দরকার? দুইটা। প্রথমটার সাথে দ্বিতীয়টা জোড়া লাগানোর জন্য একটা আর দ্বিতীয়টার সাথে তৃতীয়টা জোড়া লাগানোর জন্য আর একটা।
আমরা জানি যেকোন ট্রি এর ক্ষেত্রে,
|E(T)| = |V(T)|–1
উপরের গ্রাফে আরও দুটি এজ কম আছে। তাহলে এই গ্রাফের ক্ষেত্রে,
|E(T)| = |V(T)|–1–2
বা, |E(T)| = |V(T)|–3
বা, |E(T)| = |V(T)|–k
এখানে k দ্বারা component সংখ্যা বুঝানো হয়েছে। তাহলে কোন forest এর,
নোড সংখ্যা |V(T)| = n
এজ সংখ্যা |E(T)|= m ও
component সংখ্যা k হলে,
আমরা লিখতে পারি, m = n–k.
অয়লারকে নিয়ে একটি মজার তথ্য দিই। আমরা যে কোন ফাংশন লিখার সময় f(x) প্রতীকটি ব্যবহার করি, এটা অয়লার বাবাজি সর্বপ্রথম ব্যবহার করেছিলেন।
