اندازهٔ گراف: مفهوم تعداد یالها و کاربرد آن در مدلسازی شبکهها
۱. تعریف اندازه در گراف و تمایز آن از ترتیب
در نظریهٔ گراف1، دو کمیت بنیادی وجود دارد: ترتیب (Order) و اندازه (Size). ترتیب برابر است با تعداد رئوس2 یا گرههای گراف، در حالی که اندازه تعداد یالها3 یا پیوندهای میان رئوس را نشان میدهد. به زبان ساده، اگر گراف را مانند نقشهای از شهرها (رئوس) و جادهها (یالها) در نظر بگیرید، اندازه به شما میگوید «چند جاده در این نقشه وجود دارد».
برای نمونه، گرافی با 4 رأس و 5 یال داشته باشید: ترتیب آن 4 و اندازه آن 5 است. تفاوت این دو مفهوم اغلب در محاسبهٔ چگالی یا میانگین درجه اهمیت پیدا میکند. در ادامه با مثال های گوناگون این تفاوت را بهتر درک خواهید کرد.
۲. روشهای محاسبهٔ اندازه در گرافهای ساده و غیرساده
برای محاسبهٔ اندازه، سادهترین حالت گراف ساده4 است که در آن بین هر دو رأس حداکثر یک یال وجود دارد و هیچ حلقهای (یالی که یک رأس را به خودش وصل کند) نداریم. در چنین گرافی، اندازه مستقیماً از روی شمارش یالها به دست میآید. اما در گرافهای غیرساده، با دو حالت اضافی روبرو هستیم:
- گراف چند یالی5: بین یک زوج رأس، چند یال مجاز است. در اینجا اندازه برابر با مجموع همهٔ یالها (با تکرار) است.
- حلقه6: یالی که از یک رأس به خودش میرود. هر حلقه معمولاً به عنوان 2 واحد در شمارش درجه تأثیر میگذارد، اما در اندازه، یک حلقه به عنوان 1 یال محسوب میشود.
فرمول کلی برای اندازه در هر نوع گرافی:
برای گراف ساده با n رأس، حداکثر اندازه ممکن برابر است با:
این فرمول از این واقعیت میآید که هر جفت از n رأس حداکثر یک یال میتواند داشته باشد و تعداد جفتها برابر $ \binom{n}{2} = n(n-1)/2 $ است. چنین گرافی «گراف کامل»7 نامیده میشود و با نماد $ K_n $ نشان داده میشود.
۳. جدول مقایسهٔ اندازه در انواع گرافها
| نوع گراف | تعداد رئوس (ترتیب) | تعداد یالها (اندازه) | مثال |
|---|---|---|---|
| گراف تهی8 | 5 | 0 | پنج جزیرهٔ بدون پل |
| گراف مسیر9$ P_4 $ | 4 | 3 | چهار ایستگاه در یک خط راهآهن |
| گراف چرخ10$ W_5 $ | 5 | 8 | چهار دوچرخه دور یک مرکز |
| گراف کامل $ K_3 $ | 3 | 3 | سه دوست که همگی با هم دوست هستند |
۴. کاربرد عملی: محاسبهٔ اندازه در شبکهٔ اجتماعی مدرسه
فرض کنید در یک مدرسه، 20 دانشآموز در یک گروه آنلاین عضو هستند. میخواهیم بدانیم اگر هر دانشآموز با 5 نفر دیگر به طور مستقیم دوست باشد (گراف دوستی ساده بدون یال تکراری)، اندازهٔ این گراف چقدر است؟ طبق قضیهٔ دست دادن11، مجموع درجات همهٔ رئوس برابر با دو برابر تعداد یالهاست:
در این مثال، هر یک از 20 دانشآموز درجهٔ 5 دارد، پس مجموع درجات برابر $ 20 \times 5 = 100 $ است. بنابراین:
یعنی اندازهٔ گراف برابر 50 یال است. این روش زمانی مفید است که به جای شمارش مستقیم یالها، درجهٔ رئوس را بدانیم. حال اگر مدرسه بخواهد بداند آیا این شبکه پراکنده است یا متراکم، از شاخص چگالی استفاده میکند:
برای این مثال: $ 2 \times 50 / (20 \times 19) = 100 / 380 \approx 0.263 $ یعنی چگالی حدود 26.3 درصد، که نشان میدهد شبکه نسبتاً پراکنده است.
۵. چالشهای مفهومی در شمارش یالها
پرسش ۱: اگر یک گراف دارای 7 رأس و چندین یال باشد و مجموع درجات رئوس برابر 24 باشد، اندازهٔ گراف چقدر است؟ آیا این گراف میتواند ساده باشد؟
پاسخ: از رابطهٔ $ 2|E| = 24 $ داریم $ |E| = 12 $. برای ساده بودن، حداکثر اندازه ممکن با 7 رأس برابر $ 7 \times 6 / 2 = 21 $ است. از آنجا که 12 \le 21، گراف میتواند ساده باشد. بله چنین گرافی وجود دارد.
پرسش ۲: آیا گرافی با 4 رأس و 6 یال وجود دارد؟ اگر آری، چه نوع گرافی است؟
پاسخ: بله. حداکثر اندازه برای 4 رأس برابر $ 4 \times 3 / 2 = 6 $ است. به چنین گرافی $ K_4 $ (گراف کامل با 4 رأس) گفته میشود. در این گراف هر جفت از رئوس به هم وصل شدهاند.
پرسش ۳: اگر یک گراف دارای حلقه باشد، آیا همچنان رابطهٔ $ \sum \deg(v) = 2|E| $ برقرار است؟
پاسخ: نه دقیقاً به همان شکل. در حضور حلقه، هر حلقه به درجهٔ آن رأس 2 واحد اضافه میکند ولی در اندازه تنها 1 یال محسوب میشود. بنابراین اگر $ \ell $ حلقه داشته باشیم، رابطه به صورت $ \sum \deg(v) = 2|E| + 2\ell $ اصلاح میشود. برای گرافهای بدون حلقه، همان رابطهٔ اولیه همچنان معتبر است.
جمعبندی
اندازهٔ گراف یا تعداد یالها یکی از سادهترین اما بنیادیترین مفاهیم در نظریهٔ گراف است. این کمیت در کنار ترتیب (تعداد رئوس) پایهٔ بسیاری از محاسبات پیچیدهتر مانند چگالی، قطر، و میانگین درجه را تشکیل میدهد. در این مقاله یاد گرفتیم که اندازه در گرافهای ساده، چند یالی و همراه با حلقه چگونه محاسبه میشود. همچنین با استفاده از قضیهٔ دست دادن توانستیم اندازه را از روی مجموع درجات رئوس پیدا کنیم. درک درست این مفهوم به شما کمک میکند تا شبکههای اجتماعی، مسیرهای حملونقل، و ساختارهای داده را به شکل مؤثرتری تحلیل کنید.
پاورقی
1 نظریهٔ گراف (Graph Theory): شاخهای از ریاضیات که به مطالعهٔ گرافها (ساختارهای متشکل از رأس و یال) میپردازد.
2 رأس (Vertex): نقطه یا گره در یک گراف که نشاندهندهٔ یک شیء یا موجودیت است (جمع آن: رئوس).
3 یال (Edge): پیوند میان دو رأس در گراف که نشاندهندهٔ رابطه یا اتصال بین آن دو است.
4 گراف ساده (Simple Graph): گرافی بدون حلقه و بدون یالهای موازی (چند یالی).
5 گراف چند یالی (Multigraph): گرافی که در آن بین یک زوج رأس، چندین یال مجاز است.
6 حلقه (Loop): یالی که یک رأس را به خودش متصل میکند.
7 گراف کامل (Complete Graph): گراف سادهای که در آن هر دو رأس متمایز توسط یک یال به هم متصل شدهاند. با نماد $ K_n $ نشان داده میشود.
8 گراف تهی (Null Graph): گرافی که از مجموعهای از رئوس بدون هیچ یالی تشکیل شده است.
9 گراف مسیر (Path Graph): گرافی که رئوس آن در یک زنجیرهٔ خطی به هم متصل شدهاند. با نماد $ P_n $ نشان داده میشود.
10 گراف چرخ (Wheel Graph): گرافی که از یک چرخه (cycle) به همراه یک رأس مرکزی که به همهٔ رئوس چرخه متصل است، ساخته میشود. با نماد $ W_n $ نشان داده میشود (n تعداد کل رئوس است).
11 قضیهٔ دست دادن (Handshaking Lemma): قضیهای که میگوید مجموع درجات همهٔ رئوس یک گراف برابر با دو برابر تعداد یالهاست.