فرض کنید $G$ یک گراف باشد که روی هر یال آن یکی از دو عدد $1$ و $-1$ نوشته شده است. در هر مرحله می‌توان یک رأس از گراف در نظر گرفت و عدد تمام یال‌های متصل به آن را قرینه کرد. کمینه‌ی تعداد یال‌های با عدد $-1$ را که می‌توان با انجام تعدادی مرحله به آن‌ رسید، $f(G)$ می‌نامیم. برای مثال در گراف زیر مقدار تابع $f$ برابر ۰ است.

بیشینه‌ی مقدار $f(G)$ را به ازای تمام مقادیر اولیه‌ی ممکن برای یال‌ها، $h(G)$ در نظر می‌گیریم. برای مثال در گراف زیر مقدار $h$ برابر ۱ است:

همان‌طور که در مثال بالا می‌بینید، ورودی تابع $f$ گرافی با یال‌های مقداردهی‌ شده و ورودی تابع $h$ گرافی با یال‌های مقداردهی‌ نشده است.

مقدار $h$ را برای گراف زیر بیابید:

1. $0$
2. $1$
3. $2$
4. $3$
5. $4$

مقدار $h$ را برای گراف زیر بیابید:

1. $0$
2. $1$
3. $2$
4. $3$
5. $4$

کدام گزاره‌های زیر درست هستند؟

• الف) مقدار $h$ در هر گراف از بیشینه‌ی تعداد دورهای یال‌مجزا کم‌تر نیست (به مجموعه‌ای از دورها، دورهای یال‌مجزا می‌گوییم اگر هر یال از گراف در حداکثر یکی از دورهای آن مجموعه آمده باشد).
• ب) مقدار $h$ در هر گراف از بیشینه‌ی تعداد دورهای یال‌مجزا بیش‌تر نیست.
• ج) فرض کنید $G$ یک گراف با یک مقداردهی اولیه باشد که $f(G)=0$. اگر $G$ دارای $k$ مؤلفه باشد، دقیقاً $2^k$ روش وجود دارد که در آن هر رأس انتخاب شود یا نشود و در انتها عدد روی تمام یال‌ها $1$ شوند.

1. الف
2. الف و ب
3. ب و ج
4. الف و ج
5. الف و ب و ج

• سوال بعد
• سوال قبل