Poset¶

اولین مسئله¶

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

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

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

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

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

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

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

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

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

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

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

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

الگوریتم¶

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

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

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

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

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

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

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

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

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

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

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

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