گراف جهتدار: یالهایی که مسیر را تعیین میکنند
گراف جهتدار چیست؟ تعریف و نمادگذاری
در ریاضیات و علوم کامپیوتر، یک گراف جهتدار1 (یا دایگراف) از دو مجموعه تشکیل میشود: مجموعهای از رأسها2 و مجموعهای از یالهای جهتدار3. هر یال جهتدار، جفتی مرتب از رأسها است و جهت خاصی را نشان میدهد. اگر یال جهتداری از رأس $ u $ به رأس $ v $ داشته باشیم، میگوییم $ u $ به $ v $ متصل است و آن را با $ (u, v) $ نمایش میدهیم. برخلاف گراف بدون جهت، در گراف جهتدار یال $ (u, v) $ با $ (v, u) $ متفاوت است.
برای نمونه، فرض کنید سه نفر به نامهای علی، بابک و جمشید در یک شبکهٔ اجتماعی داریم. اگر علی، بابک را دنبال کند اما بابک، علی را دنبال نکند، این رابطه با یک یال جهتدار از علی به بابک نشان داده میشود. همچنین اگر جمشید هر دو نفر را دنبال کند، دو یال جهتدار از جمشید به علی و از جمشید به بابک خواهیم داشت. این مثال ساده، قدرت گراف جهتدار را در مدلسازی روابط نامتقارن نشان میدهد.
درجه ورودی و درجه خروجی: اندازهگیری جریان روابط
در گراف جهتدار، برای هر رأس دو نوع درجه تعریف میشود: درجه خروجی4 تعداد یالهایی است که از آن رأس خارج میشوند و درجه ورودی5 تعداد یالهایی است که به آن رأس وارد میشوند. این مفهوم به ما کمک میکند تا میزان تأثیرگذاری یا تأثیرپذیری هر رأس را در شبکه بسنجیم. در شبکه اجتماعی دنبال کردن، درجه خروجی نشاندهندهٔ تعداد افرادی است که یک کاربر دنبال میکند و درجه ورودی نشاندهندهٔ تعداد دنبالکنندگان اوست.
| نوع درجه | نماد ریاضی | معنی در شبکهٔ اجتماعی |
|---|---|---|
| درجه خروجی | $ deg^+(v) $ | تعداد افرادی که کاربر $ v $ دنبال میکند |
| درجه ورودی | $ deg^-(v) $ | تعداد دنبالکنندگان کاربر $ v $ |
یک قضیهٔ مهم در گرافهای جهتدار این است که مجموع درجههای خروجی همهٔ رأسها برابر با مجموع درجههای ورودی همهٔ رأسها و برابر با تعداد کل یالها است:
مسیر جهتدار و دور جهتدار: حرکت در گراف
یک مسیر جهتدار6 دنبالهای از رأسها مانند $ v_1, v_2, ..., v_k $ است به طوری که هر جفت متوالی $ (v_i, v_{i+1}) $ یک یال جهتدار در گراف باشد. اگر مسیر جهتدار در رأس شروع به رأس پایان بازگردد (یعنی $ v_1 = v_k $) و طول آن حداقل $ 1 $ باشد، آن را یک دور جهتدار7 مینامیم. دورها در تحلیل چرخههای بازخوردی مانند چرخههای وابستگی در پروژههای نرمافزاری اهمیت زیادی دارند.
مثال عملی: فرض کنید برای یادگیری برنامهنویسی وب، درس «مبانی کامپیوتر» پیشنیاز درس «برنامهنویسی پایتون» است و درس «پایتون» پیشنیاز «طراحی وب» باشد. این روابط یک مسیر جهتدار از «مبانی» به «پایتون» و سپس به «طراحی وب» میسازد. اگر درس «طراحی وب» پیشنیاز «مبانی» باشد (که غیرمنطقی است)، آنگاه یک دور جهتدار ایجاد میشود که نشاندهندهٔ یک چرخهٔ پیشنیازی نامعتبر است.
کاربرد عملی: رتبهبندی صفحه در موتورهای جستجو
یکی از مشهورترین کاربردهای گراف جهتدار، الگوریتم رتبهبندی صفحه8 است که توسط بنیانگذاران گوگل ابداع شد. در این الگوریتم، هر صفحهٔ وب یک رأس است و پیوندی که از صفحهٔ $ A $ به صفحهٔ $ B $ وجود دارد، به عنوان یک یال جهتدار از $ A $ به $ B $ مدل میشود. صفحاتی که درجه ورودی بالاتری دارند (یعنی صفحات معتبر بیشتری به آنها پیوند دادهاند) اهمیت بیشتری دارند. البته رتبهبندی صفحه فقط به تعداد پیوندها توجه نمیکند، بلکه به اهمیت صفحات پیونددهنده نیز وزن میدهد. این ایده، پایهٔ اولیهٔ موتور جستجوی گوگل بود و انقلابی در جستجوی وب ایجاد کرد.
چالشهای مفهومی
بله. هر گراف بدون جهت را میتوان به یک گراف جهتدار تبدیل کرد که در آن به ازای هر یال بدون جهت $ \{u, v\} $، دو یال جهتدار مخالف $ (u, v) $ و $ (v, u) $ قرار دهیم. در این حالت، درجه ورودی و خروجی هر رأس با هم برابر و برابر با درجه آن در گراف بدون جهت میشود.
خیر. گراف جهتدار ممکن است همبندی قوی9 نباشد. یک گراف جهتدار قویاً همبند نامیده میشود اگر برای هر دو رأس $ u $ و $ v $، هم مسیر جهتداری از $ u $ به $ v $ وجود داشته باشد و هم مسیری از $ v $ به $ u $. در بسیاری از شبکههای اجتماعی واقعی، گراف جهتدار قویاً همبند نیست.
در هر دو نوع گراف، حلقه یالی است که یک رأس را به خودش متصل میکند. در گراف جهتدار، یک حلقه معمولاً هم به عنوان یال خروجی و هم به عنوان یال ورودی آن رأس محسوب میشود (یعنی درجه ورودی و خروجی را هر کدام $ 1 $ واحد افزایش میدهد). در گراف بدون جهت، حلقه درجهٔ رأس را $ 2 $ واحد افزایش میدهد. این تفاوت در محاسبهٔ قضیهٔ دست دادن (Handshaking lemma) دیده میشود.
گراف جهتدار ابزاری قدرتمند برای مدلسازی روابط یکطرفه و نامتقارن در دنیای واقعی است. با مفاهیمی مانند درجه ورودی و خروجی، مسیر و دور جهتدار، میتوان شبکههای اجتماعی، پیشنیازهای درسی، پیوندهای صفحات وب و بسیاری از سیستمهای دیگر را تحلیل کرد. الگوریتم رتبهبندی صفحه یکی از نمونههای موفق کاربرد این ساختار ریاضی است. درک گرافهای جهتدار پایهٔ بسیاری از حوزههای علوم کامپیوتر و تحقیق در عملیات را تشکیل میدهد.
پاورقی
2 رأس (Vertex): هر نقطه یا گره در گراف که نشاندهندهٔ یک موجودیت یا شیء است.
3 یال جهتدار (Directed Edge یا Arc): جفتی مرتب از رأسها که جهت از رأس اول به رأس دوم را نشان میدهد.
4 درجه خروجی (Out-degree): تعداد یالهایی که از یک رأس خارج میشوند.
5 درجه ورودی (In-degree): تعداد یالهایی که به یک رأس وارد میشوند.
6 مسیر جهتدار (Directed Path): دنبالهای از رأسها که هر جفت متوالی توسط یک یال جهتدار به هم متصل شدهاند.
7 دور جهتدار (Directed Cycle): مسیر جهتداری که رأس شروع و پایان آن یکی باشد و طول آن حداقل یک باشد.
8 رتبهبندی صفحه (PageRank): الگوریتمی برای تعیین اهمیت صفحات وب بر اساس ساختار پیوندهای جهتدار بین آنها.
9 همبندی قوی (Strong Connectivity): خاصیتی از گراف جهتدار که در آن از هر رأس به هر رأس دیگر مسیر جهتدار وجود داشته باشد.