বাইকানেক্টেড কম্পোনেন্ট , ব্রিজ, আরটিকুলেশন পয়েন্ট [ থিওরি ]

আগে জেনে আসা উচিত:    বেসিক গ্রাফ থিওরি , গ্রাফ কানেক্টিভিটি , DFS

এই পোস্ট এ আমরা থিওরি জানবো , পরে আরেকটি পোস্ট এ আমরা বাইকানেক্টেড কম্পোনেন্ট , ব্রিজ, আরটিকুলেশন পয়েন্ট বের করার অ্যালগোরিদম নিয়ে আলোচনা করব।

ধরো, তোমার একজন বন্ধুর নাম সাফওয়াত। তুমি এখন তার বাসায়ে যাবে, এখন তুমি একটা ম্যাপ বের করলে যেখানে তুমি থাকো 0 নং নোডে , এবং তোমার বন্ধু থাকে ৬ নং নোডে। নিচের গ্রাফ টি দেখঃ

bcc1

এখন খেয়াল কর , তুমি ০ থেকে ৫ নং নোডে ২ ধরনের রাস্তা ব্যবহার করতে পার। সেগুলো হচ্ছে-

১। ০ – > ১ – >৪ – > ৫

২। ০ -> ২ -> ৩ -> ৫

দুটো পথের কোন টাই কিন্তু কেউ কারো উপর দিয়ে যাচ্ছে না, তাই না ? কিন্তু যদি আমি ৬ নং নোডে যেতে চাই, তাহলেও দুটি পথ আছে,

১। ০ -> ১ -> ৪-> ৫-> ৬

২। ০ -> ২ -> ৩ -> ৫ ->৬

এখন দেখ, আমাকে ৫->৬ এই খানে দুটি পথ এক হয়ে গেছে। এক হয়ে গেছে তো কি হয়েছে ? একটা সমস্যা হয়ে যাচ্ছে, ধরো তুমি বন্ধুর বাসায়ে যাচ্ছ , ১ নং পথ ধরে, হঠাত ভুমিকম্প হল, আর ৪ থেকে ৫ এ যাওয়ার রাস্তা গেল ভেঙ্গে , তুমি গিয়ে দেখলে ৪ নং নোড থেকে ৫ নং  এ যাওয়া যাচ্ছে না, কিন্তু তোমাকে তো ৫ এ যেতেই হবে , নাইলে ৬ নং নোড এ যাওয়া যাবে না !

bcc9

কিন্তু তোমার কাছে তো ম্যাপ আছে, এবং তুমি দেখলে যে আরেক টা রাস্তা আছে , যেই টা ব্যবহার করে ৫ নং নোড এ যাওয়া যায়, তো তুমি ঘুরে আবার তোমার বাসায় এসে, ২য় পথ ধরে তুমি তোমার বন্ধুর বাসায় পৌছাইলা।

ব্রিজঃ

সাধারণ মানুষ হইলে , তুমি বন্ধুর বাসায় গিয়ে আড্ডা মেরে সুন্দর মত নিজের বাসায়ে চলে যাইতা! সমস্যা হইল তুমি একজন প্রব্লেম সল্ভার , তোমার মাথায়ে সবসময় চিন্তা আসে যে যদি এইটা হইত তাহলে কি হইত, অইটা কেন হইত না…..

একি কারনে তোমার মাথায়ে চিন্তা আসল যে যদি ভুমিকম্পে ৫->৬ এর রাস্তা টা নস্ট হয়ে যাইত, তাহলে কি করতা ? তাহলে কি আর কোন পথ ছিল বন্ধুর বাসায় যাওয়ার ? না, আর কোন পথ থাকত না । :(

আমি যদি গ্রাফ এর ৫ থেকে ৬ নং নোড এ যাওয়ার রাস্তা  টাকে বাদ দেই, তাহলে গ্রাফ টা দাড়ায় এরকম – 

bcc2

bcc8

তুমি এখন নিজেকেই প্রশ্ন করলা যে, যদি ভুমিকম্পে শুধুমাত্র একটি রাস্তা নষ্ট হয়, তারপরেও তোমার বাসা থেকে কোন কোন নোড এ যাওয়া যাবে এবং রাস্তা যেটাই নষ্ট হোক না কেন তুমি সবসময়ে অই নোড গুলা তে যেতে পারবে ? যেমন ধরো, যখন ৪ থেকে ৫ এর রাস্তা টা নষ্ট হইল , তখন কিন্তু তুমি ৬ নং নোড এ যেতে পারসো। কিন্তু যদি ৫ থেকে ৬ এর রাস্তা নষ্ট হইত , তাইলে কিন্তু ৬ নং নোড এ যেতে পারতা না। তারমানে যেকোনো একটি রাস্তা নষ্ট হলেও, সবসময়  তোমার বাসা থেকে  ৬ নং নোড এ যেতে পারবে না। তাহলে কোন কোন নোড এ যেতে পারবা ? গ্রাফ টার দিকে ভালো করে খেয়াল কর, নিজেই বের করতে পারো কিনা দেখ।

উত্তরঃ ১, ২, ৩, ৪, ৫ এই নোড গুলা তে যাইতে পারবা।

তাহলে দেখ যদি আমরা ৫ থেকে ৬ এ যাওয়ার রাস্তা গ্রাফ থেকে সরায়ে দেই, তাহলে গ্রাফ থিউরি এর ভাষায়ে গ্রাফ টা কিন্তু কানেক্টেড না। যেই রাস্তাকে [ edge ] বাদ দিলে পুরো গ্রাফ টি ডিস্কানেক্টেড হয়ে যাবে মানে সব নোড থেকে সব নোডে যাওয়া যাবে না,  অই রাস্তা বা edge কে বলা হয় ব্রিজ [Bridge] , আমাদের পদ্মা ব্রিজ এর কথা চিন্তা করতে পার। :)

ফরমাল ভাষায় বললে, যদি কোন এজ [ edge ]  কে একটি গ্রাফ থেকে বাদ দিলে,যদি গ্রাফ টা ডিস্কানেক্টেড হয় পরে বা দুই বা তার বেশী সাব গ্রাফ এ ভাগ হয়ে যায়, তাহলে অই এজ [edge] কে বলা হবে ব্রিজ [ Bridge ].

আরটিকুলেশন পয়েন্টঃ

এতক্ষন ০, ১, ২ এইগুলাকে নোড বললাম, ধরো এই গুলা একেক টা শহর, এখন ধরো, ৩ নং শহরে কারফিউ জারি করা হইল, তার মানে তুমি কারফিউ এর সময় অই শহর দিয়ে যেতে পারবা না। তাহলে ধরা যায় যে, ৩ নং নোড টা গ্রাফেই নাই ।

bcc4

bcc5

তাহলে দেখ এর পরেও কিন্তু তুমি সব নোড থেকে সব নোড এ  যেতে পারছ তাই না ? মানে তারা এখনও কানেক্টেড।

কিন্তু যদি ৫ নং নোড / শহরে কারফিউ জারি করা থাকতো , তখন গ্রাফ টা কেমন হইত ?

bcc6

bcc7

এই খানে দেখ, সব নোড থেকে সব নোড এ যাওয়া যাচ্ছে না। তারমানে গ্রাফ টা ডিসকানেক্টেড হয়ে যাচ্ছে। এই রকম অবস্থায় অই কারফিউ জারি করা নোড টা কে বলা হয় আরটিকুলেশন পয়েন্ট [ Articulation Point ] ।

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

এতক্ষন তো Articulation Point এবং Bridge নিয়া বললাম কিন্তু বাইকানেক্টেড কম্পোনেন্ট টা কি ? 

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

bcc11

নিচের দুইটা গ্রাফ এর পুরোটা কিন্তু বাইকানেক্টেড না , কেন ? কারন গ্রাফ গুলো তে আরটিকুলেশন পয়েন্ট আছে – 

bcc10

বরং তাদের সাব গ্রাফ গুলো একেকটা বাইকানেক্টেড কম্পোনেন্ট , যেমন -

bcc13

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

সব সংজ্ঞা এক সাথে:

 ব্রিজ: যদি কোন এজ [ edge ]  কে একটি গ্রাফ থেকে বাদ দিলে,যদি গ্রাফ টা ডিস্কানেক্টেড হয় পরে বা দুই বা তার বেশী সাব গ্রাফ এ ভাগ হয়ে যায়, তাহলে অই এজ [edge] কে বলা হবে ব্রিজ [ Bridge ].

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

 বাইকানেক্টেড কম্পোনেন্ট: যদি একটি গ্রাফে কোন আরটিকুলেশন পয়েন্ট না থাকে, তাহলে অই গ্রাফ টি একটি বাইকানেক্টেড কম্পোনেন্ট।

নিচে কয়েকটি গ্রাফ দেয়া হবে উত্তর বের করে মিলাও, উত্তর মিললে বুঝা যাবে যে , হ্যাঁ তুমি BCC, Bridge, Articulation point কি বুঝেছ।

১। নিচের গ্রাফ টা কি বাইকানেক্টেড ?

২। নিচের গ্রাফ টা কি বাইকানেক্টেড ? 

bcc6

৩। নিচের গ্রাফ টা কি বাইকানেক্টেড ?

৪। নিচের গ্রাফে কোন গুলো আরটিকুলেশন পয়েন্ট এবং কোন কোন সাব গ্রাফ বাইকানেক্টেড কম্পোনেন্ট?

 

৫। নিচের গ্রাফ এ কয়টি ব্রিজ এবং আরটিকুলেশন পয়েন্ট আছে ?

 

উত্তরঃ

১। হ্যাঁ

২। হ্যাঁ

৩। না,

৪। A, H, G, J এরা হচ্ছে AP, আর বাইকানেক্টেড কম্পোনেন্ট গুলো হচ্ছে – 

{A, C, G, D, E, F}, {G, J, L, B।}, B, H, I, K

৫। ৩ টা Bridge, ২ টা AP.

আরও জানতে:

১। http://en.wikipedia.org/wiki/Biconnected_component

২। http://www.ics.uci.edu/~dan/class/161/notes/8/Bicomps.html

৩। http://www.scribd.com/doc/56802813/Bridge-Algorithm