Graph Theory: Matching

ম্যাচিং

ধর,একটি বাইপার্টাইট গ্রাফ আছে যার এক পাশে $ n$ সংখ্যক ব্যক্তি এবং অপর পাশে $ m$ সংখ্যক চাকরির পোস্ট আছে। প্রতিটি এজ দ্বারা বুঝায় যে একজন ব্যক্তি এই চাকরির জন্য আবেদন করে আপাতভাবে উপযুক্ত বলে নির্বাচিত হয়েছেন। এখন একজন মানুষ একাধিক চাকরির জন্য উপযুক্ত বলে নির্বাচিত হতে পারেন। আবার একটি চাকরির পোস্ট এর জন্য একাধিক ব্যক্তিকে সাময়িক অনুমোদন দেওয়া হতে পারে। কিন্তু শেষ পর্যন্ত একজন ব্যক্তি একটি চাকরিই করবেন। এবং একটি চাকরির পোস্ট একজন ব্যক্তিই পাবেন। এখন কিভাবে কাকে কোন পোস্ট এ চাকরি দিলে সবচেয়ে বেশি বেকারত্ব বিমোচন করা যাবে? একাধিক সমাধান থাকতেই পারে।

অথবা মনে কর, একজন ঘটক এর অফিস এ প্রত্যেক পাত্র কয়েকজন পাত্রির ব্যাপারে আগ্রহ প্রকাশ করেন। প্রত্যেক পাত্রি ও কিছু পাত্রের ব্যাপারে আগ্রহ প্রকাশ করেন। এখন ঘটক চাচ্ছেন সবচেয়ে বেশি সংখ্যক বিয়ে যেন হয়। কারণ একটি বিয়ে ঘটাতে পারলে ঘটক আর্থিকভাবে বেশ লাভবান হন। এখন তিনি এমনভাবে পাত্র ও পাত্রি দের একে অপরের প্রতি প্রলুব্ধ করতে চান যেন বিয়ের সংখ্যা সর্বোচ্চ হয়। তার কার কাছে গিয়ে কার ব্যাপারে গুণগান করা উচিত? এবং সর্বোচ্চ বিয়ে কতগুলো হতে পারে?

এসকল সমস্যার সমাধানে আমরা গ্রাফের বর্তমান এজ গুলো থেকে একটি সাবসেট বাছাই করব এবং নতুন একটি গ্রাফ বানাবো যেখানে কোন ভারটেক্স এর ডিগ্রী ১ এর বেশি না হয়। কারণ, আমরা চাই না একটি ছেলে একের বেশি মেয়ে কে বিয়ে করুক বা একটি মেয়ে অনেক ছেলেকে বিয়ে করুক বা একজন মানুষ অনেক গুলি চাকরি করুক অথবা একটি চাকরি অনেকে মিলে করুক। অর্থাৎ, আমরা এখানে একজন মানুষের সাথে একটি চাকরিকে ম্যাচ করছি, একটি ছেলের সাথে একটি মেয়েকে ম্যাচ করাচ্ছি। আমরা গ্রাফ থিওরির মাধ্যমে ঘটকালি করতে যাচ্ছি।

কিন্তু মনে করার কারণ নেই যে, ম্যাচিং শুধু বাইপার্টাইট গ্রাফ এর জন্য। যেমন বিয়ের সমস্যায় এমন হতেই পারে যে বাইসেক্সুয়াল, হোমোসেক্সুয়াল বা আরো অন্য ওরিয়েন্টেশন এর মানুষ থাকতেই পারে।

অথবা, একটি ক্লাসের শিক্ষার্থীদের মধ্যে বন্ধুত্বের গ্রাফ দেওয়া আছে। শিক্ষক ২ জন এর টিম করে তাদেরকে প্রজেক্ট দিতে চান। উনি ভালভাবে জানেন যে, টিমের ২ জনের সম্পর্ক ভাল না হলে টিমে কাজ হবে না। এইক্ষেত্রে তিনি চান বন্ধুত্বের উপর ভিত্তি করে সর্বোচ্চ সংখ্যক টিম তৈরি করতে। এই ক্ষেত্রেও আসলে তিনি ম্যাচিং চান কিন্তু গ্রাফটি বাইপার্টাইট নয়।

সংজ্ঞা: একটি গ্রাফ $ G = (V, E)$ এর একটি সাবগ্রাফ $ M$ কে $ G$ এর উপর একটি ম্যাচিং বলা হবে যদি $ \Delta(M) \leq 1$. যদি কোন ভারটেক্স $ v$ এর জন্য $ d_{M}(v) = 0$ হয়, এমন ভারটেক্স কে বলে $ M$-অসম্পৃক্ত ভারটেক্স। আর যেসব ভারটেক্স এর জন্য $ d_{M}(v) = 1$, তাদের কে বলে $ M$-সম্পৃক্ত ভারটেক্স।

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

সংজ্ঞাঃ যদি একটি ম্যাচিং $ M$ একটি গ্রাফ $ G$ এর প্রতিটি ভারটেক্স কে সম্পৃক্ত করে, তাহলে $ M$ কে $ G$ এর উপর একটি পারফেক্ট ম্যাচ বলে।

ম্যাচিং তৈরির উপায় হচ্ছে প্রতিবার একটি এজ নেওয়া যার দুই প্রান্ত সম্পৃক্ত হয়নি। তারপর সেই এজ কে এ যোগ করা। একটা সময় দেখা যাবে যে নতুন এজ সংযোগ দেওয়া যাচ্ছে না। এই অবস্থায় ম্যাচিংটিকে বলে ম্যাক্সিমাল ম্যাচিং। আবার একটি গ্রাফের সবগুলো ম্যাচিং এর মাঝে যেইসব ম্যাচিং সর্বোচ্চ সংখ্যক এজ ব্যবহার করে তাদেরকে বলে ম্যাক্সিমাম ম্যাচিং। তবে খেয়াল রাখা উচিত ম্যাক্সিমাল ম্যাচিং মানেই কিন্তু ম্যাক্সিমাম ম্যাচিং নয়। যেমন নিচের দুটি গ্রাফের ম্যাচিংগুলো।

সংজ্ঞাঃ যদি একটি ম্যাচিং এ আর কোন এজ যোগ করা যায় না, তবে ম্যাচিংটি ম্যাক্সিমাল। আর যদি একটি ম্যাচিং এ সর্বোচ্চ সংখ্যক এজ থাকে তবে ম্যাচিংটি ম্যাক্সিমাম।

বাম পাশের গ্রাফে একটি পাথ আছে যার প্রথম এজটি ম্যাচিং এ আছে, পরেরটি নেই, তারপরেরটি আছে, কিন্তু তারপরেরটি নেই। এরকম পাথ এর দৈর্ঘ্য যদি জোড় হয়, তবে প্রথম এজটি ম্যাচিং এ থাকলে শেষেরটি থাকবে না। আবার প্রথমটি ম্যাচিং এ না থাকলে শেষেরটি অবশ্যই থাকবে। যদি পাথ এর দৈর্ঘ্য বিজোড় হয়, তবে প্রথম এজ ম্যাচিং এ থাকলে শেষটিও থাকবে। আবার প্রথম টি না থাকলে শেষটিও থাকবে না। যদি প্রথম ও শেষ এজ ম্যাচিং এ না থাকলে তাহলে আমরা অবশ্যই যেসব এজ ম্যাচিং এ আছে তাদের কে ম্যাচিং থেকে বাদ দিয়ে, যারা ম্যাচিং এ নাই তাদের কে ম্যাচিং এ যোগ করি তাহলে আরো বড় একটি ম্যাচিং পাবো।

সংজ্ঞাঃ যদি একটি পাথ এর যেকোন দুটি পাশাপাশি এজ এর একটি $ M$ এ থাকে এবং অন্যটি $ M$ এ না থাকে, তবে এই পাথটিকে বলে $ M$-অল্টারনেটিং পাথ। আর যদি পাথ এর প্রথম এজটি $ M$ এ না থাকে এবং শেষ এজটিও $ M$ এ না থাকে তবে একে $ M$-অগমেন্টিং পাথ বলে।

সংজ্ঞাঃ দুটি গ্রাফ $ A$, $ B$ যদি একই ভারটেক্স সেট এর উপর হয়, তাহলে তাদের সিমেট্রিক ডিফারেন্স $ A \Delta B$ হচ্ছে এমন একটি গ্রাফ $ C$ যেই গ্রাফটি শুধু $ A$ তে আছে এমন এজ এবং শুধু $ B$ তে আছে এমন সব এজ নিয়ে তৈরি। যেই এজ $ A$ এবং $ B$ দুই গ্রাফেই আছে সেটি $ C$ তে থাকবে না।অর্থাৎ, $ C = A \Delta B = (A - B) \cup (B - A)$.

অনেক কিছুর সিমেট্রিক ডিফারেন্স হতে পারে। যেমন দুটি পাথ $ P_{1}$ ও $ P_{2}$ এর জন্য $ P_{1} \Delta P_{2}$, দুটি সাইকেল $ C_{1}$ ও $ C_{2}$ এর জন্য $ C_{1} \Delta C_{2}$, দুটি ম্যাচিং $ M_{1}$ ও $ M_{2}$ এর জন্য $ M_{1} \Delta M_{2}$.

সুত্রঃ দুটি ম্যাচিং সিমেট্রিক ডিফারেন্স এর প্রতিটি কম্পোনেন্ট একটি জোড় দৈর্ঘ্যের সাইকেল অথবা একটি পাথ হবে।

প্রমাণঃ ধরি ম্যাচিং দুটি $ M_{1}$ ও $ M_{2}$ এবং তাদের সিমেট্রিক ডিফারেন্স $ D$। যেই এজটি দুটি ম্যাচিং এই আছে সে $ D$ এ থাকবে না। তাহলে মূল গ্রাফটি কিছু কম্পোনেন্ট এ ভাগ হয়ে যেতে পারে। এখন, প্রতিটি কম্পোনেন্ট এর যে কোন ভারটেক্স এর ডিগ্রী ২ এর বেশি হবে না। কারণ, তার সর্বোচ্চ একটি এজ $ M_{1}$ এ থাকবে এবং সর্বোচ্চ আরেকটি এজ $ M_{2}$ এ থাকবে। তাই গ্রাফের কম্পোনেন্টগুলো হবে সাইকেল অথবা পাথ। যেহেতু সাইকেল এর পাশাপাশি দুটি এজ কোন ম্যাচিং এ থাকতে পারবে না, তাই সাইকেল এর দৈর্ঘ্য বিজোড় হতে পারবে না। পাথের ক্ষেত্রেও একটি এজ যদি $ M_{1}$ এর হয়, তার পাশের দুটি এজ হবে $ M_{2}$ এর। অর্থাৎ, পাথ গুলোকে $ M_{1}$-অল্টারনেটিং পাথ বলা যায়, আবার $ M_{2}$-অল্টারনেটিং পাথ ও বলা যায়।

উপপাদ্যঃ[Berge's Theorem] $ G$ এর উপর একটি ম্যাচিং $ M$ ম্যাক্সিমাম হবে যদি ও কেবল যদি $ G$ তে কোন $ M$-অগমেন্টিং পাথ না থাকে।

প্রমাণঃ প্রথমে প্রমাণ করি, $ M$ ম্যাক্সিমাল হলে কোন $ M$-অগমেন্টিং পাথ থাকবে না। ধরলাম, একটি $ M$-অগমেন্টিং পাথ পাওয়া গেল। এবার এই পাথ এর যেই এজ $ M$ এ আছে তাকে $ M$ থেকে বাদ দেই, এবং যেই এজ $ M$ এ নেই, তাকে $ M$ এ যোগ করি। তাহলে এমন একটি ম্যাচিং $ M'$ পাই যেটা $ M$ থেকেও বড়। কিন্তু আমরা জানি $ M$ হচ্ছে ম্যাক্সিমাম ম্যাচিং। অর্থাৎ, অগমেন্টিং পাথ পাওয়া সম্ভব না।

এবার প্রমাণ করি, $ M$-অগমেন্টিং পাথ না থাকলে $ M$ ম্যাক্সিমাম। আমরা যদি প্রমাণ করতে পারি যে, $ M$ ম্যাক্সিমাম না হলে $ M$-অগমেন্টিং পাথ অবশ্যই থাকবে, তাহলে যেহেতু $ M$-অগমেন্টিং পাথ নেই, তাই ম্যাচিংটি ম্যাক্সিমামই হবে। ধরে নেই, $ M$ ম্যাক্সিমাম না। অতএব অন্য একটি ম্যাচিং $ M'$ আছে যেটি ম্যাক্সিমাল। ধরি, $ D = M \Delta M'$। যেহেতু $ D$ এর প্রতিটি কম্পোনেন্ট জোড় সাইকেল অথবা পাথ এবং সাইকেল এর প্রতি দুটি পাশাপাশি এজ এর একটি $ M$ এর আরেকটি $ M'$ এর এবং $ M'$ এ অন্তত একটি এজ বেশি আছে, তাই এমন একটি পাথ থাকবে যেখানে এর $ M'$ এজ বেশি। অর্থাৎ শুরু হবে $ M'$ দিয়ে শেষও হবে $ M'$ দিয়ে। অর্থাৎ, এটি একটি $ M$-অগমেন্টিং পাথ। তার মানে, যে কোন ম্যাচিং যদি ম্যাক্সিমাম না হয়, তাহলে গ্রাফে একটি অগমেন্টিং পাথ থাকবেই। অতএব, $ G$ তে যদি $ M$-অগমেন্টিং পাথ না থাকে তাহলে $ M$ ম্যাক্সিমাম ম্যাচিং হবে।