نظریه گراف

در ریاضی و علوم کامپیوتر، نظریه گراف علمی است که بهمطالعه گراف‌ها می‌پردازد.گراف مجموعه‌ای از راس‌هاست که بوسیله یال‌ها به هم وصلشده‌اند.به عبارت ساده‌تر به مجموعه‌ای از نقاط که بوسیله خطوط به هم وصل شده‌‌اند،گراف گویند. مفهوم گراف در سال 1736 توسط اویلر و با طرحراه‌حلی برای مساله پلKongsberg ارائه شد و به تدریج توسعه یافت.گراف‌ها امروزهکاربرد زیادی در علوم دارند. از گراف‌ها در شبکه‌ها،طراحی مدارهای الکتریکی, اصلاحهندسی خیابان‌ها برای حل مشکل ترافیک،و.... استفادهمیشود.

تعریف

فرض کنیدV یک مجموعه ناتهی وE زیرمجموعه‌ای ازباشد در اینصورت زوجرا یکگراف می نامندV. را مجموعه راس ها وE را مجموعه یال ها می گویند. اگر ترتیب قرارگرفتن راس ها در مجموعهE مهم باشد،گراف راگراف جهت‌دارمی گویند و یال از راسبه سمتراسرا بهصورتنشانمی‌دهند.در غیر این صورت گراف را بدون جهت می‌نامند و یال بین راس هایوبا نمادنشانمی‌دهند. تعداد راس های یک گراف رامرتبهو تعدادیال های آن رااندازهگراف می نامیم.
در شکل زيرگرافی را با شش راس وهفت یال مشاهده می کنیم

انواع گراف‌ها

گراف‌ها دارای انواع متعددی هستند که به برخی از آنهااشاره می‌کنیم:
گراف همبند
گراف ناهمبند
گراف کامل
گراف اویلری
گراف همیلتونی
گراف درختی
گراف مسطح
گراف دو بخشی
گراف چندبخشی
گرافk-مکعب
گراف چرخ 
گراف ستاره‌ای
گراف بازه‌ای
گراف اشتراکی
گراف منظم
گراف جهت‌دار

گراف‌ها و ساختار داده‌ها

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

مسایل گراف

تئوری رنگ آمیزی
قضیه چهار رنگ
مسائل حل نشده در رنگ آمیزی
مسائل موجود در زمینه مسیر
هفت پلKongsberg
Minimum spanning tree
درختSteiner
مساله کوتاهترین مسیر
مساله پستچی چینی
مساله فروشنده دوره گرد
الگوریتم‌های مهم
الگوریتمkruskal
الگوریتمprim
الگوریتم کوتاهترین مسیر
منبع:http://daneshnameh.roshd.ir-1
/خ