গ্রাফ থিওরি (পর্ব ৩)
প্রোগ্রামিং — ১
প্রথম থিওরেমের ছোঁয়া!!
প্রথমেই মজার একটা সম্পর্ক দেখে নিই। নিচের ছবিটি খেয়াল করি,
উপরের গ্রাফের প্রতিটি নোডে তার ডিগ্রি সংখ্যা লিখা আছে। নোডসংখ্যাগুলি যোগ করলে ৩+২+৪+২+১=১২ পাওয়া যায়। এই গ্রাফে কয়টা এজ আছে? ৬টা। কোন সম্পর্ক বুঝতে পারছো? যেকোন গ্রাফের মোট ডিগ্রি = ২ × ওই গ্রাফের এজসংখ্যা।
এখন প্রশ্ন হচ্ছে যে, এই সম্পর্কটা কি সব গ্রাফের জন্যই সত্য? জ্বী হ্যা, তবে যদি সেটি একটি undirected graph হয়। এখন প্রশ্ন হচ্ছে এই undirected graph মানে কি? নিচের ছবিটি খেয়াল করলেই অনেকটা বোঝা যাবে আশা করি,
ছবি ২২ (এই ছবির গ্রাফদুটোতে নোডগুলোর নাম দেয়া হয়েছে ১, ২, ৩ ইত্যাদি; এগুলো তাদের ডিগ্রি বোঝাচ্ছেনা) এ F গ্রাফটি একটি undirected graph এবং G গ্রাফটি হচ্ছে একটি directed graph। undirected graph এ তুমি ১ নং নোড থেকে ২ নং নোডে যেমন যেতে পারবা ঠিক তেমনি ২ নং নোড থেকে ১ নং নোডেও যেতে পারবা কিন্তু directed graph এ যে বরাবর দিক দেয়া থাকবে শুধু সেদিকেই যেতে পারবা। যেমন উপরের G গ্রাফে তুমি ১ নং নোড থেকে ২ নং নোডে যেতে পারবা কিন্তু ২ নং নোড থেকে ১ নং নোডে যেতে পারবানা।
সূত্রঃ যেকোন গ্রাফের (G) ক্ষেত্রে, Σdeg(v) = 2 |E(G)| অর্থাৎ যেকোন গ্রাফের মোট ডিগ্রি = ২×ওই গ্রাফের এজসংখ্যা
প্রমাণঃ মনে করি, গ্রাফের যেকোন একটি এজ হচ্ছে e এবং এর দুটি প্রান্ত u ও v।
আমরা যখন u নোডের এজ গুনছি তখন একবার e কে ধরে নিচ্ছি, আবার v নোডের এজ গোনার সময়ও e কে ধরছি। তারমানে এক এজ দুইবার করে গোনা হচ্ছে। একারণেই মোট এজের সংখ্যা, মোট ডিগ্রির দ্বিগুণ।
এই সূত্র থেকে আমরা একটি সিদ্ধান্ত নিতে পারি, যাকে অনুসিদ্ধান্ত বলে আরকি।
অনুসিদ্ধান্তঃ যেকোন গ্রাফে জোড়সংখ্যক বিজোড় ডিগ্রির নোড থাকে।
প্রমাণঃ আগের সূত্র থেকে আমরা দেখেছি,
Σdeg(v) = 2 |E(G)|
অর্থাৎ deg(v₁) + deg(v₂) + deg(v₃) + ….. + deg(vₙ) = 2 |E(G)|
এই সমীকরণের ডানপক্ষ জোড়, তাহলে অবশ্যই বামপক্ষকেও জোড় হতে হবে (নাহলে সমান হবে কিভাবে?)। তোমাকেই একটা প্রশ্ন করি। কয়েকটি বিজোড় সংখ্যার যোগফল কি কখনো জোড় হয়? যেমন, ১+৭+৯ = ১৭, এখানে তিনটি বিজোড় সংখ্যা নিয়েছি। তিন নিজেই একটি বিজোড় সংখ্যা, আর এদের যোগফলও হয়েছে বিজোড়। এভাবে অসংখ্য উদাহরণ তুমি নিজে নিজে তৈরি করতে পারো, কিন্তু কখনোই বিজোড় সংখ্যক বিজোড় সংখ্যার যোগফল তুমি জোড় পাবানা। তাই উপরের সমীকরণের বামপক্ষকে জোড় হতে হলে, যদি বিজোড় ডিগ্রি থাকে তাহলে বিজোড় ডিগ্রির সংখ্যা জোড় হতে হবে। যেমন, ৩, ৩, ৪; এখানে তিনটি নোডের ডিগ্রি সংখ্যা দেখানো হল। এদের মধ্যে ৩ দুইবার আছে অর্থাৎ বিজোড় ডিগ্রি আছে জোড়সংখ্যকবার এবং এদের যোগফলও ৩+৩+৪=১০ হচ্ছে জোড়।
কেউ যদি তোমাকে বলে যে উমুক গ্রাফে ১০ ডিগ্রির দুটি নোড ও ৩ ডিগ্রির একটি নোড আছে। তুমি বলবা যে, এটা সম্ভব না। কারণ ৩ ডিগ্রির অর্থাৎ বিজোড় ডিগ্রির নোড আছে ১ টি অর্থাৎ বিজোড় সংখ্যক, এটা সম্ভব না।
এখন ধরো যে আমরা কম্পিউটার বাবাজিকে দিয়ে কিছু কাজ করিয়ে নিতে চাই। যেমন উমুক গ্রাফের উমুক বৈশিষ্ট্য আছে কিনা বের করে দে বা আরও অনেককিছু হতে পারে। সেক্ষেত্রে আমাদের গ্রাফের সাথে কম্পিউটার বাবাজির পরিচয় করিয়ে না দিলে বাবাজি কিভাবে আমাদের কাজ করে দেবে? তাহলে আমরা এখন আলোচনা করবো, কিভাবে একটি গ্রাফকে আমরা কম্পিউটারের মধ্যে ঢেলে দিয়ে কাজ আদায় করে নিতে পারি।
কম্পিউটারকে আমাদের কথা বুঝানোর জন্য আমরাকে কম্পিউটারের ভাষায় কথা বলতে হবে, যে ভাষার নাম হচ্ছে প্রোগ্রামিং ভাষা। আমাদের মানুষের ভাষাকে বলা হয় হিউম্যান ল্যাঙ্গুয়েজ। অনেক ধরনের হিউম্যান ল্যাঙ্গুয়েজ আছে, যেমন বাংলা, ইংরেজি, উর্দু, ফারসি, হিন্দি ইত্যাদি। তেমনি অনেক ধরনের প্রোগ্রামিং ল্যাঙ্গুয়েজ আছে, যেমন সি, সি++, জাভা, প্যাসকেল, পাইথন ইত্যাদি।
যেকোন একটা ভাষাতে বাবাজির সাথে কথা বললেই হবে। আমাদের এই সিরিজে আমরা সি++ ভাষাটি ব্যবহার করবো। আচ্ছা তো যে কথায় ছিলাম। গ্রাফকে কম্পিউটারে স্টোর (store) করা বা ঢেলে দেয়ার দুটি জনপ্রিয় পদ্ধতি আছে। যথাঃ adjacency list ও adjancency matrices।
আমরা এখন এই পদ্ধতি দুটো নিয়ে বিশদ আলোচনা করবো। কেউ যদি প্রশ্ন করে যে, কোন্ পদ্ধতিটি বেশি ভালো? তাহলে এর উত্তরে আমি বলবো যে, তুমি শাক-সবজি, মাছ-মাংস ইত্যাদি বাজার করতে গেলে কি ধরনের ব্যাগ বা বস্তা নিয়ে যাবা? সেটা নির্ভর করবে তুমি কি ধরনের বাজার করতে চাও। ঠিক সেরকমই তুমি কোন্ ধরনের কাজের জন্য এই পদ্ধতিগুলো ব্যবহার করতে চাও সেটার ওপর নির্ভর করবে কোন্ পদ্ধতিটি বেশি কাজের।
সাধারণভাবে বলা যায় যে, যদি কোন গ্রাফে এজসংখ্যা বেশ কম হয় তাহলে লিস্ট পদ্ধতি বেশি কাজের এবং যদি গ্রাফটি খুব ঘন হয় অর্থাৎ এজসংখ্যা অনেক বেশি হয় তাহলে ম্যাট্রিক্স পদ্ধতি ভালো। গাণিতিকভাবে বললে,
যখন |E| এর মান |V|² এর থেকে অনেক কম হয় তখন লিস্ট পদ্ধতি এবং যখন |E| এর মান |V|² এর কাছাকাছি মানের হয় তখন ম্যাট্রিক্স পদ্ধতি ভালো কাজে দেয়।
আমি আশা করছি |E| ও |V| কি অর্থ প্রকাশ করে তোমাদের মনে আছে।
ছবি ২৪ এ আমরা F গ্রাফের adjacency list ও adjacency matrices প্রকাশ বা representation দেখতে পাচ্ছি। adjacency list এর ক্ষেত্রে আমরা গ্রাফের প্রতিটি নোডকে পেস্ট কালারের বক্সে রেখে, এর সাথে যে যে নোডের সম্পর্ক বা এজ আছে তারাকে পরপর লিখেছি। যেমন ১ নং নোডের সাথে ২ ও ৫ নং নোডের এজ আছে। অনুরূপভাবে পরের নোডগুলোর ক্ষেত্রেও লিখা হয়েছে। আর adjacency matrices এর ক্ষেত্রে আমরা |V|×|V| আকারের একটি ম্যাট্রিক্স নিয়েছি । এক্ষেত্রে |V| = 5। এরপর আমরা নিচের সূত্র অনুযায়ী ম্যাট্রিক্সটি পূরণ করে ফেলেছি।
উপরের কথাটুকুর অর্থ হচ্ছে যে, Aᵢⱼ এর মান ১ হবে যদি i ও j নোডের মধ্যে এজ থাকে এবং যদি না থাকে তাহলে শূন্য হবে। এখানে i সারি ও j কলাম নির্দেশ করছে। উপরের ম্যাট্রিক্সটায় খেয়াল করে দেখো যে, ১ নং নোডের সাথে ১ নং নোডের কোন এজ নাই তাই A₁₁ = 0 কিন্তু ১ নং নোডের সাথে ২ নং নোডের এজ আছে তাই A₁₂ = 1 হয়েছে এবং এভাবে ম্যাট্রিক্সের বাকি জায়গাগুলো পূরণ করা হয়েছে।
এখন আমরা দেখবো যে, কিভাবে প্রোগ্রামিং ভাষার মাধ্যমে এই adjacency list ও adjacency matrices কম্পিউটারকে বুঝানো যায়। আমরা প্রথমে adjacency list নিয়ে কথা বলবো। adjacency list এর মাধ্যমে কম্পিউটারে গ্রাফ স্টোর করতে গেলে আমরাকে ভেক্টর সম্পর্কে কিছুটা জানতে হবে। এই ভেক্টর অবশ্য পদার্থবিজ্ঞানের ভেক্টর নয়। এটি হচ্ছে সি++ ভাষার একটি standard template library। আবার প্রশ্ন তৈরি হলো, এই standard template library (STL) টা আবার কি? এটা নিয়ে পরে কথা বলবো।
তাহলে শুরু করি ভেক্টর নিয়ে আলোচনা।
ভেক্টর হচ্ছে একটি ডায়নামিক এ্যারে। এতে আমরা প্রয়োজনমতো তথ্য রাখতে পারি এবং এর আকার আমরা পরিবর্তন করতে পারি।
আমি আশা করছি যে, সি++ ভাষা তোমাদের মোটামোটি জানা আছে। যেকোন সি++ প্রোগ্রামে যে অংশটি অবশ্যই থাকে তাকে আমরা কোড স্কেলেটন (skeleton মানে কঙ্কাল) বলতে পারি। মোটা বা পাতলা হোক, প্রত্যেক মানুষের মধ্যে যেমন কঙ্কাল থাকবে ঠিক তেমনি প্রোগ্রাম বড় হোক বা ছোট হোক এই কোড স্কেলেটন (কোড ০০১) থাকবেই।
আমরা সি++ ভাষা ব্যবহার করে প্রোগ্রাম লিখলে কোড ০০১ এর কাঠামো থাকবে। ৫ ও ৬ নং লাইনে প্রয়োজনীয় কোড লিখে আমরা আমাদের প্রয়োজনমাফিক কাজ করে ফেলতে পারি। সেক্ষেত্রে অবশ্য আমাদের কোড শুধু ৫ ও ৬ নং লাইনে সীমাবদ্ধ থাকবেনা এবং আমাদের ৭ নং লাইন পিছিয়ে অনেক দূরে চলে যাবে। নিচের কোডটি খেয়াল করলেই বোঝা যাবে,
৫ নং লাইন — ইন্টিজার টাইপের ভেক্টর ডিক্লেয়ার করা হয়েছে, নাম দেয়া হয়েছে ‘বাবাজি’।
৬-৯ নং লাইন — ভেক্টরে এক একটি তথ্য ঢুকিয়ে দেয়ার পদ্ধতি দেখানো হয়েছে।
১০ নং লাইন — ভেক্টরের আকার দেখানোর বুদ্ধি। এখানে ভেক্টরের আকার হচ্ছে ৪, কারণ ইতিমধ্যেই আমরা ভেক্টরে ৪টি তথ্য ঢুকিয়ে দিয়েছি।
১১-১৩ নং লাইন — ‘বাবাজি’ ভেক্টরের তথ্যগুলো আমরা ‘ফর লুপ’ ব্যবহার করে প্রিন্ট করেছি। এই লুপটি অবশ্যই ভেক্টরের আকারের সমান বার চলবে।
১৫ নং লাইন — এখানেও ইন্টিজার টাইপের অয়লার নামের ভেক্টর ডিক্লেয়ার করা হয়েছে, তবে এটা ভেক্টরের এ্যারে। তারমানে এখানে আমরা পাঁচটি ভেক্টর ব্যবহার করতে পারবো।
১৬ ও ১৭ নং লাইন — পাঁচটি ভেক্টরের এ্যারের প্রথমটিতে তথ্য ঢুকানো হচ্ছে। এক্ষেত্রে ইনডেক্স শূন্য থেকে শুরু করা হয়েছে।
১৮ নং লাইন — চার নম্বর ভেক্টরে তথ্য ঢুকানো হচ্ছে।
১৯ নং লাইন — অয়লার ভেক্টর এ্যারের প্রথম ভেক্টরে দুটি তথ্য ঢুকানো হয়েছে ১৬ ও ১৭ নং লাইনে, তাই এখানে ভেক্টরের আকার ২ দেখাবে।
২০ নং লাইন — ভেক্টর এ্যারের মধ্যে থেকে কোন একটি নির্দিষ্ট তথ্য কিভাবে প্রিন্ট করতে হয় সেটা দেখানো হয়েছে। এখানে ভেক্টর এ্যারের প্রথমটির দ্বিতীয় উপাদান (১ ইনডেক্সের উপাদান) প্রিন্ট করা হয়েছে।
২১-২৩ নং লাইন — ভেক্টর এ্যারের প্রথমটির সব উপাদান ‘ফর লুপ’ দিয়ে প্রিন্ট করা হয়েছে।
কোন গ্রাফকে কিভাবে adjacency list এর মাধ্যমে প্রকাশ করা হয় সেটা আমরা ছবি ২৪ এ দেখেছি। এখন সেটার কোড লিখার চেষ্টা করা যেতে পারে।
৫ নং লাইন — ভেক্টরের একটি এ্যারে নিয়েছি ৬ সাইজের, নাম দিয়েছি ওগগেমাগে। আসলে আমার ৫ সাইজের দরকার ছিল কারণ যে গ্রাফের ক্ষেত্রে কোডটি লিখছি তাতে ৫টি নোড আছে, প্রতিটি নোডের সাথে কে কে adjacent সেই তথ্য ঢুকানোর জন্য আমাদের ৫টি ভেক্টর লাগবে। কিন্তু ইনডেক্সিং ‘শূন্য’ থেকে শুরু হওয়ায় আমরা oggemage[0] কে বাদ দিয়ে oggemage[1] থেকে oggemage[5] কে নিয়েছি।
৬ নং লাইন — গ্রাফে কটা নোড ও এজ আছে সেটা ডিক্লেয়ার করেছি।
৭ নং লাইন — ইনপুট নিয়ে নিলাম।
৮ নং লাইন — দুটো ভ্যারিয়েবল নিয়েছি, পরবর্তীতে কাজে আসবে।
৯-১৪ নং লাইন — এখানে আমরা একটি ‘ফর লুপ’ ব্যবহার করেছি। এর মধ্যে কিছু কাজ করা হয়েছে। আমাদের আলোচ্য গ্রাফের এজগুলো হচ্ছে ১২, ১৫, ২৩, ২৪, ৩৪, ৪৫। যেহেতু ৬টি এজের তথ্য সংরক্ষণ করতে হবে তাই লুপটি ৬ বার অর্থাৎ এজের সংখ্যা যত ততবার ঘুরবে। ১ নং থেকে যেমন ২ নং নোডে এজ আছে তেমনি আমরা বলতে পারি ২ নং নোড থেকে ১ নং নোডেও এজ আছে। এভাবে প্রতিটি এজের ক্ষেত্রেই একই কথা বলা যায়। তাই ১২ ও ১৩ নং লাইনে একই কাজ ঘুরিয়ে দুবার করা হয়েছে। এ্যারে ভেক্টরের প্রথমটিতে তথ্য হিসেবে ‘২’ কে সংরক্ষণ করে আবার ভেক্টরের দ্বিতীয়টিতে ‘১’ কে সংরক্ষণ করা হয়েছে। ৮ নং লাইনে যে ভ্যারিয়েবল দুটি নেয়া হয়েছিল তাদের সাহায্যে আমরা এখানে কার কার মধ্যে এজ আছে সেটা ইনপুট হিসেবে নিয়েছি।
১৫ ও ১৬ নং লাইন — এখানে তুমি ইচ্ছা করলে যেকোন এজের লিস্ট প্রিন্ট করে ফেলতে পারো।
এবার আমরা ওই একই গ্রাফের adjacency matrices এর মাধ্যমে প্রকাশের কোড লিখে ফেলি।
৩ নং লাইন — এই ধরনের ডিক্লেরেশনকে (মানে মেইন ফাংশনের বাইরের কথা বলছি আরকি) গ্লোবাল ডিক্লেরেশন বলে। এতে করে যেটা হয় সেটা হচ্ছে এ্যারের প্রতিটি মান ‘শূন্য’ দ্বারা আগে থেকেই পূরণ হয়ে যায়।
৬ ও ৭ নং লাইন — কটা নোড ও এজ আছে সেটার বন্দোবস্ত করা হলো।
৮-১১ নং লাইন — কোড ০০৩ এর মতোই।
১২ ও ১৩ নং লাইন — যাদের মধ্যে এজ আছে সেখানে ‘১’ বসিয়ে দিলাম।
১৫-২০ নং লাইন — এবার পালা ম্যাট্রিক্সটি প্রিন্ট করার।
Incidence Matrix নামে একটি বিষয় আছে, সেটা নিয়ে একটু আলোচনা করা যাক। সেজন্য আমরা উদাহরণ হিসেবে একটি গ্রাফ নিতে পারি। নিচের ছবিটি খেয়াল করি,
উপরের ছবি ২৫ এর গ্রাফের adjacency matrix দেখতে পাওয়া যাচ্ছে। প্রতিটি সারির যোগফল ওই নোডের ডিগ্রি প্রকাশ করছে। এখানে যোগফলগুলো দেখানো আছে, যেমন নোড ‘১’ এর ডিগ্রি ২, নোড ‘২’ এর ডিগ্রি ৩ ইত্যাদি। একইভাবে তুমি কলামগুলোর যোগফল বের করলেও একই ফলাফল আসবে। তাহলে আমরা বলতে পারি যে, কলাম বা সারির যোগফল ওই নোডের ডিগ্রি প্রকাশ করে।
এবার আসি Incidence Matrix এর কথায়। এর ক্ষেত্রে সারিগুলো প্রকাশ করে নোডগুলোকে এবং এজগুলোকে প্রকাশ করে কলামেরা। গ্রাফের দিকে খেয়াল করলে দেখা যাবে যে, গ্রাফের এজগুলোর নাম দেয়া আছে আলাদা করে। এইক্ষেত্রে adjacency matrix এর মতোই সারিগুলোর যোগফল ওই নোডের ডিগ্রি প্রকাশ করে। আর কলামগুলোর যোগফল হয় সর্বদা ২, কেননা প্রতিটি এজের দুটি করে প্রান্ত থাকে।
বাবাজিকে নিয়ে আরেকটা তথ্য দেয়া যাক। মহামান্য অয়লার সাহেব উনার সারাজীবনে গণিত বিষয়ে এত এত এত বেশি লিখালিখি করেছেন যে, হিসাব করলে বোঝা যায় উনি প্রতিবছর গড়ে ৮০০ পৃষ্ঠা করে লিখেছেন।
