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

گراف آزاد مثلث. در حوزه ریاضیات نظریه گراف، یک گراف آزاد-مثلث گرافی بدون جهت است که هیچ سه راس آن تشکیل مثلث ندهند. معادل گراف های آزاد-مثلث می تواند گراف هایی که عدد خوشه ای آن ها حداکثر ۲ است، گراف هایی که کوچکترین دور در آن ها حداقل ۴ است، گراف های بدون دور ۳تایی یا گراف های با استقلال محلی باشد.طبق نظریه توران یک گراف n راسی آزاد-مثلث با بیشترین تعداد یال یک گراف کامل دوبخشی است که در آن تعداد راس ها در هر بخش تا جای ممکن برابرند.
مسئله پیدا کردن مثلث مانند این مسئله است که گراف، آزاد-مثلث هست یا نه. وقتی گراف مثلث داشته باشد الگوریتمها معمولاً نیازمند این هستند که ۳ راس پیدا کنند که با هم تشکیل مثلث می دهند.
برای گراف با m راس در (O(m1.41 می توان فهمید که گراف بدون مثلث است یا خیر. راه دیگر، پیدا کردن اثر ماتریس A3 است که A ماتریس (به انگلیسی: trace) همجواری گراف است. اثر ماتریس صفر است اگر و فقط اگر گراف آزاد-مثلث باشد. برای گراف های متراکم بهتر است از این الگوریتم ساده استفاده شود که مبتنی بر ضرب ماتریسی است. چرا که این الگوریتم پیچیدگی را به (O(n2.373 می رساند که در آن n تعداد رئوس است.
همان طور که (Imrich, Klavžar & Mulder (1999 نشان داده اند پیدا کردن گراف آزاد-مثلث از نظر پیچیدگی مانند پیدا کردن گراف میانه است. اگرچه بهترین الگوریتم های کنونی برای پیدا کردن گراف میانه از پیدا کردن مثلث به عنوان زیرروال استفاده می کند تا برعکس آن.