গ্রাফ থিওরি (পর্ব ২)
প্রোগ্রামিং — ১
গ্রাফের বংশ, করে দিন ধ্বংস
“গ্রাফের বংশ, করে দিন ধ্বংস” মানে হচ্ছে যে গ্রাফের পরিচয় এবং তার বংশ সম্পর্কে জেনে শেষ করে ফেলতে হবে আমরাকে। গ্রাফ বলতে আমার চোখের সামনে প্রথমেই ভেসে ওঠে, ছোট ক্লাসে আমরা গ্রাফ পেপারে কিছু বিন্দু বসিয়ে তাদেরকে যোগ করে বিভিন্ন আকার আকৃতি তৈরি করতাম সেগুলো। কিন্তু আমরা যে গ্রাফ থিওরি নিয়ে পড়তে বসেছি সেটা অন্যকিছু।
“গ্রাফ কাকে বলে” এই প্রশ্নের উত্তরে আমরা কিছু ইংরেজি কথা বলবো। ঘাবড়ানোর কিছু নেই, আমি সেগুলো ব্যাখ্যা করবো।
“A Graph (G) is an ordered pair, G = (V, E) where V is (finite) set of elements and E is a set of 2-subsets of V.”
উপরের কথাগুলোর সহজ বাংলা করতে গেলে দাঁড়ায়, একটি গ্রাফ যাকে আমরা G নাম দিয়েছি সেটা হচ্ছে কিছু ভার্টেক্স বা নোড (V) ও এজের (E) সমষ্টি (সমষ্টি না বলে সমাবেশ বা combination বলা বোধহয় বেশি ভালো হয়!)। কিছু উদাহরণ নিচে দেয়া হলো,
ছবি ৫ এর ১ নং গ্রাফের ক্ষেত্রে আমরা লিখতে পারি, V = {1, 2, 3}
এর অর্থ, V হচ্ছে নোডগুলোর সেট। সেট কিভাবে লিখতে হয় আশা করছি সেটা সবাই জানে। উপাদানগুলোকে কমা দিয়ে আলাদা আলাদা করে দ্বিতীয় বন্ধনীর মধ্যে লিখে ফেলতে হয়।
আবার আমরা লিখতে পারি যে, E = {{1, 2}, {2, 3}, {3, 1}}
এর অর্থ, E হচ্ছে এজগুলোর সেট। উপরে গ্রাফের সংজ্ঞায় “2-subsets” কথাটার অর্থ হচ্ছে যে, সেটের মধ্যে আমরা আবার দ্বিতীয় বন্ধনীর মধ্যে দুটো করে সংখ্যা আলাদা আলাদা করে লিখেছি। কারণ এখানে বুঝানো হচ্ছে যে, ১ ও ২ নং নোডের মধ্যে একটা এজ আছে, আবার ২ ও ৩ নং নোডের মধ্যে একটা এজ আছে ইত্যাদি।
এখানে একটা কথা বলে রাখি, আমরা আমাদের আলোচনা আপাতত simple graph এর মধ্যেই সীমাবদ্ধ রাখবো। simple graph হচ্ছে সেই সকল গ্রাফ যেই গ্রাফে লুপ (loop) ও মাল্টিপল এজ (multiple edges) নাই। নিচের উদাহরণটা দেখলেই বিষয় দুইটি পরিষ্কার হয়ে যাবে আশা করছি।
ছবি ৬ এ আমরা একটি গ্রাফ দেখিয়েছি যার নাম দিয়েছি L, এই গ্রাফে খেয়াল করলে দেখা যাবে যে ২ ও ৩ নং নোডের মধ্যে একাধিক এজ আছে। এই বিষয়টিকে বলে একাধিক এজ বা multiple edges। আবার ১ নং নোডের দিকে খেয়াল করলে দেখা যাবে যে, এই নোড থেকে ৩, ৪ ও ৫ নং নোডের দিকে এজ বের হয়ে গেছে। আরেকটু খেয়াল করলে দেখা যাবে যে, আরেকটা এজ ১ নং থেকে বের হয়ে আবার নিজের মধ্যেই প্রবেশ করছে। এই বিষয়টিকে বলা হয় লুপ।
কোন গ্রাফে যতগুলো নোড থাকে তাকে ঐ গ্রাফের অর্ডার (order) বলে। বিষয়টিকে নিচের প্রতীক দিয়ে প্রকাশ করা হয়,
|V| = গ্রাফের অর্ডার
আবার কোন গ্রাফে যতগুলো এজ থাকে তাকে ঐ গ্রাফের আকার (size of the graph) বলে। এটাকে প্রকাশ করা হয়,
|E| = গ্রাফের আকার
উদাহরণস্বরূপ আমরা ছবি ৫ এর ২ নং গ্রাফের ক্ষেত্রে বলতে পারি, F গ্রাফের অর্ডার হচ্ছে ৪ এবং গ্রাফের আকারও হচ্ছে ৪। এইক্ষেত্রে অর্ডার ও আকার সমান হয়েছে মানে যে সবক্ষেত্রেই হবে তা নয়।
এবার আমরা কিছু notation বা প্রতীকের সাথে পরিচিত হবো, সেজন্য নিচের উদাহরণটা দেখা যেতে পারে।
উপরের গ্রাফের নাম দেয়া হয়েছে G। আমরা এই গ্রাফকে G = (V(G), E(G)) দিয়েও প্রকাশ করতে পারি। এখানে V(G) দ্বারা নোডের সেট ও E(G) দ্বারা এজের সেট বুঝানো হয় আর V ও E এর পাশে G লিখে বুঝানো হয়েছে যে এই নোডগুলো ও এজগুলো হচ্ছে উমুক গ্রাফের এবং এদের সমষ্টিই হচ্ছে গ্রাফ। তাহলে আমরা লিখতে পারি,
V = {V₁, V₂, V₃, V₄, V₅} ও
E = {V₁V₂, V₂V₃, V₃V₄, V₄V₁, V₁V₅}
অর্থাৎ নোডের সেটে কি কি নোড আছে সেগুলো এবং এজের সেটে কোন্ নোডের সাথে কোন্ নোডের সম্পর্ক আছে সেটা আমরা লিখবো। এখানে যেমন একটা এজ আছে V₁V₂, এখানে V₁ হচ্ছে একটা প্রান্ত ও V₂ হচ্ছে আরেকটা প্রান্ত। এদেরকে আমরা adjacent বা প্রতিবেশী (neighbours) নোড বলতে পারি। তাহলে দুটো নোড এজ দ্বারা যুক্ত থাকলে তারা হচ্ছে adjacent nodes।
মনে করি V₁V₂ এজের নাম দিলাম E₁ এবং V₁V₅ এজের নাম দিলাম E₂। এই দুটি এজের মধ্যে V₁ নোডটি দুটি এজেই আছে। তাই E₁ ও E₂ কে আমরা প্রতিবেশী বা adjacent এজ বলতে পারি অর্থাৎ V₁ নোডটি E₁ ও E₂ এজকে প্রতিবেশি বানিয়েছে। আরও একটি উদাহরণ দেখা যেতে পারে,
উপরের গ্রাফটি হচ্ছে একটি বিচ্ছিন্ন গ্রাফ বা disconnected graph। কারণ এই গ্রাফে c নোডটির সাথে অন্য কারও সম্পর্ক নাই বা এটা সবার থেকে বিচ্ছিন্ন। এই গ্রাফের ক্ষেত্রে লিখা যায়, V = {a, b, c} এবং E = {ab}.
এখন আমরা বিভিন্ন প্রকার গ্রাফ দেখবো, ওই শ্রেণীবিভাগ আরকি!
সম্পূর্ণ বা complete graph: যখন কোন গ্রাফের প্রতিটি নোড প্রতিটির সাথে এজ দ্বারা যুক্ত থাকে তখন তাকে আমরা complete graph বলি। এই গ্রাফকে সাধারণত Kₙ দ্বারা প্রকাশ করা হয়ে থাকে। এখানে n দ্বারা নোডের সংখ্যা বুঝানো হয়েছে। নিচে কয়েকটি complete graph দেখানো হল। কোন complete graph এ কতগুলো এজ আছে সেটা বের করার একটি সূত্র আছে। এজের সংখ্যা = ⁿC₂
সম্পূর্ণ গ্রাফ বা complete graph এর ক্ষেত্রেই এজসংখ্যা সর্বাধিক (simple graph এর আলোচনায়) হয় আর সেটা আমরা দেখলাম, |E| = ⁿC₂
তাহলে অন্য যে কোন গ্রাফের ক্ষেত্রে লিখা যায়,|E|< ⁿC₂
সবমিলিয়ে বলা যায়, যে কোন গ্রাফের ক্ষেত্রে, |E| ≤ ⁿC₂.
শূন্য বা empty graph: শূন্য গ্রাফ হচ্ছে সেই গ্রাফ যেই গ্রাফে যেকোন সংখ্যক নোড থাকতে পারে কিন্তু তাদের মধ্যে কোন এজ থাকবেনা, একটাও না। নিচে চারটি নোডের একটি শূন্য গ্রাফ দেখানো হল।
বাইপারটাইট গ্রাফ (Bipartite graph): এই শব্দটির বাংলা করার বোধহয় খুব একটা প্রয়োজন নাই, ইংরেজি দিয়েই মনে রাখাটা ভালো হবে। এই ধরনের গ্রাফের সংজ্ঞা দেয়ার চেয়ে উদাহরণ দিয়ে বোঝাটা বেশি কাজে দিবে মনে হয়। তাই প্রথমে আমরা কিছু উদাহরণ দেখে নিই, তারপর নাহয় সংজ্ঞাটা দেখলাম। আর একটা কথা, গ্রাফ থিওরিতে বাইপারটাইট গ্রাফের বেশ গুরুত্ব আছে তাই এটা আমরা বেশ মনোযোগ দিয়ে পড়বো।
বেশ রঙচঙে একটা গ্রাফ দেখা যাচ্ছে। খেয়াল করে দেখো, নীল রঙের নোডগুলোর নিজেদের মধ্যে কোন সম্পর্ক বা এজ নেই আবার টিয়া রঙের নোডগুলোর নিজেদের মধ্যেও কোন এজ নেই। কিন্তু নীল রঙের নোডগুলোর সাথে টিয়া রঙের নোডগুলোর এজ রয়েছে। এভাবে আমরা যদি কোন গ্রাফের সবগুলো নোডকে দুইভাগে ভাগ করে ফেলতে পারি, তাহলে সেই গ্রাফকে বাইপারটাইট গ্রাফ বলা হবে। এবার কিছু প্রতীক ব্যবহার করে এই গ্রাফকে বর্ণনা করার চেষ্টা করা যেতে পারে।
ধরি নীল রঙের নোডগুলোকে নিয়ে একটা সেট বানালাম, নাম দিলাম V₁। আর টিয়া রঙের নোডগুলোর সেটের নাম দেয়া হল V₂। তাহলে, V₁ = {a, b, c} এবং V₂ = {d, e}.
তাহলে আমরা একটি গ্রাফকে বাইপারটাইট বলবো যদি uv ∈ E এবং u ∈ V₁ ও v ∈ V₂ হয়। ∈ (epsilon) দিয়ে উপাদান বুঝানো হয়। তাহলে uv ∈ E দিয়ে আমরা বুঝবো uv হচ্ছে E সেটের একটি উপাদান। E হচ্ছে এজসমূহের সেট। তাহলে uv হচ্ছে গ্রাফের একটি এজ। এই এজের এক প্রান্ত (u) যদি প্রথম সেটের (V₁) হয় এবং অপর প্রান্ত (v) দ্বিতীয় সেটের (V₂) হয়, শুধুমাত্র সেইক্ষেত্রেই আমরা সেই গ্রাফকে বাইপারটাইট বলবো।
সম্পূর্ণ বাইপারটাইট গ্রাফ বা complete bipartite graph: যদি কোন বাইপারটাইট গ্রাফের প্রথম সেটের প্রতিটি নোড দ্বিতীয় সেটের প্রতিটি নোডের সাথে সম্পর্কযুক্ত থাকে তবে সেই গ্রাফকে আমরা complete bipartite graph বলবো। নিচে উদাহরণ ও এই গ্রাফকে কোন্ প্রতীক দিয়ে প্রকাশ করা হয় সেটা দেখানো হল।
তাহলে ছবি ১২ এর গ্রাফকে K₃, ₂ দ্বারা প্রকাশ করা যায়।
এক ধরনের বিশেষ complete bipartite graph আছে যাদেরকে star বলে। এই গ্রাফে প্রথম সেটে একটিমাত্র নোড থাকে এবং অপর সেটে যেকোন সংখ্যক নোড থাকতে পারে। নিচে এর উদাহরণ দেখানো হল।
এই গ্রাফকে আমরা K₁, ₃ দ্বারা প্রকাশ করতে পারি।
এখন আমরা পথ (path) ও চক্র (cycle) নিয়ে কথা বলবো। সংজ্ঞা দেখার আগে উদাহরণ দেখা বোধহয় ভালো হবে, নিচের উদাহরণটা খেয়াল করি।
ছবি দেখে নিশ্চয়ই বোঝা যাচ্ছে যে, path কে P দ্বারা ও cycle কে C দ্বারা প্রকাশ করা হয়। আর একটি বিষয় বুঝতে কষ্ট হওয়ার কথা নয় যে, যতগুলো নোড থাকবে সেই সংখ্যাটা P বা C এর পায়ের কাছে (subscript) লিখে দিলেই হবে। আমরা যদি path এর শেষ নোডটিকে প্রথম নোডের সাথে একটা এজ দিয়ে যুক্ত করে দিই তাহলে সেটি cycle এ পরিণত হবে। আশা করি বুঝতে কষ্ট হচ্ছেনা।
তাহলে আমরা path বলতে কি বুঝলাম? কিছু নোডকে যদি আমরা পরপর সাজিয়ে এজ দিয়ে যুক্ত করে দিই তাহলেই path তৈরি হয়ে যায়। ছবি ১৪ এর path এর এজগুলোকে যদি লিখি, E = {V₁V₂, V₂V₃, V₃V₄}
খেয়াল করে দেখো “ভি ওয়ান” এর পরে “ভি টু” আছে, আবার “ভি টু” এর পরে “ভি থ্রি” আছে; এভাবেই চলতে থাকবে। যদি অনেকগুলো এজ থাকে সেক্ষেত্রে আমরা প্রতিটি এজের নাম লিখে E সেট লিখতে পারবোনা, খাতা শেষ হয়ে যাবে! তাহলে উপায়? আমরা ছোট ক্লাসে পড়ে এসেছি সেট দুইভাবে লিখা যায়, একটা হচ্ছে তালিকা পদ্ধতি এবং আরেকটা হচ্ছে সেট বিল্ডার পদ্ধতি। যখন সেটের উপাদান সংখ্যা কম থাকে তখন আমরা প্রতিটি উপাদান কমা দিয়ে আলাদা আলাদা করে লিখে ফেলি, এটা হচ্ছে তালিকা পদ্ধতি। এই পদ্ধতিতে এতক্ষণ আমরা সেট লিখে এসেছি।
কিন্তু যদি এজের সংখ্যা কয়েকশ হয়! তখন আমরাকে সেই সেট “বিল্ডার পদ্ধতি” তে লিখতে হবে। path এর এজসমূহের সেট নিচে বিল্ডার পদ্ধতিতে দেখানো হল,
E = {VᵢVᵢ₊₁ | i = 1, 2, 3, ………, n-1}
প্রথমে আমরা সেটের নাম দিয়ে দিলাম (E), এরপর “সমান” দিয়ে দ্বিতীয় বন্ধনী শুরু হয়ে গেলো। এরপর আমরা যে অংশটা (VᵢVᵢ₊₁) লিখেছি সেটা দিয়ে বুঝানো হয়েছে আমাদের এই সেটের উপাদানগুলোর চেহারা কেমন হবে। এটা বুঝতে নিশ্চয়ই সমস্যা হওয়ার কথা না যে, আমরা এজগুলো এভাবেই লিখে থাকি। এবার আসি পায়ের কাছে i ও i+1 এর কথায়। খেয়াল করলেই বুঝা যাবে যে, i এর মান প্রথম প্রান্তে যত হবে শেষ প্রান্তে তার চেয়ে এক বেশি হবে যেমন V₃V₄।
আচ্ছা এবার দেখা যাক i এর মান কেন n-1 পর্যন্ত। ধরি আমরা একটা path নিলাম যাতে ১০টি নোড আছে। অর্থাৎ n এর মান ১০। তাহলে i এর মান হবে ১০ - ১ = ৯ পর্যন্ত। তাহলে আমাদের এই path এর শেষ এজ হবে “ভি₉ভি₉₊₁”। তাই হওয়া উচিত নয় কি?
এখানে আর একটা তথ্য দেয়া যাক, প্রতিটি path ই হচ্ছে বাইপারটাইট। এটা দেখানো খুব সহজ, নিচের ছবিটি খেয়াল করি।
তাহলে cycle এর এজসমূহের সেটটা কেমন হওয়া উচিৎ?
E = {VᵢVᵢ₊₁ | i = 1, 2, 3, ………, n-1} ∪ {V₁Vₙ}; n≥3
এখানে প্রথম অংশটুকু path এর মতোই, কিন্তু ইউনিয়ন (∪) এর পরের অংশটা কেন আসলো? আমরা আগেই বলেছি যে, শুরু ও শেষের নোডটা জুড়ে দিলেই path হয়ে যায় cycle। এখানে তাই করা হয়েছে। তবে একটা শর্ত আছে যে, গ্রাফে নোডের সংখ্যা কমপক্ষে তিনটি হতে হবে নাহলে cycle হওয়া সম্ভব না। তুমি যদি দুটি নোড দিয়ে cycle বানাতে চাও সেখানে multiple edges চলে আসবে, সেটা আর simple graph থাকবেনা। নিচের ছবিটি খেয়াল করি।
তোমাকে যদি K₃ বা C₃ আঁকতে বলি, পারবানা? মনে আছে K₃ বলতে কি বুঝায়? K₃ হচ্ছে একটি complete graph যার নোডসংখ্যা হচ্ছে ৩। আর কিছুক্ষণ আগেই তো C₃ দেখেছো। ব্যাপারটা মজার না? দুটো আসলে একই। এর একটি বিশেষ নাম আছে, triangle। এরকম নাম হওয়ার কারণ খুবই সোজা। triangle মানে যে ত্রিভুজ সেটা তো আর বলে দিতে হচ্ছেনা।
গ্রাফের যে বংশপরিচয় নিয়ে পড়তে বসেছিলাম তার শেষের দিকে চলে এসেছি। এখন আমরা যুক্ত গ্রাফ (connected graph) ও নিয়মিত গ্রাফ (regular graph) সম্পর্কে খানিকটা জেনে নিয়ে এই অংশের আলোচনা শেষ করবো।
এবারও আমরা আগে কয়েকটা উদাহরণ দেখে নিয়ে সংজ্ঞার দিকে মনোযোগ দিবো। নিচের উদাহরণগুলো একটু দেখি,
আশা করছি ছবি ১৭ দেখেই বোঝা যাচ্ছে যে বিষয়টা কি। যদি আমরা কোন গ্রাফের একটি নোড থেকে এজ ধরে ধরে অন্য যে কোন নোডে চলে যেতে পারি তাহলে সেই গ্রাফকে আমরা বলবো connected graph। যেমন উপরের ছবির সবশেষের গ্রাফটির দিকে খেয়াল করলে দেখা যাবে যে, আমরা a নোড থেকে যাত্রা আরম্ভ করে কোনভাবেও b বা e নোডে যেতে পারবোনা, তাহলে এটি নিঃসন্দেহে একটি disconnected graph। এবার প্রতিবেশি বা neighbour/adjacent নোড নিয়ে দুটো কথা বলে নেয়া যাক। নিচের ছবিটি খেয়াল করি,
উপরের ছবি ১৮ থেকে আমরা দেখতে পাচ্ছি যে, a নোডের সাথে b, c, d এর সম্পর্ক আছে। এই সম্পর্ককে open neighbourhood বলে। এটা লিখার একটা নিয়ম আছে, সেটা হচ্ছে,
উপরের নিয়ম মেনে যদি আমরা এখন a নোডের open neighbourhood লিখতে চাই, N(a) = {b, c, d}.
এবার আমরা a নোডের closed neighbourhood লিখতে চাই, N[a] = {b, c, d, a}.
তাহলে open ও closed neighbourhood এর মধ্যে পার্থক্য হচ্ছে যে, closed neighbourhood এ নোডটি নিজেও উপস্থিত থাকবে এবং এটা প্রকাশ করার জন্য আমরা তৃতীয় বন্ধনী ((a) এর স্থলে [a] ব্যবহার করা হয়েছে) ব্যবহার করবো।
তোমাদের নিশ্চয়ই মনে আছে, কোন নোডের ডিগ্রি বলতে কি বোঝায়। কোন নোডের ডিগ্রি বলতে বোঝায় যে, ওই নোড থেকে কতগুলো এজ বের হয়েছে। আমরা যেহেতু এখন পর্যন্ত simple graph নিয়ে পড়াশোনা করছি তাই বলতে পারি যে, কোন দুটি নোডের মধ্যে একাধিক এজ নেই। তাহলে কোন নোডের প্রতিবেশি যতগুলো, ওই নোড থেকে ততগুলোই এজ বের হয়েছে। অতএব কোন নোডের ডিগ্রি বলতে তার প্রতিবেশির সংখ্যাকেই বুঝাচ্ছে। সুতরাং আমরা লিখতে পারি যে,
deg(v) =| N(v)|
এবার সময় এসেছে নিয়মিত বা regular graph নিয়ে জানার। যদি কোন গ্রাফের সবগুলো নোডের ডিগ্রি একই হয় তাহলে তাকে আমরা regular graph বলবো। প্রতিটি নোডের যত ডিগ্রি হবে সেই গ্রাফকে “তত” রেগুলার গ্রাফ বলা হবে। উদাহরণস্বরূপ, যদি কোন গ্রাফের প্রতিটি নোডের ডিগ্রি ২ করে হয়, তাহলে সেই গ্রাফের নাম 2-regular। নিচের ছবিগুলো খেয়াল করো,
এবার কয়েকটি গুরুত্বপূর্ণ কথা বলে এই অংশের আলোচনা শেষ করা যাক। path কখনই regular হতে পারেনা, কারণ একটু মনে করে দেখো path এর প্রথম ও শেষের নোডের ডিগ্রি ১, কিন্তু ভেতরের নোডগুলোর ডিগ্রি ২। আবার cycle সবসময় 2-regular হবে, ব্যাখ্যা নিজে নিজেই করো। আরেকটা মজার সম্পর্ক আছে, সম্পূর্ণ বা complete graph (Kₙ) সবসময় (n-1)-regular হবে। এই ব্যাপারটাও তোমরা নিজে নিজে উদারহণ তৈরি করে দেখতে পারো।
ছবি ৭ থেকে দেখে আসো, deg(V₁)=3 এবং deg(V₅)=1, অর্থাৎ ওই গ্রাফের সর্বোচ্চ ডিগ্রি ৩ ও সর্বনিম্ন ডিগ্রি ১। এই ব্যাপারটা প্রকাশের জন্য প্রতীক রয়েছে,
সর্বনিম্ন ডিগ্রি বা minimum degree: δ(G)
সর্বোচ্চ ডিগ্রি বা maximum degree: ∆(G)
তাহলে n-regular graph এর জন্য, δ(G) = ∆(G) = n.
কেননা regular graph এর সব নোডগুলোর ডিগ্রি একই।
অয়লার বাবাজিকে নিয়ে একটি তথ্য দিই। ২৯ আগস্ট, ১৯৭৩ সালে রাশিয়ান এক ভদ্রমহিলা (Tamara Smirnova) একটি গ্রহাণু আবিষ্কার করেন। এই ভদ্রমহিলা যেনতেন কেউ নন, উনি একজন জ্যোতির্বিজ্ঞানি। ওই গ্রহাণুর নাম রাখা হয় 2002 Euler, বাবাজিকে সম্মান জানানোর জন্য।
