موضوع مقاله: گراف‌های پنجه‌آزاد | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # گراف‌های پنجه‌آزاد | مقدمه: یک گراف پنجه‌آزاد گرافی است که هیچ‌یک از زیر گراف‌های آن پنجه نباشد؛ یعنی هر زیرگراف چهار راسی آن یالی بیش از سه یالی که آن‌ها را بدین شکل به هم متصل می‌کنند داشته باشد. | ## بخش 1: گراف‌های پنجه‌آزاد | به بیانی دیگر گراف پنجه‌آزاد گرافی است که در آن مکمل گراف القایی همسایه‌های هر راس آن گراف، مثلث آزاد باشد. کشف راه حل چند جمله‌ای برای پیدا کردن مجموعه مستقل بیشینه در گراف‌های پنجه آزاد. مثال‌ها گراف یالی هر گراف پنجه‌آزاد است؛ به ازای هر یال یک راس دارد، و دو راس در با یکدیگر مجاورند هرگاه یال‌های متناظر آن‌ها در ، در یک سر خود مشترک باشند. گراف یالی نمی‌تواند پنجه داشته باشد، زیرا اگر سه یال و هر سه در با یال دیگری مثل سر مشترک داشته باشند، طبق اصل لانه‌کبوتر حداقل دوتا از یال‌ها در یک سر مشترک با آن اشتراک دارند و بنابراین با هم مشترک هستند و در بین آنها یال وجود دارد. گراف دی براین (گرافی که به هر راس آن یک کد بیتی باینری نسبت داده شده‌است و بین دو راسی که هم پوشانی دارند یال وجود دارد) پنجه‌آزاد است. تشخیص بررسی کردن پنجه‌آزاد بودن یا نبودن یک گراف دلخواه با رأس و یال در زمان کار ساده‌ای است، کافی است به ازای هر ۴ رأس بررسی کرد که آیا زیرگراف القایی روی آن ۴ رأس تشکیل یک پنجه می‌دهد یا خیر., p. رویکردی پیچیده‌تر اما اندکی کارا تر این است که در گراف پنجه‌آزاد، گراف مکمل همسایه‌های هر رأس مثلث‌آزاد نباشد. یک گراف مثلث دارد اگر و تنها اگر عددی ناصفر روی قطر مربع ماتریس مجاورت آن باشد، پس یافتن مثلث در گراف از نظر پیچیدگی زمانی مانند محاسبهٔ ضرب دو ماتریس است. | ## بخش 2: گراف‌های پنجه‌آزاد | از این رو، با استفاده از الگوریتم کوپراسمیت–وینوگارد زمان تشخیص پنجه آزاد بودن یک گراف خواهد بود.. در سال ۲۰۰۰ میلادی، کلاکس، کراتش و مولر به این نتیجه رسیدند که هر رأس در گراف پنجه‌آزاد حداکثر همسایه دارد، در غیر اینصورت طبق قضیهٔ توران همسایه‌های آن رأس به تعداد کافی یال نخواهند داشت تا بتوانند مکمل یک گراف مثلث‌آزاد باشند. با این مشاهده بررسی همسایه‌های یک رأس با استفاده از روش ضرب ماتریسی سریع تر از قبل انجام می‌شود و به زمانی نظیر ضرب دو ماتریس نیاز دارد و برای رئوس با درجه کمتر این بررسی حتی سریع تر هم انجام می‌پذیرد. بدترین حالت این الگوریتم زمانی رخ می‌دهد که رأس هرکدام همسایه داشته باشند و بقیهٔ رئوس تعداد کمتری همسایه داشته باشند. شمارش چون مکمل هر گراف مثلث‌آزاد یک گراف پنجه‌آزاد است، رشد تعداد گراف‌های پنجه‌آزاد حداقل به اندازهٔ رشد تعداد گراف‌های مثلث‌آزاد سریع است، به صورت تابعی نمایی بر حسب . تطابق لاس ورناگس (۱۹۷۵) و سومنر (۱۹۷۴)‌ به‌طور مستقل اثبات کردند که هر گراف زوج رأسی همبند پنجه‌آزاد یک تطابق کامل دارد. یکی از نتایج مهم این نکته در گراف یالی آن است که در هر گراف با تعداد زوجی یال می‌توان یال‌ها را به مسیرهایی به طول ۲ افراز کرد. از تطابق کامل می‌توان برای توصیف یکی دیگر از خصوصیات گراف‌های پنجه‌آزاد استفاده کرد:گراف‌هایی که هر زیرگراف القایی زوج رأسی همبند آن‌ها دارای تطابق کامل باشد، پنجه آزادند و برعکس.نتیجهٔ قوی تر اثبات Sumner نشان می‌دهد که در هر گراف همبند پنجه آزاد دو رأس مجاور وجود دارند که با حذف آنها گراف همچنان همبند می‌ماند. | ## بخش 3: گراف‌های پنجه‌آزاد | برای اثبات، Sumner دو رأس و را به گونه ای یافت که بیشترین فاصلهٔ ممکن نسبت به یکدیگر را داشته باشند و از میان همسایه‌های رأس رأس را به گونه ای انتخاب کرد که از دورترین باشد. آنگونه که او نشان داد، رئوس و در هیچ کوتاه‌ترین مسیر از هیچ رأسی از گراف نسبت به قرار ندارند. با تکرار همین عمل و حذف رئوس متطابق، یک تطابق کامل از گراف پنجه‌آزاد داده شده به دست می‌آید. ایدهٔ اثبات بالا برای وقتی که یک رأس دلخواه از گراف باشد، و یکی از دورترین رئوس نسبت به باشد و هم یکی از دورترین همسایه‌های نسبت به باشد همچنان کاراست. در این حالت حذف دو رأس و فاصلهٔ بقیهٔ رئوس نسبت به را تغییر نخواهد داد؛ بنابراین فرایند یافتن تطابق کامل در گراف با یافتن و حذف زوج که نسبت به دورترین رئوس هستند با پیمایش پس ترتیب درخت جستجوی اول سطحی که از رأس ریشه دار شده باشد، در زمان خطی امکان‌پذیر است. چروباک، نائور و نویک الگوریتم دیگری بر اساس جستجوی عمق اول در زمان خطی ارائه کردند. چند نتیجه شامل نتایج زیر بدست آوردند: هر گراف همبند -آزاد زوج رأسی برای هر تطابق کامل دارد هر گراف پنجه آزاد فرد رأسی با حداکثر یک رأس درجه ۱ قابل افراز به یک دور فرد و یک تطابق است. | ## جمع‌بندی | هر گراف پنچه آزاد به ازای هر کمتر از نصف مینیمم درجهٔ گراف، که یا تعداد راس‌ها زوج است، گراف یک عاملِ دارد.