گرافهای پنجهآزاد
نظریه ای در ریاضیات / From Wikipedia, the free encyclopedia
در نظریه گراف، که بخشی از ریاضیات است، گراف پنجهآزاد گرافی است که زیرگراف پنجه نداشته باشد. پنجه نام دیگر گراف دوبخشی کامل است (یک گراف ستاره با سه برگ و یک راس مرکزی). یک گراف پنجهآزاد گرافی است که هیچیک از زیر گرافهای آن پنجه نباشد؛ یعنی هر زیرگراف چهار راسی آن یالی بیش از سه یالی که آنها را بدین شکل به هم متصل میکنند داشته باشد. به بیانی دیگر گراف پنجهآزاد گرافی است که در آن مکمل گراف القایی همسایههای هر راس آن گراف، مثلث آزاد باشد.[1]
گرافهای پنجهآزاد، در ابتدا به عنوان تعمیم گراف یالی شناخته میشدند، اما با کشف این سه خاصیت مهم، اهمیت بیشتری پیدا کردند:
- اثبات این که هر گراف پنجهآزاد زوج راسی تطابق کامل دارد.
- کشف راه حل چند جملهای برای پیدا کردن مجموعه مستقل بیشینه در گرافهای پنجه آزاد.
- توصیف خصوصیات گراف ایدهآل[1] پنجه آزاد.