نظریه گراف
از ویکی‌پدیا، دانشنامهٔ آزاد.
نظریه گراف شاخه ای از ریاضیات است که درباره اشیاء خاصی در ریاضی به نام گراف بحث می‌کند. به صورت شهودی گراف نمودار یا دیاگرامی است شامل تعدادی رأس که با یالهایی به هم وصل شده‌اند. تعریف دقیق‌تر گراف به این صورت است که گراف مجموعه‌ای از رأس‌ها است که توسط خانواده‌ای از زوج‌های مرتب که همان یالها هستند به هم مربوط شده‌اند.
یالها بر دو نوع ساده و جهت دار هستند که هر کدام در جای خود کاربردهای بسیاری دارد. مثلا اگر صرفا اتصال دو نقطه -مانند اتصال تهران و زنجان با کمک آژادراه- مد نظر شما باشد کافیست آن دو شهر را با دو نقطه نمایش داده و اتوبان مزبور را با یالی ساده نمایش دهید. اما اگر بین دو شهر جاده ای یکطرفه وجود داشته باشد آنگاه لازمست تا شما با قرار دادن یالی جهت دار مسیر حرکت را در آن جاده مشخص کنید.
آغاز نظریهٔ گراف به سدهٔ هجدهم بر می‌گردد. اویلر ریاضیدان بزرگ مفهوم گراف را برای حل مسئله پل‌های کونیگسبرگ ابداع کرد اما رشد و پویایی این نظریه عمدتاً مربوط به نیم سدهٔ اخیر و با رشد علم داده‌ورزی (انفورماتیک) بوده است.
مهم‌ترین کاربرد گراف مدل‌سازی پدیده‌های گوناگون و بررسی بر روی آنهاست. با گراف می‌توان به راحتی یک نقشه بسیار بزرگ یا شبکه‌ای عظیم را در درون یک ماتریس به نام ماتریس وقوع گراف ذخیره کرد و یا الگوریتمهای مناسب مانند الگوریتم دایسترا یا الگوریتم کروسکال و ... را بر روی آن اعمال نمود.
یکی از قسمت‌های پركاربرد نظریهٔ گراف، گراف‌های مسطح یا هامنی است که به بررسی گراف‌هایی می‌پردازد كه می‌توان آن‌ها را به نحوی روی صفحه كشید كه یالها جز در محل راس ها یكدیگر را قطع نكنند. این نوع گراف در ساخت جاده ها و حل مساله کلاسیک و قدیمی سه خانه و سه چاه آب به کار می رود.
نظریه گراف یکی از پرکاربردترین نظریه ها در شاخه های مختلف علوم مهندسی (مانند عمران)، باستانشناسی(کشف محدوده یک تمدن) و ... است.
[ویرایش] مطالعهٔ بیشتر
- کتاب آشنایی با نظریهٔ گراف نوشتهٔ علیرضا علیپور، انتشارات فاطمی
