شعاع گراف چیست؟

راهنمایی کوتاه: شعاع گراف، کمترین فاصله‌ی ممکن از یک رأس تا دورترین رأس دیگر در گراف است.

گام‌به‌گام:

• ۱) فرض کن یک گراف داریم (مجموعه‌ای از نقاط به نام رأس و خطوط اتصال به نام یال).
• ۲) برای هر رأس در گراف، فاصله‌ی آن تا دورترین رأس دیگر را محاسبه می‌کنیم. این مقدار را «شعاع خارجی» آن رأس می‌نامیم.
• ۳) از بین تمام رأس‌ها، کوچک‌ترین شعاع خارجی را پیدا می‌کنیم.
• ۴) این مقدار کوچک‌ترین، همان «شعاع گراف» است.
• ۵) به بیان ریاضی: اگر $d(u,v)$ فاصله‌ی بین دو رأس $u$ و $v$ باشد، آنگاه شعاع گراف برابر است با: $r\left(G\right)=\underset{u\in V\left(G\right)}{\min }\underset{v\in V\left(G\right)}{\max }d(u,v)$

پاسخ نهایی: شعاع یک گراف، کمترین مقدار از بیشینه‌ی فاصله‌های هر رأس است. به عبارت دیگر، کوتاه‌ترین فاصله‌ای است که می‌توانیم از یک رأس مرکزی تا دورترین نقطه‌ی گراف داشته باشیم.

مثال مشابه: یک شهر را در نظر بگیر که چند محله دارد و جاده‌هایی آنها را به هم وصل می‌کند. اگر بخواهیم یک ایستگاه آتش‌نشانی طوری بگذاریم که در بدترین حالت (دورترین محله) کمترین فاصله را داشته باشد، آن کمترین فاصله در بدترین حالت، شبیه شعاع گراف شهر است.

اگر می‌خواهی بیشتر یاد بگیری: شعاع با قطر گراف مرتبط است. قطر، بیشترین فاصله‌ی ممکن بین هر دو رأس در گراف است. همیشه شعاع کوچک‌تر یا مساوی نصف قطر است. می‌توانی روی یک گراف ساده (مثلاً یک مسیر یا یک دایره) شعاع و قطر را محاسبه کنی تا رابطه را ببینی.