پرش به محتویات

تمرین ۴

ددلاین تحویل: ۲۳ خرداد ۲۳:۵۹

ثبت اولویت ویدیوی حلاگر می‌خواهید برای این تمرین ویدیوی حل ضبط کنید، اولویت سوال‌ها را ثبت کنید.
ثبت اولویت
نمایش:

مقدماتی

سوال ۱ — زیردرخت فراگیر با کمینه ضرب

صورت سوال

یک گراف وزن‌دار \(G\) داریم که وزن هر یال آن عددی طبیعی است. وزن یک زیردرخت فراگیر را برابر با حاصل‌ضرب وزن یال‌های آن تعریف می‌کنیم. الگوریتمی با پیچیدگی زمانی \(\mathcal{O}(n + mlog(n))\) ارائه دهید که زیردرخت فراگیر با کمینه وزن را پیدا کند.

mst

سوال ۲ — کمینه زیردرخت فراگیر آرایه

صورت سوال

یک آرایه به طول \(n\) داریم که مقدار خانه \(i\) ام آن برابر با \(a_i\) است. از روی این آرایه یک گراف کامل بدون‌جهت وزن‌دار \(n\) راسی به اسم \(G\) می‌سازیم و وزن یال بین دو راس \(i , j\) را برابر با \(a_i + a_j\) قرار می‌دهیم. الگورتیمی با پیچیدگی زمانی \(\mathcal{O}(n)\) ارائه دهید که MST این گراف را پیدا کند.

mst

سوال ۳ — درخت پر جنب و جوش

صورت سوال

گراف بدون جهت و وزن‌دار \(G\) و درخت پوشای کمینه‌ی آن داده شده است. می‌خواهیم یک یال به این گراف اضافه کنیم. الگوریتمی ارائه دهید که در زمان \(O(V)\) درخت پوشای کمینه گراف جدید را محاسبه کند.

mst

سوال ۴ — درخت پوشا بازگشتی

صورت سوال

پروفسور بوردن یک الگوریتم جدید تقسیم و غلبه را برای محاسبه درختان پوشای کمینه پیشنهاد می‌کند که به شرح زیر است:

به شما یک گراف \(G = (V,E)\) داده شده است. دسته \(V\) از رئوس را به دو دسته \(V_1\) و \(V_2\) تقسیم کنید به صورتی که حداکثر اختلاف بین \(|V_1|\) و \(|V_2|\) برابر \(1\) باشد. \(E_1\) را مجموعه‌ای از یال‌هایی قرار دهید که فقط مجاور رئوس در \(V_1\) و \(E_2\) هم مجموعه‌ای از یال‌هایی باشند که فقط مجاور رئوس در \(V_2\) هستند. به صورت بازگشتی یک مسئله درخت پوشای کمینه را روی هر یک از دو زیرگراف \(G_1 = (V_1,E_1)\) و \(G_2 = (V_2,E_2)\) حل کنید. در نهایت، یال با کمترین وزن در \(E\) را انتخاب کنید که از برش \((V_1,V_2)\) عبور می‌کند و این یال را برای تبدیل کردن دو درخت پوشای کمینه به دست آمده به یک درخت پوشا استفاده کنید.

استدلال کنید که الگوریتم یک درخت پوشای کمینه از \(G\) به درستی محاسبه می‌کند، یا مثالی ارائه کنید که الگوریتم برای آن شکست بخورد.

mst

سوال ۵ — وزن‌های یکتا، زیردرخت یکتا!

صورت سوال

یک گراف وزن‌دار \(G\) داریم که وزن هر یال آن عددی مثبت است. همچنین وزن هیچ دو یالی یکسان نیست. ثابت کنید که درخت فراگیر کمینه در این گراف یکتا مشخص می‌شود.

mst

سوال ۶ — درست یا نادرست!

صورت سوال

درستی یا نادرستی گزاره‌های زیر را مشخص کنید! برای گزاره‌های درست اثبات و برای گزاره‌های نادرست مثال نقض ارائه دهید.

برای هر مورد کافیه تو حداکثر ۲ جمله به هسته‌ی اثبات اشاره کنید. سخت نگیرید.

فرض کنید \(G\) یک گراف بدون جهت \(n\) راسی و \(m\) یالی و همبند باشد. وزن یال‌ها می‌تواند یکسان باشد مگر اینکه در گزاره‌ای خلاف آن ذکر شده باشد.

  1. اگر \(n \leq m\) باشد و یال با وزن بیشینه در گراف \(G\) یکتا باشد، آنگاه این یال بیشینه در هیچ زیردرخت فراگیر کمینه‌ای ظاهر نمی‌شود.
  2. اگر یال بیشینه گراف \(G\) یکتا باشد و این یال در حداقل 1 دور ظاهر شده باشد آنگاه این یال بیشینه در هیچ زیردرخت فراگیر کمینه‌ای ظاهر نمی‌شود.
  3. فرض کنید \(e\) یک یال با وزن کمینه در \(G\) باشد(لزومی ندارد تنها یال با وزن کمینه باشد). در این صورت این یال در تمام زیردرخت‌های فراگیر \(G\) ظاهر می‌شود.
  4. اگر یال با وزن کمینه در \(G\) یکتا باشد، آنگاه این یال حتما در تمام زیردرخت‌های فراگیر \(G\) ظاهر می‌شود.
  5. الگوریتم PRIM در حالتی که وزن یال‌ها منفی باشد هم درست کار می‌کند.
mst

سوال ۷ — آب

صورت سوال

فرض کنید \(n\) ظرف در یک ردیف قرار دارند. ظرف \(i\) ام گنجایش \(a[i]\) دارد.
در ابتدا تمام ظرف‌ها خالی هستند.

دو نوع عملیات باید پشتیبانی شود:

  1. ریختن آب: مقدار \(x\) واحد آب به ظرف \(p\) اضافه کن.
    اگر مجموع آب موجود در ظرف \(p\) به‌همراه \(x\) از گنجایش \(a[p]\) بیشتر شود،
    مقدار اضافی (سرریز) به طور خودکار به ظرف بعدی (\(p+1\)) منتقل می‌شود.
    این سرریز به همین ترتیب تا جایی ادامه می‌یابد که یا آب اضافی تمام شود، یا به ظرف آخر (\(n\)) برسیم.
    سرریز از ظرف آخر روی زمین می‌ریزد (از دست می‌رود).

  2. پرسش: مقدار فعلی آب درون ظرف \(k\) را گزارش کن.

هدف: طراحی الگوریتمی با \(O((n + m) \log n)\) که \(m\) تعداد کل عملیات‌ها است.

dsu

سوال ۸ — پوشش‌دوری

صورت سوال

فرض کنید یک گراف بدون‌جهت وزن‌دار داده شده است. مجموعه \(F\) یک مجموعه پوشش‌دوری گفته می‌شود اگر به ازای هر دور در گراف، حداقل یکی از یال‌های دور در \(F\) حضور داشته باشد. الگوریتمی با زمان اجرای چندجمله‌ای ارائه دهید که مجموعه \(F\)‌با مجموع وزن کمینه را پیدا کند.

mst
پاسخ - محمد مهدی سیاوشی

سوال ۹ — وزن محدود

صورت سوال

گراف همبند وزن دار \(G\) با \(n\) راس و \(m\) یال داریم که در آن وزن هر یال عددی طبیعی بین \(1\) و \(K\) است. الگوریتمی بهینه برای پیدا کردن کمینه درخت پوشا ارائه دهید.

مرتبه زمانی الگوریتم خود را بر حسب پارامتر های \(n\), \(m\) و \(K\) بررسی کنید.

mst
پاسخ - بهار برقبانی

سوال ۱۰ — برووکا

صورت سوال

فرض کنید \(G\) یک گراف وزن‌دار \(n\) راسی و \(m\) یالی باشد. به ازای هر راس \(v\)، یال‌های متصل به آن را در نظر بگیرید و بین این یال‌ها، یالی که کمینه وزن را دارد را \(mn_v\) بنامید. برای سادگی فرض کنید که وزن یال‌ها متمایز است.

  1. الگوریتمی با پیچیدگی زمانی \(\mathcal{O}(n + m)\) ارائه دهید که برای تمام رئوس \(v\) مقدار \(mn_v\) را محاسبه کند.
  2. ثابت کنید مجموعه یال‌های \(mn_v\) تشکیل دور نمی‌دهند. (این مجموعه یال‌ها را \(M\) بنامید.)
  3. ثابت کنید یال‌های \(M\) در MST ظاهر می‌شوند. یعنی حداقل یک MST وجود دارد که شامل \(M\) باشد.
  4. مولفه‌های همبندی‌ای که یال‌های \(M\) می‌سازند را در نظر بگیرید و رئوس هر مولفه را ادغام کنید (هر مولفه را یک راس در نظر بگیرید) و یال‌هایی که دو سر آن‌ها درون یک مولفه همبندی‌ست را حذف کنید. این عملیات را به طور بازگشتی تکرار کنید تا زمانی که به ۱ راس برسیم.
  5. مختصرا اثبات کنید اجتماع یال‌های انتخاب شده در هر مرحله یک MST از گراف اولیه را می‌سازند.
  6. پیچیدگی زمانی این الگوریتم از چه اردری است؟
mst

سوال ۱۱ — مجموع فاصله‌ها

صورت سوال

یک گراف وزن‌دار \(G\) داریم که وزن هر یال آن عددی طبیعی است. فاصله بین دو راس \(u , v\) (که آن را با \(dis(u , v)\) نمایش می‌دهیم) را برابر با کمینه مقدار \(w\) تعریف می‌کنیم که بتوان با طی کردن یال‌های با وزن حداکثر \(w\) از راس \(u\) به \(v\) رسید. همچنین مقدار \(dis(u , u) = 0\) در نظر می‌گیریم.

الگوریتمی با پیچیدگی زمانی \(\mathcal{O}(n + mlog(n))\) ارائه دهید که مجموع فاصله تمام جفت راس‌ها را محاسبه کند. (جفت‌های \((u , v) , (v , u)\) را یکسان در نظر بگیرید.)

mst
پاسخ - امیرحسین اسفندیاری

سوال ۱۲ — بیشینه تطابق گراف دوبخشی

صورت سوال

فرض کنید \(G\) یک گراف دوبخشی باشد. روشی بر پایه‌ی الگوریتم بیشینه‌شار ارائه دهید که بزرگ‌ترین تطابق در \(G\) را پیدا کند.

به زیرمجموعه‌ای از یال‌های \(G\) تطابق می‌گوییم اگر هیچ دو یالی در آن مجاور نباشند.

flow
راهنمایی‌ها

از روی گراف ورودی گرافی بسازید که شار بیشینه‌ش به اندازه‌ی ماکسیمم مچینگ گراف ورودی باشه.

سوال ۱۳ — جفت خوب

صورت سوال

\(n\) عدد طبیعی داریم. به یک جفت \((a, b)\) از اعداد خوب می‌گوییم اگر نسبت به هم اول باشند و یک \(c\) وجود داشته باشد که \(a^2 + b^2 = c^2\) باشد. الگوریتم چندجمله‌ای ارائه دهید که بررسی کند ایا میتوانیم اعداد را به ‫\(\frac{n}{2}\) ‫جفت خوب افراز کنیم یا خیر. منظور از افراز این است که هر عدد در دقیقا یکی از جفت‌ها آمده باشد.

flow
پاسخ - محمدمهدی فراهانی
فایل‌های همراه

سوال ۱۴ — کمینه بیشینه هزینه k-شار

صورت سوال

‫فرض کنید یک شبکه \(G\) به شما داده شده است به طوری که هر یال ظرفیت محدود و یک هزینه‌ای دارد. می‌خواهیم یک شار با مقدار \(k\) پیدا کنیم به طوری که هزینه آن کمینه باشد. هزینه یک شار برابر با بیشینه هزینه یال‌هایی هست که جریان گذرنده از آنها صفر نیست.

یک الگوریتم چندجمله‌ای ارائه دهید که کمینه هزینه را بدست آورد.

flow
پاسخ - محسن زارع
فایل‌های همراه

سوال ۱۵ — مسیر مجزا

صورت سوال

گراف \(G\) داریم که در آن دو راس \(s\) و \(t\) مشخص شده است. الگوریتمی چندجمله‌ای ارائه دهید که بیشترین تعداد مسیری که از \(s\) به \(t\) باشند و هر راس به جز شروع و پایان در حداکثر یک مسیر آمده باشد را پیدا کنید.

حال فرض کنید یک راس می‌تواند در چند مسیر باشد ولی هر یال در حداکثر یک مسیر می‌تواند باشد. حال برای این حالت نیز الگوریتمی چند جمله‌ای ارائه دهید.

flow
پاسخ - کیان تراکمه

سوال ۱۶ — شار افزایشی

صورت سوال

فرض کنید \(G=(V,E)\) یک گراف جهت‌دار باشد که ظرفیت‌ هر یال یک عدد مثبت صحیح است و در ضمن این گراف دارای یک مبدا \(s\) و یک مقصد \(t\) می‌باشد. فرض کنید شار بیشینه این شبکه مشخص است. در واقع می‌دانیم در شار بیشینه از هر یال چه میزان جریان عبور می‌کند. ظرفیت یکی از یال‌های \(G\) را یک واحد کاهش می‌دهیم. الگوریتمی از مرتبه \(O(n+m)\) ارائه دهید تا شار بیشینه گراف جدید را محاسبه کند که \(n\) و \(m\) تعداد رئوس و تعداد یال‌های گراف است. درستی الگوریتم خود را اثبات کنید.

حال سوال را دوباره به ازای حالتی که به جای افزایش یک واحدی کاهش یک واحدی داشته باشیم، حل کنید.

اگر ظرفیت یال‌ها علاوه بر اعداد صحیح می‌توانستند اعداد حقیقی مثبت باشند چطور‌؟

flow
پاسخ - مهدی شیرین بیان

سوال ۱۷ — برادر

صورت سوال

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

اگر شهر آن‌ها \(n\) تقاطع و \(m\) خیابان داشته‌باشد و خانه و مدرسه‌شان هم خودشان یک تقاطع باشند، الگوریتمی از زمان چند‌جمله‌ای برای پیداکردن ۲ مسیر که دلخواه این دو برادر باشند پیدا کنید. ممکن است ۲ مسیر مجزا یالی با طول‌های کمینه موجود نباشد که در آن صورت الگوریتم باید تشخیص‌بدهد که چنین‌کاری امکان‌پذیر نیست.

flow

سوال ۱۸ — تورنومنت شطرنج

صورت سوال

در مسابقات شطرنج هر ۲ بازیکن با یکدیگر مسابقه می‌دهند و هر بازیکن در صورت برد هر بازی ۲ امتیاز، در صورت تساوی ۱ امتیاز و در صورت باخت صفر امتیاز می‌گیرد. گری کاسپاروف، در دفترچه‌ی خاطراتش همواره جدول نهایی امتیازات مسابقات را به‌ترتیبِ امتیاز نوشته است، ولی علاقه‌ای به نوشتن ریز نتایج بازی‌ها نداشته است.

هدف ما این است که ببینیم این نوشته‌ها حقیقی هستند یا خیر. برای این کار می‌خواهیم ببینیم که آیا جدولی از نتایج مسابقات وجود دارد که جدول امتیازات نوشته‌شده متعلق به آن باشد؟

فرض‌کنید تعداد بازیکن‌ها برابر \(n\) است، برای پیداکردن چنین جدولی الگوریتمی از زمان چند‌جمله‌ای ارائه‌دهید.

flow
پاسخ - Negar yarahmadi
فایل‌های همراه

سوال ۱۹ — برش کمینه یا شار بیشینه؟

صورت سوال

در گراف زیر یک شار بیشینه از \(s\) به \(t\) پیدا کنید.

flow graph flow graph

سپس یک برش کمینه برای \(s\) و \(t\) ارائه دهید.

سوال ۲۰ — پروژه

صورت سوال

به محمد \(n\) پروژه ساختمانی پیشنهاد شده است. می‌دانیم که انجام پروژه \(i\) برای او \(A_i\) واحد سود دارد. البته ممکن است که این عدد منفی باشد که نشان از ضرر است.

برای انجام بعضی از پروژه‌ها لازم است تا قبل از آن مجموعه خاصی از پروژه‌ها انجام شده باشد. به طور دقیق‌تر \(m\) رابطه پیش‌نیازی بین پروژه‌ها داریم. اگر این روابط را با گراف جهتدار مدل کنیم، گراف حاصل بدون دور خواهد بود.

حال به محمد کمک کنید تا تعدادی از پروژه ها را انتخاب کند تا انجام دهد که سودش بیشینه شود و شرط‌های پیش‌نیازی نیز برقرار باشد.

flow
پاسخ - ثنا نیرومند
فایل‌های همراه

سوال ۲۱ — رستوران

صورت سوال

در رستوران تازه تاسیس خرس، سرآشپز لیستی از \(n\) غذا و \(m\) ماده اولیه آماده کرده است. به ازای هر غذا مواد مورد نیاز برای تهیه آن را می‌دانیم. به ازای هر غذا اگر در منو قرار گیرد، در مجموع \(A_i\) دلار سود می‌کنیم. اگر ماده اولیه \(i\) در یکی از غذاهای منو نیاز باشد، برای تهیه آن باید \(B_i\) دلار هزینه کنیم. توجه کنید که اگر یک ماده در چند غذا مورد نیاز باشد، تنها یکبار آن را تهیه میکنیم.

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

flow
پاسخ - نرگس کاری
فایل‌های همراه

سوال ۲۲ — تنگنای کمینه

صورت سوال

شبکه‌ای متشکل از \(n\) رأس، و دو رأس معین \(s\) و \(t\) از این شبکه داده شده است. فرض کنید ظرفیت تمام یال‌های شبکه نامتناهی است. به ازای یک شار \(f\) از \(s\) به \(t\)، یالی که بیش‌ترین شار از آن عبور می‌کند را یال تنگنا، و مقدار شار عبوری از آن یال را «تنگنای» شار \(f\) می‌نامیم. می‌خواهیم به ازای یک مقدار صحیح \(C\) داده‌شده، شاری با مقدار \(C\) را با کم‌ترین تنگنا از \(s\) به \(t\) منتقل کنیم. با چند بار استفاده از الگوریتم فورد-فالکرسن می‌توان این شار را به دست آورد؟

flow
پاسخ - رادین بهارصفت

سوال ۲۳ — آندو‌دار

صورت سوال

یک گراف بدون‌جهت با \(n\) رأس داریم. در ابتدا هیچ یالی در گراف وجود ندارد. سپس \(q\) عملیات از یکی از سه نوع زیر داده می‌شود:

  • add u v: یال \((u,v)\) را به گراف اضافه کن.
  • undo: آخرین عملیات add را که هنوز برگردانده نشده است، برگردان.
  • ask u v: بگو آیا \(u\) و \(v\) در یک مؤلفه‌ی همبند هستند یا نه.

فرض کنید هر بار که عملیات undo داده می‌شود، حداقل یک عملیات add وجود دارد که هنوز undo نشده است.

الگوریتمی ارائه دهید که به همه‌ی پرسش‌های ask پاسخ دهد و پیچیدگی زمانی کل آن \(O(n + q \log n)\) باشد.

راهنمایی‌ها

DSU

پاسخ - صبا خانمحمدی ابهری
فایل‌های همراه

پیشرفته

سوال ۲۴ — MST در صفحه

صورت سوال

فرض کنید \(n\) نقطه در صفحه داشته باشیم. می‌خواهیم پاره‌خط واصل بین \(n - 1\) جفت از این نقاط را رسم کنیم به طوری که از هر کدام از این نقاط تنها با طی کردن پاره‌خط‌های رسم شده بتوان به تمام نقاط دیگر رسید و همچنین مجموع طول پاره‌خط‌های رسم شده کمینه باشد.

ثابت کنید که در این حالت هیچ دو پاره‌خطی همدیگر را قطع نمی‌کنند.

mst
پاسخ - فاطیما تیمارچی
فایل‌های همراه

سوال ۲۵ — یکتایی MST

صورت سوال

گراف همبند \(G=(V,E)\) را در نظر بگیرید. به ازای هر کات \((A,B)\) سبکترین‌ یال(ها) که یک سر آن در \(A\)‌ و دیگری در \(B\) است (لزوما این یال یکتا نیست) را داخل مجموعه \(E'\) قرار می‌دهیم. ثابت کنید درخت پوشای کمینه \(G\) یکتاست اگر و فقط اگر مجموعه یال‌های \(E'\) تشکیل یک درخت پوشا دهند.

mst
پاسخ - سهیل سیاح ورگ

سوال ۲۶ — امن یا خطرناک

صورت سوال

فرض کنید یک گراف همبند و وزن‌دار \(G\) داده شده است. یک یال را امن می‌نامیم اگر در هیچ دوری حضور نداشته باشد. یک یال را خطرناک گوییم اگر سنگین‌ترین یال در یک دور باشد. به سوال‌های زیر پاسخ دهید.

  1. نشان دهید هر یال امن عضو درخت پوشای کمینه است و هر یال خطرناک که تنها سنگین‌ترین یال یک دور باشد عضو درخت پوشای کمینه نیست.
  2. یک پیاده‌سازی کارا از الگوریتم anti-kruskal ارائه و آن را تحلیل کنید. الگوریتم anti-kruskal بدین شکل عمل می‌کند که یال‌ها را به ترتیب از سنگین‌ترین یال به سبک‌ترین یال پردازش می‌کند. اگر نوبت یال \(e\) باشد و این یال، در گراف \(G\) یال خطرناک باشد آن را از گراف \(G\) حذف می‌کند.
mst

سوال ۲۷ — جی‌پی‌تی

صورت سوال

آقای الف می‌خواهد برای آزمون درس طراحی الگوریتم‌ها آماده شود، او روی یک کاغذ یک گراف \(n\) راسی و \(m\) یالی همبند کشیده.

برای یادگیری مبحث درخت پوشای کمینه(MST) او از چت جپت کمک می‌گیرد تا تعدادی زیرمجموعه از یال‌های گراف را به او بدهد. چت جپت در نهایت به آقای الف \(k\) زیرمجموعه از یال‌های گراف(که می‌توانند اشتراک داشته باشند) را می‌دهد به طوری که جمع طول زیر‌مجموعه‌ها برابر \(s\) است.

در نهایت، آقای الف برای تمرین این مبحث، تصمیم گرفته تا به ازای هر زیرمجموعه بفهمد که آیا درخت پوشای کمینه‌ای در گرافش وجود دارد که شامل تمام یال‌های زیرمجموعه باشد یا نه.

به آقای الف کمک کنید تا الگوریتمی با پیچیدگی زمانی طرح کند \(\mathcal{O}((s + m) \log (s + m))\) پاسخ این سوال برای همه زیرمجموعه‌ها بدهد.

mst

سوال ۲۸ — همه یا هیچ‌ کدام

صورت سوال

یک گراف وزن دار با \(n\) راس و \(m\) یال داریم. الگوریتمی با پیچیدگی زمانی \(O(nm)\) ارائه دهید که به ازای هر یال این گراف، مشخص کند در کدام یک از دسته‌های زیر قرار دارد.

  1. در تمام درخت‌های فراگیر کمینه‌ی این گراف حضور دارد.
  2. در بعضی از درخت‌های فراگیر کمینه حضور دارد اما در بعضی حضور ندارد.
  3. در هیچ درخت فراگیر کمینه‌ای حضور ندارد.
mst
پاسخ - محمد بنی‌احمدی
فایل‌های همراه

سوال ۲۹ — کمینه پوشا برای همه

صورت سوال

گراف وزن دار همبند \(G\) را داریم. می‌خواهیم به ازای هر یال آن، کمینه وزن بین زیردرخت‌های فراگیر شامل آن یال را بدست بیاوریم.

الگوریتمی از مرتبه زمانی \(\mathcal{O}((n+m) log(n))\) ارائه دهید که جواب را به ازای تمامی یال‌ها محاسبه کند.

mst

سوال ۳۰ — دومین زیردرخت فراگیر کمینه

صورت سوال

فرض کنید \(G\) یک گراف بدون جهت وزن‌دار باشد. مجموع وزن یال‌های زیردرخت فراگیر کمینه \(G\) را \(T\) در نظر بگیرید. الگوریتمی با پیچیدگی زمانی \(\mathcal{O}(n + mlog(n))\) ارائه دهید که یک زیردرخت فراگیر از \(G\) پیدا کند که مجموع وزن یال‌های آن کمینه باشد، اما از \(T\) بیشتر باشد. در صورت عدم وجود چنین زیردرختی، عدم آن را گزارش کنید.

mst

سوال ۳۱ — شرکت هرمی

صورت سوال

در شکرستان \(n\) نفر داریم که \(m\) جفت از آن‌ها با هم دوست هستند. افراد با اعداد \(1\) تا \(n\) شماره‌گذاری شده‌اند و رابطه‌ی دوستی دوطرفه است.

در حال حاضر شخص شماره‌ی \(1\) از تنها عضو شرکت است. می‌خواهیم همه‌ی افراد عضو شرکت شوند. برای عضو شدن یک فرد جدید، باید یکی از دوستان او که در همان لحظه عضو شرکت است او را دعوت کند. اگر شخص \(u\) کسی را دعوت کند، برای همان دعوت باید مبلغ \(A_u\) به عنوان پورسانت به او پرداخت شود.

الگوریتمی با مرتبه زمانی \(O(n + m \log n)\) ارائه دهید که کمترین هزینه برای عضو کردن تمامی افراد را محاسبه کند.

mst
پاسخ - زهرا امیربیگی

سوال ۳۲ — کمینه پوشای مسطح

صورت سوال

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

mst
راهنمایی‌ها

در گراف مسطح تعداد یال ها حداکثر برابر \(3n - 6\) است.

سوال ۳۳ — شار بازه‌ای

صورت سوال

یک شبکه‌ی جهت‌دار \(G=(V,E)\) داریم. برای هر یال \(e\)، دو مقدار داده شده است: پایین‌کران \(\ell(e)\) و کران بالای \(u(e)\)، به‌طوری که \(0 \leq \ell(e) \leq u(e).\)

می‌خواهیم بدانیم آیا می‌توان روی یال‌ها جریانی تعریف کرد که یک جریان مجاز باشد؛ یعنی برای هر یال \(e\) داشته باشیم \(\ell(e) \leq f(e) \leq u(e)\), و برای هر رأس \(v\)، مقدار کل جریان ورودی به \(v\) برابر با مقدار کل جریان خروجی از \(v\) باشد.

الگوریتمی طراحی کنید که تشخیص دهد آیا چنین جریانی وجود دارد یا نه. در پاسخ خود ایده‌ی اصلی الگوریتم، اثبات درستی و تحلیل زمان اجرا را توضیح دهید.

flow
پاسخ - میلاد رستمی

سوال ۳۴ — شار بازه‌ای بیشینه

صورت سوال

یک شبکه‌ی جهت‌دار \(G=(V,E)\) و دو راس \(s\) و \(t\) داریم. برای هر یال \(e\)، دو مقدار داده شده است: پایین‌کران \(\ell(e)\) و کران بالای \(u(e)\)، به‌طوری که \(0 \leq \ell(e) \leq u(e).\)

می‌خواهیم بدانیم آیا می‌توان روی یال‌ها جریانی تعریف کرد که یک شار مجاز باشد؛ یعنی برای هر یال \(e\) داشته باشیم \(\ell(e) \leq f(e) \leq u(e)\), و برای هر رأس \(v\) به جز \(s\) و \(t\)، مقدار کل جریان ورودی به \(v\) برابر با مقدار کل جریان خروجی از \(v\) باشد.

الگوریتمی طراحی کنید که بیشینه شار مجاز از \(s\) به \(t\) را در زمان چند جمله‌ای پیدا کند یا گزارش کند که شار مجازی وجود ندارد. در پاسخ خود ایده‌ی اصلی الگوریتم، اثبات درستی و تحلیل زمان اجرا را توضیح دهید.

flow

سوال ۳۵ — جدول رنگی

صورت سوال

یک جدول \(n \times n\) داریم که بعضی از خانه‌های سیاه و بقیه خانه‌ها سفیدند. در هر حرکت می‌توانیم یک زیر جدول \(H \times W\) انتخاب کنیم و تمامی خانه‌های داخل آن را سفید بکنیم. هزینه این عملیات \(min(H, W)\) است. حداقل هزینه سفید کردن کل جدول چند است‌؟ الگوریتمی از مرتبه زمانی \(\mathcal{O}(n^3)\) ارائه بدهید.

اگر هزینه رنگ‌آمیزی یک زیر جدول به \(max(H, W)\) تغییر کند، آنگاه الگوریتمی با مرتبه زمانی \(\mathcal{O}(n^5)\) یا کمتر مطلوب است.

flowبرنامه‌ریزی پویا

سوال ۳۶ — برش بسته

صورت سوال

یک گراف دلخواه با مجموعه رئوس \(V(G)\) را در نظر بگیرید. برای دو راس \(s\) و \(t\) یک برش از این گراف میان این دو راس، معادل افراز \(V(G)\) به دو مجموعه
\(S\) و \(T\) است که \(s \in S\) و \(t \in T\). و در این صورت، با حذف تمام تمام یال‌های از \(S\) به \(T\)، \(s\) و \(t\) از هم جدا می‌شوند. در این صورت، اندازه برش برابر است با تعداد یال‌های بین \(S\) و \(T\). یک برش کمینه، برشی است که اندازه آن از همه برش‌های دیگر کمتر باشد.

فرض کنید که \((S_1, T_1)\) و \((S_2, T_2)\) دو برش کمینه از گراف باشند، ثابت کنید که \((S_1 \cap S_2, T_1 \cup T_2)\) و \((S_1 \cup S_2, T_1 \cap T_2)\) نیز دو برش کمینه هستند.

flow
پاسخ - علیرضا منصوری
فایل‌های همراه

سوال ۳۷ — برش کمینه یکتا

صورت سوال

یک شبکه‌ی جهت‌دار \(G=(V,E)\) با مبدأ \(s\)، مقصد \(t\)، و ظرفیت‌های نامنفی روی یال‌ها داریم.

می‌دانیم ممکن است در یک شبکه چندین برش کمینه‌ی مختلف بین \(s\) و \(t\) وجود داشته باشد.

یک شرط لازم و کافی برای یکتا بودن برش کمینه‌ی \(s\)-\(t\) ارائه دهید. الگوریتمی طراحی کنید که تشخیص دهد آیا برش کمینه یکتا است یا نه.

در پاسخ خود ایده‌ی اصلی الگوریتم، اثبات درستی و تحلیل زمان اجرا را توضیح دهید.

flow
راهنمایی‌ها

ابتدا یک بیشینه‌جریان پیدا کنید و گراف باقیمانده‌ی متناظر با آن (residual) را در نظر بگیرید. سپس رأس‌هایی را بررسی کنید که از \(s\) قابل دسترسی‌اند، رأس‌هایی که می‌توانند به \(t\) برسند را تحلیل کنید.

پاسخ - سیدمحمدیاسین حاجی‌خلیلی
فایل‌های همراه

سوال ۳۸ — بدون دور منفی

صورت سوال

یک شبکه‌ی جهت‌دار با ظرفیت و هزینه روی یال‌ها داریم. فرض کنید \(f\) یک جریان مجاز \(s\)-\(t\) با مقدار ثابت \(|f|\) است و گراف باقیمانده‌ی متناظر با \(f\) را در نظر می‌گیریم.

ثابت کنید اگر گراف باقیمانده هیچ چرخه‌ای با مجموع هزینه‌ی منفی نداشته باشد، آنگاه \(f\) در میان همه‌ی جریان‌های مجاز با مقدار \(|f|\)، کمترین هزینه را دارد.

به بیان دیگر، نشان دهید نبودن چرخه‌ی منفی در گراف باقیمانده یک شرط کافی برای این است که \(f\) یک کم‌هزینه‌ترین \(|f|\)-جریان باشد. همچنین لازم بودن این شرط را نیز اثبات کنید.

در اثبات خود می‌توانید از این ایده استفاده کنید که اختلاف دو جریان هم‌مقدار را می‌توان به تعدادی چرخه در گراف باقیمانده تجزیه کرد.

flow

سوال ۳۹ — کمینه هزینه بیشینه شار

صورت سوال

یک شبکه‌ی جهت‌دار \(G=(V,E)\) با \(n\) رأس، \(m\) یال، مبدأ \(s\)، مقصد \(t\)، ظرفیت‌های صحیح نامنفی \(c(e)\)، و هزینه‌ی \(w(e)\) روی هر یال داریم. هزینه‌ی یک جریان برابر است با

\[ \sum_{e\in E} f(e)w(e). \]

فرض کنید مقدار بیشینه‌جریان برابر \(F\) است. الگوریتمی طراحی کنید که در میان همه‌ی بیشینه‌جریان‌های \(s\)-\(t\)، جریانی با کمترین هزینه پیدا کند.

الگوریتم شما باید در زمان \(\mathcal{O}(Fnm)\) اجرا شود.

در پاسخ خود توضیح دهید چگونه در هر مرحله از گراف باقیمانده استفاده می‌کنید، چگونه مسیر افزایشی کم‌هزینه را پیدا می‌کنید، چرا تعداد مراحل حداکثر \(F\) است، و چرا جریان نهایی کم‌هزینه‌ترین بیشینه‌جریان است.

flow

سوال ۴۰ — افراز به مسیر

صورت سوال

یک گراف جهت‌دار بدون دور \(n\) راسی و \(m\) یالی داریم. می‌خواهیم تعدادی مسیر انتخاب کنیم که هر راس در دقیقا یک مسیر آمده باشد. کمینه تعداد مسیر مورد نیاز چند است‌‌؟

الگوریتمی ارائه دهید که با حداکثر یک بار استفاده از بیشینه شار بر روی گرافی دلخواه و محاسباتی از مرتبه زمانی \(\mathcal{O}(n + m)\) جواب را پیدا کند.

flow

سوال ۴۱ — عدددهی عجیب

صورت سوال

به یک گراف که به هر یال آن یک عدد نامنفی نسبت داده شده است، عجیب می‌گوییم اگر به ازای هر زیر مجموعه از رئوس مانند \(S\) از اعضای آن، مجموع اعداد نسبت داده شده به یال هایی که بین اعضای مجموعه \(S\) هستند، حداکثر \(|S| - 1\) باشد. حال الگوریتمی چندجمله‌ای ارائه دهید که عجیب بودن یا نبودن یک گراف را بررسی کند.

flow

سوال ۴۲ — اسنپ

صورت سوال

یک شهر داریم که از \(n\) میدان تشکیل شده که با \(m\) جاده به هم متصل شده‌اند. به ازای هر جاده مدت زمان لازم عبور از آن را \(w_i\) می‌نامیم. در شرکت اسنپ می‌دانیم که امروز قرار است \(k\) مشتری داشته باشیم. مشتری \(i\)م در زمان \(t_i\) می‌خواهد که از شهر \(a_i\) به شهر \(b_i\) برود.

به علت مشکلات عمده، مشتری‌ها از منتظر ماندن خوششان نمی‌آید و حتما باید در ثانیه \(t_i\) تاکسی در \(a_i\) باشد. حداقل چند راننده نیاز داریم تا بتوانیم همه مشتری ها را برسانیم؟

توجه کنید که راننده‌ها از هر مسیری می‌توانند بروند و در هر لحظه حداکثر یک مشتری را سوار می‌کنند. همچنین راننده ها می‌توانند در میدان‌ها استراحت کنند و حرکت نکنند اما نمی‌توانند در بین جاده استراحت یا تغییر حهت بدهند.

الگوریتمی چند جمله‌ای برای پیدا کردن جواب مسئله ارائه دهید.

flow