مجموعهٔ یال‌های گراف: مجموعهٔ همهٔ یال‌های گراف، با نماد E(G)

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

مجموعهٔ یال‌های گراف: ساختار، نمادگذاری و کاربردها

آشنایی با مجموعهٔ E(G) به عنوان یکی از دو رکن اصلی هر گراف و نقش آن در مدل‌سازی روابط

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

۱. تعریف دقیق مجموعهٔ یال‌ها و نمادگذاری

در نظریهٔ گراف، یک گراف $G$ از دو مجموعهٔ اصلی تشکیل شده است: مجموعهٔ رأس‌ها $V(G)$ و مجموعهٔ یال‌ها $E(G)$. هر یال نشان‌دهندهٔ یک ارتباط یا پیوند بین دو رأس است. اگر گراف بدون جهت باشد (غیرجهت‌دار)، هر یال به صورت یک جفت نامرتب $\{u,v\}$ نمایش داده می‌شود. در گراف جهت‌دار (که اصطلاحاً دی‌گراف نامیده می‌شود)، هر یال به صورت یک جفت مرتب $(u,v)$ نوشته می‌شود که نشان‌دهندهٔ جهت از $u$ به $v$ است.

مثال ساده: گرافی با سه رأس $V(G)=\{a,b,c\}$ و یال‌های بین a-b و b-c. در این صورت مجموعهٔ یال‌ها به صورت $E(G)=\{\{a,b\},\{b,c\}\}$ خواهد بود. اگر گراف جهت‌دار باشد و یال از a به b و از b به c داشته باشیم، آنگاه $E(G)=\{(a,b),(b,c)\}$.

۲. انواع مجموعهٔ یال‌ها بر اساس ساختار گراف

بسته به نوع گراف، مجموعهٔ یال‌ها ویژگی‌های متفاوتی پیدا می‌کند. در ادامه مهم‌ترین حالت‌ها را مرور می‌کنیم:

گراف ساده: فاقد یال چندگانه (یال موازی) و حلقه^۱ است. در این گراف‌ها هر جفت از رأس‌ها حداکثر با یک یال به هم متصل می‌شوند.
گراف با یال چندگانه (چندگراف): مجموعهٔ یال‌ها اجازهٔ تکرار دارد. در این حالت به جای مجموعه از خانوادهٔ یال‌ها صحبت می‌شود.
گراف وزن‌دار: به هر یال یک مقدار عددی (وزن) نسبت داده می‌شود. در چنین مواردی معمولاً تابع وزن $w:E(G)\to \mathbb{R}$ تعریف می‌شود.

نوع گراف	ویژگی مجموعهٔ یال‌ها	نماد پیشنهادی
گراف ساده	فاقد یال تکراری و حلقه	$E(G) \subseteq \binom{V(G)}{2}$
چندگراف	قابلیت تکرار یال و وجود حلقه	$\text{چندمجموعهٔ }E(G)$
گراف جهت‌دار	یال‌ها جفت‌های مرتب هستند	$E(G)\subseteq V(G)\times V(G)$

۳. اعمال مهم روی مجموعهٔ یال‌ها

مجموعهٔ یال‌ها از جنس مجموعه است، بنابراین عملیات مجموعه‌ای مانند اجتماع، اشتراک و تفاضل برای آن تعریف می‌شود. همچنین در نظریهٔ گراف، افزودن یا حذف یک یال به صورت نقطه‌ای اهمیت زیادی دارد.

اجتماع یال‌ها: اگر دو گراف $G_1$ و $G_2$ روی رأس‌های یکسان داشته باشیم، مجموعهٔ یال‌های اجتماع $E(G_1\cup G_2)=E(G_1)\cup E(G_2)$ است.
حذف یک رأس: با حذف یک رأس، همهٔ یال‌های وابسته به آن نیز از مجموعهٔ یال‌ها خارج می‌شوند.
مکمل گراف: در گراف کامل^۲ با $n$ رأس، مجموعهٔ یال‌ها شامل همهٔ زوج‌های ممکن است. مکمل گراف $G$ مجموعهٔ یال‌هایی را دارد که در $G$ وجود ندارند.

فرمول شمارش یال‌ها در گراف ساده: در یک گراف ساده با $n$ رأس، حداکثر تعداد یال‌ها برابر است با $\binom{n}{2}=\frac{n(n-1)}{2}$. برای گراف‌های جهت‌دار ساده (بدون حلقه)، حداکثر تعداد یال‌ها $n(n-1)$ است.

۴. کاربرد عملی: مدل‌سازی شبکهٔ دوستان در یک کلاس

فرض کنید در یک کلاس $6$ نفره، رابطهٔ "دوستی" را به صورت یک گراف بدون جهت مدل می‌کنیم. هر دانش‌آموز یک رأس است و اگر دو نفر با هم دوست باشند، بینشان یال قرار می‌دهیم. مجموعهٔ یال‌ها در این حالت نشان می‌دهد که چه کسانی با هم ارتباط مستقیم دارند. به عنوان مثال، اگر دوستی‌ها به صورت $\{1,2\},\{2,3\},\{3,4\},\{4,5\},\{5,6\},\{1,6\}$ باشد، این مجموعهٔ یال‌ها یک چرخهٔ $6$ رأسی را می‌سازد. در این مدل، با نگاه کردن به مجموعهٔ یال‌ها می‌توان فهمید شبکهٔ دوستی چند لبه دارد و آیا شامل زیرگراف خاصی (مانند مثلث) است یا خیر.

۵. چالش‌های مفهومی پیرامون مجموعهٔ یال‌ها

پرسش ۱: آیا در یک گراف می‌توان یالی داشت که دو سر آن یکی باشد؟
پاسخ: بله، چنین یالی حلقه نامیده می‌شود و معمولاً به صورت $\{v,v\}$ یا $(v,v)$ نمایش داده می‌شود. در گراف‌های ساده حلقه مجاز نیست.

پرسش ۲: مجموعهٔ یال‌های یک گراف خالی چیست؟
پاسخ: گراف خالی به گرافی گفته می‌شود که مجموعهٔ رأس‌های آن ناتهی اما مجموعهٔ یال‌های آن تهی است: $E(G)=\emptyset$. چنین گرافی هیچ ارتباطی بین رأس‌ها ندارد.

پرسش ۳: چگونه می‌توان تعداد یال‌های یک گراف را بدون برشماردن مستقیم به دست آورد؟
پاسخ: با استفاده از قانون دست دادن^۳ که می‌گوید مجموع درجهٔ همهٔ رأس‌ها برابر با دو برابر تعداد یال‌ها است. یعنی $\sum_{v\in V(G)} \deg(v) = 2|E(G)|$.

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