منقبض کردن

منقبض کردن یک دور عملی در گراف است که در آن یک دور را در نظر می گیریم و به جای رئوس آن یک راس می گذاریم و به ازای هر راسی که در بیرون دور به یکی از راس های این دور یال داشته باشد یالی بین این راس و راس جدیدی که گذاشتیم قرار می دهیم.

انتخاب مناسب برای منقبض کردن

دوری که می خواهیم منقبض کنیم بهتر است یالی درون خودش نداشته باشد و بعد از منقبض کردن آن گراف همچنان ساده بماند. برای مثال مثلث در یک گراف بدون بادبادک یا کمر گراف اگر بیش از چهار راس داشته باشد این خواص را دارند و در نتیجه کاندید مناسبی برای منقبض کردن هستند.

یک مثال

یک گراف ساده داریم که دور هایش اشتراک یالی ندارند و \(2n+1\) راس دارد. بیشینه میزان یال های این گراف چیست؟

پاسخ \(3n\) است.

مثال

برای مثالی با این میزان یال، می توانید یک راس را در وسط گراف بگذارید و به ازای هر دو راس، یک مثلث که شامل این راس هست نیز بسازید.

اثبات بیشینه بودن

در این جا با استقرا ثابت می کنیم که در هر گرافی که دور هایش اشتراک یالی ندارند، \(2m \le 3n-1\) برقرار است. کوچک ترین مثال نقض این قضیه را در نظر بگیرید. این گراف نمی تواند بدون دور باشد چون در این صورت تعداد یال هایش از راس هایش کمتر است و یعنی حکم برایش برقرار است. واضح است که دور های این گراف نمی توانند وتر داشته باشند. (یعنی یالی درون آن ها وجود داشته باشد) چون در این صورت دو دور با اشتراک یالی به وجود می آید. و هم چنین یک راس نمی تواند به دو راس از یک دور یال داشته باشد. پس یکی از دور های این گراف را منقبض می کنیم. گراف همچنان ساده می ماند و می توان نشان داد که دور هایش همچنان اشتراک یالی ندارند. (این مطلب را ثابت کنید تا روی انقباض شهود بگیرید. ) و چون کوچک ترین مثال نقض را در نظر گرفته بودیم، در گراف جدید حکم برقرار است. اگر دوری به طول k را منقبض کرده باشیم، k یال و \(k-1\) راس از گراف حذف می شوند. پس داریم:

\[2(m - k) \le 3(n - k + 1) - 1\]

و از قبل می دانستیم که:

\[2m > 3n - 1\]

از این دو گزاره در می یابیم که:

\[2k < 3(k + 1)\]

که یعنی دوری که حذف کردیم کم تر از ۳ راس داشته که در گراف های ساده ممکن نیست. از این مطلب به تناقض می رسیم. با کمی دقت می توان دریافت که برابری تنها زمانی رخ می دهد که k دقیقا برابر 3 باشد و این یعنی تمام دور های گراف مثلث باشند. (همانگونه که مثال ما این شرط را داشت)