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

در نظریه گراف، که بخشی از ریاضیات است، گراف پنجه‌آزاد گرافی است که زیرگراف پنجه نداشته باشد. پنجه نام دیگر گراف دوبخشی کامل ${\displaystyle K_{1,3}}$ است (یک گراف ستاره با سه برگ و یک راس مرکزی). یک گراف پنجه‌آزاد گرافی است که هیچ‌یک از زیر گراف‌های آن پنجه نباشد؛ یعنی هر زیرگراف چهار راسی آن یالی بیش از سه یالی که آن‌ها را بدین شکل به هم متصل می‌کنند داشته باشد. به بیانی دیگر گراف پنجه‌آزاد گرافی است که در آن مکمل گراف القایی همسایه‌های هر راس آن گراف، مثلث آزاد باشد.^[1]

نمایی دیگر از پنجه

گراف پنجه

گراف‌های پنجه‌آزاد، در ابتدا به عنوان تعمیم گراف یالی شناخته می‌شدند، اما با کشف این سه خاصیت مهم، اهمیت بیشتری پیدا کردند:

1. اثبات این که هر گراف پنجه‌آزاد زوج راسی تطابق کامل دارد.
2. کشف راه حل چند جمله‌ای برای پیدا کردن مجموعه مستقل بیشینه در گراف‌های پنجه آزاد.
3. توصیف خصوصیات گراف ایده‌آل^[1] پنجه آزاد.

مثال‌ها

• گراف یالی ${\displaystyle L(G)}$ هر گراف ${\displaystyle G}$ پنجه‌آزاد است؛ ${\displaystyle L(G)}$ به ازای هر یال ${\displaystyle G}$ یک راس دارد، و دو راس در ${\displaystyle L(G)}$ با یکدیگر مجاورند هرگاه یال‌های متناظر آن‌ها در ${\displaystyle G}$، در یک سر خود مشترک باشند. گراف یالی ${\displaystyle L(G)}$ نمی‌تواند پنجه داشته باشد، زیرا اگر سه یال ${\displaystyle e_{1},e_{2}}$ و ${\displaystyle e_{3}}$ هر سه در ${\displaystyle G}$ با یال دیگری مثل ${\displaystyle e_{4}}$ سر مشترک داشته باشند، طبق اصل لانه‌کبوتر حداقل دوتا از یال‌ها در یک سر مشترک ${\displaystyle e_{4}}$ با آن اشتراک دارند و بنابراین با هم مشترک هستند و در ${\displaystyle L(G)}$ بین آنها یال وجود دارد.
• گراف دی براین (گرافی که به هر راس آن یک کد ${\displaystyle n}$ بیتی باینری نسبت داده شده‌است و بین دو راسی که ${\displaystyle n-1}$ هم پوشانی دارند یال وجود دارد) پنجه‌آزاد است.
• مُکمّل هر گراف مثلث-آزاد پنجه‌آزاد است.^[2]
• گراف اِشلفلی که ۲۷ راس دارد یک گراف پنجه آزاد است.^[3]

تشخیص

بررسی کردن پنجه‌آزاد بودن یا نبودن یک گراف دلخواه با ${\displaystyle n}$ رأس و ${\displaystyle m}$ یال در زمان ${\displaystyle O(n^{4})}$ کار ساده‌ای است، کافی است به ازای هر ۴ رأس بررسی کرد که آیا زیرگراف القایی روی آن ۴ رأس تشکیل یک پنجه می‌دهد یا خیر.^[4] رویکردی پیچیده‌تر اما اندکی کارا تر این است که در گراف پنجه‌آزاد، گراف مکمل همسایه‌های هر رأس مثلث‌آزاد نباشد. یک گراف مثلث دارد اگر و تنها اگر عددی ناصفر روی قطر مربع ماتریس مجاورت آن باشد، پس یافتن مثلث در گراف از نظر پیچیدگی زمانی مانند محاسبهٔ ضرب دو ماتریس ${\displaystyle n\times n}$ است. از این رو، با استفاده از الگوریتم کوپراسمیت–وینوگارد زمان تشخیص پنجه آزاد بودن یک گراف ${\displaystyle O(n^{3.376})}$ خواهد بود.^[5]

در سال ۲۰۰۰ میلادی، کلاکس، کراتش و مولر به این نتیجه رسیدند که هر رأس در گراف پنجه‌آزاد حداکثر ${\displaystyle 2{\sqrt {m}}}$ همسایه دارد، در غیر اینصورت طبق قضیهٔ توران همسایه‌های آن رأس به تعداد کافی یال نخواهند داشت تا بتوانند مکمل یک گراف مثلث‌آزاد باشند.^[6] با این مشاهده بررسی همسایه‌های یک رأس با استفاده از روش ضرب ماتریسی سریع تر از قبل انجام می‌شود و به زمانی نظیر ضرب دو ماتریس ${\displaystyle 2{\sqrt {m}}\times 2{\sqrt {m}}}$ نیاز دارد و برای رئوس با درجه کمتر این بررسی حتی سریع تر هم انجام می‌پذیرد. بدترین حالت این الگوریتم زمانی رخ می‌دهد که ${\displaystyle \Omega (n)}$ رأس هرکدام ${\displaystyle \Omega (n)}$ همسایه داشته باشند و بقیهٔ رئوس تعداد کمتری همسایه داشته باشند. در این حالت زمان اجزای کل ${\displaystyle m^{3.376/2}=m^{1.688}}$ خواهد بود.

شمارش

چون مکمل هر گراف مثلث‌آزاد یک گراف پنجه‌آزاد است، رشد تعداد گراف‌های پنجه‌آزاد حداقل به اندازهٔ رشد تعداد گراف‌های مثلث‌آزاد سریع است، به صورت تابعی نمایی بر حسب ${\displaystyle n}$. تعداد گراف‌های پنجه‌آزاد ${\displaystyle n}$ رأسی برای ${\displaystyle n=1,2,3,...}$ برابر است با:

${\displaystyle 1,1,2,5,14,50,191,881,4494,26389,184749,...}$
((دنباله A022562 در OEIS)).

اگر گراف‌های ناهمبند را هم بشماریم، تعداد باز هم بیشتر می‌شود:

${\displaystyle 1,2,4,10,26,85,302,1285,6170,...}$
((دنباله A086991 در OEIS)).

با بهره بردن از تکنیک Palmer, Read & Robinson می‌توان گراف‌های مکعبی پنجه‌آزاد (گراف مکعبی، همان گراف ۳-منتظم است) را بسیار کارا شمرد که برای مسائل شمارش گراف امری طبیعی نیست.^[7]

تطابق

لاس ورناگس (۱۹۷۵) و سومنر (۱۹۷۴)‌ به‌طور مستقل اثبات کردند که هر گراف زوج رأسی همبند پنجه‌آزاد یک تطابق کامل دارد. یکی از نتایج مهم این نکته در گراف یالی آن است که در هر گراف با تعداد زوجی یال می‌توان یال‌ها را به مسیرهایی به طول ۲ افراز کرد. از تطابق کامل می‌توان برای توصیف یکی دیگر از خصوصیات گراف‌های پنجه‌آزاد استفاده کرد:

گراف‌هایی که هر زیرگراف القایی زوج رأسی همبند آن‌ها دارای تطابق کامل باشد، پنجه آزادند و برعکس.

نتیجهٔ قوی تر اثبات Sumner نشان می‌دهد که در هر گراف همبند پنجه آزاد دو رأس مجاور وجود دارند که با حذف آنها گراف همچنان همبند می‌ماند.

برای اثبات، Sumner دو رأس${\displaystyle v}$ و ${\displaystyle u}$ را به گونه ای یافت که بیشترین فاصلهٔ ممکن نسبت به یکدیگر را داشته باشند و از میان همسایه‌های رأس ${\displaystyle v}$ رأس ${\displaystyle w}$ را به گونه ای انتخاب کرد که از ${\displaystyle u}$ دورترین باشد. آنگونه که او نشان داد، رئوس ${\displaystyle v}$ و ${\displaystyle w}$ در هیچ کوتاه‌ترین مسیر از هیچ رأسی از گراف نسبت به ${\displaystyle u}$ قرار ندارند. پس حذف این دو رأس گراف را همبند نگاه می‌دارد. با تکرار همین عمل و حذف رئوس متطابق، یک تطابق کامل از گراف پنجه‌آزاد داده شده به دست می‌آید.

ایدهٔ اثبات بالا برای وقتی که ${\displaystyle u}$ یک رأس دلخواه از گراف باشد، و ${\displaystyle v}$ یکی از دورترین رئوس نسبت به ${\displaystyle u}$ باشد و ${\displaystyle w}$ هم یکی از دورترین همسایه‌های ${\displaystyle v}$ نسبت به ${\displaystyle u}$ باشد همچنان کاراست. در این حالت حذف دو رأس ${\displaystyle v}$ و ${\displaystyle w}$ فاصلهٔ بقیهٔ رئوس نسبت به ${\displaystyle u}$ را تغییر نخواهد داد؛ بنابراین فرایند یافتن تطابق کامل در گراف با یافتن و حذف زوج ${\displaystyle vw}$ که نسبت به ${\displaystyle u}$ دورترین رئوس هستند با پیمایش پس ترتیب درخت جستجوی اول سطحی که از رأس ${\displaystyle u}$ ریشه دار شده باشد، در زمان خطی امکان‌پذیر است. چروباک، نائور و نویک الگوریتم دیگری بر اساس جستجوی عمق اول در زمان خطی ارائه کردند.^[8] آنها برای همین مسئله الگوریتم کارایی برای پردازش موازی نیز ارائه دادند.^[9] چند نتیجه شامل نتایج زیر بدست آوردند: هر گراف ${\displaystyle r-1}$ همبند ${\displaystyle K_{r,1}}$-آزاد زوج رأسی برای هر ${\displaystyle r>1}$ تطابق کامل دارد هر گراف پنجه آزاد فرد رأسی با حداکثر یک رأس درجه ۱ قابل افراز به یک دور فرد و یک تطابق است. هر گراف پنچه آزاد به ازای هر ${\displaystyle k}$ کمتر از نصف مینیمم درجهٔ گراف، که ${\displaystyle k}$ یا تعداد راس‌ها زوج است، گراف یک عاملِ ${\displaystyle k}$ دارد.

پانویس

1. (Faudree، Flandrin و Ryjáček 1997), p. 88.
2. (Faudree، Flandrin و Ryjáček 1997), p. 89.
3. (Chudnovsky و Seymour 2005).
4. (Faudree، Flandrin و Ryjáček 1997), p. 132.
5. (Itai و Rodeh 1978).
6. Kloks, Ton; Kratsch, Dieter; Müller, Haiko (2000). "Finding and counting small induced subgraphs efficiently". Inf. Process. Lett. 74 (3–4): 115–121. doi:10.1016/S0020-0190(00)00047-8.
7. Palmer، Edgar M.؛ Read، Ronald C.؛ Robinson، Robert W. (۲۰۰۲). Counting claw-free cubic graphs.
8. Chrobak, Marek; Naor, Joseph; Novick, Mark B. (1989). Dehne, F.; Sack, J. -R.; Santoro, N. (eds.). "Using bounded degree spanning trees in the design of efficient algorithms on claw-free graphs". Algorithms and Data Structures. Lecture Notes in Computer Science (به انگلیسی). Springer Berlin Heidelberg: 147–162. doi:10.1007/3-540-51542-9_13. ISBN 9783540482376.
9. (Faudree، Flandrin و Ryjáček 1997), pp. 120–124.