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

تعريف

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

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

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

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

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

مسايل گراف

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