موضوع مقاله: گراف آزاد-مثلث | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # گراف آزاد-مثلث | مقدمه: در حوزه ریاضیات نظریه گراف، یک گراف آزاد-مثلث گرافی بدون جهت است که هیچ سه راس آن تشکیل مثلث ندهند. | ## بخش 1: گراف آزاد-مثلث | معادل گراف‌های آزاد-مثلث می‌تواند گراف‌هایی که عدد خوشه‌ای آن‌ها حداکثر ۲ است، گراف‌هایی که کوچکترین دور در آن‌ها حداقل ۴ است، گراف‌های بدون دور ۳تایی یا گراف‌های با استقلال محلی باشد. طبق نظریه توران یک گراف n راسی آزاد-مثلث با بیشترین تعداد یال یک گراف کامل دوبخشی است که در آن تعداد راس‌ها در هر بخش تا جای ممکن برابرند. مسئله یافتن مثلث مسئله پیدا کردن مثلث مانند این مسئله است که گراف، آزاد-مثلث هست یا نه. وقتی گراف مثلث داشته باشد الگوریتمها معمولاً نیازمند این هستند که ۳ راس پیدا کنند که با هم تشکیل مثلث می‌دهند. برای گراف‌های متراکم بهتر است از این الگوریتم ساده استفاده شود که مبتنی بر ضرب ماتریسی است. اگرچه بهترین الگوریتم‌های کنونی برای پیدا کردن گراف میانه از پیدا کردن مثلث به عنوان زیرروال استفاده می‌کند تا برعکس آن. پیچیدگی درخت تصمیم یا پیچیدگی پرسش (جستار) این مسئله (Θ(n2 است (پرسش به برنامه‌ای است برای ذخیره‌سازی ماتریس هم جواری گراف). برای الگوریتم‌های کوانتومی بهترین کران پایین شناخته شده (Ω(n است اما بهترین الگوریتم شناخته شده، الگوریتم (Belovs (2011 با پیچیدگی (O(n1.29 است. | ## بخش 2: گراف آزاد-مثلث | عدد استقلال و نظریه رمزی پیدا کردن یک مجموعه مستقل n√ راسی در یک گراف n راسی آزاد-مثلث ساده است. یا یک راس با بیش از n√ همسایه وجود دارد (که در این صورت آن همسایه‌ها یک مجموعه مستقل هستند) یا همه راس‌ها کمتر از n√ همسایه دارند (که در این صورت هر مجموعه مستقل ماکسیمال باید حداقل n√ راس داشته باشند). در هر گراف آزاد-مثلث یک مجموعه مستقل با تعداد راس وجود دارد و در برخی از گراف‌های آزاد-مثلث هر مجموعه مستقل راس دارد. یک راه برای تولید گراف آزاد-مثلث که در آن مجموعه‌های مستقل کوچک هستندT پردازش آزاد-مثلث است. در این روش ماکسیمال گراف آزاد-مثلث با اضافه کردن متناوب یال‌های انتخابی به صورت تصادفی که تولید مثلث نکنند، تولید می‌شود. این نتایج می‌توانند با دادن کران‌های مجانب به اعداد رمزی (R(3,t به فرم نتبیجه شوند. اگر یال‌های یک گراف راسی با رنگ‌های قرمز و آبی رنگ‌آمیزی شوند در این صورت چه گراف قرمز شامل مثلث باشد چه آزاد-مثلث باشد، باید یک مجموعه مستقل با اندازه t مربوط به خوشهٔ با همان اندازه در گراف آبی داشته باشد. رنگ آمیزی گراف آزاد-مثلث حجم زیادی از تحقیقات در مورد گراف آزاد-مثلث روی مبحث رنگ‌آمیزی گراف متمرکز شده‌است. | ## بخش 3: گراف آزاد-مثلث | هر گراف دو قسمتی (یعنی، هر گراف قابل رنگ‌آمیزی با دو رنگ) آزاد-مثلث است، و تئوری Grötzsch بیان می‌کند که هر گراف آزاد-مثلث مسطح ممکن است سه رنگ باشد. میسیلیسکی(۱۹۵۵) دستورالعملی را برای ساختن یک گراف آزاد-مثلث جدید از روی گراف آزاد-مثلث دیگری تعریف کرد که امروزه با نام میسیلیسکیان شناخته می‌شود. بنابراین این دستوالعمل می‌تواند برای نشان دادن اینکه ممکن است رنگ کردن گراف‌های آزاد-مثلث نامسطح تعداد به دلخواه زیادی از رنگ‌ها را نیاز داشته باشد، استفاده شود. به ویژه، گراف Grötzsch (یک گراف ۱۱ راسی که با استفادهٔ مکرر از دستورالعمل میسیلیسکی به وجود می‌آید) یک گراف آزاد-مثلث است که نمی‌توان آن را با کمتر از ۴ رنگ، رنگ آمیزی کرد و کوچک‌ترین گراف موجود با این خاصیت است. گیمبِل و توماسِن (۲۰۰۰) و نیلی (۲۰۰۰) نشان دادند که تعداد رنگ‌های مورد نیاز برای رنگ آمیزی هر گراف آزاد-مثلث با m یال برابر با است و البته گراف‌های آزاد-مثلثی وجود دارند که عدد رنگی آن‌ها متناسب با این کران است. هم چنین تا به حال نتایج زیادی در مورد رنگ کردن گراف‌های آزاد-مثلث با کمترین درجه به دست آمده است. این بهترین نتیجه ممکن است چون دور ۵تایی نیازمند ۳ رنگ است اما هر راس دقیقاً 2n/۵ همسایه دارد. جین نشان داد که هر گراف آزاد-مثلث n رأسی که در آن هر راس بیش از 10n/۲۹ همسایه دارد باید با ۳ رنگ قابل رنگ‌آمیزی باشد باشد. | ## جمع‌بندی | همان‌طور که Hajnal مثال‌هایی را از گراف‌های آزاد-مثلث با عدد رنگی بزرگ دلخواه و با درجه کمینه ε-1/3)n) برای هر ε > ۰ پیدا کرد نتایج دیگری برای این نوع ممکن نیست.