مفهوم گراف در سال 1736 توسط اویلر و با طرح راه حلی برای مسئله پل konigsberg ارائه شد،و به تدریج توسعه یافت.گرافها امروزه کاربرد زیادی در علوم دارند. از گرافها در شبکه ها،طراحی مدارهای الکتریکی, اصلاح هندسی خیابانها برای حل مشکل ترافیک،و.... استفاده میشود.
تعریف
فرض کنید v یک مجموعه ناتهی باشد در این صورت زوج
را یک گراف مینامند.V را مجموعه راسها و E را مجموعه یالها میگویند. اگر ترتیب قرار گرفتن راسها در مجموعه E مهم باشد،گراف را گراف جهت دار می گویند و یال از راس
به سمت راس
را به صورت
نشان میدهند.در غیر این صورت گراف را بدون جهت مینامند و یال بین راسهای
و
با نماد
نشان میدهند.
تعداد راسهای یک گراف را
مرتبه و تعداد یالهای آن را
اندازه گراف مینامیم.
حال به ذکر یک مثال میپردازیم:
در شکل روبرو گرافی را با شش راس و هفت یال مشاهده میکنیم
هر گراف را میتوان با یک ماتریس نمایش داد ، که به آن
ماتریس مجاورت گراف گویند.
انواع گرافها
گرافها دارای انواع متعددی هستند که به برخی از آنها اشاره میکنیم:
گراف همبند
گراف کامل
گراف اویلری
گراف همیلتونی
گراف درختی
گراف مسطح
گرافها و ساختار داده ها
مسایل گراف
از معروفترین مسائل گراف میتوان به
مسئله پستچی چینی و نیز به مسئله
فروشنده دوره گرد اشاره کرد.
الگوریتمهای مهم
همچنین ببینید
پیوندهای خارجی
http://math.youngzones.org/Konigsberg.html
www.wikipedia.com