مسئلهٔ گراف کامل با برچسب‌های دودویی

روی هر یال از گراف کاملِ $2^n$ راسی، یکی از اعداد مجموعهٔ $\set{0, 1, 2, \ldots , 2^{\,n-1}-1}$ (یعنی یک عددِ $(n-1)$ بیتی) نوشته شده است. به‌طوری‌که در هر مثلث، مجموع دو یال برابرِ یال سوم است ثابت کنید در این گراف مثلثی وجود دارد که روی هر سه یال آن عدد صفر نوشته شده باشد. (امریکا ۲۰۰۲)

ایدهٔ اصلی: استقرا بر $n$

چرا استقرا در مسائل ترکیبیاتی چنین قدرتمند است؟

استقرا یکی از مؤثرترین ابزارهای حل مسئله است—به‌ویژه زمانی که ساختار مسئله در اندازه‌های مختلف «خویشاوند» باشد.

در مسائل گرافی با برچسب‌های عددی، معمولاً دو مسیر برای دیدن استقرا وجود دارد:

پیدا کردن یک زیرگراف کوچک‌تر که همان شکل مسئله را (اما در اندازه کوچکتر) داشته باشد؛
تبدیل کردن وزن‌ها (برچسب یال‌ها) به وزن‌هایی ساده‌تر،
به‌گونه‌ای که باز هم همان شرط مسئله برقرار بماند.

در این مسئله نیز دقیقاً همین دو ایده را بررسی می‌کنیم.

تلاش اول: پیدا کردن زیرگراف مناسب برای فرض استقرا

می‌خواهیم فرض استقرا را درون حکم پیدا کنیم؛ یعنی زیرگرافی از گراف اصلی بسازیم که:

تعداد رئوسش برابر $2^{n-1}+1$ باشد؛
و روی یال‌هایش اعداد $\set{0, 1, 2, \ldots, 2^{n-2}-1}$ (یعنی $(n-2)$ بیتی) نوشته شده باشد؛
(چون فرض استقرا برای $n-1$ به چنین وضعیتی اشاره دارد)
و شرط مسئله که در هر مثلث جمع دو یال برابر سوم است برقرار باشد.

یک ایدهٔ طبیعی این است که یک رأس را درنظر بگیریم و به یال‌های متصل به آن نگاه کنیم.
تمام این یال‌ها یا مقدارشان کوچک است یعنی کوچک‌تر از $2^{n-2}$ هستند (بیتِ $n-1$ آن‌ها صفر است)

یا بزرگ است یعنی بزرگ‌تر یا مساوی $2^{n-2}$ هستند (بیتِ $n-1$ آن‌ها یک است).

در یک مثلث اگر مقدار دو یال برابر $a$ و $b$ باشد، مقدار یال سوم یا $a+b$ است و یا $\mid a-b \mid$ .
اگر دو یال از یک مثلث بزرگ‌ باشند یال سوم نمی‌تواند بزرگ باشد چرا که جمع دو عدد بزرگ بیش از $2^{n-1}$ می‌شود.
اگر تعداد رأس‌هایی که با یال‌های بزرگ به رأس انتخاب‌شده وصل‌اند
بیش از $2^{n-1}+1$ باشد،
تمام یال‌های میان این دسته از رأس‌ها کوچک هستند (بیت سمت چپشان صفر است)
در این صورت زیرگراف مناسب را پیدا کرده‌ایم.

اما مشکل اینجاست:

برای آن دسته از رأس‌هایی که با یال‌های کوچک به رأس اولیه وصل‌اند،
نمی‌توانیم به‌سادگی یک استدلال مشابه بسازیم.

و این شکاف باعث می‌شود این مسیر به نتیجهٔ مورد انتظار نرسد. به بیان دیگر، تقسیم رأس‌ها به دو دستهٔ «یال کوچک» و «یال بزرگ» فقط نیمهٔ ماجرا را کنترل می‌کند و نیمهٔ دیگر مهارناپذیر باقی می‌ماند.

تلاش دوم: کاهش بیت‌ها با تبدیل وزن‌ها

چگونه وزن‌های $(n-1)$ بیتی را به وزن‌های $(n-2)$ بیتی تبدیل کنیم؟

اگر بخواهیم یک زیرگراف با وزن‌های کوچک‌تر پیدا کنیم، می‌توانیم به جای انتخاب زیرمجموعهٔ رئوس، خود وزن‌ها را تبدیل کنیم:

وزن‌ها در گراف اصلی $(n-1)$ بیتی‌اند یعنی عددی از مجموعه‌ی $\set{0, 1, 2, \ldots , 2^{\,n-1}-1}$ ؛
وزن‌های مورد نیاز برای فرض استقرا $(n-2)$ بیتی‌اند یعنی عددی از مجموعه‌ی $\set{0, 1, 2, \ldots, 2^{n-2}-1}$ ؛
پس باید یکی از بیت‌ها را حذف کنیم.

سؤال طبیعی:
چطور می‌توان یکی از بیت‌های وزن‌ها را حذف کرد، بدون آن‌که شرط مسئله («در هر مثلث مجموع دو یال برابر سوم باشد») خراب شود؟

یک مشاهدهٔ کلیدی این است:

اگر عددی را بر ۲ تقسیم کنیم (شیفت به راست در دودویی)،
بیت سمت راست حذف می‌شود.
و از آن‌جا که اگر $a + b = c$ آن‌گاه $\frac{a}{2} + \frac{b}{2} = \frac{c}{2}$ ،
هر شرطی از نوع «مجموعِ دو یال برابر یال سوم»
پس از تقسیم بر ۲ همچنان برقرار می‌ماند به شرطی که تمام وزن‌ها زوج باشند.

بنابراین اگر بتوانیم زیرگرافی پیدا کنیم که تمام وزن‌های یال‌های آن زوج‌ باشد و حداقل $2^{n-1} + 1$ راس داشته باشد می‌توانیم با خیال راحت وزن‌ها را نصف کنیم و یک گراف جدید بسازیم که:

$2^{n-1} + 1$ رأس دارد،
اما وزن‌هایش $(n-2)$ بیتی شده‌اند،
و همچنان شرط جمع روی مثلث‌ها برقرار است.

این دقیقاً «دروازهٔ ورود» به فرض استقرا است.

گام کلیدی: جدا کردن یال‌های زوج و فرد

اکنون به سراغ ایدهٔ اصلی برای اجرای استقرا می‌رویم.

یک رأس دلخواه از گراف را در نظر بگیرید و آن را $v$ بنامید.
تمام یال‌های متصل به این رأس یا زوج هستند یا فرد.

بر این اساس، رأس‌های دیگر را به دو دسته تقسیم می‌کنیم:

دستهٔ اول: رأس‌هایی که با یالِ زوج به $v$ متصل‌اند؛
دستهٔ دوم: رأس‌هایی که با یالِ فرد به $v$ متصل‌اند.

این تقسیم‌بندی تمام رأس‌های گراف (به‌جز خود $v$ ) را پوشش می‌دهد.

یک مشاهدهٔ ساده اما تعیین‌کننده

ادعا می‌کنیم:

یال‌های میان راس‌های دسته‌ی اول و همچنین یال‌های میان راس‌های دستهٔ دوم، حتماً زوج‌اند.

چرا؟

فرض کنید $u$ و همچنین $w$ رأسی‌هایی باشند که یال $vu$ و $vw$ زوج است در مثلث $vuw$ ، طبق شرط مسئله، یکی از این سه رابطه برقرار است:

vu + vw = uw \quad \text{یا} \quad |vu - vw| = uw.

اما در هر دو حالت جمع یا تفاضل دو عدد زوج زوج است. (مانند همین استدلال برای جمع یا تفاضل دو عدد فرد نیز برقرار است).

انتخاب زیرگراف مناسب برای استقرا

اکنون به تعداد رأس‌ها نگاه می‌کنیم.

اگر تعداد رأس‌هایی که با یال فرد به $v$ وصل‌اند
بیش از $\;2^{n-1}$ باشد،
زیرگراف القایی روی این رأس‌ها دارای:

حداقل $2^{n-1}+1$ رأس،
و تمام یال‌های آن زوج است
(چون یال‌های داخل یک دسته زوج‌اند).

در این صورت، زیرگراف مناسب برای استقرا را پیدا کرده‌ایم.

و اگر چنین نباشد؟

یعنی اگر تعداد رأس‌های متصل با یال فرد کمتر یا مساوی $2^{n-1}$ باشد،
آن‌گاه تعداد رأس‌های متصل با یال زوج حداقل $2^{n-1}$ است.

در این حالت، رأس $v$ را نیز به این مجموعه اضافه می‌کنیم.
در نتیجه مجموعه‌ای با دست‌کم:

2^{n-1} + 1

رأس به‌دست می‌آوریم که:

تمام یال‌های بین آن‌ها زوج هستند.

نتیجهٔ این گام

در هر دو حالت، موفق شده‌ایم زیرگرافی با:

حداقل $2^{n-1}+1$ رأس،
و فقط یال‌های زوج،

پیدا کنیم.

اکنون می‌توانیم وزن تمام یال‌های این زیرگراف را بر ۲ تقسیم کنیم؛
با این کار:

وزن‌ها $(n-2)$ بیتی می‌شوند،
شرط مسئله روی مثلث‌ها حفظ می‌شود،
و فرض استقرا قابل‌اعمال است.

در گام بعد، با اعمال فرض استقرا روی این زیرگراف، به وجود یک مثلث با یال‌های صفر می‌رسیم، مثلث صفر در زیرگراف با وزن‌های جدید مثلث صفر در گراف اصلی را نتیجه می‌دهد چرا که $0 \times 2 = 0$ و اثبات کامل می‌شود.

جمع‌بندی

در این مسئله، با گراف کاملی سروکار داشتیم که یال‌های آن با عددهای دودویی برچسب‌گذاری شده بودند و شرطی محلی اما بسیار قوی روی هر مثلث برقرار بود:
در هر مثلث، یکی از یال‌ها برابر مجموع دو یال دیگر است.

کلید حل مسئله، دیدن ساختار استقراییِ پنهان در دل همین شرط محلی بود. ابتدا تلاش کردیم با پیدا کردن یک زیرگراف مناسب مستقیماً فرض استقرا را بیابیم، اما دیدیم که تقسیم سادهٔ یال‌ها به «بزرگ» و «کوچک» تنها نیمی از مسئله را مهار می‌کند.

در گام بعد، با تغییر زاویهٔ نگاه، به‌جای انتخاب زیرگراف، خودِ وزن‌ها را هدف قرار دادیم. ایدهٔ تعیین‌کننده این بود که اگر بتوانیم مجموعه‌ای بزرگ از رأس‌ها پیدا کنیم که تمام یال‌های میان آن‌ها زوج باشند، می‌توانیم با نصف‌کردن وزن‌ها یک گراف جدید بسازیم که دقیقاً شکل فرض استقرا را دارد.

تقسیم رأس‌ها بر اساس زوج یا فرد بودن یال‌های متصل به یک رأس ثابت و استفاده از شرط مسئله روی مثلث‌ها، به ما اجازه داد چنین زیرگرافی را با حداقل $2^{n-1}+1$ رأس پیدا کنیم. پس از آن، با نصف‌کردن وزن‌ها و اعمال فرض استقرا، به وجود یک مثلث با یال‌های صفر رسیدیم.