====== سوال ۳ ======


یک گراف ساده‌ی ‎$G$‎ داریم. می‌خواهیم به هر یال مانند ‎$e$‎، یک عدد حقیقی مانند ‎$f(e)$‎ نسبت دهیم، طوری که شروط زیر برقرار باشد:
  * برای هر یال مانند ‎$e$‎ داشته باشم: ‎$0 \leq f(e) \leq 1$.
  * مجموع اعداد یال‌های متصل به هر رأس، حداکثر ‎۱‎ باشد.

بیشینه‌ی ممکن مجموع اعداد یال‌های ‎$G$‎ را، ‎$max(G)$‎ می‌نامیم. حال هر یک از قسمت‌های زیر را حل کنید.

  - ثابت کنید اگر گراف داده شده، دوبخشی باشد، می‌توان به هر یال، یکی از اعداد ‎۰‎ و ‎۱‎ را نسبت داد، طوری که مجموع اعداد یال‌های ‎$G$‎، برابر ‎$max(G)$‎ شود.
  - ثابت کنید اگر گراف داده شده، دور زوج نداشته باشد، می‌توان به هر یال، یکی از اعداد ‎۰‎ و ‎$\frac{1}{2}$‎ و ‎۱‎ را نسبت داد، طوری که مجموع اعداد یال‌های ‎$G$‎، برابر ‎$max(G)$‎ شود. ‎
  - ثابت کنید برای هر گراف داده شده، می‌توان به هر یال، یکی از اعداد ‎۰‎ و ‎$\frac{1}{2}$‎ و ‎۱‎ را نسبت داد، مجموع اعداد یال‌های ‎$G$‎، برابر ‎$max(G)$‎ شود. ‎‎‎ ‎


  * [[سوال ۲|سوال قبل]]