مجموعهٔ رأسهای گراف: بنیاد نظریهٔ گراف
1. تعریف و نمادگذاری مجموعهٔ رأسها
در نظریهٔ گراف1، یک گراف از دو بخش اصلی تشکیل شده است: مجموعهٔ رأسها2 و مجموعهٔ یالها3. مجموعهٔ رأسها که با نماد $V(G)$ نمایش داده میشود، شامل همهٔ نقطهها یا گرههای آن گراف است. هر رأس معمولاً با یک عدد، حرف یا برچسب مشخص میشود.
به عنوان مثال، اگر گرافی با $3$ رأس داشته باشیم که نامهای $a$، $b$ و $c$ را یدک میکشند، آنگاه مجموعهٔ رأسها به صورت زیر نوشته میشود:
تعداد اعضای این مجموعه را مرتبهٔ گراف (Order) مینامند و با $|V(G)|$ یا $n$ نشان میدهند. در مثال بالا، $|V(G)| = 3$.
2. انواع گراف از دیدگاه مجموعهٔ رأسها
مجموعهٔ رأسها میتواند در گرافهای مختلف ویژگیهای متفاوتی داشته باشد. در ادامه به چند نوع مهم اشاره میکنیم:
| نوع گراف | ویژگی مجموعهٔ رأسها | مثال نمادگذاری |
|---|---|---|
| گراف کامل4 | هر رأس به همهٔ رأسهای دیگر متصل است | $K_n$ با $|V|=n$ |
| گراف تهی5 | هیچ یالی بین رأسها وجود ندارد | $\overline{K_n}$ یا $E_n$ |
| گراف دو بخشی6 | مجموعهٔ رأسها به دو زیرمجموعهٔ مجزا افراز میشود | V(G)=X \cup Y و X \cap Y=\varnothing |
در یک گراف جهتدار7 نیز مجموعهٔ رأسها همچنان به همان صورت باقی میماند، اما یالها جهتدار هستند. برای نمونه، در گرافی با $V(G)=\{1,2,3\}$ میتوان یالی از رأس $1$ به $2$ داشت بدون آنکه یال برگشتی وجود داشته باشد.
3. مثال عملی: شبکهٔ دوستان در یک کلاس
فرض کنید در یک کلاس 5 نفره، هر دانشآموز یک رأس از گراف باشد. اگر بخواهیم رابطهٔ "دوستی" را به صورت یال نشان دهیم، مجموعهٔ رأسها را به این ترتیب مینویسیم:
حال اگر احمد با بهاره و پویا دوست باشد، و بهاره با سارا، و پویا با رضا، آنگاه این گراف دارای $|V(G)|=5$ رأس و $4$ یال است. دقت کنید که حتی اگر هیچ یالی بین دو رأس نباشد، آن دو رأس همچنان عضو مجموعهٔ رأسها هستند. مجموعهٔ رأسها مستقل از یالها تعریف میشود.
4. عملیات روی مجموعهٔ رأسها
بر روی مجموعهٔ رأسهای یک گراف میتوان عملیات نظریهٔ مجموعهها مانند اجتماع، اشتراک و تفاضل را انجام داد. این عملیات در ساخت گرافهای جدید کاربرد دارند:
- اجتماع گرافها: اگر دو گراف $G_1$ و $G_2$ داشته باشیم، مجموعهٔ رأسهای گراف حاصل از اجتماع، برابر است با $V(G_1) \cup V(G_2)$.
- اشتراک گرافها: $V(G_1 \cap G_2) = V(G_1) \cap V(G_2)$ و یالها فقط بین رأسهای مشترک حفظ میشوند.
- حذف یک رأس: با حذف رأس $v$ از گراف، مجموعهٔ رأسهای جدید برابر $V(G) \setminus \{v\}$ میشود و همهٔ یالهای متصل به $v$ نیز حذف میگردند.
5. کاربردهای واقعی مجموعهٔ رأسها
مفهوم مجموعهٔ رأسها فقط به ریاضیات محدود نمیشود. در بسیاری از زمینههای علمی و روزمره، از این ایده استفاده میشود:
- شبکههای اجتماعی: هر کاربر یک رأس است و مجموعهٔ همهٔ کاربران، $V(G)$ را میسازد.
- شبکههای کامپیوتری: رأسها همان گرهها ( رایانهها یا مسیریابها) هستند.
- نقشهٔ مترو: ایستگاهها به عنوان رأس و خطوط ارتباطی بین آنها به عنوان یال در نظر گرفته میشوند.
- مسیریابی در بازیهای رایانهای: مکانهای مختلف در یک نقشه به صورت رأس ذخیره میشوند.
برای نمونه، در یک اپلیکیشن نقشه، هر مکان دیدنی با یک رأس مشخص میشود و مجموعهٔ رأسها شامل همهٔ مکانهایی است که کاربر میتواند به آنها سفر کند. مسیرهای بین آنها نیز یالها را تشکیل میدهند.
6. چالشهای مفهومی (پرسش و پاسخ)
پرسش 1: آیا ممکن است دو گراف متفاوت، مجموعهٔ رأسهای یکسانی داشته باشند؟
پاسخ: بله، بسیار هم محتمل است. دو گراف میتوانند رأسهای یکسان ولی یالهای متفاوت داشته باشند. برای مثال، گراف تهی و گراف کامل روی یک مجموعهٔ رأس مشخص، هر دو $V(G)$ یکسان دارند اما کاملاً متفاوت هستند.
پرسش 2: آیا مجموعهٔ رأسها میتواند تهی باشد؟
پاسخ: بله، به چنین گرافی گراف تهی-تهی میگویند که هیچ رأس و هیچ یالی ندارد. در این حالت $V(G)=\varnothing$ و مرتبهٔ گراف برابر صفر است. هرچند این یک حالت مرزی و صرفاً نظری است.
پرسش 3: چگونه میتوانیم بدون دانستن یالها، فقط از روی مجموعهٔ رأسها، تعداد یالهای یک گراف کامل را محاسبه کنیم؟
پاسخ: در یک گراف کامل با $n$ رأس، هر رأس به $n-1$ رأس دیگر متصل است. از آنجا که هر یال دو بار شمارش میشود، تعداد کل یالها برابر است با:
$\displaystyle \frac{n(n-1)}{2}$بنابراین صرفاً با دانستن $|V(G)|=n$ میتوان تعداد یالهای گراف کامل روی آن مجموعه را به دست آورد.
7. راهنمای گامبهگام برای تعیین مجموعهٔ رأسها از روی یک تصویر گراف
فرض کنید یک شکل گراف به شما داده شده است. برای نوشتن $V(G)$ گامهای زیر را دنبال کنید:
- همهٔ نقطهها یا گرههای موجود در شکل را پیدا کنید. به هر نقطه یک برچسب (عدد، حرف یا نام) بدهید اگر از قبل نداشته باشد.
- آنها را در یک مجموعه - معمولاً با کروشه یا آکولاد - بنویسید. ترتیب اعضا مهم نیست.
- تعداد اعضا را بشمارید. این عدد همان مرتبهٔ گراف $n$ است.
- اگر گراف دارای زیرمجموعههایی از رأسهاست (مانند گراف دو بخشی)، آنها را جداگانه مشخص کنید.
مثال: در گرافی با رأسهای مثلثی شکل که رأسهای آن $x$، $y$، $z$ نامگذاری شدهاند، مجموعهٔ رأسها به صورت $V(G)=\{x,y,z\}$ نوشته میشود و $|V(G)|=3$.
پاورقی
1 نظریهٔ گراف (Graph Theory): شاخهای از ریاضیات که به مطالعهٔ گرافها، به عنوان مدلی برای روابط بین اشیاء، میپردازد.
2 رأس (Vertex): یک نقطه یا گره در گراف که میتواند با یال به رأسهای دیگر متصل شود. جمع آن در فارسی «رأسها» و در انگلیسی «Vertices» است.
3 یال (Edge): ارتباط بین دو رأس در گراف که میتواند جهتدار یا بدون جهت باشد.
4 گراف کامل (Complete Graph): گرافی که در آن هر دو رأس متمایز دقیقاً با یک یال به هم متصل شدهاند.
5 گراف تهی (Empty Graph یا Null Graph): گرافی که مجموعهٔ یالهای آن خالی است، اگرچه ممکن است رأس داشته باشد.
6 گراف دو بخشی (Bipartite Graph): گرافی که مجموعهٔ رأسهای آن را میتوان به دو زیرمجموعهٔ مجزا افراز کرد به طوری که هر یال یک رأس از یک بخش و رأس دیگر را از بخش دیگر وصل کند.
7 گراف جهتدار (Directed Graph یا Digraph): گرافی که یالهای آن دارای جهت هستند و با پیکان نشان داده میشوند.
