GRAPH THEORY

نظریه گراف و کاربرد های آن

  • : نویسنده
  • 01/02/13

سریع ترین مسیر از از پایتخت به هر کدام از شهر های کشور کدام است ؟
چطور می توان n نفر را در n شغل قراداد طوری که هر کس ماکسیمم رضایت را از شغلش داشته باشد؟
چگونه می توان با گذار حداقل تعداد هفته برای یک لیگ ورزشی برنامه ریزی کرد؟
فروشنده دورگرد برای به حداقل رساندن زمان سفر باید به ترتیب به چه شهرهایی مراجعه کند ؟
آیا می توان مناطق یک نقشه را با استفاده از چهار رنگ، رنگ کرد به طوری مناطق مجاور رنگ های مختلف داشته باشند؟
تمام موارد بالا و خیلی از مسائل دیگر هستند که راه حل آنها را نظریه گراف ارائه کرده است. در این مقاله می خواهیم کمی در رابطه با نظریه گرافها صحبت کنیم و شما را کمی با کاربرد آن آشنا کنیم.

تاریخچه نظریه گراف

تولد نظریه گراف از یک مشکل شروع شده !
مشکل پل کونیگسبرگ در شهر کونیگسبرگ (کونیگسبرگ نام پیشین و اصلی شهر فعلی کالینینگراد متعلق به فدراسیون روسیه است) بود
این شهر دو جزیره به اضافه مناطقی را در هر دو ساحل اشغال کرده بود. همانطور که در تصویر پایین ملاحظه می کنید، این مناطق توسط هفت پل به هم مرتبط بودند سوال مردم آنجا این بود که آیا می توانند از یک نقطه پل شروع به حرکت کنند و از هر پل یک بار عبور کنند و دوباره به همان نقطه ای که از آن شروع کرده اند برگردند ؟

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

گراف تئوریست های زیادی از سراسر جهان مقاله هایی در رابطه با مسائل مختلف ارائه کردند که مشکلات مختلفی را حل کرده است. شما می توانید به منبعی از مراجع نظریه گراف و مقاله های مرتبط با آن دسترسی داشته باشید . برای دسترسی به لینک مراجعه کنید graph theory association.

برخی از کاربرد های نظریه گراف در رشته ها :


مهندسی برق :
گراف در مهندسی برق برای نمایش اتصال مدارها به کار می‌رود. برخی از این اتصالات به عنوان ستاره، مثلث، سری و موازی شناخته می‌شوند.
علوم کامپیوتر :
یکی از کاربردهای گراف در علوم کامپیوتر، مطالعه الگوریتم‌ها است. همچنین، برای بیان رابطه بین کامپیوترها در شبکه، از گراف‌ها استفاده می‌شود.
علوم پزشکی و شیمی :
ساختار مولکولی و شیمیایی ماده، ساختار DNA و… از مواردی هستند که برای نمایش آن‌ها از گراف‌ها استفاده می‌شود.
عمومی:
نمایش مسیرهای بین شهرها نیز یکی از کاربردهای عمومی نظریه گراف است.

:برخی از تعاریف ابتدایی و مهم نظریه گراف

تعریف گراف :
یک گراف، نمایشی تصویری از مجموعه اشیائی است که با هم ارتباط دارند. هر یک از این اشیا را «راس» یا گره می‌نامند. راس‌ها نیز از طریق «یال‌»ها یا لبه‌ها با هم مرتبط هستند. تا این‌جا، چیزی که به ذهنمان می‌آید، تعدادی نقطه است که با خطوطی به یک‌دیگر متصل شده‌اند.

اگر بخواهیم کمی رسمی‌تر بنویسیم، یک گراف را با (V,E) تعریف می‌کنیم که در آن، E مجموعه راس‌ها و V مجموعه یال‌ها است. شکل زیر، یک گراف را نشان می‌دهد. احتمالاً این شکل، تا حدودی شبیه همان چیزی است که تصور کرده‌اید.


در شکل بالا، V و E به‌صورت زیر هستند:
V = {a, b, c, d, e}
E = {ab, ac, bd, cd, de}
در این مقاله به همین حد از توضیحات کفایت می کنیم و به سراغ جنبه های دیگری از نظریه گراف می رویم.

راس
یک راس، نقطه‌ای است که در آن، چند خط به هم می‌رسند. راس، گره نیز نامیده می‌شود. مشابه نقاط، رأس را نیز می‌توان با یکی از حروف الفبا نام‌گذاری کرد.
یال
یال، اصطلاحی ریاضی است که برای خطی به‌کار می‌رود که دو راس را به یک‌دیگر وصل می‌کند. از یک راس ممکن است تعداد زیادی یال شکل بگیرد. بدون وجود راس، یالی هم وجود نخواهد داشت. برای هر یال، یک راس ابتدا و یک راس انتها وجود دارد. در شکل زیر، دو راس «a» و «b»، و ارتباط بین آن‌ها، یعنی یال نشان داده شده است.

پل اردوش (Paul Erdős)

تولد: ۲۶ مارس ۱۹۱۳ -- بوداپست، اتریش-مجارستان
درگذشت: ۲۰ سپتامبر ۱۹۹۶ (۸۳ سالگی) ورشو، لهستان
عدد اردوش (اردیش) عدد اردوش (Erdős number) "فاصله همکاری" بین یک شخص و ریاضیدان مجارستانی پل اردوش است که با نگارش مقالات ریاضی مشترک اندازه‌گیری می‌شود.
عدد اردوش خود اردوش صفر است.
عدد اردوش هر کس که با او مقاله مشترک داشته باشد ۱ است.
عدد اردوش کسی که با کسی که عدد اردوش او ۱ است مقاله مشترک دارد، ۲ است.
عدد اردوش کسی که با کسی که عدد اردوش او ۲ است مقاله مشترک دارد، ۳ است.

اردوش در طول زندگی اش بالغ بر 1500 مقاله و کتاب را به تنهایی یا با همکاری دیگران به رشته تحریر درآورده است و از این رو می‌توان گفت که بیش از هر کسی در تاریخ ریاضیات با ریاضی‌دانان دیگر همکاری داشته است. اردوش 511 همکار مستقیم داشته است. این افراد دارای عدد اردوش 1 هستند. همچنین تا سال 2010، تعداد 9267 نفر، عدد اردوش 2 را کسب کرده اند.

برخی از گراف تئوریست های مشهور

مهدی بهزاد

زمینه تحقیق : گراف تئوری
پدر علم گراف ایران
عدد اردوش : 1
homepage

سعید اکبری


زمینه تحقیق :
Algebra, Graph Theory & Algebraic Combinatorics

ایمیل:s_akbari@sharif.ir
عدد اردوش : 2
homepage

Douglas B.west


زمینه تحقیق :
combinatory, Graph Theory

ایمیل: dwest@illinois.edu
نویسنده کتاب : Introduction to Graph Theory
homepage

برای مشاهده لیست کامل گراف تئوریست ها کلیک کنید

شما می توانید برای مشاهده مقالات، ژورنال ها، همچنین آشنایی با گراف تئوریست ها به وبسایت رسمی انجمن نظریه گرافها مراجعه کنید.