گراف‌های پنجه‌آزاد کیست؟ توضیح بده.
در نظریه گراف، که بخشی از ریاضیات است، گراف پنجه‌آزاد گرافی است که زیرگراف پنجه نداشته باشد. پنجه نام دیگر گراف دوبخشی کامل formula_1 است (یک گراف ستاره با سه برگ و یک راس مرکزی). یک گراف پنجه‌آزاد گرافی است که هیچ‌یک از زیر گراف‌های آن پنجه نباشد؛ یعنی هر زیرگراف چهار راسی آن یالی بیش از سه یالی که آن‌ها را بدین شکل به هم متصل می‌کنند داشته باشد. به بیانی دیگر گراف پنجه‌آزاد گرافی است که در آن مکمل گراف القایی همسایه‌های هر راس آن گراف، مثلث آزاد باشد.گراف‌های پنجه‌آزاد، در ابتدا به عنوان تعمیم گراف یالی شناخته می‌شدند، اما با کشف این سه خاصیت مهم، اهمیت بیشتری پیدا کردند:تشخیص.بررسی کردن پنجه‌آزاد بودن یا نبودن یک گراف دلخواه با formula_15 رأس و formula_18 یال در زمان formula_19 کار ساده‌ای است، کافی است به ازای هر ۴ رأس بررسی کرد که آیا زیرگراف القایی روی آن ۴ رأس تشکیل یک پنجه می‌دهد یا خیر. رویکردی پیچیده‌تر اما اندکی کارا تر این است که در گراف پنجه‌آزاد، گراف مکمل همسایه‌های هر رأس مثلث‌آزاد نباشد. یک گراف مثلث دارد اگر و تنها اگر عددی ناصفر روی قطر مربع ماتریس مجاورت آن باشد، پس یافتن مثلث در گراف از نظر پیچیدگی زمانی مانند محاسبهٔ ضرب دو ماتریس formula_20 است. از این رو، با استفاده از الگوریتم کوپراسمیت–وینوگارد زمان تشخیص پنجه آزاد بودن یک گراف formula_21 خواهد بود.در سال ۲۰۰۰ میلادی، کلاکس، کراتش و مولر به این نتیجه رسیدند که هر رأس در گراف پنجه‌آزاد حداکثر formula_22 همسایه دارد، در غیر اینصورت طبق همسایه‌های آن رأس به تعداد کافی یال نخواهند داشت تا بتوانند مکمل یک گراف مثلث‌آزاد باشند. با این مشاهده بررسی همسایه‌های یک رأس با استفاده از روش ضرب ماتریسی سریع تر از قبل انجام می‌شود و به زمانی نظیر ضرب دو ماتریس formula_23 نیاز دارد و برای رئوس با درجه کمتر این بررسی حتی سریع تر هم انجام می‌پذیرد.بدترین حالت این الگوریتم زمانی رخ می‌دهد که formula_24 رأس هرکدام formula_24 همسایه داشته باشند و بقیهٔ رئوس تعداد کمتری همسایه داشته باشند. در این حالت زمان اجزای کلformula_26 خواهد بود.شمارش.چون مکمل هر گراف مثلث‌آزاد یک گراف پنجه‌آزاد است، رشد تعداد گراف‌های پنجه‌آزاد حداقل به اندازهٔ رشد تعداد گراف‌های مثلث‌آزاد سریع است، به صورت تابعی نمایی بر حسب formula_15. تعداد گراف‌های پنجه‌آزاد formula_15 رأسی برای formula_29 برابر است با:formula_30اگر گراف‌های ناهمبند را هم بشماریم، تعداد باز هم بیشتر می‌شود:formula_31با بهره بردن از تکنیک Palmer, Read &amp; Robinson می‌توان گراف‌های مکعبی پنجه‌آزاد (گراف مکعبی، همان گراف ۳-منتظم است) را بسیار کارا شمرد که برای مسائل شمارش گراف امری طبیعی نیست.تطابق.لاس ورناگس (۱۹۷۵) و سومنر (۱۹۷۴)‌ به‌طور مستقل اثبات کردند که هر گراف زوج رأسی همبند پنجه‌آزاد یک تطابق کامل دارد. یکی از نتایج مهم این نکته در گراف یالی آن است که در هر گراف با تعداد زوجی یال می‌توان یال‌ها را به مسیرهایی به طول ۲ افراز کرد. از تطابق کامل می‌توان برای توصیف یکی دیگر از خصوصیات گراف‌های پنجه‌آزاد استفاده کرد:گراف‌هایی که هر زیرگراف القایی زوج رأسی همبند آن‌ها دارای تطابق کامل باشد، پنجه آزادند و برعکس.نتیجهٔ قوی تر اثبات Sumner نشان می‌دهد که در هر گراف همبند پنجه آزاد دو رأس مجاور وجود دارند که با حذف آنها گراف همچنان همبند می‌ماند.برای اثبات، Sumner دو رأسformula_32 و formula_33 را به گونه ای یافت که بیشترین فاصلهٔ ممکن نسبت به یکدیگر را داشته باشند و از میان همسایه‌های رأس formula_34 رأس formula_35 را به گونه ای انتخاب کرد که از formula_36 دورترین باشد. آنگونه که او نشان داد، رئوس formula_32 و formula_38 در هیچ کوتاه‌ترین مسیر از هیچ رأسی از گراف نسبت به formula_33 قرار ندارند. پس حذف این دو رأس گراف را همبند نگاه می‌دارد. با تکرار همین عمل و حذف رئوس متطابق، یک تطابق کامل از گراف پنجه‌آزاد داده شده به دست می‌آید.ایدهٔ اثبات بالا برای وقتی که formula_33 یک رأس دلخواه از گراف باشد، و formula_41 یکی از دورترین رئوس نسبت به formula_33 باشد و formula_38 هم یکی از دورترین همسایه‌های formula_41 نسبت به formula_33 باشد همچنان کاراست. در این حالت حذف دو رأس formula_41 و formula_38 فاصلهٔ بقیهٔ رئوس نسبت به formula_48 را تغییر نخواهد داد؛ بنابراین فرایند یافتن تطابق کامل در گراف با یافتن و حذف زوج formula_49 که نسبت به formula_33 دورترین رئوس هستند با پیمایش پس ترتیب درخت جستجوی اول سطحی که از رأس formula_33 ریشه دار شده باشد، در زمان خطی امکان‌پذیر است. چروباک، نائور و نویک الگوریتم دیگری بر اساس جستجوی عمق اول در زمان خطی ارائه کردند. آنها برای همین مسئله الگوریتم کارایی برای پردازش موازی نیز ارائه دادند. چند نتیجه شامل نتایج زیر بدست آوردند:هر گراف formula_52 همبند formula_53-آزاد زوج رأسی برای هر formula_54 تطابق کامل دارد هر گراف پنجه آزاد فرد رأسی با حداکثر یک رأس درجه ۱ قابل افراز به یک دور فرد و یک تطابق است. هر گراف پنچه آزاد به ازای هر formula_55 کمتر از نصف مینیمم درجهٔ گراف، که formula_55 یا تعداد راس‌ها زوج است، گراف یک عاملِ formula_57 دارد.