حل سوال ۲ امتحان تقریبی
من سوال ۲ را از خود استاد پرسیدم حل آن با این روش است:
می‌توانیم همیشه یک جواب صحیح بسازیم که جواب بهینه باشد. برای این کار وزن هر یال را صفر می‌کنیم و به یکی از یالهای غیرصفر همسایه‌اش می‌دهیم. در این صورت چون دور فرد (و در نتیجه مثلث) نداریم جمع همچنان ثابت می‌ماند و جواب مسأله تغییر نمی‌کند و قیدی هم به هم نمی‌خورد. با این کار به یک جواب صحیح می‌رسیم، چون جمع یالهای مجاور هر رأس ۱ است. چون قید صفر بودن متغیر یک رأس اگر اتفاق بیفتد، سر دیگر یالهای متصل به آن باید ۱ شوند تا قیدهای مسأله به هم نخورد و در این صورت جمعشان ۱ می‌شود. در این صورت یک گراف دوبخشی ساخته می‌شود که جواب بهینه‌ی آن باید ۰و۱ باشد. پس جواب بهینه‌ی صحیح برای مسأله وجود دارد. اگر یک رأس در هر دو دسته باشد هم مشکلی پیش نمی‌آید، چون در این صورت همه‌ی قیدهای مکمل برقرار می‌شوند.
