در گراف $G$ می‌خواهیم تطابقی (نه لزوما کامل) پیدا کنیم که بیش‌ترین وزن را دارد. ولی از آن‌جایی که دستگاه پردازشگر ما خیلی قوی نمی‌باشد مجبوریم الگوریتم ساده بدهیم. وزن یال $e$ را به صورت $w(e)$ و مجموع وزن‌های یال‌های درون مجموعه‌ی $X$ را با $w(X)$ نمایش می‌دهیم. الگوریتمی که به دستگاه ما داده شده به این صورت است:

• این الگوریتم همیشه یک عدد تطابق $M$ نگه می‌دارد. و آن را به روز می‌کند. در ابتدای کار $M$ تهی می‌باشد.
• یال‌های گراف یکی یکی به الگوریتم داده می‌شوند و به ازای هر کدام (مثلا $e$) این عملیات را اجرا می‌کند:

– مجموعه‌ی یال‌هایی از $M$ که مجاور به $e$ هستند را $X$ می‌نامیم. در صورتی $\frac{1}{2} w(e) >w(X)$ یال $e$ را به $M$ اضافه می‌کند و یال‌های $X$ را از آن حذف می‌کند.

در پایان کار $M$ را به عنوان خروجی نمایش می‌دهد.

اندازه‌ی جوای که این الگوریتم می‌یابد را $w(M)$ و اندازه‌ی تطابق بیشینه را $M_{max}$ می‌نامیم. می‌خواهیم نشان دهیم:

(۱) $$w(M)\geq \alpha M_{max}$$

الف) ثابت کنید عدد ثابت $\alpha$ ای وجود دارد که همیشه رابطه‌ی ۱ برقرار باشد.

ب) ادعای قسمت الف را به ازای $\alpha=\frac{1}{8}$ اثبات کنید.

ج) ادعای قسمت الف را به ازای $\alpha=\frac{1}{6}$ اثبات کنید.

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