زیرگراف یک گراف: ساختهشده از بخشی از رأسها و یالها
گراف چیست و چگونه زیرگراف از آن ساخته میشود؟
گراف یک ساختار ریاضی شامل رأسها (نقاط یا گرهها) و یالها (خطهای رابط بین رأسها) است. به عنوان مثال، نقشه متروی یک شهر را در نظر بگیرید: ایستگاهها رأسها و خطوط بین ایستگاهها یالها هستند. حال اگر فقط چند ایستگاه مشخص و خطوط بین آنها را انتخاب کنید، یک زیرگراف ساختهاید.
برای ساختن یک زیرگراف کافی است:
- یک مجموعه از رأسهای گراف اصلی را انتخاب کنیم.
- یک مجموعه از یالهای گراف اصلی را انتخاب کنیم به طوری که هر یال انتخابی حتماً به رأسهای انتخابی متصل باشد (در تعریف سادهتر، یالها فقط بین رأسهای انتخابی قرار دارند).
نکته مهم: اگر رأسها را انتخاب کنیم اما برخی یالهای بین آنها را نیاوریم، باز هم یک زیرگراف داریم. اما اگر یک یال را انتخاب کنیم، هر دو سر آن یال باید در مجموعه رأسها حضور داشته باشند.
انواع مهم زیرگراف: القایی، پوشا و تولیدشده توسط یالها
چند نوع خاص از زیرگراف در ریاضیات و علوم کامپیوتر بسیار پرکاربرد هستند. در جدول زیر این انواع را مقایسه میکنیم:
| نوع زیرگراف | تعریف | مثال ساده |
|---|---|---|
| زیرگراف القایی | مجموعه رأسها را انتخاب میکنیم و همه یالهای بین آنها در گراف اصلی را میآوریم. | از گراف کامل $K_4$ با انتخاب $3$ رأس، یک مثلث کامل میسازیم. |
| زیرگراف پوشا | همه رأسهای گراف اصلی را نگه میداریم، اما فقط برخی یالها را انتخاب میکنیم. | درخت پوشای یک گراف که همه رأسها را دارد ولی یالها کمتر از گراف اصلی است. |
| زیرگراف تولیدشده توسط یالها | مجموعه یالها را انتخاب میکنیم و رأسها را همان سرهای این یالها در نظر میگیریم. | اگر دو یال مجزا از یک گراف را انتخاب کنیم، زیرگراف شامل آن دو یال و چهار رأس میشود. |
کاربرد عملی: پیدا کردن مسیرهای جایگزین در شبکه حملونقل
فرض کنید میخواهید از یک نقطه به نقطه دیگر در یک شبکه جادهای بروید. گاهی برخی جادهها مسدود هستند. در این شرایط، شما زیرگرافی از گراف اصلی جادهها را در نظر میگیرید که فقط شامل جادههای باز (یالهای موجود) است. سپس در این زیرگراف به دنبال کوتاهترین مسیر میگردید. همچنین اگر فقط به ایستگاههای خاصی (مثل بیمارستانها و مراکز درمانی) علاقه داشته باشید، با نگاه کردن به زیرگراف القایی آن ایستگاهها، میتوانید روابط مستقیم بین آنها را ببینید. این ایده پایه بسیاری از نرمافزارهای مسیریاب است.
مثال دیگر: در شبکههای اجتماعی، اگر فقط دوستان نزدیک خود را در نظر بگیرید (رأسها) و ارتباطات بین آنها را نگاه کنید، در واقع یک زیرگراف القایی از شبکه بزرگ دوستانتان ساختهاید.
چالشهای مفهومی در درک زیرگراف
پاسخ: بله. اگر همه رأسها را نگه دارید اما فقط زیرمجموعهای از یالها را انتخاب کنید، آن زیرگراف «زیرگراف پوشا» نام دارد. مثلاً از یک مربع کامل (۴ رأس و ۴ یال) میتوانید زیرگرافی با همان ۴ رأس و فقط ۲ یال غیرمجاور بسازید.
پاسخ: در زیرگراف معمولی، پس از انتخاب رأسها میتوانید هر زیرمجموعهای از یالهای بین آنها را بردارید. اما در زیرگراف القایی باید همه یالهای بین رأسهای انتخابی (که در گراف اصلی وجود دارند) را بیاورید. بنابراین زیرگراف القایی یک حالت خاص و محدودتر است.
پاسخ: بله. به چنین زیرگرافی «زیرگراف تهی» یا «مجموعهٔ رأسهای تنها» میگویند. رأسها وجود دارند اما هیچ یالی بین آنها رسم نشده است. از نظر تعریف، این یک زیرگراف مجاز است.
نمادگذاری ریاضی و فرمول مرتبط با زیرگراف
اگر گراف اصلی را با $G = (V, E)$ نشان دهیم که $V$ مجموعه رأسها و $E$ مجموعه یالهاست، آنگاه یک زیرگراف $H = (V', E')$ دارای شرایط زیر است:
-
$V' \subseteq V$ و $E' \subseteq E$ و همچنین هر یال $e \in E'$ باید دو سر خود را در $V'$ داشته باشد.
برای زیرگراف القایی توسط مجموعه رأسهای $S$ (که $S \subseteq V$) داریم:
این فرمول نشان میدهد که زیرگراف القایی همه یالهای بین اعضای $S$ را حفظ میکند.
پاورقی
1 رأس (Vertex): یک نقطه یا گره در گراف که میتواند به سایر رأسها متصل شود.
2 یال (Edge): یک خط یا ارتباط بین دو رأس در گراف.
3 گراف (Graph): ساختاری متشکل از مجموعهای از رأسها و مجموعهای از یالها که هر یال دو رأس را به هم متصل میکند.
4 زیرگراف القایی (Induced Subgraph): زیرگرافی که با انتخاب مجموعه رأسها و گرفتن همه یالهای بین آنها در گراف اصلی ساخته میشود.
5 زیرگراف پوشا (Spanning Subgraph): زیرگرافی که همه رأسهای گراف اصلی را دارد اما نه لزوماً همه یالها را.