مسئلهٔ برچسبگذاری یالهای گراف کامل
روی یالهای یک گراف کامل $G$، اعداد $1, 2, \dots, n$ را نوشتهایم،
بهطوریکه در هر مثلثِ گراف:
- عددِ روی دو یال با هم برابر است،
- و عددِ روی یالِ سوم از آن دو عدد بزرگتر است.
گراف $G$ دستِ بالا چند راس میتواند داشته باشد؟
اولین برخورد با مسئله: از حالتهای ساده شروع کنیم
وقتی برای اولین بار با یک مسئلهٔ جدید روبهرو میشویم، معمولاً ساختار آن هنوز برایمان شفاف نیست.
در چنین موقعیتی، یکی از بهترین استراتژیها این است که مسئله را در سادهترین حالتهای ممکن امتحان کنیم؛
یعنی بهجای حملهٔ مستقیم به حالت کلی، ابتدا سراغ مقادیر کوچک برویم.
این کار دو فایدهٔ مهم دارد:
- ابهام مسئله کمتر میشود و میفهمیم دقیقاً با چه نوع محدودیتی طرف هستیم؛
- الگوها و رفتارهایی ظاهر میشوند که بعداً در حل کلی راهگشا هستند.
به این رویکرد معمولاً میگویند:
دستبهکار شدن و آلودن دستها (get your hands dirty)
یعنی بهجای فکر کردن انتزاعی و دور از مثال،
واقعاً با مسئله کار کنیم، مثال بسازیم، و ببینیم چه چیزهایی ممکن است و چه چیزهایی نه.
بررسی مسئله برای $n$های کوچک
گام اول: بررسی حالت $n = 1$
در حالت $n = 1$، فقط اجازه داریم عدد $1$ را روی یالها بنویسیم.
از طرفی، شرط مسئله میگوید که در هر مثلث:
- عدد دو یال برابر است،
- و عدد یال سوم از آن دو بزرگتر است.
اما وقتی تنها عدد مجاز $1$ باشد، هیچ عددی بزرگتر از $1$ وجود ندارد. پس نتیجهٔ مهمی میگیریم:
در گراف نمیتواند حتی یک مثلث وجود داشته باشد.
چون اگر مثلثی وجود داشته باشد، شرط «بزرگتر بودن یال سوم» بلافاصله نقض میشود. بنابراین در حالت $n = 1$:
- گراف میتواند حداکثر $2$ رأس داشته باشد.
این اولین دادهٔ عددی ماست.
فعلاً شاید ساده بهنظر برسد، اما همین بررسیهای کوچک هستند که مسیر حل کلی را روشن میکنند.
گام دوم: بررسی حالت $n = 2$
اولین نشانههای ساختار
حالا اجازه داریم روی یالها فقط دو عدد بنویسیم $1$ و $2$. شرط مثلث را دوباره، اما دقیقتر، در این حالت بخوانیم:
- در هر مثلث، دو یال عدد برابر دارند،
- و یال سوم عددی بزرگتر از آن دو دارد.
از آنجا که فقط دو عدد داریم، نتیجهٔ مهم و فوری این است:
در هر مثلث، دقیقاً دو یال با عدد 1
و یک یال با عدد 2 وجود دارد.
گراف با 3 رأس
گراف کامل روی 3 رأس فقط یک مثلث دارد.
میتوانیم بهراحتی یکی از یالها را 2 بگذاریم و دو تای دیگر را 1.
پس گراف با $3$ رأس ممکن است.
گراف با 4 رأس
گراف کامل روی 4 رأس، چهار مثلث دارد.
سؤال طبیعی این است:
آیا میتوان یالهای 2 را طوری انتخاب کرد
که هر مثلث دقیقاً یکی از آنها را در خود داشته باشد؟
یک انتخاب جالب این است:
- رأسها را به دو جفت تقسیم کنیم،
- یال بین هر جفت را با عدد 2 برچسب بزنیم،
- بقیهٔ یالها را 1 بگذاریم.
در این حالت:
- هر مثلث دقیقاً شامل یکی از این یالهای 2 است،
- و شرط مسئله در همهٔ مثلثها برقرار میماند.
پس گراف با 4 رأس هم امکانپذیر است.
آیا 5 رأس هم ممکن است؟
اینجا جایی است که ساختار شروع به مقاومت میکند.
اگر بخواهیم شرط «هر مثلث دقیقاً یک یال 2 دارد» را نگه داریم، باید یالهای 2 را آنقدر منظم پخش کنیم که:
- هیچ مثلثی بدون یال 2 نماند،
- و هیچ مثلثی بیش از یکی نگیرد.
اما در گراف کامل روی 5 رأس:
- تعداد مثلثها بهشدت زیاد میشود،
- و هر یال در مثلثهای متعددی شرکت میکند.
با کمی امتحان کردن (یا کمی جلوتر با استدلال دقیقتر)، میبینیم که:
هر چیدمانی از یالهای 2 در نهایت
یا یک مثلث بدون یال 2 میسازد،
یا مثلثی با دو یال 2.
و هر دو حالت، شرط مسئله را نقض میکنند.
آنچه تا اینجا بهدست آوردیم:
- برای $n = 2$:
- با $4$ رأس هم ممکن است،
- اما با $5$ رأس دیگر نمیشود شرط مثلث را حفظ کرد.
آیا ایدهٔ استقرا جواب میدهد؟
ساختن گراف بزرگتر از روی گراف کوچکتر
بعد از بررسی حالتهای $n = 1$ و $n = 2$، یک الگو کمکم خودش را نشان میدهد: هر بار که تعداد اعداد مجاز روی یالها (مقدار $n$) یک واحد بیشتر میشود، بهنظر میرسد بتوان اندازهٔ گراف را دو برابر کرد.
این مشاهده ما را به یک سؤال طبیعی میرساند:
آیا میتوان از یک گراف کامل با برچسبهای $1$ تا $n$،
یک گراف کامل بزرگتر با برچسبهای $1$ تا $n+1$ ساخت
که شرط مثلث همچنان برقرار بماند؟
اگر پاسخ مثبت باشد، ایدهٔ استقرا بهطور جدی وارد بازی میشود.
فرض استقرا
فرض کنید برای عدد $n$، یک گراف کامل وجود دارد که:
- یالهای آن با اعداد $1,2,\dots,n$ برچسبگذاری شدهاند،
- شرط مسئله در تمام مثلثها برقرار است،
- و این گراف $k$ رأس دارد.
میخواهیم با استفاده از همین گراف، یک گراف کامل جدید با برچسبهای $1,2,\dots,n+1$ بسازیم که تعداد رأسهایش بیشتر باشد.
یک تغییر ساده اما کلیدی
اولین حرکت ما بسیار ساده است، اما مهم:
- تمام برچسبهای یالهای گراف اولیه را یک واحد افزایش میدهیم.
یعنی:
- یالهایی که عدد $1$ داشتند، حالا $2$ میگیرند،
- یالهای $2$ تبدیل به $3$ میشوند،
- و بهطور کلی، هر عدد $x$ به $x+1$ تبدیل میشود.
بعد از این تغییر:
- همهٔ برچسبها در بازهٔ $2$ تا $n+1$ قرار دارند،
- و شرط مثلث همچنان برقرار است
(چون فقط یک انتقال یکنواخت روی اعداد انجام دادهایم).
دو نسخه کنار هم
حالا از این گرافِ جدید، دو نسخهٔ کاملاً یکسان میسازیم:
- هر دو نسخه گراف کاملاند،
- هر دو دقیقاً همان برچسبگذاری را دارند،
- و هیچ رأسی میان دو نسخه مشترک نیست.
تا اینجا، هر نسخه بهتنهایی تمام شرایط مسئله را ارضا میکند.
اتصال دو بخش با یالهای 1
اکنون مرحلهٔ تعیینکننده میرسد.
- هر رأس از نسخهٔ اول را به هر رأس از نسخهٔ دوم وصل میکنیم،
- و تمام یالهای بین این دو بخش را با عدد $1$ برچسب میزنیم.
در نتیجه:
- گراف نهایی هنوز یک گراف کامل است،
- و برچسبهای یالها دقیقاً اعداد $1$ تا $n+1$ را تشکیل میدهند.
بررسی شرط مثلث
حالا باید مطمئن شویم که در تمام مثلثهای گراف جدید،
شرط مسئله برقرار است.
سه حالت ممکن داریم:
۱. مثلثهایی که کاملاً در یکی از دو نسخهاند
در این حالت:
- هر سه رأس مثلث در یک نسخه قرار دارند،
- و یالهای آن فقط برچسبهای $2$ تا $n+1$ دارند.
چون این گراف از فرض استقرا آمده، شرط مسئله در این مثلثها برقرار است.
۲. مثلثهایی که دو رأس در یک نسخه و یک رأس در نسخهٔ دیگر دارند
در چنین مثلثی:
- دو یال، یالهای بین دو نسخهاند و برچسب $1$ دارند،
- یال سوم داخل یکی از نسخههاست و عددی بزرگتر از $1$ دارد.
پس در این مثلث:
- دو یال عدد برابر ($1$) دارند،
- و یال سوم عددی بزرگتر از آنها دارد.
دقیقاً همان چیزی که شرط مسئله میخواهد.
نتیجهٔ استقرایی
به این ترتیب، از یک گراف کامل با $k$ رأس و برچسبهای $1$ تا $n$، یک گراف کامل جدید با:
- برچسبهای $1$ تا $n+1$،
- و تعداد رأسهای $2k$
ساختهایم که شرط مسئله را ارضا میکند.
این یعنی:
هر بار که $n$ یک واحد افزایش پیدا میکند،
میتوان حداکثر تعداد رأسها را دو برابر کرد.
این ساخت استقرایی نهتنها امکانپذیر است، بلکه کاملاً با مثالهای کوچک $n=1$ و $n=2$ هم سازگار است.
یعنی میتوان گرافی با $2^n$ راسی ساخت که برچسبهای $1$ تا $n$ داشته باشد و شرط مثلث گفته شده برقرار باشد. (چرا که برای $n=1$ میتوان گراف $2$ راسی ساخت و هر بار که $n$ زیاد میشود اندازهی گراف دوبرابر میشود).
در گام بعدی، میتوانیم ببینیم:
- آیا این حدِ دو برابر شدن بهینه است؟
- و آیا واقعاً بیش از این نمیتوان گراف را بزرگتر کرد؟
گام بعد: کران بالا
چرا گراف کامل با $2^n+1$ رأس دیگر شدنی نیست؟
تا اینجا یک ساخت استقرایی دیدیم که نشان میداد با افزایش $n$ میتوان گراف را بزرگتر کرد (حتی بهصورت تقریباً دو برابر).
اما اگر هدف ما «حداکثر» باشد، فقط ساختن مثال کافی نیست؛ باید نشان دهیم بزرگتر از یک حد مشخص دیگر امکانپذیر نیست.
اینجاست که یک نکتهٔ آموزشی مهم رخ میدهد:
استقرا فقط ابزار اثبات «وجود» نیست؛
برای اثبات «عدم وجود» هم میتواند بسیار قدرتمند باشد.
یعنی میتوانیم با استقرا ثابت کنیم که: «هیچ آرایشی با این اندازه وجود ندارد.»
هدف
میخواهیم ثابت کنیم:
برای گراف کامل با $2^n+1$ رأس،
هیچ برچسبگذاری با اعداد $1,2,\dots,n$ وجود ندارد
که شرط مثلث مسئله را ارضا کند.
چرا از استقرای قوی استفاده میکنیم؟
وقتی میخواهیم «عدم امکان» را ثابت کنیم، معمولاً نیاز داریم از این واقعیت استفاده کنیم که:
اگر یک ساختار خیلی بزرگ وجود داشته باشد،
داخلش یک زیرساختار کوچکتر هم پیدا میشود که همان خاصیت را به ارث میبرد.
پس اگر بدانیم در اندازهٔ کوچکتر چنین چیزی ناممکن است، میتوانیم تناقض بسازیم.
این دقیقاً جایی است که استقرای قوی طبیعی بهنظر میرسد.
فرض استقرا
فرض میکنیم گزارهٔ زیر برای عدد $k < n$ درست است:
هیچ برچسبگذاری با اعداد $1,2,\dots,k$
برای گراف کامل با $2^{k}+1$ رأس وجود ندارد
که شرط مثلث مسئله را ارضا کند.
گام استقرا: تلاش برای رسیدن به تناقض
حالا باید نشان دهیم که نتیجهٔ متناظر برای $n$ هم درست است؛ یعنی نمیتوان یالهای $K_{2^n+1}$ را با برچسبهای $1$ تا $n$ برچسبگذاری کرد بهطوری که شرط مثلث گفته شده برقرار باشد.
برای این کار از یک تکنیک کلاسیک استفاده میکنیم: برهان خلف.
فرض کنید بر خلاف ادعای ما، چنین برچسبگذاریای وجود داشته باشد.
یعنی فرض میکنیم:
- یک گراف کامل با $2^n+1$ رأس داریم،
- یالهای آن با اعداد $1,2,\dots,n$ برچسبگذاری شدهاند،
- و در هر مثلث، دقیقاً دو یال همبرچسباند و یال سوم برچسبی بزرگتر دارد.
از اینجا به بعد هدف ما این است که از دل همین فرض، بهنوعی یک زیرگراف «بهاندازهی کافی بزرگ ($2^{k} + 1$)» استخراج کنیم که فقط از برچسبهای $1$ تا $k$ استفاده کند، و آنگاه با فرض استقرا به تناقض برسیم.
بیرون کشیدن زیرگرافهای ممنوعه از اطراف یک رأس
ایدهٔ کلیدی: به «طبقهبندی همسایهها بر حسب برچسب» نگاه کنیم
طبق برهان خلف، فرض میکنیم یک برچسبگذاری معتبر روی گراف کامل $K_{2^n+1}$ با برچسبهای $1$ تا $n$ وجود دارد.
حالا یک رأس دلخواه را انتخاب میکنیم و آن را $v$ مینامیم.
تمام رأسهای دیگر به $v$ وصلاند، و هر یال یکی از برچسبهای $1$ تا $n$ را دارد.
پس میتوانیم همسایههای $v$ را بر اساس برچسب یالِ وصلکننده دستهبندی کنیم.
برای هر $i=1,2,\dots,n$ تعریف میکنیم:
- $m_i$ = تعداد رأسهایی که با یالی با برچسب $i$ به $v$ وصل شدهاند.
پس داریم: \(m_1 + m_2 + \cdots + m_n = 2^n\) چون در $K_{2^n+1}$ دقیقاً $2^n$ رأسِ دیگر غیر از $v$ وجود دارد.
مشاهدهٔ اول: زیرگرافِ همسایههای برچسب $1$
به مجموعهٔ رأسهایی نگاه کنید که با یالِ برچسب $1$ به $v$ وصل شدهاند.
این مجموعه را $S_1$ مینامیم، بنابراین $|S_1| = m_1$.
حالا دو رأس دلخواه $a,b \in S_1$ را بردارید.
در مثلث $vab$ داریم:
- یال $va$ برچسب $1$ دارد،
- یال $vb$ هم برچسب $1$ دارد.
پس در این مثلث، «دو یال برابر» همین دو یال هستند،
و بنابراین یال سوم یعنی $ab$ باید برچسبی بزرگتر از $1$ داشته باشد.
یعنی:
هیچ یالی بین دو رأسِ $S_1$ نمیتواند برچسب $1$ داشته باشد.
پس در زیرگراف کاملِ القاشده روی $S_1$، برچسبها فقط از مجموعهٔ ${2,3,\dots,n}$ میآیند.
ترفند مهم: کم کردن یک واحد از همهٔ برچسبها
حالا یک حرکت فکری انجام میدهیم که در این نوع مسائل خیلی کلیدی است:
- روی همهٔ یالهای داخل $S_1$، از برچسبها یک واحد کم میکنیم.
آنگاه برچسبهای ${2,3,\dots,n}$ تبدیل میشوند به ${1,2,\dots,n-1}$.
و نکتهٔ حیاتی این است که:
شرط مثلث با این «جابجایی یکنواخت» خراب نمیشود.
چون در هر مثلث، فقط مقایسهٔ «برابر بودن دو یال» و «بزرگتر بودن سومی» مهم است؛
و کم کردن یک عدد ثابت از همهٔ یالهای یک زیرگراف، این روابط را حفظ میکند.
پس نتیجه میگیریم:
- زیرگراف کامل روی $m_1$ رأس را میتوان با برچسبهای $1$ تا $n-1$ طوری برچسبگذاری کرد که شرط مثلث برقرار باشد.
اما این دقیقاً همان چیزی است که فرض استقرا آن را برای اندازهٔ $2^{n-1}+1$ غیرممکن میداند.
پس اگر $m_1 \ge 2^{n-1}+1$ باشد، به تناقض میرسیم. بنابراین:
\[m_1 \le 2^{n-1}.\]همین ایده برای $m_2$ و بقیهٔ دستهها
حالا به دستهٔ دوم نگاه میکنیم:
- مجموعه $S_2$ برابر مجموعهٔ رأسهایی که با یالِ برچسب $2$ به $v$ وصلاند،
- بنابراین $\mid S_2 \mid = m_2$
اگر $a,b \in S_2$ باشند، در مثلث $vab$ داریم:
- $va = 2$ , $vb = 2$، پس یال سوم یعنی $ab$ باید بزرگتر از $2$ باشد.
پس در زیرگراف کامل روی $S_2$، برچسبها فقط از ${3,4,\dots,n}$ میآیند.
حالا از همهٔ این برچسبها دو واحد کم میکنیم و به برچسبهای ${1,2,\dots,n-2}$ میرسیم، و باز هم شرط مثلث حفظ میشود.
بنابراین اگر $m_2$ خیلی بزرگ باشد، یک نمونهٔ ممنوعه برای $n-2$ تولید میشود؛ پس:
\[m_2 \le 2^{n-2}.\]الگوی کلی
بهطور کلی برای هر $i$:
- $S_i$ = همسایههایی که با برچسب $i$ به $v$ وصلاند،
- در هر مثلث $vab$ با $a,b \in S_i$، دو یال برابر $i$ هستند،
- پس یال سوم $ab$ باید برچسبی بزرگتر از $i$ داشته باشد.
پس در زیرگراف کامل روی $S_i$، برچسبها از مجموعهٔ ${i+1,i+2,\dots,n}$ هستند.
حالا اگر از همهٔ این برچسبها $i$ واحد کم کنیم، به برچسبهای ${1,2,\dots,n-i}$ میرسیم، و شرط مثلث همچنان برقرار میماند.
پس اگر $\mid S_i \mid$ از حدی بزرگتر شود، به یک نمونهٔ ممنوعه برای $n-i$ میرسیم. بنابراین:
\[m_i \le 2^{n-i}.\]جمعبندی: شمارش همسایهها
اکنون تعداد کل همسایههای $v$ برابر است با:
\[m_1 + m_2 + \cdots + m_n.\]ولی طبق نامساویهای بالا داریم:
\[m_1 + m_2 + \cdots + m_n \le 2^{n-1} + 2^{n-2} + \cdots + 2^0.\]و میدانیم:
\[2^{n-1} + 2^{n-2} + \cdots + 2^0 = 2^n - 1.\]پس:
\[m_1 + m_2 + \cdots + m_n \le 2^n - 1.\]اما از طرف دیگر، در گراف $K_{2^n+1}$ تعداد همسایههای $v$ دقیقاً $2^n$ است.
یعنی باید داشته باشیم:
که با نامساوی بالا تناقض دارد.
پس فرض خلف ما نادرست بوده است.
نتیجهٔ نهایی کران بالا
بنابراین:
گراف کامل با $2^n+1$ رأس نمیتواند چنین برچسبگذاریای داشته باشد.
و در نتیجه، حداکثر تعداد رأسهای گرافی که میتواند شرط مسئله را ارضا کند برابر است با:
\[2^n.\]