گراف آزاد-مثلث

در حوزه ریاضیات نظریه گراف، یک گراف آزاد-مثلث گرافی بدون جهت است که هیچ سه راس آن تشکیل مثلث ندهند. معادل گراف‌های آزاد-مثلث می‌تواند گراف‌هایی که عدد خوشه‌ای آن‌ها حداکثر ۲ است، گراف‌هایی که کوچکترین دور در آن‌ها حداقل ۴ است، گراف‌های بدون دور ۳تایی یا گراف‌های با استقلال محلی باشد.
طبق نظریه توران یک گراف n راسی آزاد-مثلث با بیشترین تعداد یال یک گراف کامل دوبخشی است که در آن تعداد راس‌ها در هر بخش تا جای ممکن برابرند.

مسئله یافتن مثلث

مسئله پیدا کردن مثلث مانند این مسئله است که گراف، آزاد-مثلث هست یا نه. وقتی گراف مثلث داشته باشد الگوریتمها معمولاً نیازمند این هستند که ۳ راس پیدا کنند که با هم تشکیل مثلث می‌دهند.

برای گراف با m راس در (O(m^1.41 می‌توان فهمید که گراف بدون مثلث است یا خیر. راه دیگر، پیدا کردن اثر ماتریس A³ است که A ماتریس (به انگلیسی: trace) همجواری گراف است. اثر ماتریس صفر است اگر و فقط اگر گراف آزاد-مثلث باشد. برای گراف‌های متراکم بهتر است از این الگوریتم ساده استفاده شود که مبتنی بر ضرب ماتریسی است. چرا که این الگوریتم پیچیدگی را به (O(n^2.373 می‌رساند که در آن n تعداد رئوس است.

همان طور که (Imrich, Klavžar & Mulder (1999 نشان داده‌اند پیدا کردن گراف آزاد-مثلث از نظر پیچیدگی مانند پیدا کردن گراف میانه است. اگرچه بهترین الگوریتم‌های کنونی برای پیدا کردن گراف میانه از پیدا کردن مثلث به عنوان زیرروال استفاده می‌کند تا برعکس آن.

پیچیدگی درخت تصمیم یا پیچیدگی پرسش (جستار) این مسئله (Θ(n² است (پرسش به برنامه‌ای است برای ذخیره‌سازی ماتریس هم جواری گراف). برای الگوریتم‌های کوانتومی بهترین کران پایین شناخته شده (Ω(n است اما بهترین الگوریتم شناخته شده، الگوریتم (Belovs (2011 با پیچیدگی (O(n^1.29 است.

عدد استقلال و نظریه رمزی

پیدا کردن یک مجموعه مستقل n√ راسی در یک گراف n راسی آزاد-مثلث ساده است. یا یک راس با بیش از n√ همسایه وجود دارد (که در این صورت آن همسایه‌ها یک مجموعه مستقل هستند) یا همه راس‌ها کمتر از n√ همسایه دارند (که در این صورت هر مجموعه مستقل ماکسیمال باید حداقل n√ راس داشته باشند). این مرز به آرامی می‌تواند محدود و کوچک شود. در هر گراف آزاد-مثلث یک مجموعه مستقل با تعداد راس $\Omega ({\sqrt {n\log n}})$ وجود دارد و در برخی از گراف‌های آزاد-مثلث هر مجموعه مستقل $O({\sqrt {n\log n}})$ راس دارد. یک راه برای تولید گراف آزاد-مثلث که در آن مجموعه‌های مستقل کوچک هستندT پردازش آزاد-مثلث است. در این روش ماکسیمال گراف آزاد-مثلث با اضافه کردن متناوب یال‌های انتخابی به صورت تصادفی که تولید مثلث نکنند، تولید می‌شود. با احتمال زیاد این پردازش، گرافی با درجه استقلال $O({\sqrt {n\log n}})$ تولید می‌کند. همچنین می‌توان گراف‌های ساده با همین ویژگی‌ها تولید کرد.

این نتایج می‌توانند با دادن کران‌های مجانب به اعداد رمزی (R(3,t به فرم $\Theta ({\tfrac {t^{2}}{\log t}})$ نتبیجه شوند. اگر یال‌های یک گراف $\Omega ({\tfrac {t^{2}}{\log t}})$ راسی با رنگ‌های قرمز و آبی رنگ‌آمیزی شوند در این صورت چه گراف قرمز شامل مثلث باشد چه آزاد-مثلث باشد، باید یک مجموعه مستقل با اندازه t مربوط به خوشهٔ با همان اندازه در گراف آبی داشته باشد.

رنگ آمیزی گراف آزاد-مثلث

حجم زیادی از تحقیقات در مورد گراف آزاد-مثلث روی مبحث رنگ‌آمیزی گراف متمرکز شده‌است. هر گراف دو قسمتی (یعنی، هر گراف قابل رنگ‌آمیزی با دو رنگ) آزاد-مثلث است، و تئوری Grötzsch بیان می‌کند که هر گراف آزاد-مثلث مسطح ممکن است سه رنگ باشد. هر چند، گراف‌های آزاد-مثلث نامسطح ممکن است تعداد بیش از سه رنگ اختیار کنند.

میسیلیسکی(۱۹۵۵) دستورالعملی را برای ساختن یک گراف آزاد-مثلث جدید از روی گراف آزاد-مثلث دیگری تعریف کرد که امروزه با نام میسیلیسکیان شناخته می‌شود. اگر گرافی عدد رنگی k داشته باشد، میسیلیسکیان آن عدد رنگی k+1 دارد. بنابراین این دستوالعمل می‌تواند برای نشان دادن اینکه ممکن است رنگ کردن گراف‌های آزاد-مثلث نامسطح تعداد به دلخواه زیادی از رنگ‌ها را نیاز داشته باشد، استفاده شود. به ویژه، گراف Grötzsch (یک گراف ۱۱ راسی که با استفادهٔ مکرر از دستورالعمل میسیلیسکی به وجود می‌آید) یک گراف آزاد-مثلث است که نمی‌توان آن را با کمتر از ۴ رنگ، رنگ آمیزی کرد و کوچک‌ترین گراف موجود با این خاصیت است. گیمبِل و توماسِن (۲۰۰۰) و نیلی (۲۰۰۰) نشان دادند که تعداد رنگ‌های مورد نیاز برای رنگ آمیزی هر گراف آزاد-مثلث با m یال برابر با $O\left({\frac {m^{1/3}}{(\log m)^{2/3}}}\right)$ است و البته گراف‌های آزاد-مثلثی وجود دارند که عدد رنگی آن‌ها متناسب با این کران است.
هم چنین تا به حال نتایج زیادی در مورد رنگ کردن گراف‌های آزاد-مثلث با کمترین درجه به دست آمده است. (Andrásfai, Erdős & Sós (1974ثابت کردند هر گراف آزاد-مثلث با n راس که در آن هر راس بیش از 2n/۵ همسایه داشته باشد، حتماً دوبخشی است. این بهترین نتیجه ممکن است چون دور ۵تایی نیازمند ۳ رنگ است اما هر راس دقیقاً 2n/۵ همسایه دارد. (Erdős & Simonovits (1973 با الهام گرفتن از این نتیجه تخمین زدند که هر گراف آزاد-مثلث n راسی که در آن هر راس حداقل n/3 همسایه دارد با ۳ رنگ قابل رنگ آمیزی است. هرچند (Häggkvist (1981 با پیدا کردن مثال نقضی که در آن هر راس گراف Grötzsch با یک مجموعه مستقل با اندازه با دقت تعیین شده، جایگزین شده‌بود، این حدس را رد کرد. جین نشان داد که هر گراف آزاد-مثلث n رأسی که در آن هر راس بیش از 10n/۲۹ همسایه دارد باید با ۳ رنگ قابل رنگ‌آمیزی باشد باشد. این بهترین نتیجه ممکن برای این نوع است. چون گراف Häggkvist به ۴ رنگ نیاز دارد و دقیقاً 10n/۲۹ همسایه به ازای هر راس دارد. در نهایت (Brandt & Thomassé (۲۰۰۶ ثابت کردند که هر گراف آزاد-مثلث n راسی که در آن هر راس بیش از n/3 همسایه دارد بایدبا ۴ رنگ قابل رنگ‌آمیزی باشد. همان‌طور که Hajnal مثال‌هایی را از گراف‌های آزاد-مثلث با عدد رنگی بزرگ دلخواه و با درجه کمینه ε-1/3)n) برای هر ε > ۰ پیدا کرد نتایج دیگری برای این نوع ممکن نیست.

جستارهای وابسته

مسئله Monochromatic triangle، مسئله تقسیم‌بندی یک گراف داده‌شده به ۲ گراف آزاد-مثلث.

منابع

• مشارکت‌کنندگان ویکی‌پدیا. «Triangle-free graph». در دانشنامهٔ ویکی‌پدیای انگلیسی.