Graph Theory: Hall's Marriage Theorem and It's Applications
অনেক সময় আমরা বাইপার্টাইট ম্যাচিং এর যে কোন এই সাইডের সব ভারটেক্স কে সম্পৃক্ত করতে চাই। যেমন, আমরা চাই সব মানুষ একটি করে চাকরি পাক, অথবা প্রতিটি ছেলের বিয়ে হোক বা প্রতিটি মেয়ের বিয়ে হোক। যদি $X,Y$ একটি বাইপার্টাইট গ্রাফ হয়, তাহলে $ X$ এর প্রতিটি ভারটেক্স কে সম্পৃক্ত করাকে আমরা বলবো $ X$ কে সম্পৃক্ত করা। আর $N(X)$ দিয়ে বুঝাবো $X$ প্রতিটি ভারটেক্সের প্রতিবেশি সেট এর ইউনিয়ন। অর্থাৎ, $N(X) = \bigcup_{v \in X}^{} N(v)$.
উপপাদ্যঃ[Hall's Marriage Theorem] একটি বাইপার্টাইট গ্রাফ $X,Y$ এর একটি ম্যাচিং থাকবে যেটা $X$ এর প্রতিটি ভারটেক্সকে সম্পৃক্ত করবে যদি ও কেবল যদি $ X$ এর যে কোন সাবসেট $ S$ এর জন্য $ |N(S)| \geq |S|$ হয়।
প্রমাণঃ যদি $ X$ সম্পৃক্ত হয়, তাহলে $ X$ এর প্রতিটি ভারটেক্স $ Y$ এ ভিন্ন ভিন্ন ভারটেক্স এর সাথে $ M$ দ্বারা সংযুক্ত। তাই যে কোন $ S \subset X$ এর জন্য, $ |N(S)| \geq |S|$ হবে।
এবার ধরি, যে কোন $ S \subset X$ এর জন্য $ |N(S) \geq |S|$। এখন, দেখাতে হবে অবশ্যই এমন একটি ম্যাচিং $ M$ আছে যেটা $ X$ কে সম্পৃক্ত করবে। যেহেতু গ্রাফটি বাইপার্টাইট, তাই এমন কোন ম্যাচিং থাকা সম্ভব হলে, ম্যাক্সিমাম ম্যাচিং গুলোও $ X$ কে সম্পৃক্ত করবে। এখন আমরা দেখাবো যে, একটি ম্যাক্সিমাম ম্যাচিং যদি $ X$ কে সম্পৃক্ত না করে, তাহলে $ X$ এর এমন একটি সাবসেট $ S$ আছে যার জন্য $ |N(S)| < |S|$ হয়।
ধরি, $ M$ সবাইকে সম্পৃক্ত করে না এবং $ X$ এ একটি অসম্পৃক্ত ভারটেক্স $ u$ আছে এবং $ X$ এ $ u$ থেকে $ M$-অল্টারনেটিং পাথ দিয়ে যাওয়া যায় এমন ভারটেক্স এর সেট $ S$ এবং $ Y$ এ থেকে অল্টারনেটিং পাথ দিয়ে যাওয়া যায় এমন সব ভারটেক্স এর সেট $ T$। আমরা প্রমাণ করব যে, $ M$, $ S-\{u\}$ কে $ T$ এর সাথে ম্যাচ করে। কারণ, $ u$ থেকে সাধারণ এজ দিয়ে $ T$ তে যাওয়া হয়, আবার $ T$ থেকে $ M$ এর এজ ব্যবহার করে $ S$ এ আসা হয়, আবার $ S$ থেকে সাধারণ এজ দিয়ে $ T$ তে যাওয়া হয় এবং $ T$ থেকে $ M$ এর এজ দিয়ে $ S$ এ আসা হয়। অর্থাৎ, $ |T| = |S| - 1$.
এখন আমরা আরও প্রমাণ করব যে, $ |T| = |N(S)|$. মনে করি, $ X$ এ এমন একটি ভারটেক্স $ v$ আছে যেটা $ T$ তে নাই কিন্তু $ S$ এ তার কোন প্রতিবেশি আছে। এরকম ভারটেক্স যদি থাকে তাহলে সে অসম্পৃক্ত হবে। কারণ $ S$ এর কারো সাথে সে $ M$ এর এজ দিয়ে যুক্ত হতে পারবে না কারণ $ S-{u}$ এর সবাই $ T$এর কারো না কারো সাথে ম্যাচ হয়ে আছে। আবার $ u$ এর সাথে $ M$এর এজ দিয়ে যুক্ত হতে পারবে না কারণ $ u$ অসম্পৃক্ত। অর্থাৎ, ইউ এস এর সাথে সাধারণ এজ দিয়েই যুক্ত হবে। এখন $ S$ এর বাইরে $ v$এর যদি কোন প্রতিবেশি $ w$ থাকে যার সাথে $ M$ এর এজ দিয়ে যুক্ত, তাহলে, $ uw$ একটি $ M$-অল্টারনেটিং পাথ এবং যেহেতু $ w$, $ X$ এ আছে, তাই ওর $ S$ এ থাকার কথা। অর্থাৎ, $ S$ এর বাইরে কারো সাথে $ M$ এর এজ দিয়ে যুক্ত হতে পারবে না। অর্থাৎ, $ v$ অসম্পৃক্ত হবে এবং $ S$ এর সাথে সাধারণ এজ দিয়ে যুক্ত হবে। কিন্তু সেক্ষেত্রে $ uv$ একটি $ M$-অল্টারনেটিং পাথ এবং যেহেতু $ v$, $ Y$ এ আছে তার মানে এর $ T$ তে থাকার কথা। অর্থাৎ, $ T$ এর বাইরে এমন $ v$ পাওয়া সম্ভব না। অর্থাৎ, $ T = N(S)$. কিন্তু তার মানে $ |N(S)| = |T| = |S| - 1$. অর্থাৎ, $ |N(S)| < |S|$. সুতরাং, ম্যাক্সিমাম ম্যাচিং ও যদি $ X$ কে সম্পৃক্ত করতে না পারে তাহলে $ X$ এর একটি সাবসেট $ S$ পাওয়া যাবেই যার জন্য $ |N(S)| < |S|$. তার মানে $ X$ এর যে কোন সাবসেট $ S$ এর জন্য যদি $ |N(S)| \geq |S|$ হয়, তাহলে একটি ম্যাচিং পাওয়া যাবেই যেটা $ X$ কে সম্পৃক্ত করে।
উপরের উপপাদ্যে যদি $ |X| = |Y|$ হয়, তাহলে সেটাকে Frobenius's Theorem বলে।
সমস্যাঃ $ n$ একটি ধনাত্বক সংখ্যা এবং ধর $ S_{1}, S_{2}, \cdots, S_{n}$ হচ্ছে $ \{1, 2, \cdots, n\}$ সেট এর সাবসেট যেন যে কোন $ 1 \leq k \leq n$ এর জন্য যে কোন $ k$ টি সেট এর ইউনিয়নে অন্তত $ k$ টি সংখ্যা থাকবে। প্রমাণ কর যে, $ (1, 2, \cdots, n)$ এর একটি পারমুটেশন $ (a_{1}, a_{2}, \cdots, a_{n})$ আছে যেন সকল $ 1 \leq i \leq n$ এর জন্য $ a_{i} \in S_{i}$ হয়।
সমাধানঃ আমরা এটিকে একটি গ্রাফ থিওরির সমস্যায় রুপান্তর করব। আমরা একটি বাইপার্টাইট গ্রাফ $ X,Y$ বানাবো যেন $ |X| = |Y| = n$ হয়। $ X$ এর ভারটেক্স গুলোকে $ 1, 2, \cdots, n$ লেবেলিং করি। আর $ Y$ এর ভারটেক্স গুলোকে $ S_{1}, S_{2}, \cdots, S_{n}$ লেবেলিং করি। যেকোন $ S_{i}$ ভারটেক্সের সাথে এর উপাদান গুলোর এজ দেই। এখন আমাদের শুধু প্রমাণ করতে হবে যে, এই গ্রাফ এ পারফেক্ট ম্যাচিং সম্ভব। আমরা হলের উপপাদ্য ব্যবহার করে দেখাবো যে, এমন একটি ম্যাচিং আছে যেটা $ Y$ কে সম্পৃক্ত করে।
$ Y$ এর যে কোন সাবসেট $ Z$ এর ভারটেক্সের সংখ্যা যদি $ k$ হয়, তাহলে ভারটেক্সের সেট গুলোর ইউনিয়ন আসলে $ N(Z)$. কিন্তু প্রশ্নমতে, $ |N(Z)| \geq k = |Z|$. যেটা হলের উপপাদ্যের শর্ত পূরণ করে। অর্থাৎ, একটি ম্যাচিং আছে যেটা $ Y$ কে সম্পৃক্ত করে। যেহেতু $ |X| = |Y|$, তাই ঐ ম্যাচিং $ X$ কেও সম্পৃক্ত করে। এবার ধরলাম $ X$ এর $ j$ লেবেলযুক্ত যে কোন ভারটেক্স $ Y$ এর $ S_{i}$ এর সাথে যুক্ত। তাহলে, $ a_{i} = j$ নিলেই আমরা $ (1, 2, \cdots, n)$ এর একটি পারমুটেশন $ (a_{1}, a_{2}, \cdots, a_{n})$ পাই যেন সকল $ 1 \leq i \leq n$ এর জন্য $ a_{i} \in S_{i}$ হয়।
সমস্যাঃ [Canada 2006] $ m$ সারির এবং $ n$ কলামের একটি আয়তাকার গ্রীডের প্রতিটি সেল এ একটি অঋণাত্বক সংখ্যা আছে। প্রতিটি সারি এবং প্রতিটি কলামে অন্তত একটি ধনাত্বক সংখ্যা আছে। যদি একটি সারি এবং একটি কলাম একটি ধনাত্বক সংখ্যায় ছেদ করে, তাহলে ঐ সারির সংখ্যাগুলোর যোগফল ঐ কলামের সংখ্যাগুলোর যোগফলের সমান হয়। প্রমাণ কর যে, $ m = n$.
সমাধানঃ আমরা একটি বাইপার্টাইট গ্রাফ $ X,Y$ বানাই যেন $ X = m$ এবং $ Y = n$ হয়। $ X$ এর প্রতিটি ভারটেক্স দিয়ে বোঝায় একটি সারি এবং $ Y$ এর প্রতিটি ভারটেক্স দিয়ে বোঝায় একটি কলাম। যদি একটি সারি এবং একটি কলাম এর কমন সেল এ একটি ধনাত্বক সংখ্যা থাকে তাহলে তাদের মাঝে একটি এজ দেই এবং সেই এজ কে লেবেল করি ঐ ধনাত্বক সংখ্যা দিয়ে।
ধরি, এমন কোন ম্যাচিং নেই যেটা $ X$ কে সম্পৃক্ত করে। তার মানে $ X$ এ এমন কোন সাবসেট $ S$আছে যার জন্য $ |S| > |N(S)|$ হবে। মনে করি, $ S$ এ $ k$ টি সারি আছে। এই সারিগুলোর যোগফল হচ্ছে $ r_{1}, r_{2}, \cdots, r_{k}$. মনে করি, $ N(S)$ এ $ l$ টি কলাম আছে এবং কলামগুলোর যোগফল হচ্ছে $ c_{1}, c_{2}, \cdots, c_{l}$. এবার দুইটি উপায়ে আমরা $ S$ এর সাথে $ N(S)$ এর যেসব এজ আছে সেসব এজ এর যোগফল হিসাব করব। $ S$ এর দিক থেকে চিন্তা করলে সেটা $ \sum_{i = 1}^{k} r_{i}$ আবার এর দিক থেকে চিন্তা করলে সেটা $ \sum_{i = 1}^{l} c_{i}$. কিন্তু যেকোন $ c_{i}$ আসলে $ r_{1}, r_{2}, \cdots, r_{k}$ এর কোন একটির সমান আবার যেহেতু $ l < k$, তাই $ \sum_{i = 1}^{l} c_{i} < \sum_{i = 1}^{k} r_{i}$. যেটা অসম্ভব। তাই আমরা যে ধরেছিলাম $ X$ কে সম্পৃক্ত করে এমন ম্যাচিং থাকা সম্ভব না, সেই ধারনা ভুল। অর্থাৎ, একটি ম্যাচিং কে সম্পৃক্ত করে। তাই $ m \leq n$.
আবার ধরি, এমন কোন ম্যাচিং নেই যেটা $ Y$ কে সম্পৃক্ত করে। উপরের মত একইভাবে দেখাই যে, এটা সম্ভব না। তাই এমন ম্যাচিং আছে যেটা $ Y$ কে সম্পৃক্ত করে। তাই $ n \leq m$. অন্যথায়, $ m = n$.
সমস্যাঃ একটি $ n \times n$ ম্যাট্রিক্সের প্রতিটি সেলে $ 0$ অথবা $ 1$ আছে। এমন একটি ম্যাট্রিক্স কে পারমুটেশন ম্যাট্রিক্স বলা হবে যদি ম্যাট্রিক্সের প্রতিটি সারিতে কেবল ১টি $ 1$ থাকে এবং প্রতিটি কলামে কেবল ১টি $ 1$ থাকে। অঋণাত্বক সংখ্যার একটি ম্যাট্রিক্স $ M$ দেওয়া আছে যার প্রতিটি সারির যোগফল সমান এবং প্রতিটি কলামের যোগফল সমান। প্রমাণ কর যে, $ M$ কে শুধুমাত্র কিছু পারমুটেশন ম্যাট্রিক্স এর যোগফল হিসেবে লেখা যাবে।
সমাধানঃ ধরে নেই, ম্যাট্রিক্স এর প্রতিটি সারির যোগফল $ R$ এবং প্রতিটি কলামের যোগফল $ C$ । যদি আমরা ম্যাট্রিক্স এর সংখ্যাগুলোর যোগফল সারিগুলোর যোগ ফল থেকে বের করি, তাহলে সেটা $ nR$ এবং কলামগুলোর যোগফল থেকে বের করি, তাহলে সেটা $ nC$. যেহেতু, $ nC = nR$, তাই $ R = C$. অর্থাৎ সকল সারি ও কলামের যোগফল আসলে সমান।
এবার আমরা ম্যাট্রিক্স এর সারি ও কলামগুলোর এই যোগফলের উপর গাণিতিক আরোহ পদ্ধতি ব্যবহার করে আমরা প্রমাণ করব যে, কোন ম্যাট্রিক্স $ M$ এর উপাদানগুলি যদি অঋণাত্বক হয় এবং প্রতিটি সারি ও প্রতিটি কলামের যোগফল $ S$ হয়, তাহলে $ M$ কে কিছু পারমুটেশন ম্যাট্রিক্স এর যোগফল হিসেবে লেখা যাবে।
কোন ম্যাট্রিক্স এর জন্য $ S = 1$ হলে সে নিজেই একটা পারমুটেশন ম্যাট্রিক্স। অর্থাৎ, এর জন্য দাবিটি সত্যি। এবার ধরে নেই, $ S = n-1$ এর জন্য দাবিটি সত্যি, যেখানে $ n \geq 2$.
এবার আমরা $ n$ যোগফলের একটি ম্যাট্রিক্স নেই। ম্যাট্রিক্সটি থেকে একটি বাইপার্টাইট গ্রাফ $ X,Y$ বানাই যেন $ |X| = |Y| = n$ হয় এবং $ X$ এর প্রতিটি ভারটেক্স দিয়ে বোঝায় $ M$ এর একটি সারি এবং $ Y$ এর প্রতিটি ভারটেক্স দিয়ে বোঝায় $ M$ এর একটি কলাম। ধরি, $ X$ এর সারিগুলো $ r_{1}, r_{2}, \cdots, r_{n}$ এবং $ Y$ এর কলামগুলো $ c_{1}, c_{2}, \cdots, c_{n}$. যদি $ M_{ij} > 0$ হয়, তাহলে $ r_{i}$ এর সাথে $ c_{j}$ এর একটি এজ দেই। এজ এর ওয়েট $ M_{ij}$ দেই । এখন আমরা প্রমাণ করব যে, এই গ্রাফে একটি পারফেক্ট ম্যাচিং আছে।
যদি এমন কোন ম্যাচিং না থাকে যেটা $ X$ কে সম্পৃক্ত করে তাহলে $ X$ এর কোন সাবসেট $ S$ আছে যার জন্য $ |N(S)| < |S|$ হবে। ধরি, $ |S| = k$ এবং $ |N(S)| = l$. $ S$ এর সাথে $ N(S)$ এর যেই এজ গুলো আছে সেগুলোর যোগফল ২ ভাবে বের করি। সারিগুলোর দিক থেকে সেই যোগফল হচ্ছে $ \sum_{i = 1}^{k} sum(r_{i}) = nk$. আবার, কলামগুলোর দিক থেকে সেই যোগফল হচ্ছে, $ \sum_{i = 1}^{l} sum(c_{i})$. যেহেতু, যে কোন $ i$ এর জন্য $ sum(c_{i}) \leq n$ এবং $ l < k$, তাই, $ nk = \sum_{i = 1}^{k} sum(r_{i}) = \sum_{i = 1}^{l} sum(c_{i}) \leq nl$. অর্থাৎ, $ k \leq l$. যেটা অসম্ভব। তাই, অবশ্যই একটি ম্যাচিং থাকবে যেটা $ X$ কে সম্পৃক্ত করবে। আর যেহেতু, $ |X| = |Y|$, তাই সেটা $ Y$ কেও সম্পৃক্ত করবে। অর্থাৎ, এই গ্রাফে পারফেক্ট ম্যাচিং সম্ভব। এই ম্যাচিংটিকে যদি আমরা ম্যাট্রিক্স $ P$ তে পরিণত করি, তাহলে আমরা দেখতে পাই যে, $ P$ একটি পারমুটেশন ম্যাট্রিক্স। এবার মূল গ্রাফ এর কোন এজ যদি ম্যাচিং এ থাকে, ওই এজ এর ওয়েট ১ কমিয়ে দেই। তাহলে প্রতিটি কলামের যোগফল হয় $ n-1$ এবং প্রতিটি কলামের যোগফল হয় $ n-1$. এই নতুন গ্রাফ কে যদি ম্যাট্রিক্স $ N$ এ রুপান্তরিত করি, তাহলে সেই ম্যাট্রিক্স এর ক্ষেত্রে আমরা জানি যে একে $ n-1$ টি পারমুটেশন ম্যাট্রিক্স এর যোগফল হিসেবে লেখা যায়। যেহেতু, $ M = P + N$, তাই, $ M$ কেও $ n$ টি পারমুটেশন ম্যাট্রিক্স এর যোগফল হিসেবে লেখা যায়।
উপপাদ্যঃ [Konig's Marriage Theorem] যদি $ k > 0$ হয়, তবে যে কোন $ k$-রেগুলার বাইপার্টাইট গ্রাফ এর জন্য পারফেক্ট ম্যাচিং থাকবে।
প্রমাণঃ আমরা ধরে নেই গ্রাফ এর এক পার্টিশনে $ X$ সংখ্যক ভারটেক্স আছে। অপরপাশে $ Y$ সংখ্যক আছে। যেহেতু গ্রাফটি রেগুলার, তাই, $ |X|k = e = |Y|k$. অর্থাৎ, $ |X| = |Y|$. এবার, $ X$ এর যে কোন সাবসেট $ S$ নেই। $ N(S)$ থেকে যত এজ বের হয়, তার একটি সাবসেট দিয়ে সে $ S$ এর সাথে যুক্ত। তাই, $ |S|k \leq |N(S)|k$. অর্থাৎ, $ |S| \leq |N(S)|$. তার মানে, এমন একটি ম্যাচিং থাকবে যেটা $ X$ কে সম্পৃক্ত করে ফেলবে। যেহেতু, $ |X| = |Y|$ ,তাই সেটি $ Y$ কেও সম্পৃক্ত করবে এবং এটি একটি পারফেক্ট ম্যাচিং।