میان ترم الگوریتم پیشرفته

۱- n عنصر و m مجموعه داریم که هر مجموعه k عضو دارد می‌خواهیم عناصر را با k رنگ، رنگ آمیزی کنیم که از هر رنگ یکی در هر مجموعه باشد.
الف) ثابت کنید که این مسأله NP است.
ب) ثابت کنید که برای k=3 ان پی کامل است. (با استفاده از ۳-رنگ پذیری گراف)
ج) ثابت کنید برای k=2 پی است.
جواب:
الف) یک مصداقش در زمان چندجمله‌ای قابل جواب دادن است.
ب) هر رأس و رأسهای مجاور را یک مجموعه بگیرید.
ج) رنگ آمیزی گراف با دو رنگ فقط برای گراف دوبخشی ممکن است (دور فرد نداشته باشد).
۲- مسأله‌ی هش کردن پویا را با فرض اینکه به جای دو برابر رادیکال n برابر کنیم که n تعداد عناصر موجود است حل کنید.
الف) زمان درج هش پویای معمولی چقدر است.
ب) حداکثر جای خالی جدول در این تعریف جدید چقدر است؟ (ثابت کنید از مرتبه رادیکال n است)
ج) زمان درج برای این حالت جدید چقدر است؟ (سرشکنی)
جواب: تابع پتانسیل را تعداد اعداد موجود منهای توان ۲ تعداد جاهای خالی +۱ گرفتم. (اون +۱ برای حالت پایه اش بود که منفی نشه)

۳- یک گراف نامشخص داریم فقط درجه ورودی و خروجی هر رأس را می‌دانیم. گراف را پیدا کنید.

جواب: شار بیشینه. n رأس سمت راست و n رأس سمت چپ می‌گذاریم و از s با درجه خروجی هر رأس و به t با درجه ورودی هر رأس وصل می‌کنیم. بین رأسهای سمت راست و چپ هم یالهای با ظرفیت ۱ می‌گذاریم. این گراف جهت دار بدون یال چندگانه و با طوقه می‌دهد. اگر بخواهیم طوقه نداشته باشد باید رأسها را به خودشان وصل نکنیم. برای یال چندگانه هم ظرفیت بینهایت بگذاریم به جای ۱.

۴- در مورد push relabel به سوالهای زیر جواب بدهید:

الف) ثابت کنید اگر رأس u پیش شار داشته باشد در Gf مسیر از u به s هست.

ب) تعداد عملیات مختلف را به دست بیاورید. non saturating push, saturating push, relabel

*اگر سوالی هست که یادم رفته بنویسم کامنت بگذارید.