یال: ارتباط بین دو رأس در گراف
یال چیست و چه نقشی در گراف دارد؟
در نظریهٔ گراف1، یک گراف از دو مؤلفهٔ اصلی ساخته میشود: رأسها (گرهها) و یالها (پيوندها). اگر رأسها را به عنوان نقطه یا شیء در نظر بگیریم، یال همان پلی است که دو رأس را به یکدیگر متصل میکند. به عبارت سادهتر، یال نشاندهندهٔ «ارتباط» یا «رابطه» میان دو گره است.
برای مثال، فرض کنید بخواهیم نقشهٔ متروی یک شهر را با گراف نمایش دهیم. هر ایستگاه یک رأس است و هر خط راهآهن میان دو ایستگاه، یک یال خواهد بود. اگر بین دو ایستگاه مسیر مستقیم وجود داشته باشد، یک یال آن دو را به هم وصل میکند. در این حالت، یال به ما میگوید که از ایستگاه A میتوان مستقیماً به ایستگاه B رفت.
انواع یال بر اساس جهت و وزن
یالها را از دیدگاههای گوناگونی دستهبندی میکنند. مهمترین تقسیمبندی بر اساس «جهت» و «وزن» است.
| نوع یال | معادل انگلیسی | ویژگی اصلی | مثال | بدون جهت | Undirected | ارتباط دوطرفه | خط تلفن بین دو ساختمان | جهتدار (کمان) | Directed (Arc) | ارتباط یکطرفه با پیکان | دنبالکردن در اینستاگرام (از A به B) | وزنی | Weighted | دارای عدد (هزینه، فاصله) | مسافت 12 کیلومتر بین دو شهر |
|---|
برای بیان رابطهٔ ریاضی بین رأسها از نمادگذاری استفاده میکنیم. اگر دو رأس u و v با یک یال به هم وصل شده باشند، در گراف بدون جهت مینویسیم: $uv \in E$ که E مجموعهٔ یالهاست. در گراف جهتدار، یال از u به v را با $(u,v)$ نمایش میدهیم.
نمایش یال در ماتریس مجاورت و فهرست یال
برای ذخیرهٔ گراف در حافظهٔ رایانه، دو روش رایج وجود دارد: ماتریس مجاورت2 و فهرست یال3. در ماتریس مجاورت، سطرها و ستونها نمایندهٔ رأسها هستند. اگر بین رأس i و j یالی وجود داشته باشد، در خانهٔ (i,j) عدد 1 (یا وزن) قرار میگیرد؛ در غیر اینصورت 0.
روش دیگر، فهرست یال است: یک جدول ساده که هر سطر آن یک یال را نشان میدهد (مثلاً رأس مبدأ و رأس مقصد). برای گراف جهتدار ترتیب مهم است. برای گراف بدون جهت، ترتیب اهمیتی ندارد.
کاربرد عملی یال در شبکههای اجتماعی و مسیریابی
شبکههای اجتماعی مانند تلگرام یا اینستاگرام را در نظر بگیرید. هر کاربر یک رأس است. اگر دو کاربر با هم دوست باشند، یک یال بدون جهت میان آنها رسم میشود. در توییتر، رابطهٔ «دنبال کردن» یک یال جهتدار است: از کاربر دنبالکننده به کاربر دنبالشونده.
در مسیریابی خودرو با سامانهٔ نشانه (GPS)، تقاطعها به عنوان رأس و خیابانها به عنوان یال در نظر گرفته میشوند. هر یال میتواند وزنی برابر با زمان سفر یا فاصله داشته باشد. کوتاهترین مسیر از یک مبدأ به مقصد، دنبالهای از یالهاست که مجموع وزن آن کمینه باشد.
چالشهای مفهومی پیرامون یال
پاسخ: در گراف ساده خیر. اما در گراف چندگانه4 چنین یالهایی (که یال موازی نامیده میشوند) مجاز هستند. مثلاً زمانی که دو شهر با چند جادهٔ مختلف به هم وصل شوند.
پاسخ: در گراف بدون جهت، درجهٔ رأس، شمار یالهای متصل به آن است. در گراف جهتدار، دو درجه داریم: درجهٔ ورودی (تعداد یالهایی که به رأس وارد میشوند) و درجهٔ خروجی (تعداد یالهایی که از رأس خارج میشوند). جمع درجهٔ کل برابر دو برابر شمار یالهاست.
پاسخ: نه. در گرافهای انتزاعی، یال میتواند هر نوع رابطهٔ منطقی یا مجازی را نشان دهد. برای نمونه، در گراف وابستگی نرمافزارها، یال نشان میدهد که یک ماژول به ماژول دیگر وابسته است، بدون آنکه ارتباط فیزیکی در کار باشد.
جمعبندی
پاورقی
1 نظریهٔ گراف (Graph Theory): شاخهای از ریاضیات گسسته که به مطالعهٔ گرافها شامل رأس و یال میپردازد.
2 ماتریس مجاورت (Adjacency Matrix): ماتریس مربعی که در آن سطرها و ستونها به رأسها اختصاص دارند و درایهها نشاندهندهٔ وجود یا وزن یال هستند.
3 فهرست یال (Edge List): مجموعهٔ جفترأسهایی که یک یال بین آنها وجود دارد، معمولاً به صورت جدول یا لیست ساده.
4 گراف چندگانه (Multigraph): گرافی که در آن اجازهٔ وجود یالهای موازی (چند یال بین یک جفت رأس) و حلقه (یال از رأس به خودش) داده میشود.