এজ কানেক্টিভিটি / ভার্টেক্স কানেক্টিভিটি#

সংজ্ঞা#

$n$ টি ভার্টেক্স এবং $m$ টি এজ বিশিষ্ট একটি অনির্দেশিত গ্রাফ $G$ দেওয়া আছে। এজ কানেক্টিভিটি এবং ভার্টেক্স কানেক্টিভিটি উভয়ই গ্রাফের বৈশিষ্ট্য বর্ণনাকারী পরিমাণ।

এজ কানেক্টিভিটি#

গ্রাফ $G$ এর এজ কানেক্টিভিটি $\lambda$ হলো সর্বনিম্ন সংখ্যক এজ যেগুলো মুছে ফেলতে হবে যাতে গ্রাফ $G$ বিচ্ছিন্ন হয়ে যায়।

উদাহরণস্বরূপ, একটি ইতিমধ্যে বিচ্ছিন্ন গ্রাফের এজ কানেক্টিভিটি $0$, কমপক্ষে একটি ব্রিজ বিশিষ্ট একটি কানেক্টেড গ্রাফের এজ কানেক্টিভিটি $1$, এবং কোনো ব্রিজবিহীন একটি কানেক্টেড গ্রাফের এজ কানেক্টিভিটি কমপক্ষে $2$।

আমরা বলি যে এজের একটি সেট $S$ ভার্টেক্স $s$ এবং $t$ কে বিচ্ছিন্ন করে, যদি গ্রাফ $G$ থেকে $S$ এর সমস্ত এজ সরিয়ে দেওয়ার পর, ভার্টেক্স $s$ এবং $t$ ভিন্ন কানেক্টেড কম্পোনেন্টে পড়ে।

এটি স্পষ্ট যে, একটি গ্রাফের এজ কানেক্টিভিটি হলো দুটি ভার্টেক্স $s$ এবং $t$ বিচ্ছিন্নকারী এমন সেটের সর্বনিম্ন আকার, সমস্ত সম্ভাব্য জোড়া $(s, t)$ এর মধ্যে নেওয়া।

ভার্টেক্স কানেক্টিভিটি#

গ্রাফ $G$ এর ভার্টেক্স কানেক্টিভিটি $\kappa$ হলো সর্বনিম্ন সংখ্যক ভার্টেক্স যেগুলো মুছে ফেলতে হবে যাতে গ্রাফ $G$ বিচ্ছিন্ন হয়ে যায়।

উদাহরণস্বরূপ, একটি ইতিমধ্যে বিচ্ছিন্ন গ্রাফের ভার্টেক্স কানেক্টিভিটি $0$, এবং একটি আর্টিকুলেশন পয়েন্ট বিশিষ্ট কানেক্টেড গ্রাফের ভার্টেক্স কানেক্টিভিটি $1$। আমরা সংজ্ঞায়িত করি যে একটি কমপ্লিট গ্রাফের ভার্টেক্স কানেক্টিভিটি $n-1$। অন্যান্য সব গ্রাফের জন্য ভার্টেক্স কানেক্টিভিটি $n-2$ এর বেশি হয় না, কারণ আপনি এমন একটি ভার্টেক্স জোড়া খুঁজে পেতে পারেন যেগুলো এজ দ্বারা সংযুক্ত নয়, এবং অন্য সব $n-2$ টি ভার্টেক্স সরিয়ে দিতে পারেন।

আমরা বলি যে ভার্টেক্সের একটি সেট $T$ ভার্টেক্স $s$ এবং $t$ কে বিচ্ছিন্ন করে, যদি গ্রাফ $G$ থেকে $T$ এর সমস্ত ভার্টেক্স সরিয়ে দেওয়ার পর, ভার্টেক্সগুলো ভিন্ন কানেক্টেড কম্পোনেন্টে পড়ে।

এটি স্পষ্ট যে, একটি গ্রাফের ভার্টেক্স কানেক্টিভিটি হলো দুটি ভার্টেক্স $s$ এবং $t$ বিচ্ছিন্নকারী এমন সেটের সর্বনিম্ন আকার, সমস্ত সম্ভাব্য জোড়া $(s, t)$ এর মধ্যে নেওয়া।

বৈশিষ্ট্যসমূহ#

হুইটনি অসমতা#

হুইটনি অসমতা (১৯৩২) এজ কানেক্টিভিটি $\lambda$, ভার্টেক্স কানেক্টিভিটি $\kappa$, এবং গ্রাফের যেকোনো ভার্টেক্সের সর্বনিম্ন ডিগ্রি $\delta$ এর মধ্যে একটি সম্পর্ক দেয়:

স্বজ্ঞাতভাবে, যদি আমাদের কাছে $\lambda$ আকারের এজের একটি সেট থাকে যেটি গ্রাফকে বিচ্ছিন্ন করে, আমরা প্রতিটি প্রান্তের একটি করে শেষবিন্দু বেছে নিতে পারি, এবং ভার্টেক্সের একটি সেট তৈরি করতে পারি যেটিও গ্রাফকে বিচ্ছিন্ন করে। এবং এই সেটের আকার $\le \lambda$।

এবং যদি আমরা সর্বনিম্ন ডিগ্রি $\delta$ বিশিষ্ট ভার্টেক্সটি নিই এবং এর সাথে সংযুক্ত সমস্ত এজ সরিয়ে দিই, তাহলে আমরাও একটি বিচ্ছিন্ন গ্রাফ পাই। তাই দ্বিতীয় অসমতা $\lambda \le \delta$।

মজার বিষয় হলো, হুইটনি অসমতা আরও উন্নত করা যায় না: অর্থাৎ এই অসমতা পূরণকারী যেকোনো ত্রয়ীর জন্য কমপক্ষে একটি সংশ্লিষ্ট গ্রাফ বিদ্যমান। এমন একটি গ্রাফ নিম্নলিখিত উপায়ে তৈরি করা যায়: গ্রাফটি $2(\delta + 1)$ টি ভার্টেক্স নিয়ে গঠিত হবে, প্রথম $\delta + 1$ টি ভার্টেক্স একটি ক্লিক গঠন করে (সমস্ত জোড়া ভার্টেক্স একটি এজ দ্বারা সংযুক্ত), এবং দ্বিতীয় $\delta + 1$ টি ভার্টেক্স একটি দ্বিতীয় ক্লিক গঠন করে। এছাড়া আমরা দুটি ক্লিককে $\lambda$ টি এজ দ্বারা সংযুক্ত করি, এমনভাবে যাতে এটি প্রথম ক্লিকে $\lambda$ টি ভিন্ন ভার্টেক্স এবং দ্বিতীয় ক্লিকে শুধু $\kappa$ টি ভার্টেক্স ব্যবহার করে। ফলস্বরূপ গ্রাফটিতে এই তিনটি বৈশিষ্ট্য থাকবে।

ফোর্ড-ফুলকারসন উপপাদ্য#

ফোর্ড-ফুলকারসন উপপাদ্য থেকে বোঝা যায় যে দুটি ভার্টেক্সকে সংযুক্তকারী এজ-ডিসজয়েন্ট পাথের সর্বাধিক সংখ্যা, এই ভার্টেক্সদ্বয়কে বিচ্ছিন্নকারী এজের সর্বনিম্ন সংখ্যার সমান।

মান গণনা#

ম্যাক্সিমাম ফ্লো ব্যবহার করে এজ কানেক্টিভিটি#

এই পদ্ধতিটি ফোর্ড-ফুলকারসন উপপাদ্যের উপর ভিত্তি করে।

আমরা সমস্ত ভার্টেক্স জোড়া $(s, t)$ দিয়ে ইটারেট করি এবং প্রতিটি জোড়ার মধ্যে ডিসজয়েন্ট পাথের সর্বাধিক সংখ্যা খুঁজি। এই মান ম্যাক্সিমাম ফ্লো অ্যালগরিদম ব্যবহার করে পাওয়া যায়: আমরা $s$ কে সোর্স, $t$ কে সিঙ্ক হিসেবে ব্যবহার করি, এবং প্রতিটি এজে ১ ক্যাপাসিটি দিই। তখন ম্যাক্সিমাম ফ্লো হলো ডিসজয়েন্ট পাথের সংখ্যা।

এডমন্ডস-কার্প ব্যবহার করে অ্যালগরিদমের কমপ্লেক্সিটি $O(V^2 V E^2) = O(V^3 E^2)$। তবে আমাদের লক্ষ্য করা উচিত, এতে একটি হিডেন ফ্যাক্টর আছে, যেহেতু এমন গ্রাফ তৈরি করা কার্যত অসম্ভব যেখানে ম্যাক্সিমাম ফ্লো অ্যালগরিদম সমস্ত সোর্স ও সিঙ্কের জন্য ধীর হবে। বিশেষত র‍্যান্ডম গ্রাফে অ্যালগরিদম বেশ দ্রুত চলবে।

এজ কানেক্টিভিটির জন্য বিশেষ অ্যালগরিদম#

এজ কানেক্টিভিটি খোঁজার কাজটি গ্লোবাল মিনিমাম কাট খোঁজার কাজের সমতুল্য।

এই কাজের জন্য বিশেষ অ্যালগরিদম তৈরি করা হয়েছে। এর একটি হলো স্টোয়ার-ওয়াগনার অ্যালগরিদম, যেটি $O(V^3)$ বা $O(V E)$ সময়ে কাজ করে।

ভার্টেক্স কানেক্টিভিটি#

আবার আমরা সমস্ত ভার্টেক্স জোড়া $s$ এবং $t$ দিয়ে ইটারেট করি, এবং প্রতিটি জোড়ার জন্য $s$ এবং $t$ কে বিচ্ছিন্নকারী ভার্টেক্সের সর্বনিম্ন সংখ্যা খুঁজি।

এটি করতে, আমরা পূর্ববর্তী অংশে বর্ণিত একই ম্যাক্সিমাম ফ্লো পদ্ধতি প্রয়োগ করতে পারি।

আমরা প্রতিটি ভার্টেক্স $x$ যেখানে $x \neq s$ এবং $x \neq t$ কে দুটি ভার্টেক্স $x_1$ এবং $x_2$ তে বিভক্ত করি। আমরা এই ভার্টেক্সগুলোকে ১ ক্যাপাসিটি বিশিষ্ট একটি ডিরেক্টেড এজ $(x_1, x_2)$ দ্বারা সংযুক্ত করি, এবং সমস্ত এজ $(u, v)$ কে দুটি ডিরেক্টেড এজ $(u_2, v_1)$ এবং $(v_2, u_1)$ দ্বারা প্রতিস্থাপন করি, উভয়ের ক্যাপাসিটি ১। নির্মাণের ফলে ম্যাক্সিমাম ফ্লো-র মান $s$ এবং $t$ কে বিচ্ছিন্ন করতে প্রয়োজনীয় ভার্টেক্সের সর্বনিম্ন সংখ্যার সমান হবে।

এই পদ্ধতির কমপ্লেক্সিটি এজ কানেক্টিভিটি খোঁজার ফ্লো পদ্ধতির মতোই।