مرتبهٔ گراف: تعداد رأس‌های گراف

بروزرسانی شده در:1405/02/17

تعداد بازدید192

مرتبهٔ گراف: درک تعداد رأس‌ها در نظریهٔ گراف

مفهوم بنیادین مرتبه به عنوان تعداد رأس‌های یک گراف و کاربردهای آن در مسائل دنیای واقعی

در این مقاله با مفهوم «مرتبهٔ گراف» آشنا می‌شوید که همان تعداد رأس‌ها یا گره‌های یک گراف است. یاد می‌گیرید چگونه مرتبه بر ویژگی‌های گراف تأثیر می‌گذارد، تفاوت آن با اندازهٔ گراف (تعداد یال‌ها) را درک می‌کنید و با مثال‌های ملموس مانند نقشهٔ مترو و شبکهٔ اجتماعی، کاربرد آن را مشاهده می‌نمایید.

مرتبه در برابر اندازه: دو مفهوم پایه‌ای

در نظریهٔ گراف¹، هر گراف از دو مجموعهٔ اصلی تشکیل شده است: رأس‌ها² (که گره یا نقطه نیز نامیده می‌شوند) و یال‌ها³ (که خطوط رابط بین رأس‌ها هستند). مرتبهٔ گراف (Order of Graph) به تعداد رأس‌های آن گراف گفته می‌شود، در حالی که اندازهٔ گراف (Size of Graph) تعداد یال‌ها را نشان می‌دهد. این دو مفهوم پایه‌ای و مکمل یکدیگرند.

فرمول کلیدی اگر گراف $G را در نظر بگیریم، معمولاً مرتبه را با $|V(G)|$ یا $n$ و اندازه را با $|E(G)|$ یا $m$ نشان می‌دهند. بنابراین اگر گرافی دارای $n$ رأس باشد، مرتبهٔ آن برابر $n$ است.

برای درک بهتر، یک شبکهٔ اجتماعی فرضی با 5 کاربر (رأس) و 7 ارتباط دوستی (یال) را تصور کنید. در اینجا مرتبه برابر 5 و اندازه برابر 7 است. توجه داشته باشید که مرتبه می‌تواند بدون تغییر اندازه تغییر کند و برعکس. برای نمونه، افزودن یک کاربر جدید (رأس جدید) مرتبه را افزایش می‌دهد، اما اگر این کاربر هیچ ارتباطی نداشته باشد، اندازه ثابت می‌ماند.

نوع گراف	مرتبه (تعداد رأس‌ها)	اندازه (تعداد یال‌ها)	مثال
گراف تهی	3	0	سه جزیره بدون پل
گراف کامل $K_4$	4	6	چهار شهر که هر جاده مستقیم بین هر دو شهر وجود دارد
گراف مسیر $P_5$	5	4	پنج ایستگاه در یک خط مستقیم راه‌آهن

ارتباط مرتبه با درجهٔ رأس‌ها و قضیهٔ دست دادن

یکی از مهم‌ترین قضایای نظریهٔ گراف، قضیهٔ دست دادن (Handshaking Lemma) است که رابطهٔ مستقیمی بین مرتبه و مجموع درجهٔ رأس‌ها برقرار می‌کند. درجهٔ یک رأس، تعداد یال‌های متصل به آن است. قضیهٔ دست دادن بیان می‌کند که مجموع درجات همهٔ رأس‌های یک گراف، برابر دو برابر تعداد یال‌هاست.

قضیهٔ دست دادن اگر گراف $G$ دارای مرتبه $n$ و اندازه $m$ باشد، آنگاه: $\sum_{v \in V(G)} deg(v) = 2m$ که در آن $deg(v)$ درجهٔ رأس $v$ است.

نتیجهٔ مهم این قضیه این است که مجموع درجات همیشه یک عدد زوج است. بنابراین در هر گراف با مرتبهٔ دلخواه، تعداد رأس‌هایی که درجهٔ فرد دارند، حتماً زوج خواهد بود. برای مثال، در یک مهمانی با 10 نفر (مرتبه برابر 10)، تعداد افرادی که با تعداد فرد از دیگران دست داده‌اند، همیشه زوج است. این یک ویژگی جالب است که به کمک مرتبه کشف می‌شود.

نقشهٔ مترو: مثالی ملموس از مرتبه در عمل

فرض کنید نقشهٔ متروی یک شهر را به صورت یک گراف در نظر می‌گیریم. هر ایستگاه مترو یک رأس (گره) و هر مسیر بین دو ایستگاه مجاور یک یال است. در این مثال، مرتبهٔ گراف برابر تعداد کل ایستگاه‌های مترو در آن شهر است. اگر شهر 50 ایستگاه داشته باشد، مرتبه برابر 50 خواهد بود. اندازهٔ گراف نیز برابر تعداد قطعات مسیر بین ایستگاه‌های مجاور است (مثلاً 60 قطعه).

اکنون فرض کنید شهرداری قصد دارد 5 ایستگاه جدید به شبکه اضافه کند. با این کار مرتبه از 50 به 55 افزایش می‌یابد. این افزایش بر محاسبات مربوط به هزینهٔ نگهداری، زمان سفر و تحلیل ازدحام تأثیر مستقیم دارد. همچنین با قضیهٔ دست دادن می‌توان جمع درجات جدید را پیش‌بینی کرد.

حداکثر تعداد یال‌ها بر اساس مرتبه

یکی از سوالات اساسی این است: با دانستن مرتبه (تعداد رأس‌ها)، حداکثر تعداد یال‌هایی که یک گراف می‌تواند داشته باشد چقدر است؟ پاسخ به نوع گراف بستگی دارد. در یک گراف ساده⁴ (بدون حلقه و یال موازی)، حداکثر تعداد یال‌ها زمانی حاصل می‌شود که گراف کامل باشد. گراف کامل با مرتبه $n$ را با نماد $K_n$ نشان می‌دهیم.

$\text{حداکثر تعداد یال‌ها در گراف ساده با مرتبه } n = \binom{n}{2} = \frac{n(n-1)}{2}$

برای نمونه، اگر مرتبه 4 باشد (یعنی $n=4$)، حداکثر یال‌ها برابر $\frac{4 \times 3}{2} = 6$ است که همان گراف کامل $K_4$ را می‌سازد. اگر مرتبه 10 باشد، حداکثر 45 یال امکان‌پذیر است.

چالش‌های مفهومی پیرامون مرتبهٔ گراف

پرسش ۱: آیا ممکن است دو گراف با مرتبهٔ یکسان اما اندازه‌های متفاوت داشته باشیم؟
بله، کاملاً ممکن است. مرتبه فقط تعداد رأس‌ها را نشان می‌دهد و ربطی به تعداد یال‌ها ندارد. برای مثال، دو گراف با 4 رأس در نظر بگیرید: یکی می‌تواند یک گراف تهی با 0 یال باشد و دیگری یک گراف کامل $K_4$ با 6 یال. هر دو مرتبهٔ 4 دارند اما اندازه‌شان متفاوت است.

پرسش ۲: اگر مرتبهٔ یک گراف $n$ باشد، کمترین درجهٔ یک رأس چه عددی می‌تواند باشد؟
کمترین درجهٔ یک رأس می‌تواند صفر باشد. چنین رأسی را «رأس تنها» یا «رأس منزوی» می‌نامیم. اگر مرتبه بزرگتر از یک باشد، داشتن رأس تنها امکان‌پذیر است. برای نمونه، گرافی با 5 رأس که یکی از رأس‌ها به هیچ یالی متصل نباشد، مرتبهٔ 5 دارد و درجهٔ آن رأس صفر است.

پرسش ۳: آیا گرافی با مرتبهٔ 1 (یک رأس) می‌تواند دارای یال باشد؟
در یک گراف ساده، با یک رأس نمی‌توان یال داشت زیرا یال نیازمند دو رأس متمایز است. اما اگر حلقه (Loop) مجاز باشد (در برخی انواع گراف مانند شبه‌گراف‌ها)، می‌توان یک حلقه از آن رأس به خودش داشت. در نظریهٔ پایهٔ گراف‌های ساده، گراف با مرتبه 1 فقط می‌تواند بدون یال باشد.

جمع‌بندی

مرتبهٔ گراف یکی از ساده‌ترین اما مهم‌ترین مفاهیم در نظریهٔ گراف است که به سادگی تعداد رأس‌ها را مشخص می‌کند. در این مقاله یاد گرفتیم که مرتبه با اندازهٔ گراف (تعداد یال‌ها) تفاوت دارد و ارتباط آن با درجهٔ رأس‌ها از طریق قضیهٔ دست دادن بیان می‌شود. همچنین دیدیم که با دانستن مرتبه، می‌توان حداکثر تعداد یال‌ها را در یک گراف ساده محاسبه کرد. مثال نقشهٔ مترو نشان داد که چگونه این مفهوم در دنیای واقعی کاربرد دارد. درک مرتبه برای مطالعهٔ ویژگی‌های پیشرفته‌تر گراف‌ها مانند همبندی، دور، و مسائل بهینه‌سازی ضروری است.

پاورقی

¹ نظریهٔ گراف (Graph Theory): شاخه‌ای از ریاضیات که به مطالعهٔ گراف‌ها به عنوان ساختارهایی شامل رأس و یال می‌پردازد.
² رأس (Vertex): یک نقطه یا گره در گراف که نشان‌دهندهٔ یک شیء یا موجودیت است.
³ یال (Edge): ارتباط یا پیوند بین دو رأس در گراف که می‌تواند جهت‌دار یا بدون جهت باشد.
⁴ گراف ساده (Simple Graph): گرافی بدون حلقه و بدون یال موازی (بیش از یک یال بین دو رأس).

پایهٔ دوازدهم

ریاضیات گسسته دوازدهم

مرتبهٔ گراف