نظریه گراف: تفاوت میان نسخهها
محتوای حذفشده محتوای افزودهشده
جز ←تاریخچه: ویرایش جزئی |
جز ←تعریف |
||
خط ۲۲:
یالها بر دو نوع ساده و جهت دار هستند، که هر کدام در جای خود کاربردهای بسیاری دارد. مثلاً اگر صرفاً اتصال دو نقطه -مانند اتصال تهران و زنجان با کمک آزادراه- مد نظر شما باشد، کافیست آن دو شهر را با دو نقطه نمایش داده، و اتوبان مزبور را با یالی ساده نمایش دهید. اما اگر بین دو شهر جادهای یکطرفه وجود داشته باشد آنگاه لازمست تا شما با قرار دادن یالی جهت دار مسیر حرکت را در آن جاده مشخص کنید. همچنین برای اینکه فاصله بین دو شهر را در گراف نشان دهید، میتوانید از گراف وزن دار استفاده کنید و مسافت بین شهرها را با یک عدد بر روی هر یال نشان دهید.
آغاز نظریهٔ گراف به سدهٔ هجدهم بر میگردد. [[
مهمترین کاربرد گراف [[مدلسازی]] پدیدههای گوناگون و بررسی بر روی آنهاست. با گراف میتوان به راحتی یک نقشه بسیار بزرگ یا شبکهای عظیم را در درون یک [[ماتریس]] به نام ماتریس وقوع گراف ذخیره کرد و یا [[الگوریتم|الگوریتمهای]] مناسب مانند الگوریتم دایجسترا یا الگوریتم کروسکال و... را بر روی آن اعمال نمود.
|