سوالات ۱۶ تا ۱۸

فرض کنید $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$

پاسخ

گزینه (۳) درست است.

گراف شامل دو دور مجزایال است. هر دور اگر در ابتدا شامل تعداد فردی یال $-1$ باشد، هم‌واره تعداد فردی یال $-1$ خواهد داشت. پس پاسخ حداقل برابر ۲ است. هم‌چنین می‌توان تمام یال‌های مسیر ۴-رأسی پایین را ۱ کرد و سپس اگر در یال‌های متصل به رأس بالا بیش از دو یال $-1$ وجود داشت، با انتخاب رأس بالا تعداد یال‌های $-1$ گراف را حداکثر ۲ کرد.

سوال ۱۷

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

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

پاسخ

گزینه (۳) درست است.

فرض کنید مقداردهی اولیه به شکل زیر باشد (فقط اعداد $-1$ نوشته شده است):

ادعا می‌کنیم به ازای مقداردهی بالا مقدار $f$ از ۲ کم‌تر نیست. فرض کنید از ۲ کم‌تر باشد. به مانند استدلال سوال قبل این مقداردهی شامل یک دور با تعداد فردی $-1$ است. پس نمی‌تواند مقدار $f$ برابر ۰ باشد. هم‌چنین اگر بخواهد این مقدار برابر ۱ شود باید تنها یال $-1$، یال بین رئوس ۲ و ۵ باشد؛ زیرا هر یک از دورهای $1, 2, 4, 5$ و $2, 3, 5, 6$ شامل حداقل یک یال $-1$ خواهند بود. این حالت نیز قابل دست‌یابی نیست؛ زیرا انتخاب شدن و نشدن رأس‌ها یک‌تا تعیین می‌شود و مشاهده می‌کنیم نمی‌توان به این حالت رسید.

از طرفی به ازای هر مقداردهی اولیه می‌توان کاری کرد که حداکثر ۲ یال $-1$ داشته باشیم. پس پاسخ برابر ۲ است.

سوال ۱۸

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

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

پاسخ

گزینه (۴) درست است.

گزاره‌‌ب با مثالی که در سوال قبلی آمده متناقض است.

گزاره‌های الف و ج درست هستند.

▸ سوال قبل سوال بعد ◂