رأس هم‌درجه در گراف: دو رأس با درجهٔ برابر در یک گراف

بروزرسانی شده در: 22:22 1405/02/17 مشاهده: 40 دسته بندی: کپسول آموزشی

رأس هم‌درجه در گراف: دو رأس با درجهٔ برابر در یک گراف

بررسی مفهوم درجهٔ رأس، تشخیص رأس‌های هم‌درجه و کاربرد آن در تحلیل ساختار گراف‌ها

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

درجهٔ رأس چیست و چگونه محاسبه می‌شود؟

در نظریهٔ گراف¹، یک گراف از مجموعه‌ای از «رأس‌ها»² (نقاط) و «یال‌ها»³ (خطوط اتصال) تشکیل شده است. درجهٔ یک رأس، تعداد یال‌هایی است که به آن رأس متصل هستند. به عبارت دیگر، اگر تعداد همسایه‌های یک رأس را بشماریم، درجهٔ آن رأس به دست می‌آید.

برای محاسبهٔ درجهٔ یک رأس در گراف ساده (بدون حلقه و یال موازی)، کافی است به دور آن رأس نگاه کنیم و یال‌هایی که از آن خارج می‌شوند را بشماریم. اگر گراف دارای «حلقه»⁴ (یالی که از یک رأس به خودش می‌رود) باشد، هر حلقه به درجهٔ آن رأس 2 واحد اضافه می‌کند، زیرا حلقه هم به عنوان یال خروجی و هم یال ورودی محسوب می‌شود.

فرمول درجه برای گراف بدون حلقه: $ \deg(v) = |\{ u \in V(G) : uv \in E(G) \}| $ که در آن $V(G)$ مجموعهٔ رأس‌ها و $E(G)$ مجموعهٔ یال‌ها است.

مثال عملی: تصور کنید در یک کلاس 6 نفره، اگر هر دانش‌آموز را یک رأس در نظر بگیریم و دست دادن بین دو دانش‌آموز را یک یال، آنگاه درجهٔ هر رأس برابر است با تعداد افرادی که با آن دانش‌آموز دست داده‌اند. اگر علی با 3 نفر دست داده باشد، درجهٔ رأس علی برابر 3 است.

رأس هم‌درجه: تعریف و روش تشخیص

دو رأس در یک گراف «هم‌درجه» نامیده می‌شوند اگر درجهٔ یکسانی داشته باشند. به عبارت دیگر، اگر $\deg(u) = \deg(v)$ آنگاه رأس $u$ و $v$ هم‌درجه هستند.

برای تشخیص رأس‌های هم‌درجه در یک گراف، مراحل زیر را انجام می‌دهیم:

گام اول: درجهٔ تمام رأس‌های گراف را محاسبه کنید.
گام دوم: مقادیر درجه را یادداشت کنید.
گام سوم: هر دو رأسی که درجهٔ مساوی دارند، یک جفت رأس هم‌درجه محسوب می‌شوند.

مثال عددی: فرض کنید گرافی با 4 رأس به نام‌های $A, B, C, D$ داریم. یال‌ها به صورت $AB, AC, BC$ هستند. در این صورت:
$\deg(A)=2$ (اتصال به $B$ و $C$)، $\deg(B)=2$ (اتصال به $A$ و $C$)، $\deg(C)=2$ (اتصال به $A$ و $B$)، $\deg(D)=0$ (هیچ یالی ندارد). در اینجا رأس‌های $A$، $B$ و $C$ همگی هم‌درجه (با درجه 2) هستند. رأس $D$ با درجهٔ 0 با هیچ‌کدام هم‌درجه نیست (مگر اینکه رأس دیگری هم درجه 0 داشته باشد).

نوع گراف	تعداد رأس‌ها	آیا رأس هم‌درجه وجود دارد؟	مثال
گراف کامل $K_n$	$n$	بله، همهٔ رأس‌ها هم‌درجه	همهٔ رأس‌ها درجهٔ $n-1$ دارند
گراف مسیر $P_n$ با $n \ge 3$	$n$	بله، ولی نه همه	دو رأس انتهایی هم‌درجه (درجه 1) و رأس‌های میانی (درجه 2) هم‌درجه
گراف با درجه‌های متفاوت	$4$	ممکن است وجود داشته باشد	اگر درجه‌ها $3,2,2,1$ باشد، دو رأس با درجهٔ 2 هم‌درجه هستند

کاربرد عملی: شناسایی تقارن در شبکه‌های اجتماعی

فرض کنید یک شبکهٔ اجتماعی کوچک شامل 5 کاربر داریم: احمد، بهرام، جمشید، داریوش و ابراهیم. ارتباطات (دنبال کردن) به صورت زیر است:
احمد ← بهرام و جمشید را دنبال می‌کند.
بهرام ← احمد و داریوش را دنبال می‌کند.
جمشید ← احمد و ابراهیم را دنبال می‌کند.
داریوش ← بهرام را دنبال می‌کند.
ابراهیم ← جمشید را دنبال می‌کند.

اگر این شبکه را به صورت گراف جهت‌دار مدل کنیم، «درجهٔ خروجی» یک رأس برابر تعداد افرادی است که آن کاربر دنبال می‌کند. در اینجا:
$\deg_{out}(احمد)=2$، $\deg_{out}(بهرام)=2$، $\deg_{out}(جمشید)=2$، $\deg_{out}(داریوش)=1$، $\deg_{out}(ابراهیم)=1$. پس احمد، بهرام و جمشید هم‌درجه (همگی درجهٔ خروجی 2) هستند. داریوش و ابراهیم نیز با درجهٔ 1 هم‌درجه محسوب می‌شوند.

این اطلاعات به ما کمک می‌کند بفهمیم کدام کاربران از نظر میزان فعالیت در دنبال‌کردن دیگران مشابه هستند. رأس‌های هم‌درجه اغلب نقش‌های مشابهی در ساختار گراف دارند و می‌توانند در الگوریتم‌های خوشه‌بندی⁵ مفید باشند.

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

یکی از قضیه‌های پایه‌ای در نظریهٔ گراف، «قضیهٔ دست دادن»⁶ است که می‌گوید: مجموع درجه‌های همهٔ رأس‌های یک گراف، برابر است با دو برابر تعداد یال‌ها. به زبان ریاضی:

$\sum_{v \in V} \deg(v) = 2|E|$

این قضیه نتیجهٔ مهمی در مورد رأس‌های هم‌درجه دارد: تعداد رأس‌هایی که درجهٔ فرد دارند، همواره زوج است. بنابراین اگر در یک گراف به دنبال رأس‌های هم‌درجه با درجهٔ فرد می‌گردیم، تعداد آن‌ها باید زوج باشد.

مثال: فرض کنید گرافی با 7 رأس داریم که درجه‌های آن به ترتیب $3, 5, 2, 4, 3, 1, 2$ است. رأس‌های با درجهٔ 3 دو تاست (هم‌درجه)، رأس‌های با درجهٔ 2 نیز دو تاست (هم‌درجه). تعداد رأس‌های با درجهٔ فرد (3, 5, 3, 1) برابر 4 است که عددی زوج می‌باشد.

چالش‌های مفهومی

چالش ۱: آیا دو رأس هم‌درجه همیشه در گراف نقش یکسانی دارند؟

لزوماً خیر. دو رأس ممکن است درجهٔ مساوی داشته باشند اما از نظر ساختار محلی (همسایه‌ها) متفاوت باشند. برای نمونه، در یک گراف مسیری با 4 رأس، دو رأس انتهایی هر دو درجهٔ 1 دارند (هم‌درجه) اما هر کدام به یک رأس میانی متفاوت متصل هستند. اگر آن رأس‌های میانی غیرمشابه باشند، نقش آن دو رأس انتهایی در گراف یکسان نیست.

چالش ۲: آیا می‌توان گرافی ساخت که هیچ دو رأس هم‌درجه‌ای نداشته باشد؟

بله، به چنین گرافی «گراف نامنظم»⁷ می‌گویند. در یک گراف نامنظم، درجهٔ همهٔ رأس‌ها با یکدیگر متفاوت است. ساده‌ترین مثال، گرافی با یک رأس (درجهٔ 0) است. برای تعداد رأس‌های بیشتر، ساخت گراف نامنظم امکان‌پذیر است به شرطی که درجه‌ها اعداد متمایز $0,1,2,...,n-1$ باشند، اما طبق قضیهٔ دست دادن، چنین مجموعه‌ای فقط برای $n=1$ و $n=2$ (که غیرممکن است) قابل تحقق نیست. در واقع برای $n \ge 2$ نمی‌توان یک گراف ساده با درجه‌های کاملاً متمایز داشت، بنابراین همیشه حداقل یک جفت رأس هم‌درجه وجود دارد.

چالش ۳: در گراف‌های جهت‌دار، مفهوم هم‌درجه چگونه تعریف می‌شود؟

در گراف جهت‌دار، هر رأس دو نوع درجه دارد: درجهٔ ورودی (تعداد یال‌هایی که به رأس وارد می‌شوند) و درجهٔ خروجی (تعداد یال‌هایی که از رأس خارج می‌شوند). دو رأس می‌توانند از نظر درجهٔ ورودی هم‌درجه باشند، یا از نظر درجهٔ خروجی، یا هر دو. در حالت کلی، وقتی می‌گوییم «رأس‌های هم‌درجه» در گراف جهت‌دار، باید مشخص کنیم منظور کدام درجه است.

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