ادامه تمرینهای فصل 1 وزیرانی

5- یک تطابق ماکسیمال را می توان با یک الگوریتم حریصانه به دست آورد: یک یال را بردارید و دو سر آن را حذف کنید، این کار را ادامه بدهید تا هیچ یالی باقی نماند. آیا این کار باعث می شود الگوریتم 1.2 حریصانه شود؟

(الگوریتم 1.2: پوشش راسی با  بیشترین اعضا: یک تطابق ماکسیمال در گراف پیدا کنید و راسهای تطابق یافته را به عنوان خروجی اعلام کنید.)

بله، چون در آن از یک الگوریتم حریصانه استفاده کرده ایم.

6- یک کران پایین برای مساله پوشش راسی با هزینه دلخواه بدهید.

راهنمایی: اگر از دوگان LP استفاده نکنید ساده نیست.

پوشش راسی را با LP بخواهیم بیان کنیم متغیرهای آن را راسها می گیریم که 0 یعنی در پوشش راسی نیست و 1 یعنی هست. قیود ما یالها هستند که جمع دو متغیر راس هستند که باید از 1 کمتر باشند. تابع هدف ما هم مینیمم کردن جمع متغیرها است.

IP --> LP:

minimize sum(cost(i)*xi)

s.t. xi+xj <= 1 (i,j) in E

xi in {0,1} --> xi >= 0, xi <= 1

LP:

minimize sum(cost(i)*xi)

s.t. -xi-xj >= -1

-xi >= -1

xi >= 0

dual LP:

maximize sum_i_E(-yi)+sum_j_1_n(-yj)

s.t. yi <= cost(i)

yi >= 0

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

فکر کنم باید این در میومد که هزینه ی یالها را مینیمم کند که معادل تطابق ماکسیمال با کمترین هزینه بشود. :)

7- فرض کنید A={a1,...,an} مجموعه متناهی باشد که رابطه ای بازتابی، نامتقارن و ترایا روی آن تعریف شده است. این رابطه یک ترتیب جزئی روی A نام دارد. دو عضو ai و aj از A را قابل مقایسه می گویند اگر ai R aj باشد یا aj R ai باشد. دو عضو غیرقابل مقایسه به دو عضوی می گویند که قابل مقایسه نباشند. یک زیر مجموعه S از A را زنجیره می نامند اگر اعضای آن دو به دو قابل مقایسه باشند. اگر اعضای S دو به دو غیرقابل مقایسه باشند به آن ضدزنجیره می گویند. یک پوشش زنجیره (ضد زنجیره) مجموعه ای از زنجیره ها (ضد زنجیره ها) است که دو به دو مجزا هستند و A را پوشش می دهند. اندازه این پوشش تعداد زنجیره ها (ضد زنجیره ها)ی آن است. ثابت کنید نتیجه min-max زیر درست است: اندازه طولانی ترین زنجیره به اندازه کوچکترین پوشش ضدزنجیره است.

راهنمایی: اندازه طولانی ترین زنجیره را m فرض کنید. برای هر a عضو A، تابع f(a) را اندازه طولانی ترین زنجیره که در آن a کمترین عضو است قرار دهید. حالا افراز A را به مجموعه های A_i در نظر بگیرید که اعضای آنها زنجیره های به طول i از اعضای A هستند. i بین 1و m.

حل:

طول بزرگترین زنجیره از هر عضو A یکتا است پس A_i ها A را افراز می کنند. از هر عضو A_i دقیقا حداقل یکی در پوشش ضد زنجیره است، چون به هیچ کدام از این زنجیره ها نمی توان عضو دیگری اضافه کرد (چون هر کدام ماکسیمم هستند). پس طول کوتاهترین پوشش ضدزنجیره m می شود. (ضدزنجیره های با طول بیشتر هم می توانند باشند ولی ما کمترین را می خواهیم.)

8- ثابت کنید در هر ترتیب جزئی، اندازه ی بزرگترین ضدزنجیره مساوی کوتاهترین پوشش زنجیره ای است.

راهنمایی: از قضیه ... استفاده کنید. یک ترتیب جزئی روی یک مجموعه n عضوی داده شده است، گراف دوبخشی U و V و E را در نظر بگیرید که |U|=|V|=n و اگر و تنها اگر a_i <a_j باشد یال (u_i,v_j) عضو E است.

حل:

یک ضدزنجیره یک پوشش راسی از این گراف است، پس پوشش راسی کمینه بزرگترین ضدزنجیره است. اندازه ی آن با تطابق بیشینه مساوی است که کوتاهترین پوشش زنجیره ای است.

*بقیه سوالات فصل مربوط به ضمیمه بودند.