گراف‌های پنجه‌آزاد

گراف پنجه
در نظریه گراف، که بخشی از ریاضیات است، گراف پنجه‌آزاد گرافی است که زیرگراف پنجه نداشته باشد.
پنجه نام دیگر گراف دوبخشی کامل است (یک گراف ستاره با سه برگ و یک راس مرکزی). یک گراف پنجه‌آزاد گرافی است که هیچ‌یک از زیر گراف‌های آن پنجه نباشد؛ یعنی هر زیرگراف چهار راسی آن یالی بیش از سه یالی که آن‌ها را بدین شکل به هم متصل می‌کنند داشته باشد. به بیانی دیگر گراف پنجه‌آزاد گرافی است که در آن مکمل گراف القایی همسایه‌های هر راس آن گراف، مثلث آزاد باشد.
نمایی دیگر از پنجه
گراف‌های پنجه‌آزاد، در ابتدا به عنوان تعمیم گراف یالی شناخته می‌شدند، اما با کشف این سه خاصیت مهم، اهمیت بیشتری پیدا کردند:
اثبات این که هر گراف پنجه‌آزاد زوج راسی تطابق کامل دارد.
کشف راه حل چند جمله‌ای برای پیدا کردن مجموعه مستقل بیشینه در گراف‌های پنجه آزاد.
توصیف خصوصیات گراف ایده‌آل پنجه آزاد.
مثال‌ها
گراف یالی هر گراف پنجه‌آزاد است؛ به ازای هر یال یک راس دارد، و دو راس در با یکدیگر مجاورند هرگاه یال‌های متناظر آن‌ها در ، در یک سر خود مشترک باشند. گراف یالی نمی‌تواند پنجه داشته باشد، زیرا اگر سه یال و هر سه در با یال دیگری مثل سر مشترک داشته باشند، طبق اصل لانه‌کبوتر حداقل دوتا از یال‌ها در یک سر مشترک با آن اشتراک دارند و بنابراین با هم مشترک هستند و در بین آنها یال وجود دارد.
گراف دی براین (گرافی که به هر راس آن یک کد بیتی باینری نسبت داده شده‌است و بین دو راسی که هم پوشانی دارند یال وجود دارد) پنجه‌آزاد است.
مکمل هر گراف مثلث-آزاد پنجه‌آزاد است.
تشخیص
بررسی کردن پنجه‌آزاد بودن یا نبودن یک گراف دلخواه با راس و یال در زمان کار ساده‌ای است، کافی است به ازای هر ۴ راس بررسی کرد که آیا زیرگراف القایی روی آن ۴ راس تشکیل یک پنجه می‌دهد یا خیر. رویکردی پیچیده‌تر اما اندکی کارا‌تر این است که در گراف پنجه‌آزاد، گراف مکمل همسایه‌های هر راس مثلث‌آزاد نباشد. یک گراف مثلث دارد اگر و تنها اگر عددی ناصفر روی قطر مربع ماتریس مجاورت آن باشد، پس یافتن مثلث در گراف از نظر پیچیدگی زمانی مانند محاسبه ضرب دو ماتریس است. از این رو، با استفاده از الگوریتم کوپراسمیت–وینوگارد زمان تشخیص پنجه آزاد بودن یک گراف خواهد بود.
مشاهده کردند که هر راس در گراف پنجه‌آزاد حداکثر همسایه دارد، در غیر اینصورت طبق قضیه توران همسایه‌های آن راس به تعداد کافی یال نخواهند داشت تا بتوانند مکمل یک گراف مثلث‌آزاد باشند. با این مشاهده بررسی همسایه‌های یک راس با استفاده از روش ضرب ماتریسی سریع‌تر از قبل انجام می‌شود و به زمانی نظیر ضرب دو ماتریس نیاز دارد و برای رئوس با درجه کمتر این بررسی حتی سریع‌تر هم انجام می‌پذیرد.
بدترین حالت این الگوریتم زمانی رخ می‌دهد که راس هرکدام همسایه داشته باشند و بقیه رئوس تعداد کمتری همسایه داشته باشند. در این حالت زمان اجزای کل
خواهد بود.
شمارش
چون مکمل هر گراف مثلث‌آزاد یک گراف پنجه‌آزاد است، رشد تعداد گراف‌های پنجه‌آزاد حداقل به اندازه رشد تعداد گراف‌های مثلث‌آزاد سریع است، به صورت تابعی نمایی بر حسب . تعداد گراف‌های پنجه‌آزاد راسی برای برابر است با:
1, 1, 2, 5, 14, 50, 191, 881, 4494, 26389, 184749, …
اگر گراف‌های ناهمبند را هم بشماریم، تعداد باز هم بیشتر می‌شود:
1, 2, 4, 10, 26, 85, 302, 1285, 6170, …
با بهره بردن از تکنیک می‌توان گراف‌های مکعبی پنجه‌آزاد (گراف مکعبی، همان گراف ۳-منتظم است) را بسیار کارا شمرد که برای مسائل شمارش گراف امری طبیعی نیست.
تطابق
و به‌طور مستقل اثبات کردند که هر گراف زوج راسی همبند پنجه‌آزاد یک تطابق کامل دارد. یکی از نتایج مهم این نکته در گراف یالی آن است که در هر گراف با تعداد زوجی یال می‌توان یال‌ها را به مسیرهایی به طول ۲ افراز کرد.
از تطابق کامل می‌توان برای توصیف یکی دیگر از خصوصیات گراف‌های پنجه‌آزاد استفاده کرد:
گراف‌هایی که هر زیرگراف القایی زوج راسی همبند آن‌ها دارای تطابق کامل باشد، پنجه آزادند و برعکس.
نتیجه قوی‌تر اثبات Sumner نشان می‌دهد که در هر گراف همبند پنجه آزاد دو راس مجاور وجود دارند که با حذف آنها گراف همچنان همبند می‌ماند.
برای اثبات، Sumner دو راس و را به گونه‌ای یافت که بیشترین فاصله ممکن نسبت به یکدیگر را داشته باشند و از میان همسایه‌های راس راس را به گونه‌ای انتخاب کرد که از دورترین باشد. آنگونه که او نشان داد، رئوس و در هیچ کوتاه‌ترین مسیر از هیچ راسی از گراف نسبت به قرار ندارند. پس حذف این دو راس گراف را همبند نگاه می‌دارد. با تکرار همین عمل و خذف رئوس متطابق، یک تطابق کامل از گراف پنجه‌آزاد داده شده به دست می‌آید.
ایده اثبات بالا برای وقتی که یک راس دلخواه از گراف باشد، و یکی از دورترین رئوس نسبت به باشد و هم یکی از دورترین همسایه‌های نسبت به باشد همچنان کاراست. در این حالت حذف دو راس و فاصله بقیه رئوس نسبت به را تغییر نخواهد داد؛ بنابراین فرایند یافتن تطابق کامل در گراف با یافتن و حذف زوج که نسبت به دورترین رئوس هستند با پیمایش پس ترتیب درخت جستجوی اول سطحی که از راس ریشه دار شده باشد، در زمان خطی امکان‌پذیر است. الگوریتم دیگری بر اساس جستجوی عمق اول در زمان خطی ارائه کردند. آنها برای همین مسئله الگوریتم کارایی برای پردازش موازی نیز ارائه دادند. چند نتیحه شامل نتایج زیر بدست آوردند:
هر گراف همبند -آزاد زوج راسی برای هر تطابق کامل دارد هر گراف پنجه آزاد فرد راسی با حداکثر یک راس درجه ۱ قابل افراز به یک دور فرد و یک تطابق است. هر گراف پنچه آزاد به ازای هر کمتر از نصف مینیمم درجه گراف، که یا تعداد راس‌ها زوج است، گراف یک عامل دارد.