Poset
==========

تعریف
---------

به گراف جهت داری که دارای ویژگی زیر باشد Poset (Partially ordered set) می گوییم.

- اگر :math:`ab` و :math:`bc` یال های این گراف باشد آنگاه :math:`ac` هم یال این گراف است.

از آنجایی که بسیاری از مفاهیم ریاضی به poset تبدیل می شوند بررسی کردن آن ها مفید است.

اولین مسئله
~~~~~~~~~~~~~~

فرض کنید مجموعه ای از اعداد طبیعی مثل :math:`A` داریم و می خواهیم بزرگترین زیرمجموعه ای از آن مثل :math:`B` را پیدا کنیم که هر دو عضو :math:`B` را که در نظر بگیریم یکی بر دیگری بخش پذیر است.

می توانیم مسئله را به اینصورت به گراف مدل کنیم. به ازای هر عضو :math:`A` یک راس در گراف قرار دهید و به ازای دو راس :math:`x,y` که :math:`x|y` است از :math:`x` به :math:`y` یال بگذارید. حالا مسئله معادل پیدا کردن بلندترین مسیر در این گراف است!

زنجیر و پادزنجیر
~~~~~~~~~~~~~~~~~~

به یک دنباله از راس های غیر تکراری مثل :math:`u_1,...,u_k` که به ازای هر :math:`i<j` ، :math:`u_i` به :math:`u_j` یال داشته باشد یک زنجیر می گوییم توجه کنید که به خاطر ویژگی poset کافیست که :math:`u_1, ... u_k` یک مسیر باشد.

به یک زیرمجموعه از راس ها که هیچ دوتایی به هم یال نداشته باشند یک پادزنجیر می گوییم.

در ادامه افراز یک گراف به زنجیر ها یا پادزنجیر ها را بررسی خواهیم کرد (افراز راس های گراف مد نظر است).

توجه کنید که از این تعاریف تنها در poset ها استفاده می شود.

ماکسیمم زنجیر = مینیمم افراز به پادزنجیر
-------------------------------------

فرض کنید اندازه ماکسیمم زنجیر :math:`L` باشد. و یک زنجیر ماکسیمم مثل :math:`A` را در نظر بگیرید.

هر پادزنجیر می تواند حداکثر یکی از راس های :math:`A` را شامل شود. پس مینیمم افراز به پادزنجیر حداقل به اندازه :math:`L` می باشد. حالا ثابت می کنیم حالتی از تساوی هم وجود دارد.

به هر راس :math:`u` عدد :math:`a_i` را نسبت می دهیم که برابر است با اندازه بزرگترین زنجیری که :math:`u` انتهای آن باشد. حالا می توانید ببینید که اگر :math:`a_i = a_j` برقرار باشد امکان ندارد یالی بین :math:`i,j` باشد زیرا به عنوان مثال اگر از :math:`i` به :math:`j` یال باشد آنگاه :math:`a_j \geq a_i+1` خواهد بود.

به ازای هر راس :math:`u` به :math:`a_u` رنگ راس :math:`u` می گوییم. طبق اثبات بالا راس هایی که رنگ برابر دارند یک پادزنجیر هستند. همچنین تعداد رنگ ها برابر است با :math:`L` (چرا؟). پس توانستیم گراف را به :math:`L` پادزنجیر افراز کنیم.

قضیه یالا به قضیه میرسکی معروف است و در سال 1971 مطرح شد. جالب است بدانید این قضیه در سال 1940 توسط گالای دیلورث ، گالای،‌ فولکرسون و بسیاری دیگر شناخته شده بود و تنها دلیل آنها برای مطرح نکردن آن بدیهی فرض کردن این قضیه بود!

ماکسیمم پادزنجیر = مینیمم افراز به زنجیر
-------------------------------------

مثل قبل می توان ابتدا به این نتیجه رسید که مینیمم افراز به زنجیر ها حداقل به اندازه ماکسیمم پادزنجیر است. (زیرا در هر زنجیر ماکسیمم یکی از راس های پادزنجیر را می توانیم استفاده کنیم). حالا می خواهیم برای اثبات تساوی یک مثال ارائه دهیم.

در مورد مسئله افراز راس های گراف به مینیمم تعداد مسیر در بخش 4 صحبت کردیم. کافی بود که گراف را به فرم دوبخشی در بیاوریم و ماکسیمم تطابق را پیدا کنیم. حالا می دانیم که در poset ها هر زنجیر معادل با یک مسیر است. پس مسئله مینیمم افراز به زنجیر با پیدا کردن مینیمم افراز راس ها به مسیر ها حل می شود.

مسیر شبه افزایشی
~~~~~~~~~~~~~~~~~~~~~~~~~

پس حالا فرض کنید poset ما یک گراف جهت دار به اسم :math:`P` باشد. گراف دوبخشی معادل آن را :math:`G` بنامید. یک مینیمم افراز به مسیر ها در :math:`P` را در نظر بگیرید. یال های جهت داری که در مسیر هایمان وجود دارد را مجموعه :math:`M` بنامید. می دانیم که یال های :math:`M` معادل با یال های یک تطابق بیشینه در :math:`G` می باشد. شرط لازم و کافی برای بیشینه بودن یک تطابق این بود که مسیر افزایشی نداشته باشیم. بررسی می کنیم که معادل یک مسیر افزایشی در گراف جهت دارمان به چه شکل خواهد بود. یک راس آزاد در بخش اول :math:`G` معادل است با راسی در :math:`P` که پایان یک مسیر است. یک راس آزاد در بخش دوم :math:`G` معادل است با راسی که در :math:`P` شروع یک مسیر است.

پس می خواهیم معادل یک مسیر افزایشی که در :math:`G` که از بخش اول شروع می شود و به بخش دوم می رود را در گراف :math:`P` بفهمیم. **مسیر شبه افزایشی** در :math:`P` را اینطور تعریف می کنیم :

دنباله راس های :math:`u_1,u_2,...,u_{2k+1}` به طوریکه :math:`u_1` ابتدای و :math:`u_{2k+1}` انتهای یک مسیر انتخاب شده در افراز مینیمم باشد. همچنین به ازای :math:`u_{2i-1},u_{2i}` در :math:`P` یال :math:`u_{2i-1}u_{2i}` موجود باشد و عضو :math:`M` نباشد و به ازای :math:`u_{2i},u_{2i+1}` یال :math:`u_{2i+1}u_{2i}` در :math:`M` آمده باشد! (به عوض شدن ترتیب دقت کنید).

پس حالا می توان فرض کرد که راس های :math:`P` را به کمینه تعداد مسیر ها افراز کردیم به طوریکه در :math:`P` مسیر شبه افزایشی وجود ندارد.

الگوریتم
~~~~~~~~~~~~~~~~~~~~~~

حالا هدف ما این است که از هر کدام از زنجیر ها دقیقا یک راس را انتخاب کنیم به صورتیکه راس های انتخاب شده پادزنجیر باشند. در اینصورت می توانیم به حالت تساوی برسیم.

الگوریتم زیر را در نظر بگیرید :

- راس های اول مسیر را در نظر بگیرید. اگر بین آنها هیچ یالی نبود تنها کافیست آنها را انتخاب کنید.‌ اگر نه یعنی یالی مثل :math:`uv` وجود دارد که :math:`u,v` هر دو اول دو مسیر در افرازمان هستند.
- حالا باید راس :math:`u` را حذف کنیم. زیرا که با توجه به اینکه :math:`u` به :math:`v` یال دارد و :math:`v` اول یک مسیر است پس طبق خاصیت poset می توان نتیجه گرفت :math:`u` به تمام راس های مسیر :math:`v` یال دارد پس اگر :math:`u` را در پادزنجیر انتخاب کنیم هیچکدام از راس های مسیری که :math:`v` اول آن است را نمی توانیم انتخاب کنیم پس نمی توانیم به هدفمان که انتخاب یک راس از هر مسیر است برسیم. پس :math:`u` را حذف کنید.

آنقدر این فرایند را ادامه دهید که بین راس های اول مسیر (بعد از حذف ها) هیچ یالی نباشد و یک پادزنجیر به اندازه تعداد مسیر ها بیابیم. تنها حالتی که کار ما را خراب می کند این است که یک مسیر به طور کامل حذف شود. (در این صورت پادزنجیر به اندازه تعداد مسیر های اولیه نخواهد بود).

هیچ مسیری کاملا حذف نمی شود
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

پس ثابت می کنیم که هیچکدام از مسیر ها طی الگوریتم به طور کامل حذف نمی شوند. ایده اثبات این است که با برهان خلف فرض کنیم یک مسیر کامل حذف شده و سپس یک مسیر شبه افزایشی در گراف اولیه پیدا کنیم که با مینیمم بودن افرازمان در تناقض خواهد بود.

به ازای هر راس :math:`a` به راسی مثل :math:`b` پدر راس :math:`a` می گوییم اگر در الگوریتم :math:`a` به خاطر یال :math:`ab` حذف شده باشد. یعنی در مرحله ای از الگوریتم :math:`a,b` هر دو اول دو مسیر باشند و یال :math:`ab` عضو :math:`P` باشد و طبق الگوریتم بالا ما راس :math:`a` را حذف کنیم.

به ازای هر راس :math:`a` مسیری که :math:`a` در آن است را در نظر بگیرید و راسی که در مسیر قبل از :math:`a` است (مثل :math:`b`) را رئیس :math:`a` بنامید. (یعنی :math:`ba` یالی عضو :math:`M` باشد).

توجه کنید که به ازای هر راس :math:`a` زمان حذف شدن :math:`a` بعد از زمان حذف شدن رئیس پدر :math:`a` است. زیرا زمانی که :math:`a` حذف شده توسط پدرش باید اول یک مسیر باشد. این یعنی ریئس پدر (در صورت وجود) قبل از این حذف شده است.

حالا فرض کنید در مرحله ای راس :math:`a` حذف شود که انتهای یک مسیر از افرازمان است. از راس :math:`a` شروع کنید و یک مهره روی :math:`a` بگذارید. در هر مرحله اگر مهره روی :math:`u` باشد ابتدا مهره را به پدر :math:`u` ببرید اگر پدر :math:`u` اول یکی از مسیر ها باشد که مسیر شبه افزایشیمان را پیدا کردیم در غیر اینصورت مهره را به رئیس پدر :math:`u` ببرید. به دو مورد توجه کنید :

- فرایند پایان پذیر است زیرا طبق آنچه گفتیم بعد از هر مرحله مهره روی راسی قرار می گیرد که زمان حذف شدن آن در الگوریتم کمتر است.
- در هر مرحله راسی که مهره روی آن قرار دارد پدر دارد. زیرا که در الگوریتممان این راس زمانی حذف می شود (زیرا که زمان حذف شدن آن از :math:`a` کم تر است و گفتیم :math:`a` هم حذف می شود).

پس توانستیم یک مسیر شبه افزایشی پیدا کنیم. همانطور که گفتیم تناقض حاصله نشان می دهد هیچ مسیری کاملا حذف نمی شود!