سوال ۱

جدولی را در نظر بگیرید که تمام شکلات‌های آن در یک خانه باشند.

تنها عمل چهارم بر تعداد خانه‌هایی که شکلات دارند می‌تواند تاثیر بگذارد.

چون از یک خانه‌ی با شکلات شروع می‌کنیم و باید به $mn$ خانه‌ی با شکلات برسیم، حداقل $mn-1$ عمل نیاز داریم.

برای اثابت کافی بودن $mn-1$ عمل، تنها بر عمل نوع چهارم تمرکز کنید.

جدول مسئله را به گرافی مدل کنید که هر خانه یک راس و هر مجاورت ضلعی یک یال باشد.

زیردرخت فراگیری از گراف داده شده را در نظر بگیرید. چه استفاده‌ای از آن می‌توان کرد؟

برای هر یال زیردرخت، حذف آن یال دو مؤلفه ایجاد می‌کند که یا تعداد مناسبی شکلات در هر یک است، یا یکی تعداد بیشتر از نیازش شکلات دارد که باید به مؤلفه‌ی دیگر بدهد.

هر یال را در جهتی که باید شکلات از آن عبور کند جهت‌دهی کنید و روی هر یال، تعداد شکلات‌هایی که باید از آن عبور کند را یادداشت کنید.

اگر $O(v)$ را مجموع مقدار یال‌های خروجی راس $v$ و $I(v)$ را مجموع مقدار یال‌های ورودی راس $v$ و $C(v)$ را تعداد شکلات‌های اولیه‌ی راس $v$ در نظر بگیریم، چه رابطه‌ای بین این سه مقدار وجود دارد؟ <راهنمایی>

<راهنمایی> برای هر راس مثل $v$، $$I(v)+S(v)-O(v)=1$$

اگر یکی از این رئوس درجه‌ی ورودی صفر داشته باشد، آیا می‌شود با خیال راحت شکلات‌های مورد نیاز را از هر یال متصل به آن عبور داد؟

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

چون جهت‌دهی انجام شده روی درخت است، پس دور نداریم.

با اعمال سه راهنمایی فوق، کافی است یک topological sort از درخت را در نظر بگیریم، هر بار از یک راس بدون درجه‌ی ورودی، شکلات‌ها را منتقل کنیم.