<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Ahsan Shafiq Shawon on Medium]]></title>
        <description><![CDATA[Stories by Ahsan Shafiq Shawon on Medium]]></description>
        <link>https://medium.com/@sshawon?source=rss-550534651e5d------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*FCKip8vBsbJFxVZrU_q3DA.jpeg</url>
            <title>Stories by Ahsan Shafiq Shawon on Medium</title>
            <link>https://medium.com/@sshawon?source=rss-550534651e5d------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Wed, 18 Nov 2026 19:08:56 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@sshawon/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[পদার্থবিজ্ঞানে হাতেখড়ি]]></title>
            <link>https://medium.com/@sshawon/%E0%A6%AA%E0%A6%A6%E0%A6%BE%E0%A6%B0%E0%A7%8D%E0%A6%A5%E0%A6%AC%E0%A6%BF%E0%A6%9C%E0%A7%8D%E0%A6%9E%E0%A6%BE%E0%A6%A8%E0%A7%87-%E0%A6%B9%E0%A6%BE%E0%A6%A4%E0%A7%87%E0%A6%96%E0%A7%9C%E0%A6%BF-9396e4803d0a?source=rss-550534651e5d------2</link>
            <guid isPermaLink="false">https://medium.com/p/9396e4803d0a</guid>
            <category><![CDATA[tutorial]]></category>
            <category><![CDATA[physics]]></category>
            <category><![CDATA[elementary]]></category>
            <dc:creator><![CDATA[Ahsan Shafiq Shawon]]></dc:creator>
            <pubDate>Fri, 15 May 2020 20:29:05 GMT</pubDate>
            <atom:updated>2020-05-16T07:01:12.375Z</atom:updated>
            <content:encoded><![CDATA[<h3>পদার্থবিজ্ঞানে হাতেখড়ি (পর্ব ১)</h3><p>আলোচ্য বিষয়ঃ সরণ ও দূরত্ব</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Q00hu23Sn0UQHm3hCrv-6Q.jpeg" /><figcaption>Photo by <a href="https://unsplash.com/@thutra0803?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Tra Nguyen</a> on <a href="https://unsplash.com/s/photos/physics?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Unsplash</a></figcaption></figure><p><strong>ভূমিকা</strong></p><p>তুমি তোমার আম্মুকে কতটুকু ভালোবাসো?</p><p>— মাপা যায়না।</p><p>টিভি দেখতে কতখানি পছন্দ করো?</p><p>— মাপা যায়না।</p><p>এইরকম আরও অনেক উদাহরণ দেয়া যায়, যেমন — রাগ, হিংসা, আশা-ভরসা ইত্যাদি। এগুলো হচ্ছে আবেগ-অনুভূতি। এগুলো মাপা যায়না। যা কিছু মাপা যায়না পদার্থবিজ্ঞান সেগুলো নিয়ে কথা বলেনা।</p><p>তাহলে পদার্থবিজ্ঞান কি নিয়ে কথা বলে?</p><p>তোমার ভর কত?</p><p>— ৫০ কেজি।</p><p>স্কুল যেতে তোমার কতক্ষণ লাগে?</p><p>— ১০ মিনিট।</p><p>আজকে অনেক গরম। আজকের তাপমাত্রা কত?</p><p>— ৪০ ডিগ্রি সেলসিয়াস।</p><p>এইরকম হাজারো উদাহরণ দেয়া যায়, যেগুলো মাপা যায়।</p><p>তাহলে যা কিছু মাপা যায় পদার্থবিজ্ঞান শুধু তাদেরকে নিয়েই কথা বলে। আর যাদেরকে মাপা যায়, তাদেরকে রাশি বলে।</p><p>তাহলে ভালোবাসা রাশি না। ভর একটা রাশি, তাপমাত্রা একটা রাশি, সময় একটা রাশি। এরকম আরও আছে।</p><p>আমরা যেহেতু পদার্থবিজ্ঞান পড়তে বসেছি, আর পদার্থবিজ্ঞান যেহেতু শুধু রাশি নিয়ে কথা বলে, তাই এখন আমরা একটার পর একটা রাশি নিয়ে কথা বলবো। এভাবে ধীরে ধীরে আমরা পদার্থবিজ্ঞান শিখে ফেলবো।</p><p>এখন আমরা রাশি নিয়ে কথা বলা শুরু করবো, তারমানে পদার্থবিজ্ঞান পড়তে শুরু করবো। এখন আমরা ’সরণ’ ও ‘দূরত্ব’ এই দুটি রাশি নিয়ে কথা বলবো। এরা কিভাবে রাশি, সেই গল্প এখন বলা হবে।</p><p>H তোমাদের বাড়ি। এখানে তোমরা সবাই একসাথে বাস করো। বাবা-মা, ভাই-বোন, দাদা-দাদী। S তোমার স্কুল। বামপাশের চিত্রে (চিত্র ১) খেয়াল করো, ধরি,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/361/1*xbMkErhvMAseJOjZ3dZp7Q.png" /><figcaption>চিত্র ১</figcaption></figure><p>HS = 2 km</p><p>HB = 2 km</p><p>HA = 2 km</p><p>HS হচ্ছে তোমার স্কুলের রাস্তা এবং HB ও HA অন্য দুটি রাস্তা, কিন্তু সবগুলো রাস্তাই একই সমান লম্বা (2 km)।</p><p><strong>সরণ ও দূরত্ব</strong></p><p>মনে কর, H থেকে B তে যেতে তোমার সময় লাগে ২০ মিনিট। তাহলে H থেকে S এবং H থেকে A তে যেতেও ২০ মিনিট লাগবে কারণ প্রতিটা রাস্তা সমান। কিন্তু যেকোন রাস্তাতে গেলেই কি তুমি স্কুলে পৌঁছবা?</p><p>না, পৌঁছবা না। তাহলে তোমাকে যদি প্রশ্ন করি, তোমার স্কুল কতদূরে? তুমি যদি উত্তর দাও যে, আমার স্কুল 2 km দূরে; তাহলে ভুল হয়ে যাবে। কারণ যেকোন রাস্তাতে তুমি 2 km গেলে স্কুল খুঁজে পাবানা। তোমাকে পূর্ব দিকে 2 km যেতে হবে।</p><p>তাহলে তোমার সঠিক উত্তর হবে, আমার স্কুল 2 km পূর্বদিকে।</p><p>এবার আসি তোমার দাদুর গল্পে। মনে কর তোমার দাদুর ডায়াবেটিস রোগ আছে। এই রোগের রোগীদের অনেক হাঁটাহাঁটি করতে হয়। এতে করে তাঁদের রোগ নিয়ন্ত্রণে থাকে। তো তোমার দাদু প্রতিদিন 2 km করে হাঁটেন।</p><p>তোমার কি মনে হয় যে, ডাক্তার সাহেব তোমার দাদুকে বলবেন যে, খবরদার আপনি HB বরাবর 2 km হাঁটবেন না, হাঁটলে আপনার ডায়াবেটিস বেড়ে যাবে, আপনি HS বরাবর 2 km হাঁটবেন।</p><p>মোটেও বলবেন না। যেকোন একদিকে হাঁটলেই হলো। তাই নয় কি?</p><p>এখন প্রশ্ন হচ্ছে যে, তোমার স্কুল কতদূরে?</p><p>— 2 km</p><p>তোমার দাদু কতদূর হাঁটেন?</p><p>— 2 km</p><p>ওয়াও! দুটোই মাপা যায়। তারমানে দুটোই রাশি। কিন্তু এই দুটি রাশির মধ্যে তফাৎ আছে। সেটা কি? আসো দেখি,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/709/1*x2Wbz_XcDaLzvVjeK1vF1w.png" /></figure><p>তারমানে আমরা দেখতে পাচ্ছি যে, রাশি হতে গেলে মান ও একক থাকা লাগবে। দিক কখনও কখনও থাকতে পারে, আবার নাও পারে। তাহলে রাশি দুই প্রকার বলা যায়। যথাঃ (১) দিকওয়ালা রাশি ও (২) দিকছাড়া রাশি।</p><p>তোমার <strong>2 km পূর্বদিক</strong> একটি দিকওয়ালা রাশি। এই রাশির নাম কি? এই রাশির নাম হচ্ছে ‘সরণ’। যেমন প্রতিটা মানুষের নাম থাকে, তেমন প্রতিটা রাশিরও নাম থাকে। তুমি তো তোমার কোন বন্ধুকে ‘এই মানুষ’ বলে ডাকতে পারোনা।</p><p>‘সরণ’ শব্দটা এসেছে, তুমি কোন একটা নির্দিষ্ট দিকে কতটুকু ‘সরেছো’।</p><p>তোমার দাদুর <strong>2 km</strong> একটি দিকছাড়া রাশি। এই রাশির নাম কি? আর যাই হোক এই রাশির নাম ‘সরণ’ হতে পারেনা। কেননা এই নামটা আমরা অন্য একটি রাশিকে ইতিমধ্যেই দিয়ে দিয়েছি। তাই এই রাশির নাম হচ্ছে ‘দূরত্ব’।</p><p>‘দূরত্ব’ শব্দটা এসেছে, তোমার দাদু কত‘দূর’ গেছেন।</p><p>তাহলে আমরা দুটি রাশি পেয়ে গেলাম। এখন আমরা এদের সম্পর্কে আরও বেশি জানার চেষ্টা করবো। প্রথম প্রশ্ন হচ্ছে যে, সরণ ও দূরত্ব কিভাবে হিসাব করতে হয়?</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/329/1*xGquGldwTn9N017Fh2G3Uw.png" /><figcaption>চিত্র ২</figcaption></figure><p>পাশের চিত্রটি (চিত্র ২) খেয়াল করি। এখানে,</p><p>H = তোমার বাড়ি</p><p>S = তোমার স্কুল</p><p>G = তোমার খেলার মাঠ</p><p>এবং HS = 3 km, HG = 4 km, SG = 5 km</p><p>ধর, একদিন তুমি বাড়ি থেকে স্কুল গিয়ে অর্থাৎ 3 km গিয়ে দেখলে যে, স্কুল কোন কারণে ছুটি। এরপর তুমি ভাবলে যে, তাহলে খেলার মাঠে যাই। তো তুমি স্কুল থেকে খেলার মাঠে গেলে অর্থাৎ 5 km গেলে। গিয়ে দেখলে যে, মাঠেও কেউ নেই। কি বিচ্ছিরি একটা ব্যাপার বলোতো। যাই হোক এরপর তুমি মন খারাপ করে মাঠ থেকে বাড়ি চলে আসলে অর্থাৎ 4 km আসলে।</p><p>এখন প্রশ্ন হচ্ছে যে, তোমার সরণ কত এবং দূরত্ব [অতিক্রান্ত, আমরা তো দূরত্ব অতিক্রম করি তাইনা!] কত?</p><p>একটা একটা করে তাহলে হিসাব করা যাক। প্রথমে তোমার ‘সরণ’ কত? তারমানে তুমি কতটুকু ‘সরেছো’? তুমি ছিলে প্রথমে বাড়িতে, এখন তুমি অনেক রাস্তা ঘুরে আবার বাড়িতে। তাহলে ব্যাপার দাঁড়াচ্ছে যে, তুমি আসলে ‘সরোইনি’। অর্থাৎ তোমার কোন ‘সরণ’ হয়নি। তাহলে তোমার সরণ = 0 km।</p><p>কি বুঝলে? সরণ কিভাবে মাপতে হয়? যেখান থেকে যাত্রা আরম্ভ [এই উদাহরণের ক্ষেত্রে সেটা বাড়ি] করেছো এবং যেখানে যাত্রা শেষ [এটাও বাড়ি] করেছো, শুধু এই দুইটা স্থান মাথায় রাখতে হবে।</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/241/1*PFGYZNfDxbHI_v8P_gm5_w.png" /><figcaption>চিত্র ৩</figcaption></figure><p>আরেকটা উদাহরণ দেখা যাক, পাশের চিত্রটি (চিত্র ৩) খেয়াল করো। মনে করো এটা একটা গোল রাস্তা। তুমি A বিন্দু থেকে হাঁটতে শুরু করে B বিন্দু ঘুরে এবং C বিন্দু ঘুরে আবার A বিন্দুতে এসে থামলে। তোমার সরণ কত হবে?</p><p>তোমার সরণ হবে শূন্য। এক্ষেত্রেও আসলে তুমি ‘সরোইনি’।</p><p>একটা ব্যাপার মনে রাখো, পরে কাজে দিবে। যেখান থেকে যাত্রা শুরু করছো সেই জায়গার নাম ‘আদিবিন্দু’ [আদি মানে শুরু] এবং যেখানে শেষ করছো সেই জায়গার নাম ‘শেষবিন্দু’।</p><p>চিত্র ২ এ তোমার দূরত্ব [অতিক্রান্ত] কত?</p><p>তুমি প্রথমে বাড়ি থেকে স্কুলে 3 km, এরপর স্কুল থেকে খেলার মাঠে 5 km, সবশেষে মাঠ থেকে বাড়ি 4 km গেছো। তাহলে তোমার অতিক্রান্ত দূরত্ব = 3 km + 5 km + 4 km = 12 km.</p><p>কি বুঝলে? দূরত্ব মাপার জন্য দেখতে হয় তুমি কোন্ কোন্ রাস্তা দিয়ে কতখানি কতখানি করে গেছো। শুরু আর শেষ দেখার দরকার নাই।</p><p>এখন আমরা আরও একটি উদাহরণ দেখবো, তাহলে বিষয়টি আরও পরিষ্কার হবে তোমাদের কাছে।</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/486/1*wlAJAtQwI0oH5lxG1Q98sg.png" /><figcaption>চিত্র ৪</figcaption></figure><p>পাশের চিত্র ৪ খেয়াল করো, এখানে M হচ্ছে Market (বাজার)। তোমার আম্মু তোমাকে বললেন যে, স্কুলে যাওয়ার আগে বাজার থেকে ডিম এনে দিয়ে যা। তুমি HM বরাবর 5 km গিয়ে ডিম কিনে MG বরাবর 3 km গিয়ে খেলার মাঠ ঘুরে আবার GH বরাবর 4 km গিয়ে মা’কে ডিম দিয়ে HS বরাবর 3 km গিয়ে স্কুলে পৌঁছালে।</p><p>এখন এই ক্ষেত্রে তোমার সরণ ও দূরত্ব কত?</p><p>সরণ কিভাবে মাপতে হয়, মনে আছে? যেখান থেকে শুরু করেছো এবং যেখানে শেষ করেছো, শুধু এই দুইটা হিসাব মাথায় রাখতে হয়। তাহলে শুরু হয়েছিল বাড়ি থেকে এবং শেষ হয়েছে স্কুলে গিয়ে। তাহলে তোমার সরণ = HS = 3 km.</p><p>আর দূরত্ব কিভাবে মাপতে হয়? কোন্ কোন্ রাস্তা দিয়ে কতখানি কতখানি করে গেছো সেগুলো সব যোগ দিলেই পাওয়া যায়, তাই নয় কি? ঠিক আছে, তাহলে</p><p>H থেকে শুরু ……… HM = 5 km</p><p>তারপর M থেকে ……. MG = 3 km</p><p>এরপর G থেকে মায়ের কাছে ……. GH = 4 km</p><p>সবশেষে স্কুল …… HS = 3 km</p><p>তাহলে তোমার অতিক্রান্ত দূরত্ব = 5 km + 3 km + 4 km + 3 km = 15 km</p><p>চিত্র ৪ থেকে আমরা দেখলাম যে, একই রাস্তা ও একই ঘটনা কিন্তু তারপরেও তোমার সরণ (3 km) ও অতিক্রান্ত দূরত্ব (15 km) আলাদা। তাহলে বোঝাই যাচ্ছে যে, সরণ ও দূরত্ব আলাদা রাশি।</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*FpQH9Jiv3utWwmp3srZRBA.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/319/1*t3D1AEWZ6nQuGtlGUpKDhw.png" /><figcaption>চিত্র ৫</figcaption></figure><p>এবার আমরা একটা বিশেষ উদাহরণ দেখবো,</p><p>পাশের চিত্র ৫ এ, মনে করো তুমি প্রথমে A হতে B তে 4 km গেলে। তারপর B হতে C পর্যন্ত 2 km গেলে। তাহলে, তোমার সরণ = AC = 3 km। কিন্তু দূরত্ব = AB + BC = 4 km + 2 km = 6 km</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/368/1*3zTG51WEVUtcTn3rWTP02g.png" /><figcaption>চিত্র ৬</figcaption></figure><p>পাশের চিত্র ৬ এ, মনে করো তুমি চিত্র ৫ এর মতো করেই A হতে B তে 4 km এবং তারপর B হতে C পর্যন্ত 2 km গেলে। এবার কিন্তু তোমার সরণ = AC = 5 km হয়েছে। দেখতেই পাচ্ছো এখানে A থেকে C একটু বেশি দূরে আছে। আর দূরত্ব = AB + BC = 4 km + 2 km = 6 km ই আছে।</p><p>উপরের চিত্র দুটিতে (চিত্র ৫ ও ৬) দূরত্ব (6 km) একই আছে, কিন্তু সরণ আলাদা হয়ে গেছে। কারণ দেখো চিত্র ৫ এ কোণ ABC [তীরচিহ্ন দিয়ে নির্দেশ করা আছে] ছোট তাই সরণ কম (3 km) হয়েছে। আর চিত্র ৬ এ কোণ ABC এর মান চিত্র ৫ এর তুলনায় বড়, তাই সরণ বেশি (5 km) হয়েছে।</p><p>তাহলে আমরা বলতে পারি যে, সরণ কম হবে না বেশি হবে সেটা নির্ভর করে বিপরীত কোণের ‍ওপর। চিত্র ৫ বা চিত্র ৬ এ যদি আমরা AC কে ABC ত্রিভুজের একটি বাহু কল্পনা করি তবে তার বিপরীত দিকের কোণ হবে ABC, তাই নয় কি? ABC কোণকে নির্দেশ করার জন্য যে তীরচিহ্ন দেয়া আছে সেটা খেয়াল করলে সহজেই তোমরা বুঝে যাবে।</p><p>আমরা কোণের হিসেব করি জ্যামিতি দিয়ে। তোমাদের কি মনে আছে যে, ‘সরণ’ দিকওয়ালা রাশি? তাহলে বলা যায় যে, দিকওয়ালা রাশির হিসাব-নিকাশ অর্থাৎ যোগ-বিয়োগ হবে জ্যামিতিক উপায়ে কেননা সেখানে কোণের হিসাব-নিকাশ (উপরের উদাহরণে ABC) চলে আসছে।</p><p>ঘাবড়ানোর কিছু আপাতত নেই, কারণ নবম-দশম শ্রেণীতে তোমরা এই ধরনের হিসাব-নিকাশ দেখতে পাবেনা বললেই চলে। বড় ক্লাসে উঠে পাবে। ততদিনে পদার্থবিজ্ঞানে তুমি অনেক ভালো হয়ে যাবে।</p><p>দূরত্ব দিকছাড়া রাশি। এর হিসাব-নিকাশ তোমরা ইতিমধ্যেই দেখেছো। শুধু যোগ করে দিলেই হয়, এক্ষেত্রে কোন কোণের হিসাব করা লাগেনা। এই ধরনের যোগ-বিয়োগ তোমরা বীজগণিতে অনেক করেছো। তারমানে দিকছাড়া রাশির হিসাব হবে বীজগাণিতিক নিয়মে।</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/286/1*_Mq4vlAD0DI7OkwnGgNeWg.png" /><figcaption>চিত্র ৭</figcaption></figure><p>কিছুক্ষণ আগে উল্লেখ করা হয়েছে যে, সরণ আদিবিন্দু ও শেষবিন্দুর মধ্যকার ক্ষুদ্রতম দূরত্ব। এখন এই বিষয়টি নিয়ে একটু কথা বলা যাক। পাশের চিত্র ৭ এ দেখা যাচ্ছে যে, স্থান A ও B এর মধ্যে দুটি রাস্তা আছে। মনে করো তুমি ১ নং রাস্তা ধরে A থেকে B তে গেলে, তাহলে তোমার সরণ ও দূরত্ব কত হবে?</p><p>খেয়াল করে দেখো যে, ১ নং রাস্তাটি খানিকটা ঘুরে A হতে B তে গেছে যার দৈর্ঘ্য 6 km। তাহলে এক্ষেত্রে দূরত্ব হবে 6 km কিন্তু সরণ কত হবে?</p><p>সরণ হবে 4 km, এখন মনে প্রশ্ন জাগতে পারে যে আমরা তো ২ নং রাস্তা দিয়ে যাইনি। তুমি যে রাস্তা ব্যবহার করেই যাওনা কেন সেটা কোন বিষয় নয়। সরণ হবে সবসময় ছোট বা ক্ষুদ্রতম দূরত্ব টা। আচ্ছা যদি এবার আমরা ২ নং রাস্তা ব্যবহার করে A হতে B তে যাই সেক্ষেত্রে দূরত্ব ও সরণ কত হবে?</p><p>এক্ষেত্রে দূরত্ব হবে 4 km কেননা সেটা রাস্তার দৈর্ঘ্য এবং সরণও হবে 4 km কারণ এটা ক্ষুদ্রতম দূরত্ব। ক্ষুদ্রতম দূরত্ব নির্ধারণ করতে হয় একবিন্দু থেকে অন্যবিন্দুতে লম্ব টেনে।</p><p>এখন তোমাদের জন্য একটা প্রশ্ন। নিচে উত্তর দেয়া আছে, তবে প্রথমে নিজে চেষ্টা করো। যদি একান্তই না পারো তাহলে উত্তর দেখে নাও।</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/248/1*ftR9b7pQXRN3rp5RUW4z9A.png" /><figcaption>চিত্র ৮</figcaption></figure><p>প্রশ্নটি হচ্ছে, পাশের বৃত্তাকার রাস্তার ব্যাসার্ধ 1 km। তুমি যদি রাস্তাটিতে,</p><p>(১) A হতে A তে যাও</p><p>(২) A হতে C তে যাও</p><p>(৩) A হতে B তে যাও</p><p>(৪) A হতে D তে যাও, তাহলে তোমার সরণ ও দূরত্ব কত?</p><p>আজ তাহলে এখানেই শেষ করি। দেখা হবে পরের পর্বে। যদি লেখাটি ভালো লেগে থাকে তাহলে লাইক (এখানে অবশ্য সেটা ক্ল্যাপিং), শেয়ার ও কমেন্ট করলে ভালো হয়।</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=9396e4803d0a" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[গ্রাফ থিওরি (পর্ব ৯)]]></title>
            <link>https://medium.com/%E0%A6%AA%E0%A7%8D%E0%A6%B0%E0%A7%8B%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AE%E0%A6%BF%E0%A6%82-%E0%A6%AA%E0%A6%BE%E0%A6%A4%E0%A6%BE/%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AB-%E0%A6%A5%E0%A6%BF%E0%A6%93%E0%A6%B0%E0%A6%BF-%E0%A6%AA%E0%A6%B0%E0%A7%8D%E0%A6%AC-%E0%A7%AF-7764ccbf8a04?source=rss-550534651e5d------2</link>
            <guid isPermaLink="false">https://medium.com/p/7764ccbf8a04</guid>
            <category><![CDATA[software-engineering]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[graph-theory]]></category>
            <category><![CDATA[bangla]]></category>
            <dc:creator><![CDATA[Ahsan Shafiq Shawon]]></dc:creator>
            <pubDate>Thu, 07 Feb 2019 06:02:50 GMT</pubDate>
            <atom:updated>2019-02-08T09:32:15.577Z</atom:updated>
            <content:encoded><![CDATA[<p><strong>প্রোগ্রামিং — ১</strong></p><p><strong>উপগ্রাফের কথা</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*0q0oLwXbb9wkKp8LzR0JPA.jpeg" /><figcaption>Photo by <a href="https://unsplash.com/photos/1lfI7wkGWZ4?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">NASA</a> on <a href="https://unsplash.com/search/photos/satellite?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Unsplash</a></figcaption></figure><p>একটি গ্রাফ থেকে এক বা একাধিক নোড সরিয়ে দিয়ে নতুন যে গ্রাফ বানানো যায় তাকে আমরা মূল গ্রাফের একটা উপগ্রাফ বলতে পারি। নিচের ছবিটি খেয়াল করলে আরও পরিষ্কার হবে।</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/649/1*rHcYXvdBECG2UlCUE3AxGw.png" /></figure><p>এখানে আমরা <strong><em>G</em></strong> নামের একটি গ্রাফ নিয়েছি, এর <strong><em>v₁</em></strong> নোডটি সরিয়ে নিলে ডানপাশের গ্রাফটি তৈরি হয়। একে আমরা মূল গ্রাফের (<strong><em>G</em></strong>) উপগ্রাফ (<strong><em>subgraph</em></strong>) বলবো। তুমি যে নোডটি সরিয়ে নিবা সেই নোড থেকে যে এজগুলো বের হবে তারাও মুছে যাবে। উপগ্রাফটিকে <strong><em>G — v₁</em></strong> দ্বারা প্রকাশ করা যায়। এভাবে নোড সরিয়ে দেয়ার মাধ্যমে যে উপগ্রাফ তৈরি হয় তাদেরকে <strong><em>induced subgraph</em></strong> বলে।<br>আরেকটি উদাহরণ দেয়া যাক,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/646/1*NQYUM2aJOJg1yfwmqCO2IQ.png" /></figure><p>ছবি ৬৭ এর মূল গ্রাফ (<strong><em>G</em></strong>) থেকে <strong><em>v₁</em></strong> ও <strong><em>v₅</em></strong> নোড সরিয়ে নেয়া হয়েছে। সরিয়ে নেয়া নোডগুলো নিয়ে একটি সেট তৈরি করা হলো, নাম দিলাম <strong><em>X</em></strong>। তাহলে, <strong><em>X</em></strong> = <strong><em>{v₁, v₅}</em></strong>। একারণে উপগ্রাফটির নাম দেয়া হয়েছে <strong><em>G — X</em></strong>।</p><p>আবার কোন গ্রাফ থেকে এক বা একাধিক এজ সরিয়ে নিয়েও উপগ্রাফ তৈরি করা যায়। এদেরকে বলা হয় <strong><em>spanning</em></strong>। নিচের ছবিটি খেয়াল করি,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/808/1*HERukHFCQ7Ec5MYHC5kaqg.png" /></figure><p>ছবি ৬৮ এর মূল গ্রাফ (<strong><em>G</em></strong>) থেকে <strong><em>e₁</em></strong> এজটি সরিয়ে নিলে আমরা (২) নং গ্রাফটি পাই। একে <strong><em>G\e₁</em></strong> দ্বারা প্রকাশ করা হয় এবং একে আমরা মূল গ্রাফের একটি <strong><em>spanning</em></strong> বলবো। এবার আমরা যদি আরও একটি এজ (<strong><em>e₂</em></strong>) সরিয়ে নিই তাহলে (৩) নং গ্রাফটি পাই। তাহলে <strong><em>Y = {e₁, e₂}</em></strong> সরিয়ে নিলে আমরা <strong><em>G\Y</em></strong> গ্রাফটি পাচ্ছি। খেয়াল করে দেখো (৩) নং গ্রাফটি হচ্ছে একটি ট্রি। আশা করছি, ট্রি বলতে কি বুঝায় সেটা তোমাদের মনে আছে। না থাকলে পর্ব ৪ পড়ে আসতে পারো।</p><p>তাহলে আমরা (৩) নং গ্রাফটিকে বলতে পারি <strong><em>spanning tree</em></strong>। এখানে একটা বিষয় মনে রাখতে হবে যে, <strong><em>induced graph</em></strong> এ যে নোডগুলোকে সরিয়ে ফেলছিলাম তাদের সাথে সংশ্লিষ্ট এজগুলোও মুছে যাচ্ছিল কিন্তু <strong><em>spanning</em></strong> এর ক্ষেত্রে মূল গ্রাফে যতগুলো নোড থাকবে <strong><em>spanning</em></strong> এও ততগুলোই নোড থাকবে।</p><p><strong><em>Introduction to Algorithms (3rd Edition)</em></strong> বইয়ের ২৩নং অধ্যায়ে <strong><em>Minimum Spanning Tree (MST)</em></strong> নিয়ে আলোচনা আছে। <strong><em>Spanning Tree</em></strong> কি জিনিস সেটা নিয়ে আমরা ইতিমধ্যেই কথা বলেছি। এবার <strong><em>MST</em></strong> নিয়ে কথা হবে। নিচের ছবিটি খেয়াল করি,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/264/1*a1IFWlK3MhHYJ-sgyPGSyw.png" /></figure><p>আমরা ছবি ৬৯ এ একটি <strong><em>undirected weighted</em></strong> গ্রাফ দেখতে পাচ্ছি। তোমাকে যদি ছবি ৬৯ এর গ্রাফের <strong><em>Spanning Tree</em></strong> বের করতে বলা হয়, পারবানা? ছবি ৬৮ এর নিয়ম অবলম্বন করলেই হবে। কিন্তু দেখা যাবে যে, একেক জন একেকটা <strong><em>Spanning Tree</em></strong> বের করছে। আসলে একটি গ্রাফের অনেকগুলো <strong><em>Spanning Tree</em></strong> হতে পারে। কোন গ্রাফের এজসংখ্যা = <strong><em>n</em></strong>, নোডসংখ্যা = <strong><em>m</em></strong> এবং চক্রসংখ্যা (<strong><em>number of cycle</em></strong>) = <strong><em>k</em></strong> হলে, ঐ গ্রাফের <strong><em>Spanning Tree</em></strong> সংখ্যা = <strong><em>ⁿCₘ₋₁ — k</em></strong></p><p>তাহলে ছবি ৬৯ এর গ্রাফের ক্ষেত্রে, এজসংখ্যা, <strong><em>n = 5</em></strong>, নোডসংখ্যা, <strong><em>m = 4</em></strong> এবং চক্রসংখ্যা <strong><em>k = 2</em></strong> (নোড ১, ২, ৪ মিলে একটি চক্র এবং নোড ৪, ২, ৩ মিলে আরেকটি চক্র), তাহলে এই গ্রাফের <strong><em>Spanning Tree</em></strong> সংখ্যা = <strong><em>⁵C₃ — 2 = 8</em></strong> । আমরা এখন উপরের গ্রাফের ৮টি <strong><em>Spanning Tree</em></strong> এঁকে ফেলবো,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/875/1*pnL_5xPALue-vHJAF5PGDQ.png" /></figure><p>এজগুলোর সাথে যে মান দেয়া (<strong><em>weight</em></strong>) আছে তাদের যোগ করলে ওই <strong><em>spanning tree</em></strong> ঘুরতে কত খরচ (<strong><em>cost</em></strong>) হয় সেটা পাওয়া যায়। যে <strong><em>spanning tree</em></strong> এর ক্ষেত্রে খরচ সবথেকে কম সেটাই হচ্ছে <strong><em>MST</em></strong>। এক্ষেত্রে (৪) নং <strong><em>spanning tree</em></strong> টি হচ্ছে ছবি ৬৯ এর গ্রাফের <strong><em>MST</em></strong>। কিন্তু এভাবে গরু-গাধার মতো সবগুলো <strong><em>spanning tree</em></strong> এঁকে <strong><em>MST</em></strong> বের করা সম্ভব না, তাই আমরা অন্যপথে হাঁটবো।</p><p><strong><em>MST</em></strong> বের করার দুটি বিখ্যাত অ্যালগরিদম আছে। যথাঃ <strong><em>Kruskal’s algorithm</em></strong> ও <strong><em>Prim’s algorithm</em></strong>। এই অ্যালগরিদমগুলো নিয়ে কথা বলার আগে আমরা একটু ইতিহাস চর্চা করবো।</p><p>গণিতের রাজপুত্র লিওনার্দ অয়লারের সাথে শুধুমাত্র একটি মানুষের তুলনা হওয়া সম্ভব, তিনি হচ্ছেন পল আরডস (<strong><em>Paul Erdos</em></strong>)। হাঙ্গেরির রাজধানী বুদাপেস্টে অয়লারের মৃত্যুর ১৩০ বছর পর জন্ম নেয়া শারীরিকভাবে ছোটখাটো এই যাযাবর মানুষটি ছিলেন অবিবাহিত। সারাজীবন এক বিশ্ববিদ্যালয় থেকে আরেক বিশ্ববিদ্যালয়ে ঘুরে ঘুরে ক্লাস নিয়েছেন। কখনোই কোন স্থানে বেশিদিন একটানা অবস্থান করেননি। বিশ্ববিদ্যালয়গুলোতে ক্লাস নিয়ে আর গণিতের বিভিন্ন সেমিনারে বক্তৃতা দিয়ে উনার যে আয় হতো তা দিয়েই দিনানিপাত করতেন।</p><p>সবসময়ের সঙ্গী হিসেবে সাথে থাকতো একটা স্যুটকেস, তাতে জামা-কাপড়ের মতো প্রয়োজনীয় কিছু জিনিসপত্র থাকতো। সেই স্যুটকেস নিয়েই একেকদিন একেক গণিতবিদের দরজায় গিয়ে কড়া নাড়তেন, বলতেন “আমার মাথা খালি আছে, সমাধানের জন্য সমস্যা দাও।”</p><p>সারাজীবনে গণিতের ওপর দেড় হাজার গবেষণাপত্র লিখেছেন, যা আজ পর্যন্ত কেউই ছুঁতে পারেনি। ছিলেন মা-বাবার একমাত্র জীবিত সন্তান। শৈশবেই তার বড় দুই বোন মারা যায়। মা-বাবা দুজনেই ছিলেন গণিতের শিক্ষক। সেখান থেকেই গণিতে হাতেখড়ি হয়ে যায়। ৮৩ বছর বয়সে মৃত্যুর ঘন্টাখানেক আগেও গণিতের ওপর বক্তৃতা দিয়েছেন।</p><p>ভদ্রলোকের প্রিয় একটি বাক্য ছিল যে, <strong><em>“Another roof, another proof”</em></strong>। সারাক্ষণ বিভিন্ন বিখ্যাত গাণিতিক সমস্যা নিয়ে মাথা ঘামাতেন, যেগুলো বছরের পর বছর কেউ সমাধান করতে পারেনি। কমপক্ষে ১৫টি বিশ্ববিদ্যালয় উনাকে সম্মানসূচক ডিগ্রিতে ভূষিত করে।</p><p>পল আরডস এর হাত ধরে চারজন ব্যক্তি পিএইচডি করেছেন। এদের মধ্যে একজন হচ্ছেন বিখ্যাত <strong><em>Bell Labs</em></strong> এর গবেষক <strong><em>Joseph Bernard Kruskal</em></strong>। এই <strong><em>Kruskal</em></strong> সাহেব <strong><em>MST</em></strong> বের করার জন্য একটি অ্যালগরিদম তৈরি করেন আজ থেকে ৬৪ বছর আগে, যা পরবর্তীতে বেশ খ্যাতি লাভ করে। আমরা এখন সেই অ্যালগরিদমটি কিভাবে কাজ করে সেটা দেখবো।</p><p>উদাহরণ হিসেবে যেকোন একটি গ্রাফ নেয়া যাক,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/474/1*AzoaJS0368VjTMYa8jVZ-g.png" /></figure><p>প্রথমে আমরাকে সেই এজটি নিতে হবে যার <strong><em>weight</em></strong> সবচেয়ে কম।</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1000/1*rp7mI6sBL-gaLeK7r4aLUQ.png" /></figure><p>আমাদের উদ্দেশ্য হচ্ছে সবচেয়ে কম খরচে পুরো গ্রাফটি ঘুরে বেড়ানো অর্থাৎ যতগুলো নোড আছে সবগুলোতে ঘুরে আসা।</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1000/1*bKJn45wFMDvmo9O0Qpl0FQ.png" /></figure><p>অবশেষে,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/983/1*oTNNvLJeqM_7aYohshi85w.png" /></figure><p>তাহলে <strong><em>kruskal</em></strong> এর অ্যালগরিদমটিকে সংক্ষেপে লিখলে,<br>সবচেয়ে কম <strong><em>weight</em></strong> বিশিষ্ট এজ নিতে হবে, এরপর যেই এজ কম <strong><em>weight</em></strong> বিশিষ্ট হবে সেটা নিতে হবে। এভাবে নিতে থাকতে হবে, শুধু খেয়াল রাখতে হবে যেন কোন চক্র তৈরি না হয়। কেননা আমরা ট্রি বানাচ্ছি এবং ট্রি তে কোন চক্র থাকেনা। তাহলে ছবি ৭১ এর গ্রাফের <strong><em>MST</em></strong> হচ্ছে,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/474/1*u7ZYG5DZCYhEiwydJXnnQg.png" /></figure><p>যে সময়ে <strong><em>Bell Labs</em></strong> এ <strong><em>Kruskal</em></strong> গবেষণা করতেন; ওই সময়ে <strong><em>Robert Clay Prim</em></strong> যিনি আইনস্টাইনের স্মৃতি বিজড়িত <strong><em>Princeton University</em></strong> থেকে গণিতে পিএইচডি করেছেন, তিনিও <strong><em>Kruskal</em></strong> এর সাথে একই জায়গায় গবেষণায় নিয়োজিত ছিলেন। দেখা যাচ্ছে যে উনারা একই সময় একই জায়গায় কাজ করতেন এবং <strong><em>MST</em></strong> বের করার জন্য দুটি আলাদা বিখ্যাত অ্যালগরিদম প্রায় একই সময় আবিষ্কার করেন। তবে এখানে আরেকটি মজার ব্যাপার বলা যায়, আমরা যেটিকে <strong><em>Prim’s algorithm</em></strong> বলছি সেই অ্যালগরিদমটি <strong><em>Prim</em></strong> এর ২৭ বছর আগে <strong><em>Vojtech Jarnik</em></strong> এবং <strong><em>Prim</em></strong> এর ২ বছর পর <strong><em>Edsger Dijkstra</em></strong> আলাদা আলাদাভাবে আবিষ্কার করেন। অর্থাৎ একই অ্যালগরিদম তিনজন মানুষ আলাদা আলাদাভাবে কাউকে না জানিয়ে আবিষ্কার করেছেন। সে কারণে এই অ্যালগরিদমকে অনেক সময় <strong><em>Dijkstra-Jarnik-Prim Algorithm</em></strong> বা <strong><em>DJP algorithm</em></strong> নামেও ডাকা হয়।</p><p>যে অ্যালগরিদম নিয়ে এত কথা সেটা কিভাবে কাজ করে, তা নিয়ে এবার আলোচনা করা হবে। আমরা উদাহরণ হিসেবে ছবি ৭১ এর গ্রাফটিই ব্যবহার করবো।</p><p>প্রথমে আমরাকে সেই এজটি বেছে নিতে হবে যার <strong><em>weight</em></strong> সবথেকে কম ( <strong><em>Kruskal’s algorithm</em></strong> এর মত)।</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1009/1*T52vtnf-MvX6lddKXVRQ4A.png" /></figure><p>এখন পর্যন্ত আমরা দুটি এজ নিয়েছি (১ থেকে ৬ এবং ৬ থেকে ৫)। এই নোডগুলোর (১, ৬, ৫) সাথে যুক্ত সবচেয়ে কম <strong><em>weight</em></strong> বিশিষ্ট এজটি এবার নিতে হবে এবং এভাবেই পুরো পদ্ধতিটি কাজ করবে। এই এজগুলোর সাথে যুক্ত এজগুলোর <strong><em>weight</em></strong> হচ্ছে ২৮ (১ থেকে ২), ২৪ (৫ থেকে ৭) এবং ২২ (৫ থেকে ৪)। তাহলে আমরা নিবো ২২ <strong><em>weight</em></strong> বিশিষ্ট এজটি।</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1000/1*Mh3noFtv7X99XMexWD8cAg.png" /></figure><p><strong><em>Prim’s algorithm</em></strong> এবং <strong><em>Kruskal’s algorithm</em></strong> এর মধ্যে মূল পার্থক্য আমরা দেখতে পাচ্ছি যে, <strong><em>Kruskal’s algorithm</em></strong> এর ক্ষেত্রে আমরা সবচেয়ে কম <strong><em>weight</em></strong> বিশিষ্ট এজগুলো (যেখানেই থাকুক না কেন) একটার পর একটা নিয়েছি। কিন্তু <strong><em>Prim’s algorithm</em></strong> এর ক্ষেত্রে আমরা শুরু করবো সবচেয়ে কম <strong><em>weight</em></strong> বিশিষ্ট এজ দিয়ে, তবে এরপরের যে এজগুলো (অবশ্যই সবচেয়ে কম <strong><em>weight</em></strong> বিশিষ্ট) নিবো সেগুলো যেন অবশ্যই আগেরগুলোর সাথে কোন না কোনভাবে যুক্ত থাকে।</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/983/1*RPOX9M9GNPtNiFCTVcgM6w.png" /></figure><p>অবশেষে আমরা যে ফলাফল পেয়েছি তা ছবি ৭৫ এ প্রাপ্ত ফলাফলের অনুরূপ। এখন আলোচ্য অ্যালগরিদম দুটোর প্রোগ্রাম দেখার পালা। কিন্তু <strong><em>Prim’s algorithm</em></strong> এর জন্য <strong><em>Min heap</em></strong> এবং <strong><em>Kruskal’s algorithm</em></strong> এর <strong><em>implementation</em></strong> এর জন্য <strong><em>Union set data structure</em></strong> জানা প্রয়োজন।</p><p>আমরা অ্যালগরিদম দুটির প্রোগ্রাম দেখার আগে এই পূর্বশর্তগুলো নিয়ে আলোচনা করবো। এই পর্বে এগুলো নিয়ে আলোচনা করলে অনেক লম্বা হয়ে যাবে, তাই পরের পর্বে আলোচনা করাই ভালো হবে।</p><p>মাত্র ২৬ বছর বয়সে লিওনার্দ অয়লার সেন্ট পিটার্সবার্গ অ্যাকাডেমির গণিত বিভাগের প্রধান হিসেবে নিয়োগ পান।</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=7764ccbf8a04" width="1" height="1" alt=""><hr><p><a href="https://medium.com/%E0%A6%AA%E0%A7%8D%E0%A6%B0%E0%A7%8B%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AE%E0%A6%BF%E0%A6%82-%E0%A6%AA%E0%A6%BE%E0%A6%A4%E0%A6%BE/%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AB-%E0%A6%A5%E0%A6%BF%E0%A6%93%E0%A6%B0%E0%A6%BF-%E0%A6%AA%E0%A6%B0%E0%A7%8D%E0%A6%AC-%E0%A7%AF-7764ccbf8a04">গ্রাফ থিওরি (পর্ব ৯)</a> was originally published in <a href="https://medium.com/%E0%A6%AA%E0%A7%8D%E0%A6%B0%E0%A7%8B%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AE%E0%A6%BF%E0%A6%82-%E0%A6%AA%E0%A6%BE%E0%A6%A4%E0%A6%BE">প্রোগ্রামিং পাতা</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[গ্রাফ থিওরি (পর্ব ৮)]]></title>
            <link>https://medium.com/%E0%A6%AA%E0%A7%8D%E0%A6%B0%E0%A7%8B%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AE%E0%A6%BF%E0%A6%82-%E0%A6%AA%E0%A6%BE%E0%A6%A4%E0%A6%BE/%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AB-%E0%A6%A5%E0%A6%BF%E0%A6%93%E0%A6%B0%E0%A6%BF-%E0%A6%AA%E0%A6%B0%E0%A7%8D%E0%A6%AC-%E0%A7%AE-656cd6274688?source=rss-550534651e5d------2</link>
            <guid isPermaLink="false">https://medium.com/p/656cd6274688</guid>
            <category><![CDATA[software-engineering]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[bangla]]></category>
            <category><![CDATA[graph-theory]]></category>
            <dc:creator><![CDATA[Ahsan Shafiq Shawon]]></dc:creator>
            <pubDate>Thu, 07 Feb 2019 05:44:42 GMT</pubDate>
            <atom:updated>2019-02-07T07:03:23.744Z</atom:updated>
            <content:encoded><![CDATA[<p><strong>প্রোগ্রামিং — ১</strong></p><p><strong>মজবুত সম্পর্কের গ্রাফ</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Vp6gBtj4gL7szswUFFH2uA.jpeg" /><figcaption>Photo by <a href="https://unsplash.com/photos/jpgRztEuaV4?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">michael podger</a> on <a href="https://unsplash.com/search/photos/spider-web?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Unsplash</a></figcaption></figure><p><strong><em>Undirected graph</em></strong> এর ক্ষেত্রে আমরা জানি যে, ১ নং নোড থেকে ২ নং নোডে যদি যাওয়া যায় তাহলে ২ নং থেকে ১ নং এ যাওয়া যাবে। কিন্তু <strong><em>directed graph</em></strong> এর ক্ষেত্রে বিষয়টি সেরকম নাও হতে পারে। নিচের ছবিটি খেয়াল করি,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/467/1*CuJ_y56zBNxk0nqerQFOpA.png" /></figure><p>(১) নং গ্রাফটি <strong><em>undirected</em></strong> তাই আবুল যেমন বাবুলের বন্ধু, ঠিক তেমনি বাবুলও আবুলের বন্ধু। আবুল মনে মনে সখিনাকে খুব ভালোবাসে কিন্তু সখিনা আবুলকে পাত্তা দেয়না। তাহলে আবুলের দিক থেকে সখিনার সাথে সম্পর্ক থাকলেও, সখিনার দিক থেকে নেই। ছবির (২) নং অংশে <strong><em>directed graph</em></strong> দ্বারা এই বিষয়টি বুঝানো হয়েছে। তাহলে বলা যায় যে, আবুল ও সখিনার মধ্যে মজবুত সম্পর্ক নাই। এক হাতে তালি বাজছে আরকি।</p><p>তাহলে সম্পর্ক তখনই মজবুত হবে যখন দুই পক্ষ থেকেই সম্পর্ক থাকবে। নিচের ছবিটি দেখা যাক,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/802/1*_UkOtrq2v7I1SwJQPP--ew.png" /></figure><p>(১) নং গ্রাফে, খুলনা থেকে সিলেট যাওয়া যায় আবার সিলেট থেকে খুলনাও যাওয়া যায়। এদের মধ্যে মজবুত সম্পর্ক আছে দেখা যাচ্ছে। (২) নং গ্রাফে ঢাকা থেকে খুলনা যাওয়া যায়, আবার ঢাকা থেকে খুলনা হয়ে সিলেট যাওয়া যায়। খুলনা থেকে সিলেট যাওয়া যায়, আবার খুলনা থেকে সিলেট হয়ে ঢাকা যাওয়া যায়। সবার সাথে সবার খুব ভালো সম্পর্ক। (৩) নং গ্রাফেও তাই। যদি কোন গ্রাফে এরকম সম্পর্ক পাওয়া যায় তবে তাদেরকে আমরা <strong><em>strongly connected</em></strong> বলবো।</p><p>পর্ব ৪ এ আমরা <strong><em>disconnected graph</em></strong> এর <strong><em>component</em></strong> সংখ্যা নিয়ে কথা বলেছি। নিচের ছবিটি খেয়াল করি,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/801/1*YPJcUs9c70CZiKr0pegZlw.png" /></figure><p>(১) নং গ্রাফটি <strong><em>undirected</em></strong> ও <strong><em>disconnected</em></strong>, এর <strong><em>component</em></strong> সংখ্যা হচ্ছে ২। (২) নং গ্রাফটি <strong><em>directed</em></strong> ও <strong><em>connected</em></strong>। কিন্তু ঢাকা, খুলনা, সিলেট থেকে সব জায়গায় যাওয়া গেলেও টোকিও থেকে কোথাও যাওয়া যাচ্ছেনা। তাই বলা যায়, ঢাকা, খুলনা, সিলেট এর মধ্যে সম্পর্ক মজবুত কিন্তু টোকিওর সাথে অন্যদের সম্পর্ক মজবুত নয়। তাহলে ঢাকা, খুলনা, সিলেট মিলে একটা অংশ এবং টোকিও নিজে একটা অংশ। ঢাকা, খুলনা, সিলেট <strong><em>strongly connected</em></strong> এবং টোকিও থেকে যেহেতু টোকিও যাওয়া যায় তাই এটা নিজে নিজে <strong><em>strongly connected</em></strong>। তাহলে (২) নং গ্রাফে <strong><em>strongly connected component</em></strong> কয়টা? ২টা।</p><p>গ্রাফের গল্প থেকে একটু বিরতি নিয়ে তোমাদের সাথে ভারতে জন্ম নেয়া এক ভদ্রলোকের সাথে পরিচয় করিয়ে দেই। পৃথিবীর সেরা ১৫ টি বিশ্ববিদ্যালয়ের একটি হচ্ছে জন হপকিন্স বিশ্ববিদ্যালয়। এই বিশ্ববিদ্যালয়ের কম্পিউটার বিজ্ঞানের একজন প্রফেসর হচ্ছেন <strong><em>Sambasiva Rao Kosaraju</em></strong>। ৭৬ বছর বয়স্ক এই প্রফেসর বর্তমানে যুক্তরাষ্ট্রের ন্যাশনাল সায়েন্স ফাউন্ডেশনের একটি বিভাগের পরিচালক হিসেবে দায়িত্ব পালন করছেন।</p><p>এই <strong><em>Kosaraju</em></strong> সাহেব, কোন একটা গ্রাফে কয়টি <strong><em>strongly connected component (SCC)</em></strong> আছে সেটা বের করার জন্য একটি বিখ্যাত অ্যালগরিদম তৈরি করেন ৪১ বছর আগে। উনার নামেই এই অ্যালগরিদমের নাম হচ্ছে <strong><em>Kosaraju’s algorithm</em></strong>।</p><p>আমরা এই পর্বে উল্লেখিত অ্যালগরিদমটি কিভাবে কাজ করে এবং তার প্রোগ্রাম দেখবো। তাহলে কাজ শুরু করা যাক।</p><p>প্রথমে অ্যালগরিদমটি ব্যাখ্যা করার জন্য আমরা একটি গ্রাফ নিয়ে নিই। নিচের ছবিটি খেয়াল করি,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/725/1*XlTs8XTs4ekGZbs2ShRNCg.png" /></figure><p>ছবি ৫৮ থেকে যে ধারণা পাওয়া গেছে তা ব্যবহার করে ছবি ৫৯ এর <strong><em>SCC</em></strong> বের করার চেষ্টা করে দেখতে পারো।<br>এখন আমরা অ্যালগরিদমটি ব্যাখ্যা করবো।<br>১ম ধাপ — প্রথমে প্রদত্ত গ্রাফের সবগুলো নোডের <strong><em>finishing time</em></strong> বের করে ফেলতে হবে। আমি আশা করছি তোমরা <a href="https://medium.com/%E0%A6%AA%E0%A7%8D%E0%A6%B0%E0%A7%8B%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AE%E0%A6%BF%E0%A6%82-%E0%A6%AA%E0%A6%BE%E0%A6%A4%E0%A6%BE/%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AB-%E0%A6%A5%E0%A6%BF%E0%A6%93%E0%A6%B0%E0%A6%BF-%E0%A6%AA%E0%A6%B0%E0%A7%8D%E0%A6%AC-%E0%A7%AD-10145d61ac6">পর্ব ৭ থেকে</a> <strong><em>discovery time</em></strong> ও <strong><em>finishing time</em></strong> এর ধারণা নিয়ে এসেছো। তাহলে সেই ধারণা প্রয়োগ করে আমরা নিচের ছবিটি তৈরি করে ফেলতে পারি। যদি আমরা ১ নং নোড থেকে যাত্রা আরম্ভ করি তাহলে,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/770/1*CgygwSRMGIqz6nMDaNVedw.png" /></figure><p>সবচেয়ে বেশি <strong><em>finishing time</em></strong> থেকে সবচেয়ে কম হিসেবে সাজালে আমরা পাই,<br>১ — ২ — ৪ — ৫ — ৩ — ৬ — ৮ — ৭ — ১০ — ৯ — ১১ — ১২</p><p>২য় ধাপ — ছবি ৫৯ এর গ্রাফের সবগুলো এজের দিক আমরা এখন উল্টিয়ে দিবো। তাহলে যে গ্রাফটি পাওয়া যাবে তাকে বলা হবে মূল গ্রাফের ট্রান্সপোজ গ্রাফ (<strong><em>Transpose graph</em></strong>)। যদি মূল গ্রাফটি (ছবি ৫৯) <strong><em>G</em></strong> হয়, তাহলে এর ট্রান্সপোজ গ্রাফকে (ছবি ৬১) <strong><em>Gᵀ</em></strong> দ্বারা প্রকাশ করা হয়।</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/725/1*4uM-EBQ-XylzqFLfdvmCaQ.png" /></figure><p>৩য় ধাপ — ছবি ৬১ এর গ্রাফের নোডগুলোর <strong><em>finishing time</em></strong> আবার বের করবো আমরা। তবে ইচ্ছামতো নোড থেকে শুরু করবোনা। ছবি ৬০ থেকে যে ধারাটা পেয়েছিলাম অর্থাৎ ১ — ২ — ৪ — ৫ — ৩ — ৬ — ৮ — ৭ — ১০ — ৯ — ১১ — ১২ অনুযায়ী আমরা <strong><em>finishing time</em></strong> বের করবো।<br>শুরু করা যাক ১ নং নোড থেকে। দেখা যাচ্ছে যে এখান থেকে কোথাও যাওয়া যাচ্ছেনা। তাহলে এটি একটি <strong><em>SCC</em></strong>। (ছবি ৬২)</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/737/1*Q0AyUYK9cphY8JYNVZnFhg.png" /></figure><p>(১) — ২ — ৪ — ৫ — ৩ — ৬ — ৮ — ৭ — ১০ — ৯ — ১১ — ১২ ধারা থেকে ১ নং নোডের কাজ শেষ (তাই একে প্রথম বন্ধনীর মধ্যে দেখানো হল)। এবার তাহলে ২ নং নোড থেকে শুরু হবে। ‘২’ থেকে শুরু করে ‘৫’ ও ৪ নং নোড ঘুরে আবার ‘২’ এ ফেরত এসে দেখা যাচ্ছে আর কোথাও যাওয়া যাচ্ছেনা। তাহলে নোড ২, ৫, ৪ মিলে একটি <strong><em>SCC</em></strong>। (ছবি ৬৩)</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/749/1*pKoLlTdZIckWp5P62rRg6w.png" /></figure><p>(১) — (২ — ৪ — ৫) — ৩ — ৬ — ৮ — ৭ — ১০ — ৯ — ১১ — ১২ ধারা থেকে আমরা এবার ৩ নং নোড দিয়ে শুরু করবো। একইরকমভাবে ৩ ও ৬ নং নোড দিয়ে আরেকটি SCC তৈরি হচ্ছে কেননা ৩ নং নোড থেকে যাত্রা শুরু করে ৬ নং নোডে এসে আর কোথাও যাওয়া যাচ্ছেনা। তাই ৩ নং নোডে ফেরত গিয়ে দেখা যাচ্ছে সেখান থেকেও অন্য কোথাও যাওয়া যাচ্ছেনা। (ছবি ৬৪)</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/757/1*JfSq7Tssn72xJlhK5vfhDA.png" /></figure><p>(১) — (২ — ৪ — ৫) — (৩ — ৬) — ৮ — ৭ — ১০ — ৯ — ১১ — ১২ ধারা থেকে আমরা এবার ৮ নং নোড দিয়ে শুরু করবো। আগের মতো করেই হিসাব করলে আমরা দেখতে পাবো যে, ৮, ৭, ১০, ৯, ১১ ও ১২ নং নোড মিলে আরেকটি <strong><em>SCC</em></strong> তৈরি করেছে। এটার জন্য আর <strong><em>finishing time</em></strong> দেখালাম না।</p><p>তাহলে দেখা যাচ্ছে যে, আমাদের আলোচ্য গ্রাফটিতে ৪টি <strong><em>strongly connected component</em></strong> পাওয়া যাচ্ছে। এখানে আমরা ইচ্ছাকৃত একটা ভুল করেছি, সেটা হচ্ছে <strong><em>SCC</em></strong> গুলো ট্রান্সপোজ গ্রাফে দেখিয়েছি। এটা করা হয়েছে একান্তই আলোচনার সুবিধার জন্য। <strong><em>SCC</em></strong> দেখাতে হয় সবসময় মূল গ্রাফে। (ছবি ৬৫)</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/780/1*lRSwF_XQhE2X_rb2p1pO_w.png" /></figure><p>এই ছিল <strong><em>Kosaraju’s algorithm</em></strong> ব্যবহার করে কোন <strong><em>directed graph</em></strong> এর <strong><em>strongly connected component</em></strong> বের করার পদ্ধতি। এবার আমরা এর প্রোগ্রাম দেখবো, তবে তার আগে কিছু আলোচনা সেরে নেয়া ভালো হবে।</p><p>যারা ১ম পর্ব থেকে এ পর্যন্ত সব লেখা পড়ে ফেলেছো তাদের অভিনন্দন, কারণ <strong><em>Introduction to Algorithms</em></strong> বইয়ের ২২ নং অধ্যায়ে যেসব বিষয় আছে সেগুলো আমাদের আলোচনা করা শেষ। অর্থাৎ ২২ নং অধ্যায় পড়া শেষ!</p><p>এ পর্যন্ত আলোচ্য বিষয়ের মধ্যে ছিল, গ্রাফের সাথে পরিচয়, গ্রাফকে কিভাবে কম্পিউটারে স্টোর করা যায়, DFS, BFS, Topological Sorting এবং এই পর্বে SCC। বাস্তব জীবনে এগুলো কোন্ কোন্ কাজে লাগে সে সম্পর্কে ধারণা থাকলে পড়াশোনা করে মজা পাওয়া যায়। এখন আমরা এ সম্পর্কিত সংক্ষিপ্ত কিছু আলোচনা করে ফেলি।</p><p>DFS — কোন গ্রাফে <strong><em>cycle</em></strong> বা চক্র আছে কিনা সেটা বের করার জন্য আমরা ডিএফএস ব্যবহার করে থাকি। Topological Sorting এবং SCC বের করার জন্য যে আমরা ডিএফএস ব্যবহার করেছি সেটাতো মনে আছেই। আরও অনেক গুরুত্বপূর্ণ ব্যবহারের মধ্যে একটা হচ্ছে কোন একটা গ্রাফ Bipartite কিনা সেটা বের করার জন্যও ডিএফএস ব্যবহার করা হয়। আমি আশা করছি তোমাদের নিশ্চয়ই মনে আছে, Bipartite গ্রাফের কথা।</p><p>BFS — বিভিন্ন ধরনের নেটওয়ার্ক তৈরিতে বা নেটওয়ার্কের যোগাযোগ (<strong><em>connection</em></strong>) পরীক্ষা করতে বিএফএস ব্যবহার করা হয়।</p><p>এবার প্রোগ্রাম দেখার পালা।</p><p>**কিছুদিন পর <strong><em>SCC</em></strong> এর প্রোগ্রাম এখানে যুক্ত করা হবে।</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=656cd6274688" width="1" height="1" alt=""><hr><p><a href="https://medium.com/%E0%A6%AA%E0%A7%8D%E0%A6%B0%E0%A7%8B%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AE%E0%A6%BF%E0%A6%82-%E0%A6%AA%E0%A6%BE%E0%A6%A4%E0%A6%BE/%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AB-%E0%A6%A5%E0%A6%BF%E0%A6%93%E0%A6%B0%E0%A6%BF-%E0%A6%AA%E0%A6%B0%E0%A7%8D%E0%A6%AC-%E0%A7%AE-656cd6274688">গ্রাফ থিওরি (পর্ব ৮)</a> was originally published in <a href="https://medium.com/%E0%A6%AA%E0%A7%8D%E0%A6%B0%E0%A7%8B%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AE%E0%A6%BF%E0%A6%82-%E0%A6%AA%E0%A6%BE%E0%A6%A4%E0%A6%BE">প্রোগ্রামিং পাতা</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[গ্রাফ থিওরি (পর্ব ৭)]]></title>
            <link>https://medium.com/%E0%A6%AA%E0%A7%8D%E0%A6%B0%E0%A7%8B%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AE%E0%A6%BF%E0%A6%82-%E0%A6%AA%E0%A6%BE%E0%A6%A4%E0%A6%BE/%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AB-%E0%A6%A5%E0%A6%BF%E0%A6%93%E0%A6%B0%E0%A6%BF-%E0%A6%AA%E0%A6%B0%E0%A7%8D%E0%A6%AC-%E0%A7%AD-10145d61ac6?source=rss-550534651e5d------2</link>
            <guid isPermaLink="false">https://medium.com/p/10145d61ac6</guid>
            <category><![CDATA[software-engineering]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[graph-theory]]></category>
            <category><![CDATA[bangla]]></category>
            <dc:creator><![CDATA[Ahsan Shafiq Shawon]]></dc:creator>
            <pubDate>Wed, 16 Jan 2019 11:09:24 GMT</pubDate>
            <atom:updated>2019-01-16T11:09:24.011Z</atom:updated>
            <content:encoded><![CDATA[<p><strong>প্রোগ্রামিং — ১</strong></p><p><strong>প্রফেসর বামস্টিড সাহেবের সাজুগুজু</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*yZWunekTH1rb4DgIGwoPXw.jpeg" /><figcaption>Photo by <a href="https://unsplash.com/photos/lRssALOk1fU?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">rawpixel</a> on <a href="https://unsplash.com/search/photos/map?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Unsplash</a></figcaption></figure><p><strong><em>Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, Clifford Stein</em></strong> কর্তৃক রচিত <strong><em>Introduction to Algorithms</em></strong> বইটি সম্পর্কে প্রোগ্রামিং পথের সব পথিকেরা মোটামুটি জ্ঞাত। এই বইয়ের ‘গ্রাফ থিওরি’ অংশটি পড়ার সময় <strong><em>Henry Andrews Bumstead</em></strong> এর নামটি পেলাম। খানিকটা খোঁজাখুঁজির পর দেখলাম এই ভদ্রলোক ইয়েল বিশ্ববিদ্যালয়ের পদার্থবিজ্ঞানের প্রফেসর ছিলেন দীর্ঘদিন। জ্বী, ইয়েল বিশ্ববিদ্যালয়। বিশ্বের অন্যতম সেরা বিদ্যাপীঠ। উল্লেখিত বই থেকে একটি স্ক্রিনশট দিচ্ছি এখানে।</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/730/1*neHViX1oenOSpB8hUHF3lg.png" /></figure><p>এই পর্যায়ে এসে আমার মনে প্রশ্ন জাগলো প্রফেসর বামস্টিডের সাথে এই বইয়ের লেখকদের কি সম্পর্ক। কিন্তু আমি জানতে পারলাম যে, একটা বিখ্যাত কার্টুন চরিত্র আছে যার নাম <strong><em>Dagwood Bumstead</em></strong>। এই চরিত্রটি প্রায় সবসময় স্যুটেড-ব্যুটেড অবস্থায় থাকে তাই লেখকেরা মজা করে উদাহরণ হিসেবে তাকে গ্রহণ করেছেন। উপরের উদাহরণের সাথে আসলে বাস্তবের প্রফেসর বামস্টিডের কোন যোগাযোগ নেই।</p><p>আচ্ছা বেশ খানিকটা গল্প হলো, এবার পড়াশোনায় মনোযোগ দেয়া যাক। উপরের ছবিটি ভালো করে খেয়াল করলে দেখা যাবে যে, এটি একটি <strong><em>directed graph</em></strong>। আমি আশা করছি তোমাদের <strong><em>directed graph</em></strong> কি, সেটা মনে আছে।</p><p>প্রশ্ন হচ্ছে যে, উপরের ছবিটির কাজ কি এখানে? সেটা বোঝার জন্য আমরা ধাপে ধাপে আগাবো। প্রথমেই আমরাকে <strong><em>directed acyclic graph (DAG)</em></strong> সম্পর্কে জেনে নিতে হবে এবং সেটার জন্য নিচের ছবিটি খেয়াল করা যেতে পারে,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/418/1*r6Ydja6tkK8iwKYEsG5DKA.png" /></figure><p>ছবি ৫১ এর (১) নং গ্রাফটি খেয়াল করি, প্রতিটি এজের দিক নির্দেশ করা আছে অর্থাৎ এটি একটি <strong><em>directed graph</em></strong>। সাথে আরেকটি ব্যাপার, আমরা যদি <strong><em>a</em></strong> নোড থেকে যাত্রা আরম্ভ করে <strong><em>b</em></strong> নোডে যেয়ে <strong><em>c</em></strong> নোডের দিকে যেতে চাই, সেটা সম্ভব হবেনা। কারণ <strong><em>b</em></strong> থেকে <strong><em>c</em></strong> তে যাওয়ার উপায় নেই (তীরচিহ্নটি খেয়াল করো)। আবার যদি <strong><em>a</em></strong> নোড থেকে যাত্রা আরম্ভ করে <strong><em>c</em></strong> নোডে যেয়ে <strong><em>b</em></strong> নোডের দিকে যেতে চাই, সেটা সম্ভব। কিন্তু <strong><em>b</em></strong> থেকে <strong><em>a</em></strong> তে যাওয়া যাবেনা (তীরচিহ্ন উল্টাদিকে আছে)। তাহলে যা দেখা গেলো সেটা হচ্ছে যে, <strong><em>a</em></strong> নোড থেকে যাত্রা আরম্ভ করে আবার <strong><em>a</em></strong> নোডে ফিরে আসা যাচ্ছেনা। অর্থাৎ এখানে কোন <strong><em>cycle</em></strong> বা চক্র তৈরি হয়নি মানে এটি <strong><em>acyclic</em></strong>। তাহলে (১) নং গ্রাফটিকে বলা যায় এটি একটি <strong><em>DAG</em></strong>। ঠিক একই কারণে (২) নং গ্রাফটি <strong><em>DAG</em></strong> নয়।</p><p>তোমরা ছবি ৫০ এর গ্রাফটি (জ্বী, এটি অবশ্যই একটি গ্রাফ। জামা-কাপড়, জুতা-মোজা এগুলো নোড বুঝাচ্ছে এবং সাথে একগাদা এজ তো আছেই।) ভালোভাবে খেয়াল করলে দেখবে যে এটিও একটি <strong><em>DAG</em></strong>।</p><p>তোমাদের কি <strong><em>DFS</em></strong> এর কর্মপদ্ধতি মনে আছে? না মনে থাকলে চট করে পর্ব ৫ পড়ে আসো। সেখানে আমরা দেখেছি যে, একটি নির্দিষ্ট নোড থেকে যাত্রা আরম্ভ করে বিভিন্ন নোডে চলে যাওয়া যায়। যখন আমরা কোন “একটি নোড থেকে যাত্রা আরম্ভ করি” তার মানে কি? ওই নোডটিকে আমরা আবিষ্কার করলাম, ওই মুহূর্তটিকে বলা হয় আবিষ্কারের সময় বা <strong><em>discovery time</em></strong>। ওই নোডের কাজ শেষ হয়ে গেলে আমরা তার <strong><em>finishing time</em></strong> টাও লিখে রাখতে পারি। আমরা এখন ছবি ৫০ কে একটু পাল্টিয়ে (জামা-কাপড়ের নামের জায়গায় ১, ২, ৩ ইত্যাদি সংখ্যা লিখবো) প্রতিটি নোডের <strong><em>discovery time</em></strong> ও <strong><em>finishing time</em></strong> বের করার চেষ্টা করবো।</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/513/1*JCL_04l6Z13MC7VN6pNtgA.png" /></figure><p>আমাদের ইচ্ছামত নোড থেকে শুরু করতে পারি হিসাব-নিকাশ। ছবি ৫০ এ ওরা <strong><em>shirt</em></strong> বা ৪ নং নোড থেকে যাত্রা শুরু করেছে। আমরা এখানে ছবি ৫২ এ ১ নং নোড থেকে শুরু করবো। তুমি ইচ্ছা করলে অন্য কোথাও থেকে শুরু করতে পারো। যাই হোক তাহলে শুরু করা যাক।</p><p>কিভাবে সময় (কখন আবিষ্কার করছি বা যাত্রা শেষ করছি তার সময়) হিসাব করবো সেটার নিয়ম বলে দিই। আমরা ১ নং নোড থেকে যাত্রা শুরু করছি, তাহলে ১ নং নোডের <strong><em>discovery time</em></strong> হচ্ছে ১ (মানে প্রথম সেকেন্ডেই [তুমি সময়ের যেকোন একক ব্যবহার করতে পারো] ১ নং নোড আবিষ্কার হয়েছে)। এর নিয়ম অনুযায়ী আমরা ১ নং নোডের সাথে যাদের সম্পর্ক আছে সেসব নোডে যাবো। মনে কর, ১ নং নোড থেকে গেলাম ২ নং নোডে (যদিও ৮ নং নোডেও যাওয়া যেত, ওইযে তোমার ইচ্ছা)। তাহলে ২ নং নোডও আবিষ্কার হয়ে গেলো। তাহলে ২ নং নোডের <strong><em>discovery time</em></strong> হচ্ছে ২। ২ নং নোড থেকে মনে কর গেলাম ৩ নং নোডে, তাহলে ৩ নং নোডের <strong><em>discovery time</em></strong> হচ্ছে ৩। এবার ৩ নং নোড থেকে গেলাম ৬ নং নোডে। তাহলে ৬ নং নোডের <strong><em>discovery time</em></strong> হচ্ছে ৪। এবার আমরা উপরের ছবিটি নতুন করে অঙ্কন করি।</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*-Misl60NuLpvQomt-83L2A.png" /></figure><p>ছবি ৫৩ এর (১) নং অংশে স্ল্যাশ চিহ্নের (/) বামপাশে আমরা <strong><em>discovery time</em></strong> উল্লেখ করেছি এবং ডানপাশটা <strong><em>finishing time</em></strong> এর জন্য ফাঁকা রেখে দিয়েছি।</p><p>আবার শুরু করা যাক, ৬ নং নোডে এসে কোন রাস্তা পাচ্ছিনা সামনের যাওয়ার। তাহলে এবার আমরাকে <strong><em>backtracking</em></strong> করে যেখান থেকে ৬ নং নোডে এসেছিলাম অর্থাৎ ৩ নং নোডে ফেরত যেতে হবে এবং সাথে সাথে ৬ নং নোডের কাজ শেষ হয়ে যাওয়ায়, এখানে <strong><em>finishing time</em></strong> হিসেবে ৫ লিখে দিতে হবে (ছবি ৫৩ এর (২) নং অংশ)।<br>৩ নং নোডেও এসে দেখা যাচ্ছে একই অবস্থা। কোন দিকে আগানো যাচ্ছেনা, তাহলে পেছনে সরে গিয়ে ২ নং নোডে যাবো এবং সাথে ৩ নং নোডের <strong><em>finishing time</em></strong> হিসেবে ৬ লিখে দিবো (সময় এক এক করে বাড়ছে আরকি!)। (ছবি ৫৩ এর (২) নং অংশ)</p><p>এবার ২ নং নোড থেকে ৮ নং নোডে যাওয়ার সুযোগ আছে দেখা যাচ্ছে। তাহলে যাই আমরা ৮ নং নোডে, এটা আবিষ্কার হয়ে গেলো। তাহলে ৮ নং নোডের <strong><em>discovery time</em></strong> হিসেবে ৭ লিখে দিয়ে আমরা দেখছি যে এখান থেকে আর কোন দিকে যাওয়া যাচ্ছেনা। তারমানে ৮ নং নোডেরও কাজ শেষ। তাহলে সাথে সাথে এর <strong><em>finishing time</em></strong> হিসেবে ৮ লিখে দেয়া যায়। এবার <strong><em>backtracking</em></strong> করে ২ নং নোডে এসেও একই অবস্থা, তাহলে ২ নং নোডের <strong><em>finishing time</em></strong> হবে ৯। ‘২’ থেকে ‘১’ এ এসে ১০ লিখা যায়। (চিত্র ৫৪ এর (১) নং অংশ)</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Hf5Pe-RL5dLvDD-jT3THtA.png" /></figure><p>আমাদের সময়ের এখন পর্যন্ত ১০ একক পর্যন্ত পৌঁছেছে। এবার যে সকল নোড এখনও ঘুরে দেখা হয়নি তাদের দিকে মনোযোগ দেয়া যেতে পারে। যেমন ৪ নং নোড। তাহলে ৪ নং নোড থেকে নতুন যাত্রা শুরু করলে এর <strong><em>discovery time</em></strong> হবে ১১। ‘৪’ থেকে ‘৫’ এ যাওয়া যায়, তাহলে এর ক্ষেত্রে <strong><em>discovery time</em></strong> হবে ১২। (ছবি ৫৪ এর (২) নং অংশ)</p><p>১২ নং নোড থেকে অন্য কোথাও যাওয়া যাচ্ছেনা অর্থাৎ এর কাজ শেষ। তাহলে এর <strong><em>finishing time</em></strong> হবে ১৩। এবার পেছনে ফিরে ‘৪’ এ এসে দেখা যাচ্ছে যে, এরও কাজ শেষ তাহলে ৪ নং নোডের <strong><em>finishing time</em></strong> হবে ১৪। (ছবি ৫৫ এর (১) নং অংশ)</p><p>একই নিয়ম মেনে ছবি ৫৫ এর (২) নং অংশে ৭ ও ৯ নং নোডেরও <strong><em>discovery time</em></strong> ও <strong><em>finishing time</em></strong> বসিয়ে দিয়েছি।</p><p>এবার আমরা সবগুলো নোডের <strong><em>finishing time</em></strong> গুলো দেখবো। যার <strong><em>finishing time</em></strong> যত বেশি সেই কাজ তত আগে করতে হবে। এখানে আমরা দেখতে পাচ্ছি যে, ৯ নং নোডের <strong><em>finishing time</em></strong> সবচেয়ে বেশি। তাহলে ৯ নং নোডকে সব আগে ঘুরে দেখতে হবে। তারপর? আচ্ছা সবার <strong><em>finishing time</em></strong> গুলো নিচে লিখে ফেলি।</p><p>নোড নম্বরের পাশে ব্র্যাকেটের মধ্যে <strong><em>finishing time</em></strong> দিয়ে লিখলে আমরা পাই,<br>৯(১৮) — ৭(১৬) — ৪(১৪) — ৫(১৩) — ১(১০) — ২ (৯) — ৮(৮) — ৩(৬) — ৬(৫)</p><p>এবার ছবি ৫০ এর সাথে তুলনা করলে আমরা পাই,<br> <strong><em>watch — socks — shirt — tie — undershorts — pants — shoes — belt — jacket</em></strong></p><p>উপরের ক্রম অনুযায়ী <strong><em>Professor Bumstead</em></strong> বিভিন্ন উপকরণ দিয়ে সাজুগুজু করলে কোন সমস্যা নাই। কিন্তু উনি যদি মোজা পরার আগে জুতা পরতেন বা শার্ট পরার আগে টাই পরতেন তাহলে ঝামেলা হতো।</p><p>এ ধরনের <strong><em>ordering</em></strong> বা <strong><em>sorting</em></strong> কে <strong><em>topological sort</em></strong> বলে।</p><p>এখন সময় এসেছে এর প্রোগ্রাম লিখে বিশ্লেষণ করে ফেলার। আমরা ইতিমধ্যেই <strong><em>DFS</em></strong> এর প্রোগ্রাম দেখেছি। যেহেতু <strong><em>topological sort</em></strong> এর মূল চিন্তা ভাবনা <strong><em>DFS</em></strong> এর ওপর প্রতিষ্ঠিত তাই আমরা এর কোডকে একটু এদিক ওদিক করলেই <strong><em>topological sort</em></strong> এর প্রোগ্রাম পেয়ে যাবো।</p><p>তাহলে শুরু করা যাক।</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/521/1*9BSV-zzaueQElIPSoielFQ.png" /></figure><p>এখানে শুধু ৬ নং লাইনটা নতুন, বাকি সবকিছু <strong><em>DFS</em></strong> এর কোডের অনুরূপ। ৭ নং লাইনে দুটো অ্যারে ও একটি ভ্যারিয়েবল ঘোষণা দেয়া হয়েছে আরকি। কোডের পরবর্তী অংশে এদের কাজ বোঝা যাবে।</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/482/1*ScsmBkb0gSO7BSwCXxnM8A.png" /></figure><p>উপরের অংশে (কোড ০০৮(খ)) শুধু ১৩ ও ২৩ নং লাইন নতুন। ১২ নং লাইনে যখন আমরা কোন নোডের মধ্যে যাত্রা শুরু করছি, সেটার <strong><em>starting time (discovery time)</em></strong> টা আমরা ১৩ নং লাইনে এসে লিখে দিচ্ছি। খেয়াল করে দেখো শেষে <strong>time++</strong> করা হয়েছে অর্থাৎ পরবর্তীর জন্য সময়ের মান এক বাড়িয়ে দেয়া হয়েছে। ২২ নং লাইনে যখন উপরোক্ত নোডের কাজ শেষ হয়ে যাচ্ছে তখন ২৩ নং লাইনে তার <strong><em>finishing time</em></strong> লিখে রাখা হচ্ছে।</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/476/1*mvUxCsKEVGAmcXpjqATTCA.png" /></figure><p>এই অংশে কোন পরিবর্তন নেই।</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/765/1*3EjK_DO7Ph020SGWY0UYHA.png" /></figure><p>এটি <strong><em>directed graph</em></strong> তাই আগের মতো <strong>somporko[v2][v1]=1</strong> লাইনটি আর নেই। ৪৭ নং লাইনে প্রিন্টের কাজ ছাড়া নতুন কিছু নেই।</p><p>লিওনার্দ অয়লার এর নামে একটি সংখ্যা আছে ক্যালকুলাসে, যাকে <strong><em>e</em></strong> দ্বারা প্রকাশ করা হয় এবং এর মান <strong><em>2.71828</em></strong> (প্রায়)।</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=10145d61ac6" width="1" height="1" alt=""><hr><p><a href="https://medium.com/%E0%A6%AA%E0%A7%8D%E0%A6%B0%E0%A7%8B%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AE%E0%A6%BF%E0%A6%82-%E0%A6%AA%E0%A6%BE%E0%A6%A4%E0%A6%BE/%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AB-%E0%A6%A5%E0%A6%BF%E0%A6%93%E0%A6%B0%E0%A6%BF-%E0%A6%AA%E0%A6%B0%E0%A7%8D%E0%A6%AC-%E0%A7%AD-10145d61ac6">গ্রাফ থিওরি (পর্ব ৭)</a> was originally published in <a href="https://medium.com/%E0%A6%AA%E0%A7%8D%E0%A6%B0%E0%A7%8B%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AE%E0%A6%BF%E0%A6%82-%E0%A6%AA%E0%A6%BE%E0%A6%A4%E0%A6%BE">প্রোগ্রামিং পাতা</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[গ্রাফ থিওরি (পর্ব ৫)]]></title>
            <link>https://medium.com/%E0%A6%AA%E0%A7%8D%E0%A6%B0%E0%A7%8B%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AE%E0%A6%BF%E0%A6%82-%E0%A6%AA%E0%A6%BE%E0%A6%A4%E0%A6%BE/%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AB-%E0%A6%A5%E0%A6%BF%E0%A6%93%E0%A6%B0%E0%A6%BF-%E0%A6%AA%E0%A6%B0%E0%A7%8D%E0%A6%AC-%E0%A7%AB-732f7b73749a?source=rss-550534651e5d------2</link>
            <guid isPermaLink="false">https://medium.com/p/732f7b73749a</guid>
            <category><![CDATA[bangla]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[graph-theory]]></category>
            <category><![CDATA[software-engineering]]></category>
            <dc:creator><![CDATA[Ahsan Shafiq Shawon]]></dc:creator>
            <pubDate>Wed, 16 Jan 2019 11:02:22 GMT</pubDate>
            <atom:updated>2019-01-17T09:04:05.330Z</atom:updated>
            <content:encoded><![CDATA[<p><strong>প্রোগ্রামিং — ১</strong></p><p><strong>গ্রাফের মধ্যে ঘুরাঘুরি</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*_gQ9wDGX3B4OwgMnlLFPZg.jpeg" /><figcaption>Photo by <a href="https://unsplash.com/photos/tmdIzj9n7Bg?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Mohit Kumar</a> on <a href="https://unsplash.com/@98mohitkumar?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Unsplash</a></figcaption></figure><p>আসো, কনরাড জিউস (<strong><em>Konrad Zuse</em></strong>) এর সাথে পরিচয় করিয়ে দিই তোমাদের। আধুনিক কম্পিউটার (<strong><em>prorgrammable computer</em></strong>) ও প্রথম হাই লেভেল প্রোগ্রামিং ভাষার (<strong><em>Plankalkul</em></strong>) “আব্বা” হচ্ছেন এই ভদ্রলোক। পেশায় একজন সিভিল ইঞ্জিনিয়ার জার্মানির এই ভদ্রলোক বিশ্বের প্রথম কম্পিউটার ব্যবসায়ীও ছিলেন। দেখা যাচ্ছে যে, অনেককিছুর প্রথম তিনি।</p><p>জিউস সাহেব উনার পিএইচডি পেপারে ‘গ্রাফে ঘুরে বেড়ানোর’ একটি পদ্ধতি নিয়ে আলোচনা করেন। কিন্তু উনার পেপার বাতিল করা হয়। পরবর্তীতে প্রায় ১৪ বছর পর একইসাথে এমআইটি এবং হার্ভাডে শিক্ষকতা করা এডওয়ার্ড মুর (<strong><em>Edward F. Moore</em></strong>), জিউসের ওই পদ্ধতিটি সফলভাবে কাজে লাগান। পদ্ধতিটির নাম হচ্ছে <strong><em>Breadth First Search</em></strong> (সংক্ষেপে <strong><em>BFS</em></strong>)।</p><p>মুর সাহেব গোলকধাঁধার (<strong><em>Maze</em></strong>) মধ্য দিয়ে সবচেয়ে ছোট রাস্তায় কিভাবে বের হয়ে আসা যায় সেটা বের করার জন্য <strong><em>BFS</em></strong> কে কাজে লাগান। গোলকধাঁধা সম্পর্কে একটা ধারণা নেয়ার জন্য নিচের ছবিটি খেয়াল করা যেতে পারে।</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/394/1*0JU3z1Lw3zwvRcJOJ0W7tA.png" /></figure><p>মুর বা জিউসের অনেক অনেক আগে চার্লস পিয়েরে ট্রিমক্স (<strong><em>Charles Pierre Tremaux</em></strong>) নামক একজন ফ্রেঞ্চ গণিতবিদ এই গোলকধাঁধা সমাধান করতে গিয়ে বা গোলকধাঁধার মধ্যে কিভাবে সবচেয়ে কম রাস্তায় ঘুরে বেড়ানো যায়, সেটার জন্য একটি পদ্ধতি আবিষ্কার করেন। এই পদ্ধতির নাম হচ্ছে <strong><em>Depth First Search</em></strong> (সংক্ষেপে <strong><em>DFS</em></strong>)।</p><p>বর্তমান সময়ে বুদ্ধি খাটিয়ে গ্রাফে ঘুরে বেড়ানোর জন্য এই দুটি (<strong><em>BFS</em></strong> ও <strong><em>DFS</em></strong>) পদ্ধতি ব্যাপকভাবে ব্যবহার করা হয়। আমরা এই পর্বে পদ্ধতি দুটো নিয়ে বিশদভাবে আলোচনা করবো। আলোচনার জন্য একটি গ্রাফ (<strong><em>L</em></strong>) উদাহরণ হিসেবে নিলাম,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/360/1*fSPi3xXpw4lLyxHyCKRDuQ.png" /></figure><p>প্রথমে <strong><em>BFS</em></strong> নিয়ে কথা বলবো।</p><p>প্রথম কথা হচ্ছে যে, আমরা গ্রাফের যেকোন নোড থেকে আমাদের যাত্রা শুরু করতে পারি। একদম ইচ্ছামত আরকি! আমরা সবগুলো উদাহরণে ১ নং নোড থেকে যাত্রা আরম্ভ করবো, তুমি ইচ্ছা করলে অন্য কোথাও থেকে শুরু করতে পারো।</p><p>দ্বিতীয় কথা হচ্ছে যে, যেখান থেকে যাত্রা শুরু করলাম তার সাথে কার কার এজ বা সম্পর্ক আছে তা খুঁজে বের করে সেখানে সেখানে ঘুরে আসতে হবে। উদাহরণ হিসেবে বলা যায়, ‘১’ থেকে যাত্রা শুরু করলাম। এরপর ১ নং নোডের সাথে ৩, ৪, ৫ নং নোডের এজ আছে, সেগুলো ঘুরে শেষ করলাম। তাহলে বলা যায়, ১ নং এর কাজ শেষ। নিচের ছবিটি খেয়াল করো,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/586/1*HUjWYcDDyNz9iEqcp66b4g.png" /></figure><p>এখানে কি কি করা হয়েছে সেটা বলা যাক।</p><p>যেহেতু ১ নং নোড থেকে যাত্রা শুরু করেছি তাই সেটা লিখে রাখলাম। তারপর ১ থেকে ৩, ৪, ৫ এ গেলাম তাই এদেরকেও লিখে রাখলাম। তুমি যদি প্রশ্ন করো যে, ‘১’ থেকে ‘৩’ এ প্রথমে না গিয়ে ‘৪’ এ বা ‘৫’ এ যাওয়া যাবে? অবশ্যই। তোমার ইচ্ছা। কারণ তুমি অন্যপথে গিয়ে দেখতে পারো, শেষে গিয়ে ফলাফল একই পাবা।<br>তারপর আমরা দেখতে পাচ্ছি যে, ‘১’ থেকে আর কোথাও যাওয়া যাবেনা মানে ১ নং ভালোমতো ঘুরাঘুরি করা হয়ে গেছে তাই এটাকে কালো করে দিয়েছি।</p><p>এবার তাহলে আমরা ৩ নং নোড থেকে যাত্রা শুরু করবো। কারণ ‘১’ এর পরে ‘৩’ আছে।</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/582/1*r9lFOcDc1B2Gwxf_GooS9g.png" /></figure><p>এখানে যা করা হয়েছে তা হল, ৩ নং থেকে যাত্রা শুরু করে ১ ও ২ নং নোডে যেতে পারি কিন্তু ১ নং নোড ইতিমধ্যেই ঘুরাঘুরি করা শেষ। তাই শুধু ২ নং নোড আমরা ঘুরে নিলাম এবং সেটাকে এখানে লিখে দিলাম। যেহেতু ৩ নং নোডের কাজ শেষ তাই এটাও কালো হয়ে গেলো।</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/249/1*KlzB8DiG7vtfvO_-rSmvRw.png" /></figure><p>অনুরূপভাবে ৪ নং থেকে ১, ২, ৫ এ যাওয়া গেলেও আমরা ওসব জায়গা ঘুরে ফেলেছি তাই ৪ নংও কালো হয়ে যাবে। একইভাবে ৫ ও ২ নং কালো হয়ে যাবে। অর্থাৎ গ্রাফে ঘুরাঘুরি শেষ। এটাই হচ্ছে <strong><em>BFS</em></strong> এর মোদ্দা কথা।</p><p>এবার আমরা <strong><em>L</em></strong> গ্রাফে <strong><em>DFS</em></strong> এর নিয়ম মেনে ঘুরাঘুরি করবো। তাহলে শুরু করা যাক।</p><p>প্রথম কথা হচ্ছে যে, এটার ক্ষেত্রেও আমরা যেকোন নোড থেকে শুরু করতে পারি।</p><p>দ্বিতীয় কথা হচ্ছে যে, ‘১’ থেকে যতগুলো নোডে যাওয়া যায় সবগুলোতে যাবোনা। উদাহরণস্বরূপ বলা যায়, ১ নং নোড থেকে যাত্রা শুরু করে হয়তো প্রথমে ‘৩’ এ আসলাম। এবার করবো কি, ৩ নং থেকে আবার কোথায় যাওয়া যায় সেটা দেখবো অর্থাৎ ভেতরে ঢুকতে থাকবো। আমরা <strong><em>BFS</em></strong> এর ক্ষেত্রে ১ নং থেকে তার আশেপাশে মানে প্রস্থ (<strong><em>breadth</em></strong>) বরাবর যতগুলো নোডে যাওয়া যায় সেভাবে ঘুরাঘুরি শেষ করেছিলাম কিন্তু <strong><em>DFS</em></strong> এর ক্ষেত্রে আমরা ‘১’ থেকে ‘৩’ এ, ‘৩’ থেকে ‘২’ এ, আবার ‘২’ থেকে ‘৪’ এ; এভাবে ভেতরে (<strong><em>deep</em></strong> এ) ঢুকতে থাকবো। আশা করছি নামকরণের সার্থকতা বোঝা গেছে।</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/618/1*SaCl47fSIBk6iZ3f03k37A.png" /></figure><p>এখানে কি করেছি? ১ নং নোড থেকে যাত্রা আরম্ভ করে ৩ নং এ এসেছি। কিন্তু ১ নং কে কালো করিনি কারণ ‘১’ এর কাজ এখনও শেষ হয়নি।</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/618/1*2M4Cc3BqgARfyATNC2BjBQ.png" /></figure><p>এখানে ৩ নং থেকে যাত্রা আরম্ভ করে ‘২’ এ এসেছি। আবারও ‘৩’ এর কাজ শেষ না হওয়ায় একে কালো করা হয়নি।</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/618/1*cdcgLV4ZMs-P_BQ-6Twe9w.png" /></figure><p>এখানে ২ নং থেকে যাত্রা আরম্ভ করে ‘৪’ এ এসেছি। ‘৪’ এর কাজ শেষ হয়নি।</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/618/1*AIDzx8XTwuvQmz2dzBE20g.png" /></figure><p>অবশেষে আমরা ৪ নং নোডে পৌঁছে গেলাম। এখানে থেকে ‘১’ ও ‘৫’ এ যাওয়ার রাস্তা আছে। কিন্তু ১ নং নোড না গিয়ে ‘৫’ এ যাওয়া ভালো কারণ ১ নং নোড থেকে যাত্রা আরম্ভ করে এসেছি মানে সেটা খানিকটা ঘুরা হয়েছে কিন্তু ‘৫’ এ কখনো যাইনি। তাই আমরা ‘৪’ থেকে ‘৫’ এ গিয়ে দেখি আর কোথাও যাওয়া যাচ্ছেনা। তাই ৫ নং কে কালো করে দিয়ে আমরা পেছনে আসা (<strong><em>backtracking</em></strong>, এটা নিয়ে পরে কথা হবে) শুরু করলাম। ৪ নং এ এসে দেখা যাচ্ছে নতুন কোন জায়গা নেই যাওয়ার তাহলে ৪ নংও কালো হয়ে যাবে।</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/249/1*g_Sp2ovb256Cg5abZekSAQ.png" /></figure><p>অনুরূপভাবে ৪ নং থেকে পেছনে এসে পৌঁছলাম ২ নং নোডে। এখান থেকেও নতুন কোন জায়গা নেই যাওয়ার, তাই এটাও কালো হয়ে যাবে। একইভাবে ৩ ও ১ নং নোড কালো হয়ে গিয়ে গ্রাফে ঘুরাঘুরি শেষ। এটাই হচ্ছে <strong><em>DFS</em></strong> এর মোদ্দা কথা।</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/249/1*_d3RbLhoH77u56G8uCv5-Q.png" /></figure><p>এবার আমরা ৪০ ও ৪৬ নং ছবি তুলনা করলে দেখবো, দুই পদ্ধতিতে দুইটি আলাদা রাস্তা ব্যবহৃত হয়েছে।</p><p><strong><em>BFS</em></strong> এর ক্ষেত্রে ১ — ৩ — ৪ — ৫ — ২<br><strong><em>DFS</em></strong> এর ক্ষেত্রে ১ — ৩ — ২ — ৪ — ৫</p><p>আশা করি সবাই বুঝেছো। যদি কারও এখনও অস্পষ্টতা থাকে সেজন্য আমি আরেকটা উদাহরণ দেখাচ্ছি, তবে এবার একটু কম কথা খরচ করে দ্রুত ব্যাখ্যা করে ফেলবো।</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/425/1*M7yf1v5F44p2jNPSXbctFw.png" /></figure><p>প্রথমে <strong><em>BFS</em></strong> অনুসারে, ১ নং থেকে শুরু করে ২, ৪, ৫ এ যাওয়া যায়। সিকোয়েন্স দাঁড়ালো, ১ — ২ — ৪ — ৫<br>এবার তাহলে ২ নং থেকে শুরু করে যাওয়া যায় ৭, ৬, ৩ এ। চূড়ান্ত সিকোয়েন্স,</p><p>১ — ২ — ৪ — ৫ — ৭ — ৬ — ৩</p><p>এবার <strong><em>DFS</em></strong> অনুসারে করে, ১ নং থেকে শুরু করে গেলাম ‘২’ এ। এবার ‘২’ থেকে ‘৩’ এ গেলাম। আমি আগেও বলেছি এবং এখনও বলছি যে, তুমি অন্য যেকোন রাস্তা পছন্দ করতে পারো। তো যা বলছিলাম, ‘৩’ এ গিয়ে দেখলাম যাওয়ার আর জায়গা নাই। তখন পেছনে আসা শুরু করলাম।</p><p>এখন পর্যন্ত সিকোয়েন্স দাঁড়ালো, ১ — ২ — ৩</p><p>পিছনে এসে পৌঁছলাম ২ নং এ। এখান থেকে গেলাম ‘৬’ এ। ৬ নং থেকে আর কোথাও যাওয়ার উপায় নাই, তাই আবার <strong><em>backtracking</em></strong>। আসলাম আবার ‘২’ এ। এবার ‘২’ থেকে ‘৭’ গিয়ে আবারও একই কাহিনী। ফেরত আসলাম ‘২’ এ। এখন পর্যন্ত সিকোয়েন্স, ১ — ২ — ৩ — ৬ — ৭</p><p>এখন দেখা যাচ্ছে যে, ‘২’ থেকে আর কোথাও যাওয়া যাচ্ছেনা। তাই আমরা ‘২’ থেকে পেছনে আসবো অর্থাৎ ‘১’ এ। এবার ‘১’ থেকে ৪ নং এ গিয়ে দেখছি ওখান কোথাও যাওয়া যাচ্ছেনা তাই পেছনে ফিরে ‘১’ এ আসলাম। এবার ‘১’ থেকে ‘৫’ এ গিয়ে একই অবস্থা। আবার আসলাম ‘১’ এ। এবার ‘১’ থেকেও কোথাও যাওয়া যাচ্ছেনা, সব জায়গা ঘুরাঘুরি করা শেষ। সিকোয়েন্স দাঁড়ালো শেষে, ১ — ২ — ৩ — ৬ — ৭ — ৪ — ৫</p><p>অনেক হলো ঘুরাঘুরি। এবার আমরা চেষ্টা করবো এই <strong><em>BFS</em></strong> ও <strong><em>DFS</em></strong> কিভাবে কম্পিউটার বাবাজিকে বুঝানো যায়, ওই কোড ফোড আরকি। তো হয়ে যাক প্রোগ্রামিং।</p><p>প্রথমে <strong><em>DFS</em></strong> এর কোড দেখবো,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/516/1*xEFrgwHNQe-UWR6VOe-MWQ.png" /></figure><p>উপরের কোডে <strong><em>adjacency matrices</em></strong> এর মাধ্যমে একটি গ্রাফ নেয়া হয়েছে। ৪১ নং লাইনে <strong>dfs()</strong> নামের একটি ফাংশন ডিক্লেয়ার করা হয়েছে। এর ব্যাখ্যা নিচে দেয়া হল,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/496/1*29PISU06hg1R35DGJHwozw.png" /></figure><p>২১ নং লাইন — এখানে <strong>dfs()</strong> ফাংশন শুরু হচ্ছে। আমাদের গ্রাফ নেয়া হয়ে গেছে (৩৩-৪০ নং লাইন), এখন আমাদের কি করা উচিৎ? আমরা একটা কৌশল অবলম্বন করবো। সেটা হচ্ছে, যে নোড আমরা এখনও ঘুরিনি সেটাকে সাদা রঙ এ, যে নোডের কাজ চলছে অর্থাৎ ঘুরাঘুরি চলছে তাকে ছাই (<strong><em>gray</em></strong>) রঙ এ এবং যে নোডের কাজ শেষ তাকে কালো রঙ এ রাঙিয়ে দিবো। তাহলে হিসাব রাখতে সুবিধা হবে যে কোন্ কোন্ নোড ঘোরা হয়েছে আর কোনটা হয়নি।<br>২, ৩, ৪ নং লাইন — এই তিন লাইনে আমরা বলে দিয়েছি যে ‘১’ সংখ্যাটি দিয়ে সাদা বুঝানো হবে এবং ‘২’ ও ‘৩’ দিয়ে যথাক্রমে ছাই ও কালো বুঝানো হবে।<br>৫ নং লাইন — কিছু ডিক্লেয়ারেশন করা হয়েছে, এগুলোর কাজ পরে বুঝা যাবে।<br>২৩, ২৪ নং লাইন — যতগুলো নোড আছে সবগুলোকে সাদা রঙে রাঙানো হল, কেননা যাত্রা শুরু করার আগে তো আমরা কাউকেই ঘুরে দেখিনি।<br>২৫-২৭ নং লাইন — এবার আমরা খুঁজে বের করবো কোন্ নোডটি সাদা, দিয়ে সেখান থেকে যাত্রা আরম্ভ করবো। তোমাদের মনে হতে পারে এখনি সবগুলোকে সাদা করলাম, তাহলে খোঁজার কি আছে? এরপর আমরা আরও কিছু কাজ করবো যাতে করে কিছু নোড ধীরে ধীরে অন্য রঙের হবে এবং সাদা নোডের সংখ্যা কমতে থাকবে।<br>২৮ নং লাইন — এখানে একটি নতুন ফাংশন ডিক্লেয়ার করা হয়েছে। এই ফাংশন দিয়ে আমরা একটি নির্দিষ্ট নোডকে ঘুরে দেখবো।<br>৮ নং লাইন — এখানে নতুন ফাংশনটির (<strong>dfsVisit()</strong>) কাজ দেখানো আছে।<br>১০ নং লাইন — খেয়াল করে দেখো এই ফাংশনটি প্যারামিটার হিসেবে একটি সংখ্যা নিচ্ছে। এই সংখ্যাটি আসছে ২৮ নং লাইন থেকে। সংখ্যাটি কি সেটা ২৭ নং লাইনের দিকে তাকালে বোঝা যাবে। যে নোডের রঙ সাদা সেই সংখ্যাটি ২৮ নং লাইনে যাচ্ছে এবং সেখান থেকে ৮ নং লাইনে প্যারামিটার হিসেবে আসছে। সেই সংখ্যাটিই আবার ১০ নং লাইনে ছাই রঙের হচ্ছে। তারমানে ওই নোডের কাজ শুরু হলো।<br>১৩ নং লাইন — আমরা এখন গ্রাফের মধ্যে খুঁজবো ১০ নং লাইনের নোডের সাথে কার কার এজ আছে।<br>১৪-১৫ নং লাইন — যাদের সম্পর্ক আছে তাদের রঙ কি সাদা? যদি হয় তাহলে তাদের মধ্যে ঘুরবো।<br>১৮ নং লাইন — ঘোরাঘুরি শেষ।<br>১৯ নং লাইন — তাহলে তাকে কালো করে দাও।</p><p><strong><em>BFS</em></strong> এর কোড নিয়ে সামনের পর্বে আলোচনা করবো, নাহলে এই পর্ব অনেক লম্বা হয়ে যাবে।</p><p>অয়লার ভাইয়াকে নিয়ে আজকে যে তথ্যটি দিবো সেটার সাথে বার্নুলি পরিবারের সম্পর্ক আছে। তাই বার্নুলি পরিবার নিয়ে দুটো কথা না বললেই নয়। বার্নুলি পরিবারের বসবাস সুইজারল্যান্ডের বাসেল শহরে। রজার ফেদেরার ভাইয়াও কিন্তু এই শহরের মানুষ। বার্নুলি পরিবার অবশ্য অনেক পুরনো। আমি মোটামুটি ৪০০ বছর আগের কথা বলছি। এই পরিবারে কমপক্ষে ৮ জন বিখ্যাত গণিতবিদ জন্মগ্রহণ করেছেন। উমুক বার্নুলি, তমুক বার্নুলি ইত্যাদি। মাথা খারাপ হয়ে যাবে ইনাদের নাম মনে রাখতে গিয়ে।</p><p>এই পরিবারের একজন বিখ্যাত সন্তান ছিলেন জোহান বার্নুলি (<strong><em>Johann Bernoulli</em></strong>), ইনি আবার কুরি পরিবারের জামাই ছিলেন। জ্বী ভাই, সেই বিখ্যাত কুরি পরিবার। এই ভদ্রলোক আবার অয়লারের বাবার বন্ধুও ছিলেন। প্রতি শনিবার তিনি অয়লারকে প্রাইভেট পড়াতেন। অয়লারের বাপ চেয়েছিল ছেলে তার ধর্মযাজক (খ্রিস্টান ধর্মের ইমাম আরকি!) হোক। কিন্তু বার্নুলি সাহেব উনাকে অনেক বুঝান যে, ছেলে আপনার মস্ত বড় গণিতবিদ হবে। তাই আমরা অয়লার সাহেবকে পেয়েছি। নইলে কি যে হতো! শেষ করতে করতে আরেকটা কথা, অয়লার মাত্র ১৭ বছর বয়সে মাস্টার্স পাশ করেছিলেন।</p><p><a href="https://medium.com/%E0%A6%AA%E0%A7%8D%E0%A6%B0%E0%A7%8B%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AE%E0%A6%BF%E0%A6%82-%E0%A6%AA%E0%A6%BE%E0%A6%A4%E0%A6%BE/%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AB-%E0%A6%A5%E0%A6%BF%E0%A6%93%E0%A6%B0%E0%A6%BF-%E0%A6%AA%E0%A6%B0%E0%A7%8D%E0%A6%AC-%E0%A7%AC-62a986fbe20b"><strong>গ্রাফ থিওরি (পর্ব ৬) পড়তে ক্লিক করুন।</strong></a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=732f7b73749a" width="1" height="1" alt=""><hr><p><a href="https://medium.com/%E0%A6%AA%E0%A7%8D%E0%A6%B0%E0%A7%8B%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AE%E0%A6%BF%E0%A6%82-%E0%A6%AA%E0%A6%BE%E0%A6%A4%E0%A6%BE/%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AB-%E0%A6%A5%E0%A6%BF%E0%A6%93%E0%A6%B0%E0%A6%BF-%E0%A6%AA%E0%A6%B0%E0%A7%8D%E0%A6%AC-%E0%A7%AB-732f7b73749a">গ্রাফ থিওরি (পর্ব ৫)</a> was originally published in <a href="https://medium.com/%E0%A6%AA%E0%A7%8D%E0%A6%B0%E0%A7%8B%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AE%E0%A6%BF%E0%A6%82-%E0%A6%AA%E0%A6%BE%E0%A6%A4%E0%A6%BE">প্রোগ্রামিং পাতা</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[গ্রাফ থিওরি (পর্ব ৬)]]></title>
            <link>https://medium.com/%E0%A6%AA%E0%A7%8D%E0%A6%B0%E0%A7%8B%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AE%E0%A6%BF%E0%A6%82-%E0%A6%AA%E0%A6%BE%E0%A6%A4%E0%A6%BE/%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AB-%E0%A6%A5%E0%A6%BF%E0%A6%93%E0%A6%B0%E0%A6%BF-%E0%A6%AA%E0%A6%B0%E0%A7%8D%E0%A6%AC-%E0%A7%AC-62a986fbe20b?source=rss-550534651e5d------2</link>
            <guid isPermaLink="false">https://medium.com/p/62a986fbe20b</guid>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[graph-theory]]></category>
            <category><![CDATA[bangla]]></category>
            <category><![CDATA[software-engineering]]></category>
            <dc:creator><![CDATA[Ahsan Shafiq Shawon]]></dc:creator>
            <pubDate>Wed, 16 Jan 2019 11:01:57 GMT</pubDate>
            <atom:updated>2019-01-17T09:08:03.658Z</atom:updated>
            <content:encoded><![CDATA[<p><strong>প্রোগ্রামিং — ১</strong></p><p><strong>গ্রাফের মধ্যে ঘুরাঘুরি (চলবে)</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*O3fDiy_86uvPcoAfMIbgNQ.jpeg" /><figcaption>Photo by <a href="https://unsplash.com/photos/2xEQDxB0ss4?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Dlanor S</a> on <a href="https://unsplash.com/search/photos/programming?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Unsplash</a></figcaption></figure><p>এখন আমরা <a href="https://medium.com/%E0%A6%AA%E0%A7%8D%E0%A6%B0%E0%A7%8B%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AE%E0%A6%BF%E0%A6%82-%E0%A6%AA%E0%A6%BE%E0%A6%A4%E0%A6%BE/%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AB-%E0%A6%A5%E0%A6%BF%E0%A6%93%E0%A6%B0%E0%A6%BF-%E0%A6%AA%E0%A6%B0%E0%A7%8D%E0%A6%AC-%E0%A7%AB-732f7b73749a"><strong>গত পর্বের</strong></a> বাকি পড়াটুকু শেষ করে ফেলবো। <strong><em>BFS</em></strong> কিভাবে কাজ করে সেটা আমরা গত পর্বে দেখে এসেছি। প্রথমে <strong><em>BFS</em></strong> এর কোড দেখে নিয়ে পরে ব্যাখ্যায় যাচ্ছি।</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/425/1*M7yf1v5F44p2jNPSXbctFw.png" /></figure><p>এখানে উল্লেখ্য যে, উপরের গ্রাফকে ইনপুট হিসেবে নিচের কোডে ব্যবহার করা হয়েছে।</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/533/1*x1o5LND30b9jHA4x76badg.png" /></figure><p>কোড ০০৬(ক) অংশে আমরা আগের মতোই গ্রাফকে <strong><em>adjacency matrices</em></strong> এর মাধ্যমে স্টোর করেছি।</p><p>লাইন ৫৭ — এখানে একটি ফাংশন ডিক্লেয়ার করা হয়েছে, এই ফাংশনের মধ্যেই আমরা <strong><em>BFS</em></strong> এর যাবতীয় কাজ করবো।</p><p>লাইন ৫৮ — <strong><em>BFS</em></strong> কিভাবে কাজ করে সেটা যখন ব্যাখ্যা করা হয়েছিল গত পর্বে, সেখানে আমরা দেখেছিলাম যেকোন একটি নির্দিষ্ট নোড থেকে যাত্রা আরম্ভ করা যায় এবং সেখান থেকে তার সাথে যাদের এজ আছে সেখানে সেখানে যাওয়া যায়। ধরি, আমি ১ নং নোড থেকে ২ নং নোডে গেলাম। তাহলে কার অবস্থান আগে? ১ নং নোডের। একে আমরা <strong><em>parent node</em></strong> বলবো। আর যেখানে যাচ্ছি (২ নং নোড) তাকে <strong><em>child node</em></strong> বলবো। আমরা ফাংশনের মধ্যে বের করে ফেলবো কোন্ নোড কোন্ নোডের <strong><em>parent</em></strong> বা <strong><em>child</em></strong>। এই লাইনে সেটাই প্রকাশ করা হয়েছে।</p><p>লাইন ৫৯ — ছবি ৪৭ এর গ্রাফে ১ নং নোড থেকে ৬ নং নোডের দূরত্ব দুটি এজ। যেহেতু এটা <strong><em>unweighted graph</em></strong> তাই প্রতিটি এজের <strong><em>value</em></strong> ধরা হয়েছে ১। এখন প্রশ্ন হচ্ছে যে, <strong><em>unweighted graph</em></strong> কি?</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/525/1*L2IDNtAhSWtkxVjOxzn-ZA.png" /></figure><p>ছবি ৪৮ এ একটি <strong><em>weighted graph</em></strong> দেখানো হয়েছে। কোন গ্রাফের প্রতিটি এজের সাথে যদি একটি করে মান দেয়া থাকে তবে তাকে আমরা <strong><em>weighted graph</em></strong> বলবো। এই মান অনেককিছুই প্রকাশ করতে পারে, যেমন উপরের গ্রাফে এক শহর (শহরকে এখানে নোড হিসেবে দেখানো হয়েছে) থেকে অন্য শহরের (অন্য নোডের) দূরত্ব বুঝানো হয়েছে এজগুলোর মান দিয়ে। আবার অন্য কোন গ্রাফে দেখা যাচ্ছে এজগুলোর মান দিয়ে এক শহর থেকে অন্য শহরে যেতে কত সময় লাগে সেটাও বুঝাতে পারে। এভাবে অনেককিছুই প্রকাশ করা যেতে পারে এইসকল মান দিয়ে।</p><p>যাই হোক, আমরা যে গ্রাফকে ইনপুট হিসেবে নিয়েছি সেটা <strong><em>unweighted graph</em></strong>। কেননা এর এজগুলোতে কোন মান দেয়া নেই। <strong><em>unweighted graph</em></strong> এর ক্ষেত্রে এজগুলোর মান একই (এক্ষেত্রে আমরা ‘১’ ধরেছি) ধরে নেয়া হয়। তাহলে ৫৯ নং লাইনে <strong>durotto[6]</strong> এর মান হবে ২।</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/738/1*aU1WnvagSeFqzjaCbVW5sw.png" /></figure><p>কোড ০০৬(খ) এ আমরা <strong><em>DFS</em></strong> এর মত কিছু প্রয়োজনীয় জিনিসপত্র নিয়ে রেখেছি।</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/656/1*XFbQgB9xS2jHgwJkfOA0lQ.png" /></figure><p>৮ নং লাইন — প্যারামিটার হিসেবে যে নোড থেকে শুরু করতে চাই সেটা নিয়ে নিবো।</p><p>১০-১৫ নং লাইন — <strong><em>DFS</em></strong> এর মত প্রথমে সব নোডগুলোকে সাদা রঙে রাঙিয়ে নিলাম। তবে এখানে আরও কিছু কাজ করা হয়েছে, সবগুলো নোডের দূরত্ব (কোথা থেকে দূরত্ব? অবশ্যই যে নোড থেকে শুরু করবো সেখান থেকে।) প্রথমে খুবই ছোট সংখ্যা ( <strong>INT_MIN</strong>) ধরে নিলাম। <strong>INT_MIN</strong> নিয়ে পরে সুযোগ পেলে কথা বলবো, তবে আপাতত জেনে রাখো এটা দিয়ে খুবই ছোট সংখ্যা বোঝায়। ১৪ নং লাইনে সবগুলো নোডের <strong><em>parent</em></strong> ঋণাত্মক ধরা হয়েছে। এগুলো আমরা পরে আপডেট করবো। এখন শুধু উল্টাপাল্টা কিছু ধরে রাখলাম।</p><p>১৬ নং লাইন — যে নোড থেকে শুরু করবো সেটার দূরত্ব অবশ্যই শূন্য, কেননা দূরত্ব আমরা মাপছি শুরুর নোড থেকেই। তাহলে নিজের সাথেই দূরত্ব শূন্যই হবে।</p><p>১৭ নং লাইন — শুরুর নোডের কোন <strong><em>parent</em></strong> নাই, সেখান থেকেই তো পথ চলা শুরু। তাই এখানে উল্টাপাল্টা মান দিয়ে দেয়া হয়েছে।</p><p>১৯-৪৩ নং লাইনের কাজকর্ম বোঝার জন্য আমাদেরকে প্রথমে আরেকটি <strong><em>standard template library (STL)</em></strong> সম্পর্কে জেনে নিতে হবে, যার নাম হচ্ছে <strong><em>queue</em></strong>। তাহলে নিচের কোডটি খেয়াল করি,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/447/1*YQclE1FnQOEWA_S4Vyof7w.png" /></figure><p>৫ নং লাইন — <strong>queue</strong> ডিক্লেয়ার করার পদ্ধতি। এখানে ইন্টিজার টাইপের ‘লাইন’ নামের <strong>queue</strong> ডিক্লেয়ার করা হয়েছে।</p><p>৬-৯ নং লাইন — <strong>queue</strong> মানে লাইন। আমরা যখন কোন টিকিট কাউন্টারের সামনে লাইন হয়ে দাঁড়াই তখন যে মানুষটি সব প্রথমে লাইনে দাঁড়িয়েছিলেন তিনি প্রথমে টিকিট পেয়ে লাইন থেকে বের হয়ে যান। এই <strong><em>STL</em></strong> এর ক্ষেত্রেও তাই ঘটবে। অর্থাৎ ডিক্লেয়ার করার সময় <strong>queue</strong> খালি থাকবে যেমনটা সবপ্রথমে লাইন থাকেনা, ধীরে ধীরে মানুষ এলে লাইন তৈরি হয়।</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/883/1*Pn3ePwCDfd6xU6HPp_zTJA.png" /></figure><p>১০ নং লাইন — <strong>line.empty() </strong>দিয়ে <strong>queue</strong> টি খালি কিনা তা দেখা হয়। এই লাইনে আমরা একটি ‘হোয়াইল লুপ’ ব্যবহার করেছি। যতক্ষণ না <strong>queue</strong> টি খালি হবে, ততক্ষণ লুপটি চলবে। <strong>line.empty() </strong>এর সামনে ‘!’ (চিহ্ন দিয়ে ‘না’ বা ঋণাত্মক কিছু বুঝানো হয়।) চিহ্ন দিয়ে বুঝানো হয়েছে যে, <strong>queue</strong> টি খালি না।</p><p>১২ নং লাইন — <strong>line.front()</strong> দিয়ে <strong>queue</strong> এর প্রথম উপাদানটিকে নির্দেশ করা হয়। এই লাইনে আমরা প্রথম উপাদানটি একটি চলক (<strong><em>variable</em></strong>) এর মধ্যে রাখছি এবং পরে তা প্রিন্ট করছি।</p><p>১৪ নং লাইন — <strong>line.pop()</strong> দিয়ে <strong>queue</strong> এর প্রথম উপাদানটিকে মুছে (<strong><em>delete</em></strong>) দেয়া হয়। তাহলে ছবি ৪৯ এর ক্ষেত্রে যদি আমরা একবার <strong>pop()</strong>ফাংশনটি ব্যবহার করি তাহলে <strong>queue</strong> থেকে ‘৫’ মুছে গিয়ে ‘৯’ প্রথম উপাদান হিসেবে জায়গা করে নিবে, যেমনটা মানুষের লাইনে হয়। এই কারণে এই <strong><em>STL</em></strong> কে <strong><em>FIFO (First In First Out)</em></strong> বলা হয়। যে প্রথমে ঢুকবে, সে প্রথমেই বের হয়ে যাবে।</p><p>আশা করছি <strong><em>queue</em></strong> সম্পর্কে মোটামুটি ধারণা তৈরি হয়েছে তোমাদের। এবার আমরা তাহলে কোড ০০৬(গ) এর ১৯-৪৩ নং লাইনের দিকে মনোযোগ দিতে পারি।</p><p>১৯ নং লাইন — <strong>q</strong> নামের একটি ইন্টিজার টাইপের <strong>queue</strong> ডিক্লেয়ার করা হয়েছে।</p><p>২০ নং লাইন — যে নোড থেকে আমরা গ্রাফে চলা শুরু করবো সেই নোডকে (<strong>startingNode</strong>) <strong>queue</strong> এর মধ্যে ঢুকিয়ে দিলাম, তাহলে ১৯ নং লাইনের ফাঁকা <strong>queue</strong> এখন আর ফাঁকা থাকলোনা, এর মধ্যে এখন উপাদান সংখ্যা একটি।</p><p>২১ নং লাইন — এখানে একটি ‘হোয়াইল লুপ’ ব্যবহার করা হয়েছে, যার শর্ত হচ্ছে যতক্ষণ <strong>queue</strong> টি ফাঁকা না হবে ততক্ষণ এটি কাজ করতে থাকবে। যেমনি <strong>queue</strong> টি ফাঁকা হয়ে যাবে ‘হোয়াইল লুপ’ এর কাজ শেষ হয়ে যাবে।</p><p>২৩-২৪ নং লাইন — <strong>queue</strong> এর প্রথম উপাদানটিকে গ্রহণ করার বন্দোবস্ত করা হয়েছে।</p><p>২৫ নং লাইন — প্রথম উপাদানটিকে বিদায় করে দেয়া হল। এখন কিন্তু আমাদের <strong>queue</strong> ফাঁকা হয়ে গেলো, কারণ ওই একটাই উপাদান ছিল আরকি। তাহলে কি এখনি ‘হোয়াইল লুপ’ কাজ করা বন্ধ করে দিবে? মোটেও না। লুপের শেষে গিয়ে কাজ করা বন্ধ করবে, যদি না এর মধ্যে আবার <strong>queue</strong> এ উপাদান ঢোকে।</p><p>২৬ নং লাইন — যেহেতু আমরা এবার ওই বিদায় করে দেয়া উপাদানের কাজ শুরু করবো, তাই একে সাদা থেকে ছাই রঙা করে দেয়া হল। পরের লাইনে একে প্রিন্ট করে দিলাম।</p><p>২৯-৪০ নং লাইন — এই লাইনগুলোর প্রধান কাজ হচ্ছে, যাকে নিয়ে কাজ শুরু হয়েছে তার সাথে কার কার এজ আছে সেটা বের করা। বের হলে, সেই নোডের রঙ সাদা আছে কিনা সেটা দেখা। যদি থাকে, তাহলে তাদের মধ্যে হিসাব করা হবে। ৩৫-৩৭ নং লাইনের কথা পরে বলছি।</p><p>৪১ নং লাইন — আমরা যেহেতু <strong><em>BFS</em></strong> পড়ছি, এক্ষেত্রে যে নোড দিয়ে শুরু করা হয় তার সবগুলোর প্রতিবেশী নোডেই ঘুরে আসা হয়। অর্থাৎ এই নোডের কাজ একেবারেই শেষ হয়ে যায়। তাই একে কালো করে দেয়া হয়েছে।</p><p>৩৫ নং লাইন — এক্ষেত্রে <strong><em>x</em></strong> হচ্ছে শুরুর নোড। এই <strong><em>x </em></strong>এর সাথে যে যে <strong><em>i</em></strong> এর সম্পর্ক আছে তারা <strong><em>x </em></strong>থেকেই বের হয়েছে। তাহলে <strong><em>x </em></strong>হচ্ছে <strong><em>parent</em></strong> এবং <strong><em>i</em></strong> গুলো হচ্ছে <strong><em>child</em></strong>।</p><p>৩৬ নং লাইন — শুরুর নোডটিকে ২০ নং লাইনে <strong>queue</strong> এর মধ্যে ঢুকিয়ে দিয়ে ওকে পরবর্তীতে <strong><em>x</em></strong> চলকের মধ্যে রেখে দিয়ে খুঁজে দেখলাম কার কার সাথে <strong><em>x </em></strong>এর সম্পর্ক আছে। এই লাইনে ওদেরকে (<strong><em>i</em></strong>) নতুন করে <strong><em>x</em></strong> এর মধ্যে ঢুকিয়ে নেয়া হল, এবার এরা আবার শুরুর নোড হিসেবে কাজ করবে।</p><p>৩৭ নং লাইন — <strong><em>parent</em></strong> তো আগে থাকে, তাইনা? তাহলে <strong><em>parent</em></strong> এর দূরত্বের সাথে ‘১’ যোগ করলে বাচ্চাকাচ্চার দূরত্ব পাওয়া যাবে, কেননা <strong><em>child</em></strong> পরে থাকে।</p><p>তাহলে আমাদের <strong><em>BFS</em></strong> ও পড়া শেষ হলো।</p><p>এবার তাহলে জনাব অয়লার সম্পর্কে আরেকটি তথ্য জেনে নেয়া যাক। অতিরিক্ত গবেষণার ও লেখালেখির কারণে বেশ অল্প বয়সেই অয়লার উনার ডানচোখের দৃষ্টিশক্তি হারিয়ে ফেলেন। কাজের চাপ অয়লারের জীবনে সবসময়ই ছিল। ৫৯ বছর বয়সে অয়লার তাঁর বাকি ভালো চোখটাও হারিয়ে ফেলে পুরো অন্ধ হয়ে যান।</p><p><a href="https://medium.com/%E0%A6%AA%E0%A7%8D%E0%A6%B0%E0%A7%8B%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AE%E0%A6%BF%E0%A6%82-%E0%A6%AA%E0%A6%BE%E0%A6%A4%E0%A6%BE/%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AB-%E0%A6%A5%E0%A6%BF%E0%A6%93%E0%A6%B0%E0%A6%BF-%E0%A6%AA%E0%A6%B0%E0%A7%8D%E0%A6%AC-%E0%A7%AD-10145d61ac6"><strong>গ্রাফ থিওরি (পর্ব ৭) পড়তে ক্লিক করুন।</strong></a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=62a986fbe20b" width="1" height="1" alt=""><hr><p><a href="https://medium.com/%E0%A6%AA%E0%A7%8D%E0%A6%B0%E0%A7%8B%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AE%E0%A6%BF%E0%A6%82-%E0%A6%AA%E0%A6%BE%E0%A6%A4%E0%A6%BE/%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AB-%E0%A6%A5%E0%A6%BF%E0%A6%93%E0%A6%B0%E0%A6%BF-%E0%A6%AA%E0%A6%B0%E0%A7%8D%E0%A6%AC-%E0%A7%AC-62a986fbe20b">গ্রাফ থিওরি (পর্ব ৬)</a> was originally published in <a href="https://medium.com/%E0%A6%AA%E0%A7%8D%E0%A6%B0%E0%A7%8B%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AE%E0%A6%BF%E0%A6%82-%E0%A6%AA%E0%A6%BE%E0%A6%A4%E0%A6%BE">প্রোগ্রামিং পাতা</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[গ্রাফ থিওরি (পর্ব ৪)]]></title>
            <link>https://medium.com/%E0%A6%AA%E0%A7%8D%E0%A6%B0%E0%A7%8B%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AE%E0%A6%BF%E0%A6%82-%E0%A6%AA%E0%A6%BE%E0%A6%A4%E0%A6%BE/%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AB-%E0%A6%A5%E0%A6%BF%E0%A6%93%E0%A6%B0%E0%A6%BF-%E0%A6%AA%E0%A6%B0%E0%A7%8D%E0%A6%AC-%E0%A7%AA-3fff7c4e952e?source=rss-550534651e5d------2</link>
            <guid isPermaLink="false">https://medium.com/p/3fff7c4e952e</guid>
            <category><![CDATA[bangla]]></category>
            <category><![CDATA[graph-theory]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[software-engineering]]></category>
            <dc:creator><![CDATA[Ahsan Shafiq Shawon]]></dc:creator>
            <pubDate>Sat, 05 Jan 2019 16:07:50 GMT</pubDate>
            <atom:updated>2019-01-17T09:02:32.741Z</atom:updated>
            <content:encoded><![CDATA[<p><strong>প্রোগ্রামিং — ১</strong></p><p><strong>গ্রাফের বন-জঙ্গল</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*kZfFmekUH9kNbUkq8Xgp0g.jpeg" /><figcaption>Photo by <a href="https://unsplash.com/photos/SowPhAbCbcs?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Stephen Hocking</a> on <a href="https://unsplash.com/search/photos/jungle?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Unsplash</a></figcaption></figure><p>আমরা ধীরে ধীরে গ্রাফের ভেতর ঢুকতে শুরু করেছি। এবার কিছু সিরিয়াস লেখাপড়ার প্রস্তুতি নেয়া যেতে পারে। নিচের ছবিটি খেয়াল করা যাক তাহলে,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/443/1*5MAO7A1vj_hFWTirx0uWxg.png" /></figure><p>উপরের ছবিতে বেশ লম্বা-চওড়া একটা গ্রাফ দেখা যাচ্ছে। গ্রাফের নাম দেয়া হয়েছে <strong><em>G</em></strong>। এই গ্রাফে অনেকগুলো এজ আছে কিন্তু আমরা শুধু দুটি এজের নাম এখানে উল্লেখ করেছি। কারণ এরা বিশেষ এজ। আমরা যদি <strong><em>p</em></strong> বা <strong><em>e</em></strong> এজটি সরিয়ে ফেলি তাহলে গ্রাফটি আর <strong><em>connected</em></strong> থাকেনা, নিচের চিত্রের মতো <strong><em>disconnected graph</em></strong> পাওয়া যায়।</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/933/1*qicrHRhIhLKtUE819QFOGw.png" /></figure><p><strong><em>p</em></strong> এজটি সরিয়ে দেয়ার ফলে দুটি বিচ্ছিন্ন অংশ তৈরি হয়েছে যাকে আমরা রঙিন এলাকা দিয়ে ঘিরে দেখিয়েছি। এখানে আমরা দুটো এলাকা পেয়েছি। এদেরকে <strong><em>component</em></strong> বলে। এটা প্রকাশ করার নিয়ম হচ্ছে, <strong><em>C(G) = 2</em></strong>, মানে হচ্ছে যে <strong><em>G</em></strong> গ্রাফের <strong><em>component</em></strong> দুটি। পাশের ছবিতে <strong><em>e</em></strong> এজ সরিয়ে নিয়েও একইভাবে দুটি <strong><em>component</em></strong> পাওয়া গেছে। এই বিষয়টিকে অন্যভাবেও প্রকাশ করা যায়। <strong><em>G\p</em></strong> বা <strong><em>G\e</em></strong> (এটার উচ্চারণ হচ্ছে ‘জি ব্যাকস্ল্যাস উমুক’) এর <strong><em>component</em></strong> দুটি।</p><p>আরেকটা উদাহরণ দেখবো,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/872/1*Gm7phB1cR4-W2Uy_Uzvq1w.png" /></figure><p>ছবি ২৮ এর <strong><em>G</em></strong> গ্রাফটি <strong><em>disconnected</em></strong>। এই গ্রাফের <strong><em>component</em></strong> আমরা দেখতে পাচ্ছি ২ টি। কিন্তু <strong><em>e</em></strong> এজটি সরিয়ে নেয়ার পর <strong><em>component</em></strong> হয়ে গেলো ৩ টি।</p><p>ছবি ২৬ এর গ্রাফটি <strong><em>connected graph</em></strong>। <strong><em>connected graph</em></strong> এর <strong><em>component</em></strong> সংখ্যা সবসময় ১ টি হয়। এরপর আমরা ছবি ২৭ এ দেখলাম বিশেষ কোন এজ সরিয়ে নিলে <strong><em>component</em></strong> বেড়ে যাচ্ছে। পরবর্তীতে ছবি ২৮ এ এসে <strong><em>disconnected graph</em></strong> এর ক্ষেত্রেও আমরা এই অবস্থা দেখলাম।</p><p><strong>যে এজ সরিয়ে নিলে গ্রাফে <em>component</em> সংখ্যা বেড়ে যায় তাকে <em>Bridge edge</em> বলে।</strong></p><p>কোন চক্র বা <strong><em>cycle</em></strong> এর এজগুলো কখনও <strong><em>bridge edge</em></strong> হতে পারেনা, কারণ বোঝার জন্য নিচের ছবিটি খেয়াল করি,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/326/1*HmyuhBaG4g6YBapTB86XtA.png" /></figure><p>উপরের ছবির গ্রাফের যেকোন একটি এজ সরিয়ে নিলে কি এটার <strong><em>component</em></strong> বেড়ে যাবে বলে তোমার মনে হয়? মোটেও না, চেষ্টা করে দেখতে পারো। গ্রাফটি <strong><em>connected</em></strong> আছে, যেকোন একটি এজ সরিয়ে নিলেও তাই থাকবে।</p><p>এখন আমরা মহাগুরুত্বপূর্ণ একটি বিষয় নিয়ে পড়াশোনা করবো, সেটা হচ্ছে ট্রি। ট্রি মানে গাছ, সবাই জানে। কিন্তু তারপরেও আমরা এটিকে ট্রি নামেই ডাকবো। তাহলে শুরু করা যাক।</p><p>যে গ্রাফে কোন চক্র বা <strong><em>cycle</em></strong> থাকেনা তাকে চক্রবিহীন গ্রাফ বা <strong><em>acyclic graph</em></strong> বলে। তোমাদের নিশ্চয়ই মনে আছে যে, <strong><em>connected</em></strong> গ্রাফ কি বস্তু!! কোন গ্রাফে যদি এই দুটি বৈশিষ্ট্য (<strong><em>acyclic</em></strong> ও <strong><em>connected</em></strong>) থাকে তবে সেই গ্রাফকে আমরা ট্রি বলবো। কিছুক্ষণ আগেই আমরা দেখেছি যে <strong><em>cycle</em></strong> এর কোন এজ <strong><em>bridge</em></strong> হতে পারেনা। তাহলে কি আমরা বলতে পারি না যে, <strong><em>acyclic graph</em></strong> এর এজগুলো অবশ্যই <strong><em>bridge</em></strong> হবে যদি সেই গ্রাফটি <strong><em>connected</em></strong> হয়? হ্যা পারি।</p><p>তাহলে ট্রি এর একটি বিকল্প সংজ্ঞা হতে পারে এরকম, “একটি যুক্ত (<strong><em>connected</em></strong>) গ্রাফের সবগুলো এজ <strong><em>bridge</em></strong> হলে তাকে ট্রি বলে।”</p><p>এবার আমরা ট্রি এর কিছু উদাহরণ দেখে ফেলি,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*hV9fMnAyicumCY9akkuTeA.png" /></figure><p>উপরের ছবির (১) নং গ্রাফটি একটি <strong><em>path</em></strong>, বুঝতে নিশ্চয়ই কষ্ট হচ্ছে না। দুনিয়ার সকল <strong><em>path</em></strong> হচ্ছে ট্রি। (২) ও (৩) নং গ্রাফ আসলে একই, একটু ভিন্নভাবে আঁকা হয়েছে আরকি। তোমাদের কি মনে পড়ছে যে, এদেরকে <strong><em>complete bipartite graph</em></strong> বা <strong><em>star</em></strong> নামে ডাকা হয়? এরাও এক ধরনের ট্রি। আরও কিছু উদাহরণ দেখা যেতে পারে,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/943/1*FPwy4qRH2sfYQsz3JQogsg.png" /></figure><p>উপরের ছবির (১) নং গ্রাফটি দেখে কি কিছু মনে পড়ছে? ওই যে অনেকগুলো পা ওয়ালা এক ধরনের পোকা আছে না, শুঁয়াপোকা। ওরকম লাগছেনা? কাছাকাছি তো লাগছে, তাই এই ট্রি এর নাম হচ্ছে শুঁয়াপোকা গ্রাফ বা <strong><em>caterpillar</em></strong>। তুমি যদি (১) নং গ্রাফের উপর-নিচের এজগুলো সরিয়ে ফেলো তাহলে একটা <strong><em>path</em></strong> বাকি থাকে, একে গ্রাফের <strong><em>spine</em></strong> বলা হয়, মেরুদন্ড আরকি। আর পাশেরটা তো <strong><em>double star</em></strong>।</p><p>এখন একটা প্রশ্নের উত্তর দাও তো, তোমাকে যদি আমি তিনটি নোড দিয়ে বলি “ট্রি আঁকো”। তাহলে কি করবা? নিচের ছবিটি খেয়াল করি,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/869/1*EloOK9ihKAg3HbJt09iDig.png" /></figure><p>উপরের ছবির (১) ও (২) নং গ্রাফ হুবহু একই, একটু খেয়াল করে দেখলেই বোঝা যাবে। তাহলে আমরা বলতে পারি, তিনটি নোড দিয়ে আসলে তিনটি (২, ৩, ৪ নং) ভিন্ন ভিন্ন ট্রি আঁকা সম্ভব। তুমি এদের চেয়ে আলাদা ট্রি আঁকার চেষ্টা করে দেখতে পারো, কিন্তু সেটা সম্ভব না। আসলে তিনটি নোড দিয়ে তিনটির বেশি আলাদা ট্রি আঁকা সম্ভব না। তাহলে মনের মধ্যে প্রশ্ন চলে আসে, ৫টি নোড দিয়ে কতগুলো আলাদা আলাদা ট্রি আঁকা সম্ভব? উপরের ছবির মতো সবগুলো আঁকা শুরু করলে তো দিন শেষ হয়ে যাবে।</p><p><strong><em>n</em></strong> সংখ্যক নোড দিয়ে আলাদা আলাদা কতগুলো ট্রি আঁকা যায় তার একটি সূত্র আছে। এই সূত্রটি আবিষ্কার করেছিলেন বিখ্যাত গণিতবিদ আর্থার ক্যালে (<strong><em>Arthur Cayley</em></strong>)। সূত্রের আলোচনায় যাওয়ার আগে এই ভদ্রলোকের কিছু গল্প বলা যাক।</p><p>বেশ অল্প বয়সে (১৭ বছর) এই জনাব ক্যামব্রিজ বিশ্ববিদ্যালয়ে ভর্তি হন। সেখানে তিনি লেখাপড়ায় বেশ সুনাম কুড়ান। কিন্তু তিনি বিশুদ্ধ গণিত নিয়ে পড়াশোনা শেষ করে টাকা-পয়সা আয়ের সুবিধা করতে পারছিলেন না। দিয়ে বাবাজি করলেন কি, ২৫ বছর বয়সে <strong><em>Lincoln’s Inn</em></strong> এ ভর্তি হয়ে গেলেন। এটা হচ্ছে সেই বিশ্ববিখ্যাত প্রতিষ্ঠান যেখান থেকে আরও অনেক দেশের মতো আমাদের দেশের কিছু বিখ্যাত উকিল ব্যারিস্টারি পাশ করে এসেছেন। যাই হোক এখান থেকে লেখাপড়া করে তিনি ১৪ বছর ওকালতিও করেন। কিন্তু গণিতের নেশা উনার তখনও কাটেনি, তাই ৪২ বছর বয়সে উনি যখন ক্যামব্রিজে গণিতের প্রফেসর হওয়ার সুযোগ পেলেন তখন আবার দৌড় দিলেন। যদিও সেখানে ওকালতির মতো আয় রোজগারের সুযোগ ছিলনা।</p><p>আচ্ছা গল্প তো হলো, এই ভদ্রলোক যে সূত্র দিয়েছিলেন সেটা হলো, <strong><em>n</em></strong> সংখ্যক নোড দিয়ে একই গ্রাফের আলাদা আলাদা <strong><em>nⁿ⁻ ²</em></strong> সংখ্যক ট্রি আঁকা যায়। ছবি ৩২ এ আমরা তিনটি নোড দিয়ে তিনটি আলাদা ট্রি এঁকেছিলাম। উপরের সূত্রে <strong><em>n</em></strong> এর মান ৩ বসিয়ে দেখো, দেখবা সূত্র ঠিকই আছে। সূত্রের প্রমাণের দিকে আপাতত না যাই।</p><p>জঙ্গল তৈরি হয় অনেকগুলো গাছ নিয়ে, আবার একটি গাছের অনেকগুলো ডালপালার একদম শেষে থাকে পাতা। আচ্ছা তোমরাকে একটা প্রশ্ন করি। পাতাকে যদি একটি নোড ধরি, তাহলে এই নোডের এজ কয়টা থাকে? চোখ বন্ধ করে একটু কল্পনা করার চেষ্টা করো তো। পাতার পর কিন্তু আর কিছু নাই। পাতার এজ কিন্তু একটা। নিচের ছবিটি খেয়াল করলেই বোঝা যাবে।</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/395/1*Ea5xm6xQY87cS3VLyb7Ftg.png" /></figure><p>গাণিতিকভাবে লিখলে, যদি কোন ট্রিকে <strong><em>T</em></strong> দ্বারা এবং এই ট্রি এর কোন নোডকে <strong><em>v</em></strong> দ্বারা প্রকাশ করা হয় অর্থাৎ <strong><em>v ∈ V(T)</em></strong>, তাহলে <strong><em>deg(v)=1</em></strong> হলে <strong><em>v</em></strong> কে আমরা লিফ (<strong><em>leaf</em></strong>) বা পাতা বলবো।</p><p>ছবি ৩২ এ খেয়াল করি আবার, ওই ট্রিতে তিনটি নোড ছিল এবং তাতে লিফ আছে ২টি। যদি ২টি নোডবিশিষ্ট ট্রি আঁকতে চাই,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/167/1*Ap_0FJKjC-dSojrqNobCjw.png" /></figure><p>এই গ্রাফেও খেয়াল করো, ২টি লিফ আছে। তারমানে দাঁড়ায় যে, পৃথিবীর যেকোন ট্রিতে (যদি তাতে কমপক্ষে ২টি নোড থাকে আরকি) কমপক্ষে ২টি লিফ থাকবে। গাণিতিকভাবে, যদি <strong><em>|V(T)|≥ 2</em></strong> হয় তাহলে ওই ট্রিতে কমপক্ষে ২টি লিফ থাকবে। ছবি ৩০ ও ৩১ এ বেশ কয়েকটি ট্রি এর উদাহরণ আছে, ওগুলোর ক্ষেত্রে খেয়াল করলেও দেখবে যে প্রতিটি ট্রিতেই কমপক্ষে ২টি লিফ থাকে।</p><p>ট্রি এর একটি বিশেষ বৈশিষ্ট্য হচ্ছে, এতে যতগুলো নোড থাকবে তার চেয়ে একটি এজ কম থাকবে।</p><p>অর্থাৎ <strong><em>|E(T)| = |V(T)|–1</em></strong>.</p><p>সব গাণিতিক সূত্রেরই প্রমাণ আছে, তবে আমরা আমাদের আলোচনা যতটুকু সহজ রাখা যায় সেই চেষ্টা করবো। তাই আমরা প্রমাণের দিকে যাবোনা, প্রতিযোগিতামূলক প্রোগ্রামিং এ ভালো করা বা সফটওয়্যার ইঞ্জিনিয়ার হিসেবে চাকরি পাওয়ার চেষ্টা থাকবে আমাদের।</p><p>এবার আমরা জঙ্গল বা <strong><em>Forest </em></strong>নিয়ে কথা বলবো। নিচের ছবিটি খেয়াল করি,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/579/1*CfSVYPS5-QGSuAu0LMYdfQ.png" /></figure><p>উপরের ছবিতে একটাই গ্রাফ আছে, তিনটা না। এটি একটি <strong><em>disconnected graph</em></strong> যার <strong><em>component</em></strong> সংখ্যা তিন এবং প্রতিটি <strong><em>component</em></strong> এক একটি ট্রি। এ ধরনের গ্রাফকে <strong><em>forest</em></strong> বলে। এই <strong><em>component</em></strong> গুলোকে জোড়া লাগানোর জন্য কটা এজ দরকার? দুইটা। প্রথমটার সাথে দ্বিতীয়টা জোড়া লাগানোর জন্য একটা আর দ্বিতীয়টার সাথে তৃতীয়টা জোড়া লাগানোর জন্য আর একটা।</p><p>আমরা জানি যেকোন ট্রি এর ক্ষেত্রে,</p><p><strong><em>|E(T)| = |V(T)|–1</em></strong></p><p>উপরের গ্রাফে আরও দুটি এজ কম আছে। তাহলে এই গ্রাফের ক্ষেত্রে,</p><p><strong><em>|E(T)| = |V(T)|–1–2</em></strong></p><p>বা, <strong><em>|E(T)| = |V(T)|–3</em></strong></p><p>বা, <strong><em>|E(T)| = |V(T)|–k</em></strong></p><p>এখানে <strong><em>k</em></strong> দ্বারা <strong><em>component</em></strong> সংখ্যা বুঝানো হয়েছে। তাহলে কোন <strong><em>forest</em></strong> এর,</p><p>নোড সংখ্যা <strong><em>|V(T)| = n</em></strong></p><p>এজ সংখ্যা <strong><em>|E(T)|= m </em></strong>ও</p><p><strong><em>component</em></strong> সংখ্যা <strong><em>k</em></strong> হলে,</p><p>আমরা লিখতে পারি, <strong><em>m = n–k</em></strong>.</p><p>অয়লারকে নিয়ে একটি মজার তথ্য দিই। আমরা যে কোন ফাংশন লিখার সময় <strong><em>f(x)</em></strong> প্রতীকটি ব্যবহার করি, এটা অয়লার বাবাজি সর্বপ্রথম ব্যবহার করেছিলেন।</p><p><a href="https://medium.com/%E0%A6%AA%E0%A7%8D%E0%A6%B0%E0%A7%8B%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AE%E0%A6%BF%E0%A6%82-%E0%A6%AA%E0%A6%BE%E0%A6%A4%E0%A6%BE/%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AB-%E0%A6%A5%E0%A6%BF%E0%A6%93%E0%A6%B0%E0%A6%BF-%E0%A6%AA%E0%A6%B0%E0%A7%8D%E0%A6%AC-%E0%A7%AB-732f7b73749a"><strong>গ্রাফ থিওরি (পর্ব ৫) পড়তে ক্লিক করুন।</strong></a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=3fff7c4e952e" width="1" height="1" alt=""><hr><p><a href="https://medium.com/%E0%A6%AA%E0%A7%8D%E0%A6%B0%E0%A7%8B%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AE%E0%A6%BF%E0%A6%82-%E0%A6%AA%E0%A6%BE%E0%A6%A4%E0%A6%BE/%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AB-%E0%A6%A5%E0%A6%BF%E0%A6%93%E0%A6%B0%E0%A6%BF-%E0%A6%AA%E0%A6%B0%E0%A7%8D%E0%A6%AC-%E0%A7%AA-3fff7c4e952e">গ্রাফ থিওরি (পর্ব ৪)</a> was originally published in <a href="https://medium.com/%E0%A6%AA%E0%A7%8D%E0%A6%B0%E0%A7%8B%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AE%E0%A6%BF%E0%A6%82-%E0%A6%AA%E0%A6%BE%E0%A6%A4%E0%A6%BE">প্রোগ্রামিং পাতা</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[গ্রাফ থিওরি (পর্ব ৩)]]></title>
            <link>https://medium.com/%E0%A6%AA%E0%A7%8D%E0%A6%B0%E0%A7%8B%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AE%E0%A6%BF%E0%A6%82-%E0%A6%AA%E0%A6%BE%E0%A6%A4%E0%A6%BE/%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AB-%E0%A6%A5%E0%A6%BF%E0%A6%93%E0%A6%B0%E0%A6%BF-%E0%A6%AA%E0%A6%B0%E0%A7%8D%E0%A6%AC-%E0%A7%A9-ea5594bebe36?source=rss-550534651e5d------2</link>
            <guid isPermaLink="false">https://medium.com/p/ea5594bebe36</guid>
            <category><![CDATA[bangla]]></category>
            <category><![CDATA[graph-theory]]></category>
            <category><![CDATA[software-engineering]]></category>
            <category><![CDATA[programming]]></category>
            <dc:creator><![CDATA[Ahsan Shafiq Shawon]]></dc:creator>
            <pubDate>Sat, 05 Jan 2019 16:07:11 GMT</pubDate>
            <atom:updated>2019-01-08T15:59:41.977Z</atom:updated>
            <content:encoded><![CDATA[<p><strong>প্রোগ্রামিং — ১</strong></p><p><strong>প্রথম থিওরেমের ছোঁয়া!!</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*56icJ6WPoNlPAcAlhzEZCg.jpeg" /><figcaption>Photo by <a href="https://unsplash.com/photos/_SFJhRPzJHs?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">NASA</a> on <a href="https://unsplash.com/search/photos/map-%2B-computer?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Unsplash</a></figcaption></figure><p>প্রথমেই মজার একটা সম্পর্ক দেখে নিই। নিচের ছবিটি খেয়াল করি,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/471/1*DPaTNlAkp41XuRjgO7lxAA.png" /></figure><p>উপরের গ্রাফের প্রতিটি নোডে তার ডিগ্রি সংখ্যা লিখা আছে। নোডসংখ্যাগুলি যোগ করলে ৩+২+৪+২+১=১২ পাওয়া যায়। এই গ্রাফে কয়টা এজ আছে? ৬টা। কোন সম্পর্ক বুঝতে পারছো? যেকোন গ্রাফের মোট ডিগ্রি = ২ × ওই গ্রাফের এজসংখ্যা।</p><p>এখন প্রশ্ন হচ্ছে যে, এই সম্পর্কটা কি সব গ্রাফের জন্যই সত্য? জ্বী হ্যা, তবে যদি সেটি একটি <strong><em>undirected graph</em></strong> হয়। এখন প্রশ্ন হচ্ছে এই <strong><em>undirected graph</em></strong> মানে কি? নিচের ছবিটি খেয়াল করলেই অনেকটা বোঝা যাবে আশা করি,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/782/1*EUVQ0-xAcr1NMr8qZgvwNA.png" /></figure><p>ছবি ২২ (এই ছবির গ্রাফদুটোতে নোডগুলোর নাম দেয়া হয়েছে ১, ২, ৩ ইত্যাদি; এগুলো তাদের ডিগ্রি বোঝাচ্ছেনা) এ <strong><em>F</em></strong> গ্রাফটি একটি <strong><em>undirected graph</em></strong> এবং <strong><em>G</em></strong> গ্রাফটি হচ্ছে একটি <strong><em>directed graph</em></strong>। <strong><em>undirected graph</em></strong> এ তুমি ১ নং নোড থেকে ২ নং নোডে যেমন যেতে পারবা ঠিক তেমনি ২ নং নোড থেকে ১ নং নোডেও যেতে পারবা কিন্তু <strong><em>directed graph</em></strong> এ যে বরাবর দিক দেয়া থাকবে শুধু সেদিকেই যেতে পারবা। যেমন উপরের <strong><em>G</em></strong> গ্রাফে তুমি ১ নং নোড থেকে ২ নং নোডে যেতে পারবা কিন্তু ২ নং নোড থেকে ১ নং নোডে যেতে পারবানা।</p><p><strong>সূত্রঃ যেকোন গ্রাফের (<em>G</em>) ক্ষেত্রে, <em>Σdeg(v) = 2 |E(G)|</em> অর্থাৎ যেকোন গ্রাফের মোট ডিগ্রি = ২×ওই গ্রাফের এজসংখ্যা</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/221/1*4IbREJI8ufVwBW3m27Uemw.png" /></figure><p>প্রমাণঃ মনে করি, গ্রাফের যেকোন একটি এজ হচ্ছে <strong><em>e</em></strong> এবং এর দুটি প্রান্ত <strong><em>u</em></strong> ও <strong><em>v</em></strong>।<br>আমরা যখন <strong><em>u</em></strong> নোডের এজ গুনছি তখন একবার <strong><em>e</em></strong> কে ধরে নিচ্ছি, আবার <strong><em>v</em></strong> নোডের এজ গোনার সময়ও <strong><em>e</em></strong> কে ধরছি। তারমানে এক এজ দুইবার করে গোনা হচ্ছে। একারণেই মোট এজের সংখ্যা, মোট ডিগ্রির দ্বিগুণ।</p><p>এই সূত্র থেকে আমরা একটি সিদ্ধান্ত নিতে পারি, যাকে অনুসিদ্ধান্ত বলে আরকি।</p><p><strong>অনুসিদ্ধান্তঃ যেকোন গ্রাফে জোড়সংখ্যক বিজোড় ডিগ্রির নোড থাকে।</strong></p><p>প্রমাণঃ আগের সূত্র থেকে আমরা দেখেছি,</p><p><strong><em>Σdeg(v) = 2 |E(G)|</em></strong></p><p>অর্থাৎ <strong><em>deg(v₁) + deg(v</em></strong>₂<strong><em>) + deg(v</em></strong>₃<strong><em>) + ….. + deg(vₙ) = 2 |E(G)|</em></strong></p><p>এই সমীকরণের ডানপক্ষ জোড়, তাহলে অবশ্যই বামপক্ষকেও জোড় হতে হবে (নাহলে সমান হবে কিভাবে?)। তোমাকেই একটা প্রশ্ন করি। কয়েকটি বিজোড় সংখ্যার যোগফল কি কখনো জোড় হয়? যেমন, ১+৭+৯ = ১৭, এখানে তিনটি বিজোড় সংখ্যা নিয়েছি। তিন নিজেই একটি বিজোড় সংখ্যা, আর এদের যোগফলও হয়েছে বিজোড়। এভাবে অসংখ্য উদাহরণ তুমি নিজে নিজে তৈরি করতে পারো, কিন্তু কখনোই বিজোড় সংখ্যক বিজোড় সংখ্যার যোগফল তুমি জোড় পাবানা। তাই উপরের সমীকরণের বামপক্ষকে জোড় হতে হলে, যদি বিজোড় ডিগ্রি থাকে তাহলে বিজোড় ডিগ্রির সংখ্যা জোড় হতে হবে। যেমন, ৩, ৩, ৪; এখানে তিনটি নোডের ডিগ্রি সংখ্যা দেখানো হল। এদের মধ্যে ৩ দুইবার আছে অর্থাৎ বিজোড় ডিগ্রি আছে জোড়সংখ্যকবার এবং এদের যোগফলও ৩+৩+৪=১০ হচ্ছে জোড়।</p><p>কেউ যদি তোমাকে বলে যে উমুক গ্রাফে ১০ ডিগ্রির দুটি নোড ও ৩ ডিগ্রির একটি নোড আছে। তুমি বলবা যে, এটা সম্ভব না। কারণ ৩ ডিগ্রির অর্থাৎ বিজোড় ডিগ্রির নোড আছে ১ টি অর্থাৎ বিজোড় সংখ্যক, এটা সম্ভব না।</p><p>এখন ধরো যে আমরা কম্পিউটার বাবাজিকে দিয়ে কিছু কাজ করিয়ে নিতে চাই। যেমন উমুক গ্রাফের উমুক বৈশিষ্ট্য আছে কিনা বের করে দে বা আরও অনেককিছু হতে পারে। সেক্ষেত্রে আমাদের গ্রাফের সাথে কম্পিউটার বাবাজির পরিচয় করিয়ে না দিলে বাবাজি কিভাবে আমাদের কাজ করে দেবে? তাহলে আমরা এখন আলোচনা করবো, কিভাবে একটি গ্রাফকে আমরা কম্পিউটারের মধ্যে ঢেলে দিয়ে কাজ আদায় করে নিতে পারি।</p><p>কম্পিউটারকে আমাদের কথা বুঝানোর জন্য আমরাকে কম্পিউটারের ভাষায় কথা বলতে হবে, যে ভাষার নাম হচ্ছে প্রোগ্রামিং ভাষা। আমাদের মানুষের ভাষাকে বলা হয় হিউম্যান ল্যাঙ্গুয়েজ। অনেক ধরনের হিউম্যান ল্যাঙ্গুয়েজ আছে, যেমন বাংলা, ইংরেজি, উর্দু, ফারসি, হিন্দি ইত্যাদি। তেমনি অনেক ধরনের প্রোগ্রামিং ল্যাঙ্গুয়েজ আছে, যেমন সি, সি++, জাভা, প্যাসকেল, পাইথন ইত্যাদি।</p><p>যেকোন একটা ভাষাতে বাবাজির সাথে কথা বললেই হবে। আমাদের এই সিরিজে আমরা সি++ ভাষাটি ব্যবহার করবো। আচ্ছা তো যে কথায় ছিলাম। গ্রাফকে কম্পিউটারে স্টোর (<strong><em>store</em></strong>) করা বা ঢেলে দেয়ার দুটি জনপ্রিয় পদ্ধতি আছে। যথাঃ <strong><em>adjacency list</em></strong> ও <strong><em>adjancency matrices</em></strong>।</p><p>আমরা এখন এই পদ্ধতি দুটো নিয়ে বিশদ আলোচনা করবো। কেউ যদি প্রশ্ন করে যে, কোন্ পদ্ধতিটি বেশি ভালো? তাহলে এর উত্তরে আমি বলবো যে, তুমি শাক-সবজি, মাছ-মাংস ইত্যাদি বাজার করতে গেলে কি ধরনের ব্যাগ বা বস্তা নিয়ে যাবা? সেটা নির্ভর করবে তুমি কি ধরনের বাজার করতে চাও। ঠিক সেরকমই তুমি কোন্ ধরনের কাজের জন্য এই পদ্ধতিগুলো ব্যবহার করতে চাও সেটার ওপর নির্ভর করবে কোন্ পদ্ধতিটি বেশি কাজের।</p><p>সাধারণভাবে বলা যায় যে, যদি কোন গ্রাফে এজসংখ্যা বেশ কম হয় তাহলে লিস্ট পদ্ধতি বেশি কাজের এবং যদি গ্রাফটি খুব ঘন হয় অর্থাৎ এজসংখ্যা অনেক বেশি হয় তাহলে ম্যাট্রিক্স পদ্ধতি ভালো। গাণিতিকভাবে বললে,</p><p>যখন <strong><em>|E| </em></strong>এর মান <strong><em>|V|</em></strong>²<strong><em> </em></strong>এর থেকে অনেক কম হয় তখন লিস্ট পদ্ধতি এবং যখন <strong><em>|E| </em></strong>এর মান <strong><em>|V|</em></strong>² এর কাছাকাছি মানের হয় তখন ম্যাট্রিক্স পদ্ধতি ভালো কাজে দেয়।</p><p>আমি আশা করছি <strong><em>|E|</em></strong> ও <strong><em>|V|</em></strong> কি অর্থ প্রকাশ করে তোমাদের মনে আছে।</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/986/1*N-3WlL62iL13ijDzSvdHHg.png" /></figure><p>ছবি ২৪ এ আমরা <strong><em>F</em></strong> গ্রাফের <strong><em>adjacency list</em></strong> ও <strong><em>adjacency matrices</em></strong> প্রকাশ বা <strong><em>representation</em></strong> দেখতে পাচ্ছি। <strong><em>adjacency list</em></strong> এর ক্ষেত্রে আমরা গ্রাফের প্রতিটি নোডকে পেস্ট কালারের বক্সে রেখে, এর সাথে যে যে নোডের সম্পর্ক বা এজ আছে তারাকে পরপর লিখেছি। যেমন ১ নং নোডের সাথে ২ ও ৫ নং নোডের এজ আছে। অনুরূপভাবে পরের নোডগুলোর ক্ষেত্রেও লিখা হয়েছে। আর <strong><em>adjacency matrices</em></strong> এর ক্ষেত্রে আমরা <strong><em>|V|</em></strong>×<strong><em>|V| </em></strong>আকারের একটি ম্যাট্রিক্স নিয়েছি । এক্ষেত্রে <strong><em>|V| = 5</em></strong>। এরপর আমরা নিচের সূত্র অনুযায়ী ম্যাট্রিক্সটি পূরণ করে ফেলেছি।</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/252/1*lGyBwAzj6mZtlGHNr024rg.png" /></figure><p>উপরের কথাটুকুর অর্থ হচ্ছে যে, <strong><em>Aᵢⱼ</em></strong> এর মান ১ হবে যদি <strong><em>i</em></strong> ও <strong><em>j</em></strong> নোডের মধ্যে এজ থাকে এবং যদি না থাকে তাহলে শূন্য হবে। এখানে <strong><em>i</em></strong> সারি ও <strong><em>j</em></strong> কলাম নির্দেশ করছে। উপরের ম্যাট্রিক্সটায় খেয়াল করে দেখো যে, ১ নং নোডের সাথে ১ নং নোডের কোন এজ নাই তাই <strong><em>A₁₁ = 0</em></strong> কিন্তু ১ নং নোডের সাথে ২ নং নোডের এজ আছে তাই <strong><em>A₁₂ = 1</em></strong> হয়েছে এবং এভাবে ম্যাট্রিক্সের বাকি জায়গাগুলো পূরণ করা হয়েছে।</p><p>এখন আমরা দেখবো যে, কিভাবে প্রোগ্রামিং ভাষার মাধ্যমে এই <strong><em>adjacency list</em></strong> ও <strong><em>adjacency matrices</em></strong> কম্পিউটারকে বুঝানো যায়। আমরা প্রথমে <strong><em>adjacency list</em></strong> নিয়ে কথা বলবো। <strong><em>adjacency list</em></strong> এর মাধ্যমে কম্পিউটারে গ্রাফ স্টোর করতে গেলে আমরাকে ভেক্টর সম্পর্কে কিছুটা জানতে হবে। এই ভেক্টর অবশ্য পদার্থবিজ্ঞানের ভেক্টর নয়। এটি হচ্ছে সি++ ভাষার একটি <strong><em>standard template library</em></strong>। আবার প্রশ্ন তৈরি হলো, এই <strong><em>standard template library (STL)</em></strong> টা আবার কি? এটা নিয়ে পরে কথা বলবো।<br>তাহলে শুরু করি ভেক্টর নিয়ে আলোচনা।</p><p>ভেক্টর হচ্ছে একটি ডায়নামিক এ্যারে। এতে আমরা প্রয়োজনমতো তথ্য রাখতে পারি এবং এর আকার আমরা পরিবর্তন করতে পারি।</p><p>আমি আশা করছি যে, সি++ ভাষা তোমাদের মোটামোটি জানা আছে। যেকোন সি++ প্রোগ্রামে যে অংশটি অবশ্যই থাকে তাকে আমরা কোড স্কেলেটন (<strong><em>skeleton</em></strong> মানে কঙ্কাল) বলতে পারি। মোটা বা পাতলা হোক, প্রত্যেক মানুষের মধ্যে যেমন কঙ্কাল থাকবে ঠিক তেমনি প্রোগ্রাম বড় হোক বা ছোট হোক এই কোড স্কেলেটন (কোড ০০১) থাকবেই।</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/391/1*Wzym-81bcwq0inrJ75wWYA.png" /></figure><p>আমরা সি++ ভাষা ব্যবহার করে প্রোগ্রাম লিখলে কোড ০০১ এর কাঠামো থাকবে। ৫ ও ৬ নং লাইনে প্রয়োজনীয় কোড লিখে আমরা আমাদের প্রয়োজনমাফিক কাজ করে ফেলতে পারি। সেক্ষেত্রে অবশ্য আমাদের কোড শুধু ৫ ও ৬ নং লাইনে সীমাবদ্ধ থাকবেনা এবং আমাদের ৭ নং লাইন পিছিয়ে অনেক দূরে চলে যাবে। নিচের কোডটি খেয়াল করলেই বোঝা যাবে,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/583/1*aQEuyXDUcTTum5ZyvqWaHA.png" /></figure><p>৫ নং লাইন — ইন্টিজার টাইপের ভেক্টর ডিক্লেয়ার করা হয়েছে, নাম দেয়া হয়েছে ‘বাবাজি’।<br>৬-৯ নং লাইন — ভেক্টরে এক একটি তথ্য ঢুকিয়ে দেয়ার পদ্ধতি দেখানো হয়েছে।<br>১০ নং লাইন — ভেক্টরের আকার দেখানোর বুদ্ধি। এখানে ভেক্টরের আকার হচ্ছে ৪, কারণ ইতিমধ্যেই আমরা ভেক্টরে ৪টি তথ্য ঢুকিয়ে দিয়েছি।<br>১১-১৩ নং লাইন — ‘বাবাজি’ ভেক্টরের তথ্যগুলো আমরা ‘ফর লুপ’ ব্যবহার করে প্রিন্ট করেছি। এই লুপটি অবশ্যই ভেক্টরের আকারের সমান বার চলবে।<br>১৫ নং লাইন — এখানেও ইন্টিজার টাইপের অয়লার নামের ভেক্টর ডিক্লেয়ার করা হয়েছে, তবে এটা ভেক্টরের এ্যারে। তারমানে এখানে আমরা পাঁচটি ভেক্টর ব্যবহার করতে পারবো।<br>১৬ ও ১৭ নং লাইন — পাঁচটি ভেক্টরের এ্যারের প্রথমটিতে তথ্য ঢুকানো হচ্ছে। এক্ষেত্রে ইনডেক্স শূন্য থেকে শুরু করা হয়েছে।<br>১৮ নং লাইন — চার নম্বর ভেক্টরে তথ্য ঢুকানো হচ্ছে।<br>১৯ নং লাইন — অয়লার ভেক্টর এ্যারের প্রথম ভেক্টরে দুটি তথ্য ঢুকানো হয়েছে ১৬ ও ১৭ নং লাইনে, তাই এখানে ভেক্টরের আকার ২ দেখাবে।<br>২০ নং লাইন — ভেক্টর এ্যারের মধ্যে থেকে কোন একটি নির্দিষ্ট তথ্য কিভাবে প্রিন্ট করতে হয় সেটা দেখানো হয়েছে। এখানে ভেক্টর এ্যারের প্রথমটির দ্বিতীয় উপাদান (১ ইনডেক্সের উপাদান) প্রিন্ট করা হয়েছে।<br>২১-২৩ নং লাইন — ভেক্টর এ্যারের প্রথমটির সব উপাদান ‘ফর লুপ’ দিয়ে প্রিন্ট করা হয়েছে।</p><p>কোন গ্রাফকে কিভাবে <strong><em>adjacency list</em></strong> এর মাধ্যমে প্রকাশ করা হয় সেটা আমরা ছবি ২৪ এ দেখেছি। এখন সেটার কোড লিখার চেষ্টা করা যেতে পারে।</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/644/1*l4Uf8C1d8cdaMgGqtFRndg.png" /></figure><p>৫ নং লাইন — ভেক্টরের একটি এ্যারে নিয়েছি ৬ সাইজের, নাম দিয়েছি ওগগেমাগে। আসলে আমার ৫ সাইজের দরকার ছিল কারণ যে গ্রাফের ক্ষেত্রে কোডটি লিখছি তাতে ৫টি নোড আছে, প্রতিটি নোডের সাথে কে কে <strong><em>adjacent</em></strong> সেই তথ্য ঢুকানোর জন্য আমাদের ৫টি ভেক্টর লাগবে। কিন্তু ইনডেক্সিং ‘শূন্য’ থেকে শুরু হওয়ায় আমরা <strong>oggemage[0]</strong> কে বাদ দিয়ে <strong>oggemage[1] </strong>থেকে <strong>oggemage[5] </strong>কে নিয়েছি।<br>৬ নং লাইন — গ্রাফে কটা নোড ও এজ আছে সেটা ডিক্লেয়ার করেছি।<br>৭ নং লাইন — ইনপুট নিয়ে নিলাম।<br>৮ নং লাইন — দুটো ভ্যারিয়েবল নিয়েছি, পরবর্তীতে কাজে আসবে।<br>৯-১৪ নং লাইন — এখানে আমরা একটি ‘ফর লুপ’ ব্যবহার করেছি। এর মধ্যে কিছু কাজ করা হয়েছে। আমাদের আলোচ্য গ্রাফের এজগুলো হচ্ছে ১২, ১৫, ২৩, ২৪, ৩৪, ৪৫। যেহেতু ৬টি এজের তথ্য সংরক্ষণ করতে হবে তাই লুপটি ৬ বার অর্থাৎ এজের সংখ্যা যত ততবার ঘুরবে। ১ নং থেকে যেমন ২ নং নোডে এজ আছে তেমনি আমরা বলতে পারি ২ নং নোড থেকে ১ নং নোডেও এজ আছে। এভাবে প্রতিটি এজের ক্ষেত্রেই একই কথা বলা যায়। তাই ১২ ও ১৩ নং লাইনে একই কাজ ঘুরিয়ে দুবার করা হয়েছে। এ্যারে ভেক্টরের প্রথমটিতে তথ্য হিসেবে ‘২’ কে সংরক্ষণ করে আবার ভেক্টরের দ্বিতীয়টিতে ‘১’ কে সংরক্ষণ করা হয়েছে। ৮ নং লাইনে যে ভ্যারিয়েবল দুটি নেয়া হয়েছিল তাদের সাহায্যে আমরা এখানে কার কার মধ্যে এজ আছে সেটা ইনপুট হিসেবে নিয়েছি।<br>১৫ ও ১৬ নং লাইন — এখানে তুমি ইচ্ছা করলে যেকোন এজের লিস্ট প্রিন্ট করে ফেলতে পারো।</p><p>এবার আমরা ওই একই গ্রাফের <strong><em>adjacency matrices</em></strong> এর মাধ্যমে প্রকাশের কোড লিখে ফেলি।</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/643/1*468Va9OxPgU1ATuA2TLXYw.png" /></figure><p>৩ নং লাইন — এই ধরনের ডিক্লেরেশনকে (মানে মেইন ফাংশনের বাইরের কথা বলছি আরকি) গ্লোবাল ডিক্লেরেশন বলে। এতে করে যেটা হয় সেটা হচ্ছে এ্যারের প্রতিটি মান ‘শূন্য’ দ্বারা আগে থেকেই পূরণ হয়ে যায়।<br>৬ ও ৭ নং লাইন — কটা নোড ও এজ আছে সেটার বন্দোবস্ত করা হলো।<br>৮-১১ নং লাইন — কোড ০০৩ এর মতোই।<br>১২ ও ১৩ নং লাইন — যাদের মধ্যে এজ আছে সেখানে ‘১’ বসিয়ে দিলাম।<br>১৫-২০ নং লাইন — এবার পালা ম্যাট্রিক্সটি প্রিন্ট করার।</p><p><strong><em>Incidence Matrix</em></strong> নামে একটি বিষয় আছে, সেটা নিয়ে একটু আলোচনা করা যাক। সেজন্য আমরা উদাহরণ হিসেবে একটি গ্রাফ নিতে পারি। নিচের ছবিটি খেয়াল করি,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/794/1*NEAOlkmy9F7kc5JlJx3USw.png" /></figure><p>উপরের ছবি ২৫ এর গ্রাফের <strong><em>adjacency matrix</em></strong> দেখতে পাওয়া যাচ্ছে। প্রতিটি সারির যোগফল ওই নোডের ডিগ্রি প্রকাশ করছে। এখানে যোগফলগুলো দেখানো আছে, যেমন নোড ‘১’ এর ডিগ্রি ২, নোড ‘২’ এর ডিগ্রি ৩ ইত্যাদি। একইভাবে তুমি কলামগুলোর যোগফল বের করলেও একই ফলাফল আসবে। তাহলে আমরা বলতে পারি যে, কলাম বা সারির যোগফল ওই নোডের ডিগ্রি প্রকাশ করে।</p><p>এবার আসি <strong><em>Incidence Matrix</em></strong> এর কথায়। এর ক্ষেত্রে সারিগুলো প্রকাশ করে নোডগুলোকে এবং এজগুলোকে প্রকাশ করে কলামেরা। গ্রাফের দিকে খেয়াল করলে দেখা যাবে যে, গ্রাফের এজগুলোর নাম দেয়া আছে আলাদা করে। এইক্ষেত্রে <strong><em>adjacency matrix</em></strong> এর মতোই সারিগুলোর যোগফল ওই নোডের ডিগ্রি প্রকাশ করে। আর কলামগুলোর যোগফল হয় সর্বদা ২, কেননা প্রতিটি এজের দুটি করে প্রান্ত থাকে।</p><p>বাবাজিকে নিয়ে আরেকটা তথ্য দেয়া যাক। মহামান্য অয়লার সাহেব উনার সারাজীবনে গণিত বিষয়ে এত এত এত বেশি লিখালিখি করেছেন যে, হিসাব করলে বোঝা যায় উনি প্রতিবছর গড়ে ৮০০ পৃষ্ঠা করে লিখেছেন।</p><p><a href="https://medium.com/%E0%A6%AA%E0%A7%8D%E0%A6%B0%E0%A7%8B%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AE%E0%A6%BF%E0%A6%82-%E0%A6%AA%E0%A6%BE%E0%A6%A4%E0%A6%BE/%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AB-%E0%A6%A5%E0%A6%BF%E0%A6%93%E0%A6%B0%E0%A6%BF-%E0%A6%AA%E0%A6%B0%E0%A7%8D%E0%A6%AC-%E0%A7%AA-3fff7c4e952e"><strong>গ্রাফ থিওরি (পর্ব ৪) পড়তে ক্লিক করুন।</strong></a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=ea5594bebe36" width="1" height="1" alt=""><hr><p><a href="https://medium.com/%E0%A6%AA%E0%A7%8D%E0%A6%B0%E0%A7%8B%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AE%E0%A6%BF%E0%A6%82-%E0%A6%AA%E0%A6%BE%E0%A6%A4%E0%A6%BE/%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AB-%E0%A6%A5%E0%A6%BF%E0%A6%93%E0%A6%B0%E0%A6%BF-%E0%A6%AA%E0%A6%B0%E0%A7%8D%E0%A6%AC-%E0%A7%A9-ea5594bebe36">গ্রাফ থিওরি (পর্ব ৩)</a> was originally published in <a href="https://medium.com/%E0%A6%AA%E0%A7%8D%E0%A6%B0%E0%A7%8B%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AE%E0%A6%BF%E0%A6%82-%E0%A6%AA%E0%A6%BE%E0%A6%A4%E0%A6%BE">প্রোগ্রামিং পাতা</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[গ্রাফ থিওরি (পর্ব ২)]]></title>
            <link>https://medium.com/%E0%A6%AA%E0%A7%8D%E0%A6%B0%E0%A7%8B%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AE%E0%A6%BF%E0%A6%82-%E0%A6%AA%E0%A6%BE%E0%A6%A4%E0%A6%BE/%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AB-%E0%A6%A5%E0%A6%BF%E0%A6%93%E0%A6%B0%E0%A6%BF-%E0%A6%AA%E0%A6%B0%E0%A7%8D%E0%A6%AC-%E0%A7%A8-85aadc1e3810?source=rss-550534651e5d------2</link>
            <guid isPermaLink="false">https://medium.com/p/85aadc1e3810</guid>
            <category><![CDATA[graph-theory]]></category>
            <category><![CDATA[bangla]]></category>
            <category><![CDATA[software-engineering]]></category>
            <category><![CDATA[programming]]></category>
            <dc:creator><![CDATA[Ahsan Shafiq Shawon]]></dc:creator>
            <pubDate>Thu, 03 Jan 2019 17:26:17 GMT</pubDate>
            <atom:updated>2019-01-08T15:58:49.976Z</atom:updated>
            <content:encoded><![CDATA[<p><strong>প্রোগ্রামিং — ১</strong></p><p><strong>গ্রাফের বংশ, করে দিন ধ্বংস</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*I55RwI0P5U_yFZ_w1R-akw.jpeg" /><figcaption>Photo by <a href="https://unsplash.com/photos/ZA6KIwNAJ-A?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Luiz Centenaro</a> on <a href="https://unsplash.com/search/photos/map?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Unsplash</a></figcaption></figure><p>“গ্রাফের বংশ, করে দিন ধ্বংস” মানে হচ্ছে যে গ্রাফের পরিচয় এবং তার বংশ সম্পর্কে জেনে শেষ করে ফেলতে হবে আমরাকে। গ্রাফ বলতে আমার চোখের সামনে প্রথমেই ভেসে ওঠে, ছোট ক্লাসে আমরা গ্রাফ পেপারে কিছু বিন্দু বসিয়ে তাদেরকে যোগ করে বিভিন্ন আকার আকৃতি তৈরি করতাম সেগুলো। কিন্তু আমরা যে গ্রাফ থিওরি নিয়ে পড়তে বসেছি সেটা অন্যকিছু।</p><p>“গ্রাফ কাকে বলে” এই প্রশ্নের উত্তরে আমরা কিছু ইংরেজি কথা বলবো। ঘাবড়ানোর কিছু নেই, আমি সেগুলো ব্যাখ্যা করবো।</p><p><strong><em>“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.”</em></strong></p><p>উপরের কথাগুলোর সহজ বাংলা করতে গেলে দাঁড়ায়, একটি গ্রাফ যাকে আমরা <strong><em>G</em></strong> নাম দিয়েছি সেটা হচ্ছে কিছু ভার্টেক্স বা নোড (<strong><em>V</em></strong>) ও এজের (<strong><em>E</em></strong>) সমষ্টি (সমষ্টি না বলে সমাবেশ বা <strong><em>combination</em></strong> বলা বোধহয় বেশি ভালো হয়!)। কিছু উদাহরণ নিচে দেয়া হলো,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/905/1*bq8SZnlTLq-y7VyeRBAmnA.png" /></figure><p>ছবি ৫ এর ১ নং গ্রাফের ক্ষেত্রে আমরা লিখতে পারি, <strong><em>V = {1, 2, 3}</em></strong></p><p>এর অর্থ, <strong><em>V</em></strong> হচ্ছে নোডগুলোর সেট। সেট কিভাবে লিখতে হয় আশা করছি সেটা সবাই জানে। উপাদানগুলোকে কমা দিয়ে আলাদা আলাদা করে দ্বিতীয় বন্ধনীর মধ্যে লিখে ফেলতে হয়।</p><p>আবার আমরা লিখতে পারি যে, <strong><em>E = {{1, 2}, {2, 3}, {3, 1}}</em></strong></p><p>এর অর্থ, <strong><em>E</em></strong> হচ্ছে এজগুলোর সেট। উপরে গ্রাফের সংজ্ঞায় <strong><em>“2-subsets”</em></strong> কথাটার অর্থ হচ্ছে যে, সেটের মধ্যে আমরা আবার দ্বিতীয় বন্ধনীর মধ্যে দুটো করে সংখ্যা আলাদা আলাদা করে লিখেছি। কারণ এখানে বুঝানো হচ্ছে যে, ১ ও ২ নং নোডের মধ্যে একটা এজ আছে, আবার ২ ও ৩ নং নোডের মধ্যে একটা এজ আছে ইত্যাদি।</p><p>এখানে একটা কথা বলে রাখি, আমরা আমাদের আলোচনা আপাতত <strong><em>simple graph</em></strong> এর মধ্যেই সীমাবদ্ধ রাখবো। <strong><em>simple graph</em></strong> হচ্ছে সেই সকল গ্রাফ যেই গ্রাফে লুপ (<strong><em>loop</em></strong>) ও মাল্টিপল এজ (<strong><em>multiple edges</em></strong>) নাই। নিচের উদাহরণটা দেখলেই বিষয় দুইটি পরিষ্কার হয়ে যাবে আশা করছি।</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/387/1*4Xo6cS3repCNE3xdyyK1-w.png" /></figure><p>ছবি ৬ এ আমরা একটি গ্রাফ দেখিয়েছি যার নাম দিয়েছি <strong><em>L</em></strong>, এই গ্রাফে খেয়াল করলে দেখা যাবে যে ২ ও ৩ নং নোডের মধ্যে একাধিক এজ আছে। এই বিষয়টিকে বলে একাধিক এজ বা <strong><em>multiple edges</em></strong>। আবার ১ নং নোডের দিকে খেয়াল করলে দেখা যাবে যে, এই নোড থেকে ৩, ৪ ও ৫ নং নোডের দিকে এজ বের হয়ে গেছে। আরেকটু খেয়াল করলে দেখা যাবে যে, আরেকটা এজ ১ নং থেকে বের হয়ে আবার নিজের মধ্যেই প্রবেশ করছে। এই বিষয়টিকে বলা হয় লুপ।</p><p>কোন গ্রাফে যতগুলো নোড থাকে তাকে ঐ গ্রাফের অর্ডার (<strong><em>order</em></strong>) বলে। বিষয়টিকে নিচের প্রতীক দিয়ে প্রকাশ করা হয়,</p><p><strong>|V| =</strong> গ্রাফের অর্ডার</p><p>আবার কোন গ্রাফে যতগুলো এজ থাকে তাকে ঐ গ্রাফের আকার (<strong><em>size of the graph</em></strong>) বলে। এটাকে প্রকাশ করা হয়,</p><p><strong>|E| =</strong> গ্রাফের আকার</p><p>উদাহরণস্বরূপ আমরা ছবি ৫ এর ২ নং গ্রাফের ক্ষেত্রে বলতে পারি, <strong><em>F</em></strong> গ্রাফের অর্ডার হচ্ছে ৪ এবং গ্রাফের আকারও হচ্ছে ৪। এইক্ষেত্রে অর্ডার ও আকার সমান হয়েছে মানে যে সবক্ষেত্রেই হবে তা নয়।</p><p>এবার আমরা কিছু <strong><em>notation</em></strong> বা প্রতীকের সাথে পরিচিত হবো, সেজন্য নিচের উদাহরণটা দেখা যেতে পারে।</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/368/1*UXQfcRTaSVhxqJdfAlkL2A.png" /></figure><p>উপরের গ্রাফের নাম দেয়া হয়েছে <strong><em>G</em></strong>। আমরা এই গ্রাফকে <strong><em>G = (V(G), E(G))</em></strong> দিয়েও প্রকাশ করতে পারি। এখানে <strong><em>V(G)</em></strong> দ্বারা নোডের সেট ও <strong><em>E(G)</em></strong> দ্বারা এজের সেট বুঝানো হয় আর <strong><em>V</em></strong> ও <strong><em>E</em></strong> এর পাশে <strong><em>G</em></strong> লিখে বুঝানো হয়েছে যে এই নোডগুলো ও এজগুলো হচ্ছে উমুক গ্রাফের এবং এদের সমষ্টিই হচ্ছে গ্রাফ। তাহলে আমরা লিখতে পারি,</p><p><strong>V = {V₁, V₂, V₃, V₄, V₅}</strong> ও</p><p><strong>E = {V₁V₂, V₂V₃, V₃V₄, V₄V₁, V₁V₅}</strong></p><p>অর্থাৎ নোডের সেটে কি কি নোড আছে সেগুলো এবং এজের সেটে কোন্ নোডের সাথে কোন্ নোডের সম্পর্ক আছে সেটা আমরা লিখবো। এখানে যেমন একটা এজ আছে <strong><em>V₁V₂</em></strong>, এখানে <strong><em>V₁</em></strong> হচ্ছে একটা প্রান্ত ও <strong><em>V₂</em></strong> হচ্ছে আরেকটা প্রান্ত। এদেরকে আমরা <strong><em>adjacent</em></strong> বা প্রতিবেশী (<strong><em>neighbours</em></strong>) নোড বলতে পারি। তাহলে দুটো নোড এজ দ্বারা যুক্ত থাকলে তারা হচ্ছে <strong><em>adjacent nodes</em></strong>।</p><p>মনে করি <strong><em>V₁V₂</em></strong> এজের নাম দিলাম <strong><em>E₁</em></strong> এবং <strong><em>V₁V₅</em></strong> এজের নাম দিলাম <strong><em>E₂</em></strong>। এই দুটি এজের মধ্যে <strong><em>V₁</em></strong> নোডটি দুটি এজেই আছে। তাই <strong><em>E₁</em></strong> ও <strong><em>E₂</em></strong> কে আমরা প্রতিবেশী বা <strong><em>adjacent</em></strong> এজ বলতে পারি অর্থাৎ <strong><em>V₁</em></strong> নোডটি <strong><em>E₁</em></strong> ও <strong><em>E₂</em></strong> এজকে প্রতিবেশি বানিয়েছে। আরও একটি উদাহরণ দেখা যেতে পারে,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/223/1*eft9_mZqEuFSf9y8PupySA.png" /></figure><p>উপরের গ্রাফটি হচ্ছে একটি বিচ্ছিন্ন গ্রাফ বা <strong><em>disconnected graph</em></strong>। কারণ এই গ্রাফে <strong><em>c</em></strong> নোডটির সাথে অন্য কারও সম্পর্ক নাই বা এটা সবার থেকে বিচ্ছিন্ন। এই গ্রাফের ক্ষেত্রে লিখা যায়, <strong><em>V = {a, b, c}</em></strong> এবং <strong><em>E = {ab}.</em></strong></p><p>এখন আমরা বিভিন্ন প্রকার গ্রাফ দেখবো, ওই শ্রেণীবিভাগ আরকি!</p><p>সম্পূর্ণ বা <strong><em>complete graph:</em></strong> যখন কোন গ্রাফের প্রতিটি নোড প্রতিটির সাথে এজ দ্বারা যুক্ত থাকে তখন তাকে আমরা <strong><em>complete graph</em></strong> বলি। এই গ্রাফকে সাধারণত <strong><em>Kₙ</em></strong> দ্বারা প্রকাশ করা হয়ে থাকে। এখানে <strong><em>n</em></strong> দ্বারা নোডের সংখ্যা বুঝানো হয়েছে। নিচে কয়েকটি <strong><em>complete graph</em></strong> দেখানো হল। কোন <strong><em>complete graph</em></strong> এ কতগুলো এজ আছে সেটা বের করার একটি সূত্র আছে। এজের সংখ্যা = <strong><em>ⁿC₂</em></strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/837/1*ccprzOsjq4ne--dgYzbosw.png" /></figure><p>সম্পূর্ণ গ্রাফ বা <strong><em>complete graph</em></strong> এর ক্ষেত্রেই এজসংখ্যা সর্বাধিক (<strong><em>simple graph</em></strong> এর আলোচনায়) হয় আর সেটা আমরা দেখলাম, <strong><em>|E| = ⁿC₂</em></strong></p><p>তাহলে অন্য যে কোন গ্রাফের ক্ষেত্রে লিখা যায়,<strong><em>|E|&lt; ⁿC₂</em></strong></p><p>সবমিলিয়ে বলা যায়, যে কোন গ্রাফের ক্ষেত্রে, <strong><em>|E| ≤ ⁿC₂</em></strong>.</p><p>শূন্য বা <strong><em>empty graph:</em></strong> শূন্য গ্রাফ হচ্ছে সেই গ্রাফ যেই গ্রাফে যেকোন সংখ্যক নোড থাকতে পারে কিন্তু তাদের মধ্যে কোন এজ থাকবেনা, একটাও না। নিচে চারটি নোডের একটি শূন্য গ্রাফ দেখানো হল।</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/215/1*H9dZOFoQkZGHTDoZAZ--Qg.png" /></figure><p>বাইপারটাইট গ্রাফ (<strong><em>Bipartite graph</em></strong>): এই শব্দটির বাংলা করার বোধহয় খুব একটা প্রয়োজন নাই, ইংরেজি দিয়েই মনে রাখাটা ভালো হবে। এই ধরনের গ্রাফের সংজ্ঞা দেয়ার চেয়ে উদাহরণ দিয়ে বোঝাটা বেশি কাজে দিবে মনে হয়। তাই প্রথমে আমরা কিছু উদাহরণ দেখে নিই, তারপর নাহয় সংজ্ঞাটা দেখলাম। আর একটা কথা, গ্রাফ থিওরিতে বাইপারটাইট গ্রাফের বেশ গুরুত্ব আছে তাই এটা আমরা বেশ মনোযোগ দিয়ে পড়বো।</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/288/1*znURsU3grwxFe3H94yq6cQ.png" /></figure><p>বেশ রঙচঙে একটা গ্রাফ দেখা যাচ্ছে। খেয়াল করে দেখো, নীল রঙের নোডগুলোর নিজেদের মধ্যে কোন সম্পর্ক বা এজ নেই আবার টিয়া রঙের নোডগুলোর নিজেদের মধ্যেও কোন এজ নেই। কিন্তু নীল রঙের নোডগুলোর সাথে টিয়া রঙের নোডগুলোর এজ রয়েছে। এভাবে আমরা যদি কোন গ্রাফের সবগুলো নোডকে দুইভাগে ভাগ করে ফেলতে পারি, তাহলে সেই গ্রাফকে বাইপারটাইট গ্রাফ বলা হবে। এবার কিছু প্রতীক ব্যবহার করে এই গ্রাফকে বর্ণনা করার চেষ্টা করা যেতে পারে।</p><p>ধরি নীল রঙের নোডগুলোকে নিয়ে একটা সেট বানালাম, নাম দিলাম <strong><em>V₁</em></strong>। আর টিয়া রঙের নোডগুলোর সেটের নাম দেয়া হল <strong><em>V₂</em></strong>। তাহলে, <strong><em>V₁ = {a, b, c}</em></strong> এবং <strong><em>V₂ = {d, e}</em></strong>.</p><p>তাহলে আমরা একটি গ্রাফকে বাইপারটাইট বলবো যদি <strong><em>uv ∈ E</em></strong> এবং <strong><em>u ∈ V₁</em></strong> ও <strong><em>v ∈ V₂</em></strong> হয়। <strong><em>∈</em></strong> (<strong><em>epsilon</em></strong>) দিয়ে উপাদান বুঝানো হয়। তাহলে <strong><em>uv ∈ E</em></strong> দিয়ে আমরা বুঝবো <strong><em>uv</em></strong> হচ্ছে <strong><em>E</em></strong> সেটের একটি উপাদান। <strong><em>E</em></strong> হচ্ছে এজসমূহের সেট। তাহলে <strong><em>uv</em></strong> হচ্ছে গ্রাফের একটি এজ। এই এজের এক প্রান্ত (<strong><em>u</em></strong>) যদি প্রথম সেটের (<strong><em>V₁</em></strong>) হয় এবং অপর প্রান্ত (<strong><em>v</em></strong>) দ্বিতীয় সেটের (<strong><em>V₂</em></strong>) হয়, শুধুমাত্র সেইক্ষেত্রেই আমরা সেই গ্রাফকে বাইপারটাইট বলবো।</p><p>সম্পূর্ণ বাইপারটাইট গ্রাফ বা <strong><em>complete bipartite graph:</em></strong> যদি কোন বাইপারটাইট গ্রাফের প্রথম সেটের প্রতিটি নোড দ্বিতীয় সেটের প্রতিটি নোডের সাথে সম্পর্কযুক্ত থাকে তবে সেই গ্রাফকে আমরা <strong><em>complete bipartite graph</em></strong> বলবো। নিচে উদাহরণ ও এই গ্রাফকে কোন্ প্রতীক দিয়ে প্রকাশ করা হয় সেটা দেখানো হল।</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/633/1*GAe09e4E1tD1rbBENHrkdw.png" /></figure><p>তাহলে ছবি ১২ এর গ্রাফকে <strong><em>K₃, ₂</em></strong> দ্বারা প্রকাশ করা যায়।</p><p>এক ধরনের বিশেষ <strong><em>complete bipartite graph</em></strong> আছে যাদেরকে <strong><em>star</em></strong> বলে। এই গ্রাফে প্রথম সেটে একটিমাত্র নোড থাকে এবং অপর সেটে যেকোন সংখ্যক নোড থাকতে পারে। নিচে এর উদাহরণ দেখানো হল।</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/186/1*Pj7z_RYVYS-DhGlJIULrAg.png" /></figure><p>এই গ্রাফকে আমরা <strong><em>K₁, ₃</em></strong> দ্বারা প্রকাশ করতে পারি।</p><p>এখন আমরা পথ (<strong><em>path</em></strong>) ও চক্র (<strong><em>cycle</em></strong>) নিয়ে কথা বলবো। সংজ্ঞা দেখার আগে উদাহরণ দেখা বোধহয় ভালো হবে, নিচের উদাহরণটা খেয়াল করি।</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/850/1*GraEKR43abIyEKmtxa_GRw.png" /></figure><p>ছবি দেখে নিশ্চয়ই বোঝা যাচ্ছে যে, <strong><em>path</em></strong> কে <strong><em>P</em></strong> দ্বারা ও <strong><em>cycle</em></strong> কে <strong><em>C</em></strong> দ্বারা প্রকাশ করা হয়। আর একটি বিষয় বুঝতে কষ্ট হওয়ার কথা নয় যে, যতগুলো নোড থাকবে সেই সংখ্যাটা <strong><em>P</em></strong> বা <strong><em>C</em></strong> এর পায়ের কাছে (<strong><em>subscript</em></strong>) লিখে দিলেই হবে। আমরা যদি <strong><em>path</em></strong> এর শেষ নোডটিকে প্রথম নোডের সাথে একটা এজ দিয়ে যুক্ত করে দিই তাহলে সেটি <strong><em>cycle</em></strong> এ পরিণত হবে। আশা করি বুঝতে কষ্ট হচ্ছেনা।</p><p>তাহলে আমরা <strong><em>path</em></strong> বলতে কি বুঝলাম? কিছু নোডকে যদি আমরা পরপর সাজিয়ে এজ দিয়ে যুক্ত করে দিই তাহলেই <strong><em>path</em></strong> তৈরি হয়ে যায়। ছবি ১৪ এর <strong><em>path</em></strong> এর এজগুলোকে যদি লিখি, <strong><em>E = {V₁V₂, V₂V₃, V₃V₄}</em></strong></p><p>খেয়াল করে দেখো “ভি ওয়ান” এর পরে “ভি টু” আছে, আবার “ভি টু” এর পরে “ভি থ্রি” আছে; এভাবেই চলতে থাকবে। যদি অনেকগুলো এজ থাকে সেক্ষেত্রে আমরা প্রতিটি এজের নাম লিখে <strong><em>E</em></strong> সেট লিখতে পারবোনা, খাতা শেষ হয়ে যাবে! তাহলে উপায়? আমরা ছোট ক্লাসে পড়ে এসেছি সেট দুইভাবে লিখা যায়, একটা হচ্ছে তালিকা পদ্ধতি এবং আরেকটা হচ্ছে সেট বিল্ডার পদ্ধতি। যখন সেটের উপাদান সংখ্যা কম থাকে তখন আমরা প্রতিটি উপাদান কমা দিয়ে আলাদা আলাদা করে লিখে ফেলি, এটা হচ্ছে তালিকা পদ্ধতি। এই পদ্ধতিতে এতক্ষণ আমরা সেট লিখে এসেছি।</p><p>কিন্তু যদি এজের সংখ্যা কয়েকশ হয়! তখন আমরাকে সেই সেট “বিল্ডার পদ্ধতি” তে লিখতে হবে। <strong><em>path</em></strong> এর এজসমূহের সেট নিচে বিল্ডার পদ্ধতিতে দেখানো হল,</p><p><strong><em>E = {VᵢVᵢ</em></strong>₊₁ | <strong><em>i = 1, 2, 3, ………, n-1}</em></strong></p><p>প্রথমে আমরা সেটের নাম দিয়ে দিলাম (<strong><em>E</em></strong>), এরপর “সমান” দিয়ে দ্বিতীয় বন্ধনী শুরু হয়ে গেলো। এরপর আমরা যে অংশটা (<strong><em>VᵢVᵢ</em></strong>₊₁) লিখেছি সেটা দিয়ে বুঝানো হয়েছে আমাদের এই সেটের উপাদানগুলোর চেহারা কেমন হবে। এটা বুঝতে নিশ্চয়ই সমস্যা হওয়ার কথা না যে, আমরা এজগুলো এভাবেই লিখে থাকি। এবার আসি পায়ের কাছে <strong><em>i</em></strong> ও <strong><em>i+1</em></strong> এর কথায়। খেয়াল করলেই বুঝা যাবে যে, <strong><em>i</em></strong> এর মান প্রথম প্রান্তে যত হবে শেষ প্রান্তে তার চেয়ে এক বেশি হবে যেমন <strong><em>V₃V₄</em></strong>।</p><p>আচ্ছা এবার দেখা যাক <strong><em>i</em></strong> এর মান কেন <strong><em>n-1</em></strong> পর্যন্ত। ধরি আমরা একটা <strong><em>path</em></strong> নিলাম যাতে ১০টি নোড আছে। অর্থাৎ <strong><em>n</em></strong> এর মান ১০। তাহলে <strong><em>i</em></strong> এর মান হবে ১০ - ১ = ৯ পর্যন্ত। তাহলে আমাদের এই <strong><em>path</em></strong> এর শেষ এজ হবে “ভি₉ভি₉₊₁”। তাই হওয়া উচিত নয় কি?</p><p>এখানে আর একটা তথ্য দেয়া যাক, প্রতিটি <strong><em>path</em></strong> ই হচ্ছে বাইপারটাইট। এটা দেখানো খুব সহজ, নিচের ছবিটি খেয়াল করি।</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/691/1*OGMho3D0x-2CtUZ0vYrNfw.png" /></figure><p>তাহলে <strong><em>cycle</em></strong> এর এজসমূহের সেটটা কেমন হওয়া উচিৎ?</p><p><strong><em>E = {VᵢVᵢ</em></strong>₊₁ | <strong><em>i = 1, 2, 3, ………, n-1}</em></strong> ∪ <strong><em>{V₁Vₙ}; n≥3</em></strong></p><p>এখানে প্রথম অংশটুকু <strong><em>path</em></strong> এর মতোই, কিন্তু ইউনিয়ন (∪) এর পরের অংশটা কেন আসলো? আমরা আগেই বলেছি যে, শুরু ও শেষের নোডটা জুড়ে দিলেই <strong><em>path</em></strong> হয়ে যায় <strong><em>cycle</em></strong>। এখানে তাই করা হয়েছে। তবে একটা শর্ত আছে যে, গ্রাফে নোডের সংখ্যা কমপক্ষে তিনটি হতে হবে নাহলে <strong><em>cycle</em></strong> হওয়া সম্ভব না। তুমি যদি দুটি নোড দিয়ে <strong><em>cycle</em></strong> বানাতে চাও সেখানে <strong><em>multiple edges</em></strong> চলে আসবে, সেটা আর <strong><em>simple graph</em></strong> থাকবেনা। নিচের ছবিটি খেয়াল করি।</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/215/1*7ec-8AS4opOYN2j33fVmDw.png" /></figure><p>তোমাকে যদি <strong><em>K₃</em></strong> বা <strong><em>C₃</em></strong> আঁকতে বলি, পারবানা? মনে আছে <strong><em>K₃</em></strong> বলতে কি বুঝায়? <strong><em>K₃</em></strong> হচ্ছে একটি <strong><em>complete graph</em></strong> যার নোডসংখ্যা হচ্ছে ৩। আর কিছুক্ষণ আগেই তো <strong><em>C₃</em></strong> দেখেছো। ব্যাপারটা মজার না? দুটো আসলে একই। এর একটি বিশেষ নাম আছে, <strong><em>triangle</em></strong>। এরকম নাম হওয়ার কারণ খুবই সোজা। <strong><em>triangle</em></strong> মানে যে ত্রিভুজ সেটা তো আর বলে দিতে হচ্ছেনা।</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/389/1*AuViZ9prAjvhkb69YhrDhw.png" /></figure><p>গ্রাফের যে বংশপরিচয় নিয়ে পড়তে বসেছিলাম তার শেষের দিকে চলে এসেছি। এখন আমরা যুক্ত গ্রাফ (<strong><em>connected graph</em></strong>) ও নিয়মিত গ্রাফ (<strong><em>regular graph</em></strong>) সম্পর্কে খানিকটা জেনে নিয়ে এই অংশের আলোচনা শেষ করবো।</p><p>এবারও আমরা আগে কয়েকটা উদাহরণ দেখে নিয়ে সংজ্ঞার দিকে মনোযোগ দিবো। নিচের উদাহরণগুলো একটু দেখি,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*raCXfE_lqAZ820E971y7MA.png" /></figure><p>আশা করছি ছবি ১৭ দেখেই বোঝা যাচ্ছে যে বিষয়টা কি। যদি আমরা কোন গ্রাফের একটি নোড থেকে এজ ধরে ধরে অন্য যে কোন নোডে চলে যেতে পারি তাহলে সেই গ্রাফকে আমরা বলবো <strong><em>connected graph</em></strong>। যেমন উপরের ছবির সবশেষের গ্রাফটির দিকে খেয়াল করলে দেখা যাবে যে, আমরা <strong><em>a</em></strong> নোড থেকে যাত্রা আরম্ভ করে কোনভাবেও <strong><em>b</em></strong> বা <strong><em>e</em></strong> নোডে যেতে পারবোনা, তাহলে এটি নিঃসন্দেহে একটি <strong><em>disconnected graph</em></strong>। এবার প্রতিবেশি বা <strong><em>neighbour/adjacent</em></strong> নোড নিয়ে দুটো কথা বলে নেয়া যাক। নিচের ছবিটি খেয়াল করি,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/470/1*fiwvqit_nNsqWLb_Vo6Cyg.png" /></figure><p>উপরের ছবি ১৮ থেকে আমরা দেখতে পাচ্ছি যে, <strong><em>a</em></strong> নোডের সাথে <strong><em>b, c, d</em></strong> এর সম্পর্ক আছে। এই সম্পর্ককে <strong><em>open neighbourhood</em></strong> বলে। এটা লিখার একটা নিয়ম আছে, সেটা হচ্ছে,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/737/1*YcT-E8A8tSlxTpXpPWDtKQ.png" /></figure><p>উপরের নিয়ম মেনে যদি আমরা এখন <strong><em>a</em></strong> নোডের <strong><em>open neighbourhood</em></strong> লিখতে চাই, <strong><em>N(a) = {b, c, d}.</em></strong></p><p>এবার আমরা <strong><em>a</em></strong> নোডের <strong><em>closed neighbourhood</em></strong> লিখতে চাই, <strong><em>N[a] = {b, c, d, a}.</em></strong></p><p>তাহলে <strong><em>open</em></strong> ও <strong><em>closed neighbourhood</em></strong> এর মধ্যে পার্থক্য হচ্ছে যে, <strong><em>closed neighbourhood</em></strong> এ নোডটি নিজেও উপস্থিত থাকবে এবং এটা প্রকাশ করার জন্য আমরা তৃতীয় বন্ধনী ((<strong><em>a</em></strong>) এর স্থলে [<strong><em>a</em></strong>] ব্যবহার করা হয়েছে) ব্যবহার করবো।</p><p>তোমাদের নিশ্চয়ই মনে আছে, কোন নোডের ডিগ্রি বলতে কি বোঝায়। কোন নোডের ডিগ্রি বলতে বোঝায় যে, ওই নোড থেকে কতগুলো এজ বের হয়েছে। আমরা যেহেতু এখন পর্যন্ত <strong><em>simple graph</em></strong> নিয়ে পড়াশোনা করছি তাই বলতে পারি যে, কোন দুটি নোডের মধ্যে একাধিক এজ নেই। তাহলে কোন নোডের প্রতিবেশি যতগুলো, ওই নোড থেকে ততগুলোই এজ বের হয়েছে। অতএব কোন নোডের ডিগ্রি বলতে তার প্রতিবেশির সংখ্যাকেই বুঝাচ্ছে। সুতরাং আমরা লিখতে পারি যে,</p><p><strong><em>deg(v) =| N(v)|</em></strong></p><p>এবার সময় এসেছে নিয়মিত বা <strong><em>regular graph</em></strong> নিয়ে জানার। যদি কোন গ্রাফের সবগুলো নোডের ডিগ্রি একই হয় তাহলে তাকে আমরা <strong><em>regular graph</em></strong> বলবো। প্রতিটি নোডের যত ডিগ্রি হবে সেই গ্রাফকে “তত” রেগুলার গ্রাফ বলা হবে। উদাহরণস্বরূপ, যদি কোন গ্রাফের প্রতিটি নোডের ডিগ্রি ২ করে হয়, তাহলে সেই গ্রাফের নাম <strong><em>2-regular</em></strong>। নিচের ছবিগুলো খেয়াল করো,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/640/1*XDd_U2k6gizrYrIjotn9Hw.png" /></figure><p>এবার কয়েকটি গুরুত্বপূর্ণ কথা বলে এই অংশের আলোচনা শেষ করা যাক। <strong><em>path</em></strong> কখনই <strong><em>regular</em></strong> হতে পারেনা, কারণ একটু মনে করে দেখো <strong><em>path</em></strong> এর প্রথম ও শেষের নোডের ডিগ্রি ১, কিন্তু ভেতরের নোডগুলোর ডিগ্রি ২। আবার <strong><em>cycle</em></strong> সবসময় <strong><em>2-regular</em></strong> হবে, ব্যাখ্যা নিজে নিজেই করো। আরেকটা মজার সম্পর্ক আছে, সম্পূর্ণ বা <strong><em>complete graph</em></strong> (<strong><em>Kₙ</em></strong>) সবসময় <strong><em>(n-1)-regular</em></strong> হবে। এই ব্যাপারটাও তোমরা নিজে নিজে উদারহণ তৈরি করে দেখতে পারো।</p><p>ছবি ৭ থেকে দেখে আসো, <strong><em>deg(V₁)=3</em></strong> এবং <strong><em>deg(V₅)=1</em></strong>, অর্থাৎ ওই গ্রাফের সর্বোচ্চ ডিগ্রি ৩ ও সর্বনিম্ন ডিগ্রি ১। এই ব্যাপারটা প্রকাশের জন্য প্রতীক রয়েছে,</p><p>সর্বনিম্ন ডিগ্রি বা <strong><em>minimum degree</em></strong>: <strong><em>δ(G)</em></strong><br>সর্বোচ্চ ডিগ্রি বা <strong><em>maximum degree</em></strong>: <strong><em>∆(G)</em></strong></p><p>তাহলে <strong><em>n-regular graph</em></strong> এর জন্য, <strong><em>δ(G)</em></strong> = <strong><em>∆(G)</em></strong> = <strong><em>n</em></strong>.<br>কেননা <strong><em>regular graph</em></strong> এর সব নোডগুলোর ডিগ্রি একই।</p><p>অয়লার বাবাজিকে নিয়ে একটি তথ্য দিই। ২৯ আগস্ট, ১৯৭৩ সালে রাশিয়ান এক ভদ্রমহিলা (<strong><em>Tamara Smirnova</em></strong>) একটি গ্রহাণু আবিষ্কার করেন। এই ভদ্রমহিলা যেনতেন কেউ নন, উনি একজন জ্যোতির্বিজ্ঞানি। ওই গ্রহাণুর নাম রাখা হয় <strong><em>2002 Euler,</em></strong> বাবাজিকে সম্মান জানানোর জন্য।</p><p><a href="https://medium.com/%E0%A6%AA%E0%A7%8D%E0%A6%B0%E0%A7%8B%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AE%E0%A6%BF%E0%A6%82-%E0%A6%AA%E0%A6%BE%E0%A6%A4%E0%A6%BE/%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AB-%E0%A6%A5%E0%A6%BF%E0%A6%93%E0%A6%B0%E0%A6%BF-%E0%A6%AA%E0%A6%B0%E0%A7%8D%E0%A6%AC-%E0%A7%A9-ea5594bebe36"><strong>গ্রাফ থিওরি (পর্ব ৩) পড়তে ক্লিক করুন।</strong></a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=85aadc1e3810" width="1" height="1" alt=""><hr><p><a href="https://medium.com/%E0%A6%AA%E0%A7%8D%E0%A6%B0%E0%A7%8B%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AE%E0%A6%BF%E0%A6%82-%E0%A6%AA%E0%A6%BE%E0%A6%A4%E0%A6%BE/%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AB-%E0%A6%A5%E0%A6%BF%E0%A6%93%E0%A6%B0%E0%A6%BF-%E0%A6%AA%E0%A6%B0%E0%A7%8D%E0%A6%AC-%E0%A7%A8-85aadc1e3810">গ্রাফ থিওরি (পর্ব ২)</a> was originally published in <a href="https://medium.com/%E0%A6%AA%E0%A7%8D%E0%A6%B0%E0%A7%8B%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AE%E0%A6%BF%E0%A6%82-%E0%A6%AA%E0%A6%BE%E0%A6%A4%E0%A6%BE">প্রোগ্রামিং পাতা</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[গ্রাফ থিওরি (পর্ব ১)]]></title>
            <link>https://medium.com/%E0%A6%AA%E0%A7%8D%E0%A6%B0%E0%A7%8B%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AE%E0%A6%BF%E0%A6%82-%E0%A6%AA%E0%A6%BE%E0%A6%A4%E0%A6%BE/%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AB-%E0%A6%A5%E0%A6%BF%E0%A6%93%E0%A6%B0%E0%A6%BF-%E0%A6%AA%E0%A6%B0%E0%A7%8D%E0%A6%AC-%E0%A7%A7-9c177b2d49e5?source=rss-550534651e5d------2</link>
            <guid isPermaLink="false">https://medium.com/p/9c177b2d49e5</guid>
            <category><![CDATA[bangla]]></category>
            <category><![CDATA[software-engineering]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[graph-theory]]></category>
            <dc:creator><![CDATA[Ahsan Shafiq Shawon]]></dc:creator>
            <pubDate>Thu, 03 Jan 2019 17:24:08 GMT</pubDate>
            <atom:updated>2019-01-08T15:58:00.371Z</atom:updated>
            <content:encoded><![CDATA[<p><strong>প্রোগ্রামিং — ১</strong></p><p><strong>কালিনিনগ্রাদের প্রেগেল নদী</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*834hho4ppiWYHKm3Q6OGkA.jpeg" /><figcaption>Photo by <a href="https://unsplash.com/photos/qoAIlAmLJBU?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">oxana v</a> on <a href="https://unsplash.com/search/photos/map?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Unsplash</a></figcaption></figure><p>কালিনিনগ্রাদ নামটা আমার প্রথম নজরে আসে এবছর রাশিয়ায় ফুটবল বিশ্বকাপ অনুষ্ঠিত হওয়ার সময়। বিশ্বকাপ শুরু হওয়ার আগ দিয়ে ফিক্সচার জোগাড় করা নিয়ে সবার বেশ ব্যস্ততা থাকে, আমারও ছিল। এক ওষুধ কোম্পানির বেশ সুন্দর একখানা ফিক্সচার পেয়েও গেলাম, সেটা বাড়িতে টিভিরুমের দেয়ালে টানিয়ে দিয়ে কবে, কোথায়, কোন্ ম্যাচ হবে দেখতে লাগলাম। সেই সময় এই কালিনিনগ্রাদ নামটা প্রথমবার চোখে পড়লো। “রাশিয়া ২০১৮ ফিফা ফুটবল বিশ্বকাপ” উপলক্ষ্যে এখানে একটা সুন্দর স্টেডিয়াম বানানো হয়। “ক্রোয়েশিয়া বনাম নাইজেরিয়া” খেলা দিয়ে এই নতুন স্টেডিয়ামের বিশ্বকাপ যাত্রা শুরু হয়েছিল।</p><p>এবার আসি কেন এই নাম নিয়ে এত কথা বলছি সেটার আলোচনায়। এই কালিনিনগ্রাদ শহরের আগে নাম ছিল কনিগসবার্গ। ১২৫৫ সালে কনিগসবার্গ শহর প্রতিষ্ঠিত হয়। ১৯৪৫ সালে দ্বিতীয় বিশ্বযুদ্ধের সময় এই শহরে বেশ তান্ডব চলে। ১৯৪৬ সালে এই শহরটা জার্মানির দখল থেকে রাশিয়ার অন্তর্ভূক্ত হয়ে যায়। এই সময়ই এর নাম পাল্টে কালিনিনগ্রাদ করা হয়।</p><p>যাই হোক এইসব ইতিহাসের কথাবার্তা আজকের আলোচনার বিষয় নয়। আমরা বরং আমাদের নির্ধারিত আলোচনার দিকেই আগাই। অন্য কোনদিন সময়-সুযোগ পেলে হয়তো ইতিহাস নিয়ে গল্প করা যাবে। এই শহরে একটা নদী আছে যার নাম প্রেগেল। নদীটা এই শহরকে বেশ কয়েকটা ভাগ করে প্রবাহিত হয়েছে। নিচের ছবিটা খেয়াল করলে একটা ধারণা পাওয়া যাবে।</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/690/1*S7z7vpUdDiqKhtzmM1K1IQ.png" /></figure><p>নদীটা এমনভাবে কনিগসবার্গ শহরের মধ্য দিয়ে গেছে যে শহরের মধ্যেই দ্বীপ তৈরি হয়ে গেছে। ছবিতে দেখা যাচ্ছে শহরের বিভিন্ন অংশে যাওয়ার জন্য নদীর ওপর সাতটা ব্রীজ (লাল রং এর দাগগুলো) আছে। তোমাকে যদি প্রশ্ন করা হয় যে, “তুমি কি প্রতিটা ব্রীজ শুধুমাত্র একবার ব্যবহার করে পুরো শহরটা (দ্বীপগুলোসহ) ঘুরে আসতে পারবে?” প্রশ্নটা এমনিতে খুব সাধারণ মনে হলেও এটা মোটেও কোন সাধারণ প্রশ্ন না। ১৭৩৬ সালে এই প্রশ্নের উত্তর দিতে গিয়ে গণিতের একটা পুরোদস্তুর শাখাই তৈরি করে ফেলেন লিওনার্দ অয়লার (<strong><em>Leonhard Euler</em></strong>)। এই ভদ্রলোককে তুমি চোখ বন্ধ করে সর্বকালের সর্বসেরা গণিতবিদ বলে দিতে পারো। ইনার কথা বলতে শুরু করলে শেষ হবার না, তাই আপাতত ঝুঁকি নিলাম না। আচ্ছা তো যা বলছিলাম, অয়লার সাহেব যে শাখা তৈরি করে ফেলেন উপরের প্রশ্নের উত্তর দিতে গিয়ে, সেই শাখার নাম হচ্ছে ‘গ্রাফ থিওরি’।</p><p>আমাদের এই সিরিজের উদ্দেশ্য হচ্ছে গ্রাফ থিওরি সম্পর্কে মোটামুটি ধারণা তৈরি করা। প্রথম কয়েক পর্বে আমরা শুধু গ্রাফ থিওরি বোঝার চেষ্টা করবো, মোটেও কোড টোডের দিকে যাবোনা। তারমানে প্রথমদিকে প্রোগ্রামিং থাকবেনা বললেই চলে। যখন আমাদের গ্রাফ থিওরি সম্পর্কে কিছুটা অনুভূতি কাজ করা শুরু করবে তারপর গেলাম কোডিং ফোডিং এর দিকে, কেমন?</p><p>আর একটা তথ্য দিয়ে ভূমিকা শেষ করে পড়ালেখায় মন দিবো আমরা। সেটা হচ্ছে যে, অয়লারের সময় যে সাতটা ব্রীজ ছিল তার মধ্যে দুইটি ব্রীজ দ্বিতীয় বিশ্বযুদ্ধের সময় বোমা বিস্ফোরণের কারণে ধ্বংসপ্রাপ্ত হয় (উপরের ছবির ২ ও ৪ নং ব্রীজ), আরও দুইটি ব্রীজ পরবর্তীতে ভেঙ্গে ফেলে আধুনিক হাইওয়ে (উপরের ছবির ১ ও ৩ নং) বানানো হয়েছে, আর একটা ব্রীজ ১৯৩৫ সালে নতুন করে বানানো হয়। তারমানে দাঁড়ায় যে, অয়লারের সময়কার দুটি ব্রীজ এখন আছে।</p><p>এখন আমরা উপরের প্রশ্নটার উত্তর খোঁজার কাজ করতে পারি। এখানে বলে রাখা ভালো যে, যেখান থেকে আমরা যাত্রা শুরু করবো সেখানেই যে যাত্রা শেষ করতে হবে এমন কোন কথা নেই। পুরো শহর ঘুরতে হবে প্রতিটা ব্রীজ শুধুমাত্র একবার ব্যবহার করে, এটাই কাজ।</p><p>ধরি, আমরা শহরের <strong><em>A</em></strong> অংশে এখন আছি। তারমানে আমাদের <strong><em>A</em></strong> অংশ ঘুরাঘুরি করা হয়ে গেছে। এবার আমরা ২ নং ব্রীজ দিয়ে নিপফ দ্বীপে চলে আসলাম। এখন পর্যন্ত আমরা <strong><em>A</em></strong> অংশ আর নিপফ দ্বীপ ঘুরে ফেলেছি আর ২ নং ব্রীজ ব্যবহার করে ফেলেছি। এরপর ধরো আমরা ৫ নং ব্রীজ দিয়ে লোমসে দ্বীপে এসে একটু চা-পানি খেয়ে নিলাম। তাহলে আপডেট হচ্ছে <strong><em>A</em></strong> অংশ, নিপফ দ্বীপ ও লোমসে দ্বীপ দেখা শেষ আর ২ ও ৫ নং ব্রীজ ব্যবহার করা হয়ে গেছে। এবার হয়তো আমরা ৭ নং ব্রীজ ধরে <strong><em>B</em></strong> অংশে এসে ৪ নং ব্রীজ দিয়ে নিপফ দ্বীপ হয়ে ১ নং ব্রীজ দিয়ে আবার <strong><em>A</em></strong> অংশে চলে আসলাম। তাহলে সর্বশেষ আপডেট হচ্ছে, শহরের সবগুলো অংশ ঘুরাঘুরি শেষ এবং ২, ৫, ৭, ৪, ১ নং ব্রীজগুলো ব্যবহার করা শেষ। সবশেষে আমরা ৬ নং ব্রীজ ব্যবহার করে আবার লোমসে দ্বীপে এসে আমাদের যাত্রা শেষ করতে পারি। তাহলে ৬ নং ব্রীজটাও ব্যবহার করা হয়ে গেলো। কিন্তু এখানে এসে আমি আর কোনদিকে যেতে পারছিনা কারণ ৫ ও ৭ নং ব্রীজ আমার ব্যবহার করা হয়ে গেছে আগেই। এভাবে আমরা পুরো ভ্রমণটা ৩ নং ব্রীজ ব্যবহার না করেই শেষ করে ফেললাম। তুমি অন্যভাবেও ভ্রমণ করে দেখতে পারো, কিন্তু তুমি কখনোই সবগুলো ব্রীজ ব্যবহার করতে পারবেনা। লিওনার্দ অয়লারও তাই বলেছেন যে, সবগুলো ব্রীজ মাত্র একবার ব্যবহার করে পুরো শহর ভ্রমণ করা যাবেনা।</p><p>এখন তোমার মনে হতে পারে যে, ব্যাপারটা তো বেশ সহজই। তাহলে পুরো একটা গণিতের শাখার কি দরকার? আচ্ছা আমি যদি তোমাকে এখন এর চাইতেও বড় সমস্যা দেই, যেমন ধরো একটা দেশের মানচিত্র দিয়ে জিজ্ঞেস করলাম সবগুলো রাস্তা একবার ব্যবহার করে পুরো দেশ ঘুরতে পারবে? তখন কিন্তু তোমার হিসাব করতে জীবন শেষ হয়ে যাবে।</p><p>ঠিক এই জায়গাটাতেই অয়লার সাহেবের কীর্তি। তিনি এমন কিছু সূত্র বা কথাবার্তা বলে গেছেন যা আমরা ব্যবহার করে কম পরিশ্রমে বড় বড় সমস্যা সমাধান করে ফেলতে পারি। তোমরা সবাই কমবেশি গুগল ম্যাপ বা অন্য কোন কোম্পানির ম্যাপ সার্ভিস ব্যবহার করেছো। এই ধরনের ‘অ্যাপ’ গুলো তৈরি করতে গ্রাফ থিওরি ব্যাপকভাবে ব্যবহৃত হয়েছে।</p><p>এখন আমরা দেখবো যে, অয়লার কিভাবে এই সমস্যাটার সমাধান করেছিলেন। প্রথম কথা হচ্ছে যে, এই সমস্যাটা জ্যামিতি দিয়ে সমাধান করা যাবেনা। কারণ শহরের কোন্ অংশ অন্য অংশের সাথে কত ডিগ্রি কোণে অবস্থান করছে এরকম কোন ব্যাপার এই সমস্যা সমাধানের ক্ষেত্রে গুরুত্বপূর্ণ নয়। তাই আমরা বলতে পারি যে, এটা কোন জ্যামিতিক সমস্যা নয়। যেহেতু তৎকালীন কোন গণিতের শাখার সাথে এই সমস্যার সমাধানকে সম্পর্কযুক্ত করা যাচ্ছিল না, তাই অয়লার সাহেব নতুন শাখার গোড়াপত্তন করলেন।</p><p>তিনি বুঝতে পারলেন যে, শহরগুলোর বিভিন্ন অংশের সাথে অন্য অংশের সম্পর্কটাই হচ্ছে এই সমস্যার মূল ব্যাপার। এক্ষেত্রে সম্পর্কগুলো স্থাপন করেছে ব্রীজগুলো। তিনি ছবি ১ কে নিচের ছবির মতো করে রূপান্তরিত করে ফেললেন।</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/389/1*A-gyWxqNOagIAbl1UxAefg.png" /></figure><p>আচ্ছা এই ছবিতে আমরা কি করেছি সেটা আগে বলে ফেলি। ছবি ১ এ <strong><em>A</em></strong> ও <strong><em>B</em></strong> বলতে যা বুঝানো হয়েছে এখানেও তাই। ছবি ১ এর নিপফ দ্বীপ ও লোমসে দ্বীপকে ছবি ২ এ যথাক্রমে <strong><em>C</em></strong> ও <strong><em>D</em></strong> দ্বারা আমরা চিহ্নিত করেছি। আর লাল দাগগুলো ব্রীজকে নির্দেশ করছে এটা বুঝতে আশা করি কারও সমস্যা নাই। এবার তোমরা ছবি ১ ও ছবি ২ কে তুলনা করলে দেখবে যে, আসলে দুটো ছবি একই। তোমাদেরকে অনেক অভিনন্দন কারণ তোমরা ইতিমধ্যেই ছবি ২ এ একটি গ্রাফ দেখতে পাচ্ছো। আমাদের প্রথম গ্রাফ।</p><p>আমরা যে গোল গোলগুলো দিয়ে ছবি ২ এ শহরের বিভিন্ন অংশ বুঝিয়েছি তাদেরকে গ্রাফ থিওরির ভাষায় বলা হয় নোড (<strong><em>Node</em></strong>) বা ভার্টেক্স (<strong><em>Vertex</em></strong>)। আর যে লাল দাগুলোগ দিয়ে ব্রীজ বুঝিয়েছি তাদেরকে গ্রাফ থিওরির ভাষায় বলা হয় এজ (<strong><em>Edge</em></strong>)। তাহলে মোদ্দা কথা দাঁড়ালো যে, নোড হচ্ছে সেইসব জিনিসপত্র যাদের মধ্যে অন্য কারও আদৌ সম্পর্ক আছে কিনা সেটা আমরা এজ দিয়ে প্রকাশ করি। যেমন ছবি ২ থেকে বলা যায় যে, শহরের <strong><em>B</em></strong> অংশের সাথে <strong><em>A</em></strong> অংশের সরাসরি কোন এজ নাই মানে এদের মধ্যে সরাসরি কোন সম্পর্ক নাই।</p><p>এখন আমরা দেখবো যে, অয়লার সাহেব কিভাবে একদম আমাদের মুখের ওপর বলে দিলেন যে সবগুলো ব্রীজ একবার ব্যবহার করে পুরো শহর ঘুরে আসা যাবেনা। আমরা ছবি ২ হতে ৫ নং এজটা (<strong><em>edge</em></strong>) সরিয়ে ফেলে নতুন করে চেষ্টা করবো যেন সবগুলো ব্রীজ একবার ব্যবহার করে পুরো শহর ঘুরে আসা যায়। তোমরা এখন আমাকে জিজ্ঞেস করতে পারো, কেন আমরা এরকম করবো? আমি বলবো, আরে করেই দেখিনা কি হয়!! উত্তরটা নাহয় পরেই দেয়া গেলো।</p><p>আচ্ছা তাহলে নিচের ছবি ৩ কে একটু খেয়াল করো, আমরা যাত্রা শুরু করলাম <strong><em>B</em></strong> থেকে। <strong><em>B</em></strong> থেকে ৩ নং ব্রীজ ব্যবহার করে <strong><em>C</em></strong> তে আসলাম। এবার <strong><em>C</em></strong> থেকে ১ নং ব্রীজ ব্যবহার করে <strong><em>A</em></strong> তে আসলাম। আপডেট হচ্ছে <strong><em>B</em></strong>, <strong><em>C</em></strong>, <strong><em>A</em></strong> ঘুরাঘুরি শেষ এবং ১ ও ৩ নং ব্রীজ ব্যবহার করা হয়েছে। এবার আমরা আবার <strong><em>A</em></strong> থেকে <strong><em>C</em></strong> তে ২ নং ব্রীজ এবং <strong><em>C</em></strong> থেকে <strong><em>B</em></strong> তে ৪ নং ব্রীজ ব্যবহার করে চলে আসলাম। অবশেষে <strong><em>B</em></strong> থেকে ৭ নং ব্রীজ ব্যবহার করে <strong><em>D</em></strong> তে এবং <strong><em>D</em></strong> থেকে ৬ নং ব্রীজ ব্যবহার করে <strong><em>A</em></strong> তে এসে যাত্রা শেষ করলাম।</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/389/1*G5WZ9d4ew_fF8JYdpqNUjQ.png" /></figure><p>খেয়াল করে দেখো আমরা পুরো শহর ভ্রমণ করেছি কোন ব্রীজ একবারের বেশি ব্যবহার না করে আর ব্যবহার করিনি এরকম কোন ব্রীজও বাকি নাই।</p><p>যখন আমরা কোন গ্রাফের প্রতিটি নোড ঘুরে আসতে পারি প্রতিটি এজ শুধুমাত্র একবার ব্যবহার করে (যেমনটা উপরের ছবি ৩ এ করতে পেরেছি), তখন এই যাত্রাকে বা ঘুরাঘুরিকে <strong><em>Eulerian walk</em></strong> বলে। এখানে যাত্রা বা <strong><em>walk</em></strong> বা হাঁটা বলার কারণ নিশ্চয়ই বুঝতে সমস্যা হচ্ছেনা, আমরা তো পুরো গ্রাফটা ঘুরেই বেড়িয়েছি, তাই না?</p><p>তাহলে দেখা যাচ্ছে যে, ছবি ২ এ এই <strong><em>Eulerian walk</em></strong> পাওয়া যাচ্ছেনা। এখন আমরা দেখবো কখন <strong><em>Eulerian walk</em></strong> পাওয়া সম্ভব এবং কখন নয়। আলোচনার জন্য নিচের ছবিটি খেয়াল করি। এখানে দুটি গ্রাফ দেখা যাচ্ছে, প্রথম গ্রাফটিতে একটি নোড ও চারটি এজ আছে এবং দ্বিতীয়টিতে একটি নোড ও পাঁচটি এজ আছে। কোন নোডের যতগুলো এজ থাকে তাকে ঐ নোডের ডিগ্রি (<strong><em>Degree</em></strong>) বলে। তাহলে প্রথম গ্রাফটির নোডের ক্ষেত্রে আমরা বলতে পারি যে, এই নোডের ডিগ্রি হচ্ছে ৪।</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/678/1*q-sa4d3UtvUdFioIQ7OWdg.png" /></figure><p>ছবি ৪ এর প্রথম গ্রাফটির ক্ষেত্রে, ধরলাম আমরা ১ নং এজ দিয়ে নোডে প্রবেশ করলাম, দিয়ে ৪ নং এজ দিয়ে বের হয়ে গেলাম। তারপর বাইরে একটু ঘুরাঘুরি করে আবার ৩ নং এজ দিয়ে প্রবেশ করে ২ নং এজ দিয়ে বের হয়ে গেলাম। এর অর্থ হচ্ছে যে আমরা সবগুলো এজ দিয়েই গেছি কিন্তু নোডে আটকা পড়িনি। কিন্তু দ্বিতীয় গ্রাফে যদি আমরা খেয়াল করি তাহলে দেখা যাবে যে, ১ নং এজ দিয়ে প্রবেশ করলাম, ৫ নং দিয়ে বের হলাম, আবার ৪ নং দিয়ে প্রবেশ করে ৩ নং দিয়ে বের হলাম, ২ নং দিয়ে প্রবেশ করে আর বের হতে পারছিনা কারণ সবগুলো এজ আমার ব্যবহার করা হয়ে গেছে। অর্থাৎ আমি নোডে আটকা পড়ে গেছি।</p><p>উপরের উদাহরণ থেকে আমরা একটা সিদ্ধান্ত নিতে পারি যে, গ্রাফের কোন একটি নোড যদি শুরুর নোড বা শেষের নোড না হয় (যেমন ছবি ৩ এর যাত্রা শুরুর নোড ছিল <strong><em>B</em></strong> এবং শেষের নোড ছিল <strong><em>A</em></strong>) তাহলে তার ডিগ্রি হবে জোড়। ছবি ৪ এ আমরা ১ নং এজ দিয়ে নোডে প্রবেশ করেছিলাম অর্থাৎ এই নোডটা আমাদের শুরুর নোড নয়, কারণ আমরা তো এখান থেকে শুরু করিনি। অন্য কোথাও থেকে শুরু করে এই নোডে এসে প্রবেশ করেছি। আবার শেষে ২ নং এজ দিয়ে বের হয়ে গেছি অর্থাৎ এই নোডটা শেষের নোডও নয়। কারণ আমরা এই নোডে শেষ করছিনা, অন্য কোথাও চলে যাচ্ছি ২ নং এজ দিয়ে।</p><p><strong>সিদ্ধান্তঃ যে নোডটা শুরুর (যাত্রা) বা শেষের নয় তার ডিগ্রি হবে জোড়।</strong></p><p>আবার ছবি ৪ এর দ্বিতীয় গ্রাফটায় আমরা দেখতে পাচ্ছি, নোডের ডিগ্রি বিজোড় (৫টি)। আমরা বাইরে থেকে শুরু করলে অর্থাৎ ১ নং এজ দিয়ে প্রবেশ করলে, শেষে ২ নং এজ দিয়ে প্রবেশ করে আটকা পড়ে যাচ্ছি। তাহলে আমরাকে এই নোডে থেমে যেতে হচ্ছে, অর্থাৎ এটা শেষের নোড। আবার যদি আমরা এই নোড থেকে শুরু করি তাহলে ১ নং দিয়ে বের হয়ে ৫ নং দিয়ে প্রবেশ করে আবার ৪ নং দিয়ে বের হয়ে ৩ নং দিয়ে প্রবেশ করে ২ নং দিয়ে বের হয়ে যেতে পারবো। তাহলে এটা হবে শুরুর নোড।</p><p><strong>সিদ্ধান্তঃ যে নোডটা শুরুর বা শেষের তার ডিগ্রি হবে বিজোড়। [এখানে শুরুর নোড বলতে আমরা যে নোড দিয়ে গ্রাফে চলা শুরু করছি এবং শেষের নোড বলতে যে নোড দিয়ে আমরা গ্রাফে চলা শেষ করছি।]</strong></p><p>ছবি ২ এ, আমাদের শুরুর নোড এবং শেষের নোড আলাদা (যথাক্রমে <strong><em>B</em></strong> ও <strong><em>A</em></strong>)। এরা যেহেতু শুরুর বা শেষের নোড তাই এদের ডিগ্রি হবে বিজোড়। তাহলে দুুটি (দুই কিন্তু জোড় সংখ্যা!!) নোডের ডিগ্রি সংখ্যা হচ্ছে বিজোড়।</p><p><strong>সিদ্ধান্তঃ যদি কোন গ্রাফের শুরু এবং শেষের নোড আলাদা হয় তাহলে বিজোড় ডিগ্রির নোডের সংখ্যা হবে দুই।</strong></p><p>কিন্তু যদি গ্রাফের শুরু এবং শেষ একই নোডে হয় তাহলে কি হবে? ছবি ৪ এর প্রথম গ্রাফটিতে যদি আমরা ওই নোড থেকেই শুরু করি এবং ১ নং এজ দিয়ে বের হয়ে ৪ নং দিয়ে প্রবেশ করে আবার ৩ নং দিয়ে বের হয়ে ২ নং দিয়ে প্রবেশ করি তাহলে যেখানে শুরু হয়েছিল সেখানেই শেষ হচ্ছে। এক্ষেত্রে বিজোড় ডিগ্রির নোড থাকছেনা অর্থাৎ শূন্যসংখ্যক থাকছে।</p><p><strong>সিদ্ধান্তঃ যদি কোন গ্রাফের শুরু এবং শেষের নোড একই হয় তাহলে বিজোড় ডিগ্রির নোডের সংখ্যা হবে শূন্য।</strong></p><p>এবার আমরা ফেরত যাবো ছবি ২ এ। এখানে, <strong><em>A</em></strong> নোডের ডিগ্রি ৩, <strong><em>B</em></strong> নোডের ডিগ্রি ৩, <strong><em>C</em></strong> নোডের ডিগ্রি ৫ এবং <strong><em>D</em></strong> নোডের ডিগ্রি ৩। অর্থাৎ এখানে বিজোড় ডিগ্রির নোডের সংখ্যা ৪। যেহেতু এই গ্রাফে শুরুর এবং শেষের নোড আলাদা তাই বিজোড় ডিগ্রির সংখ্যা দুই হলে এই গ্রাফে আমরা <strong><em>Eulerian walk</em></strong> পেতে পারতাম। কিন্তু বিজোড় ডিগ্রির নোডের সংখ্যা ৪ হওয়ায় আমরা এই গ্রাফে <strong><em>Eulerian walk</em></strong> পাইনি। এভাবেই অয়লার সাহেব সিদ্ধান্ত দিয়েছিলেন যে কনিগসবার্গ শহর ঘুরতে গিয়ে প্রতিটি ব্রীজ অন্তত একবার ব্যবহার করা সম্ভব না।</p><p>অয়লার সম্পর্কে একটা তথ্য জানিয়ে শেষ করি। অয়লারের ১৩টি বাচ্চাকাচ্চা ছিল, কিন্তু তাদের মধ্যে মাত্র ৫ জন বড় হয়েছিল এবং বাকিরা বাচ্চাকালেই মারা যায়।</p><p><a href="https://medium.com/%E0%A6%AA%E0%A7%8D%E0%A6%B0%E0%A7%8B%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AE%E0%A6%BF%E0%A6%82-%E0%A6%AA%E0%A6%BE%E0%A6%A4%E0%A6%BE/%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AB-%E0%A6%A5%E0%A6%BF%E0%A6%93%E0%A6%B0%E0%A6%BF-%E0%A6%AA%E0%A6%B0%E0%A7%8D%E0%A6%AC-%E0%A7%A8-85aadc1e3810"><strong>গ্রাফ থিওরি (পর্ব ২) পড়তে ক্লিক করুন।</strong></a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=9c177b2d49e5" width="1" height="1" alt=""><hr><p><a href="https://medium.com/%E0%A6%AA%E0%A7%8D%E0%A6%B0%E0%A7%8B%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AE%E0%A6%BF%E0%A6%82-%E0%A6%AA%E0%A6%BE%E0%A6%A4%E0%A6%BE/%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AB-%E0%A6%A5%E0%A6%BF%E0%A6%93%E0%A6%B0%E0%A6%BF-%E0%A6%AA%E0%A6%B0%E0%A7%8D%E0%A6%AC-%E0%A7%A7-9c177b2d49e5">গ্রাফ থিওরি (পর্ব ১)</a> was originally published in <a href="https://medium.com/%E0%A6%AA%E0%A7%8D%E0%A6%B0%E0%A7%8B%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AE%E0%A6%BF%E0%A6%82-%E0%A6%AA%E0%A6%BE%E0%A6%A4%E0%A6%BE">প্রোগ্রামিং পাতা</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>