فهرست      مجموعه مستقل و خوشه  سوالات   سورس

مجموعه مستقل و خوشه

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

\[\alpha(G) = \omega(\overline{G})\]

در این فصل با خواص بیشتری از این دو آشنا می شویم.

قضیه توران

این قضیه کرانی روی یال های گراف، بر حسب عدد خوشه ای آن است. اگر \(e\) را تعداد یال های گراف و \(n\) را تعداد راس های آن در نظر بگیرید، این قضیه بیان می کند که:

\[e \le \frac{n^2(\omega - 1)}{2 \omega}\]

و حالت برابری تنها در گراف \(\omega\) بخشی کامل روی می دهد.

اثبات

تعریف می کنیم \(x \sim y\) یعنی راس \(x\) و \(y\) به هم یال ندارند. در گرافی که بیشترین تعداد یال ممکن را دارد اگر \(x \sim y\) و \(y \sim z\) آن گاه \(x \sim z\) را اثبات می کنیم. برهان خلف می زنیم. فرض کنید این طور نباشد، آن گاه یکی از دو حالت زیر وجود دارد:

  • درجه راس \(y\) از دو راس دیگر بزرگتر مساوی باشد. در این صورت آن دو را حذف کنید و دو کپی از راس \(y\) اضافه کنید. واضح است که این گراف خوشه بزرگتری نخواهد داشت و با کمی محاسبه می توانید دریابید که تعداد یال هایش اکیدا بیشتر است.
  • درجه یکی از رئوس \(x\) یا \(z\) از راس \(y\) بزرگتر باشد. در این صورت راس \(y\) را حذف کنید و یک کپی از آن راس با درجه بیشتر اضافه کنید. این گراف خوشه بزرگتری نخواهد داشت اما یال هایش اکیدا بیشتر است.

از گزاره بالا نتیجه می شود که گرافی با خوشه حداکثر \(\omega\) که بیشترین تعداد یال را داشته باشد، باید یک گراف چند بخشی کامل باشد. و در میان این گراف ها، گرافی بیشترین یال را دارد که دقیقا \(\omega\) بخشی باشد و رئوس در این بخش ها به صورت مساوی تقسیم شده باشند (یعنی اختلاف اندازه بخش ها بیشتر از ۱ واحد نباشد) که این مطلب را می توانید با انتقال رئوس از بخش بزرگ به کوچک و زیاد شدن تعداد یال ها ثابت کنید.

صورت های دیگر

به حالتی که خوشه را کمتر مساوی ۲ در نظر بگیریم، قضیه منتل می گویند که معادل این می شود که در هر گرافی که مثلث نداشته باشد داریم

\[e \le \frac{n^2}{4}\]

هم چنین این قضیه را می توان برای عدد استقلال نیز بیان کرد. به این صورت که طبق توران داریم:

\[e(G) \le \frac{n^2(\omega(G) - 1)}{2 \omega(G)}\]
\[\binom{n}{2} - e(G) \ge \binom{n}{2} - \frac{n^2(\omega(G) - 1)}{2 \omega(G)}\]
\[e(\overline{G}) \ge \binom{n}{2} - \frac{n^2(\alpha(\overline{G}) - 1)}{2 \alpha(\overline{G})}\]

و چون هر گرافی یک مکمل دارد، به ازای همه گراف ها داریم:

\[e \ge \binom{n}{2} - \frac{n^2(\alpha - 1)}{2 \alpha}\]

ارتباط با اعداد رمزی

طبق تعریف اعداد رمزی که در بخش های قبل با آن آشنا شدیم، اگر \(R(s,t)=n\) باشد آن گاه هر گراف \(n\) راسی یا یک مجموعه مستقل با اندازه \(s\) و یا یک خوشه با اندازه \(t\) دارد. از قسمت قبل به خاطر داریم که \(R(a,b) \le \binom{a+b}{b}\) و بنابراین

\[R(n,n) \le \binom{2n}{n} \le 4^n\]
\[max(\alpha, \omega) \ge log_4(n)\]

که در نوع خود کران جالبی است، مخصوصا وقتی که بدانیم به ازای هر \(n\) گرافی وجود دارد که \(max(\alpha, \omega) = \theta(lg(n))\) باشد.

  قبلی بعدی  

این کتاب توسط مشارکت کنندگان شاززز به وجود آمده است.

این کتاب عمومی است و تحت پروانه cc-by-sa در دسترس است.

آخرین به روز رسانی در ژوئن 09, 2022.

ساخته شده به وسیله Sphinx (1.8.5) و تم مینو (Beta 0.9.7).