زیرگراف القایی

در نظریه گراف، یک زیرگراف القایی گرافی است که مجموعه رئوس آن، زیر مجموعه‌ای از مجموعه رئوس گرافی دیگر باشد با این ویژگی که این زیر گراف دارای تمامی یال‌هایی است که بین رئوس نظیر خود در مجموعه رئوس گراف اولیه موجود هستند.

تعریف

فرض می‌کنیم گراف (G = (V, E گرافی دلخواه باشد و مجموعه S باشرط S ⊂ V هر زیر مجموعه دلخواهی از مجموعه رئوس گراف G یعنی V باشد؛ لذا زیرگراف القایی [G[S گرافی است متشکل از رئوس موجود در زیر مجموعه S و یال‌های آن، تمامی یال‌های موجود در E است به شرطی که رئوس هر دوسر یال مذکور در S موجود باشد. این تعریف از زیر گراف القایی در مورد گراف‌های غیر جهت دار، جهت دار و گراف چندگانه نیز صادق است.

زیر گراف القایی G[S] را «زیرگراف القا شده از S در G» یا (در صورتی که در انتخاب مجموعه G ابهامی وجود نداشته باشد) «زیرگراف القا شده S» نیز می‌نامند.

نمونه‌ها

انواع مهمی از زیرگراف‌های القایی را می‌توانید در زیر مشاهدده کنید؛

• مسیرهای القایی، زیرگراف‌هایی از نوع مسیر‌ها هستند؛ به عبارت دیگر کوتاه‌ترین مسیر بین هر دو رأس دلخواه در یک گراف غیر وزن دار همواره یک مسیر القایی به شمار می‌رود؛ زیرا هر یال اضافه‌ای که موجب شود مسیر یافت شده القایی نباشد، همین‌طور موجب می‌شود که آن مسیر کوتاه‌ترین مسیر ممکن نباشد. بر عکس، در گراف‌های فاصله - ارثی (که کوتاه‌ترین فاصله در زیرگراف‌ها ی القایی متصل برابراست با آنهایی که در کل گراف هستند) همواره هر مسیر القایی، کوتاهترین مسیر خواهد بود.^[۱]
• دورهای القایی، زیر گراف‌های القایی یا مدار (دور) هستند. بعد گراف که طول کوتاه‌ترین دور گراف است که همواره یک دور القایی است مشخص می‌شود. همچنین طبق نظریه گراف آرمانی قوی، دورهای القایی و گراف‌های مکملشان نقش بسزایی را در تعریف و ایجاد گراف‌های ایده‌آل ایفا می‌کنند.^[۲]
• گروهک‌ها و مجموعه‌های ناوابسته، زیر گراف‌های القایی هستند که به ترتیب گراف کامل یا گراف تهی (گراف بی یال) به شمار می‌روند.
• همسایگی یک رأس، زیرگرافی القایی از تمامی رئوس مجاور آن رأس در گراف است.

محاسبات

مسئله یکریختی زیرگراف القایی، نوعی مسئله از یکریختی است که در آن این امر که می‌توان تشخیص داد آیا گرافی یک زیر گراف القایی از گرافی دیگر است، مورد آزمون و بررسی قرار می‌گیرد. چون این مسئله در بر دارنده مسئله گروهک‌ها به عنوان یک مورد خاص می‌باشد، یک ان‌پی کامل محسوب خواهد شد.^[۳]

منابع

1. Howorka, Edward (1977), "A characterization of distance-hereditary graphs", The Quarterly Journal of Mathematics. Oxford. Second Series, 28 (112): 417–420, doi:10.1093/qmath/28.4.417, MR 0485544
2. Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin (2006), "The strong perfect graph theorem", Annals of Mathematics, 164 (1): 51–229, doi:10.4007/annals.2006.164.51, MR 2233847.
3. Johnson, David S. (1985), "The NP-completeness column: an ongoing guide", Journal of Algorithms, 6 (3): 434–451, doi:10.1016/0196-6774(85)90012-4, MR 0800733.