نظريه گراف شاخه اي از رياضيات است كه درباره اشياء خاصي در رياضي به نام گراف بحث مي‌كند. به صورت شهودي گراف نمودار يا دياگرامي است شامل تعدادي رأس كه با يالهايي به هم وصل شده‌اند. تعريف دقيق‌تر گراف به اين صورت است كه گراف مجموعه‌اي از رأس‌ها است كه توسط خانواده‌اي از زوج‌هاي مرتب كه همان يال‌ها هستند به هم مربوط شده‌اند.

يالها بر دو نوع ساده و جهت دار هستند كه هر كدام در جاي خود كاربردهاي بسياري دارد. مثلاً اگر صرفاً اتصال دو نقطه - مانند اتصال تهران و زنجان با كمك آزادراه - مد نظر شما باشد كافيست آن دو شهر را با دو نقطه نمايش داده و اتوبان مزبور را با يالي ساده نمايش دهيد. اما اگر بين دو شهر جاده اي يكطرفه وجود داشته باشد آنگاه لازمست تا شما با قرار دادن يالي جهت دار مسير حركت را در آن جاده مشخص كنيد.

آغاز نظريهٔ گراف به سدهٔ هجدهم بر مي‌گردد. اويلر رياضيدان بزرگ مفهوم گراف را براي حل مسئله پل‌هاي كونيگسبرگ ابداع كرد اما رشد و پويايي اين نظريه عمدتاً مربوط به نيم سدهٔ اخير و با رشد علم داده‌ورزي (انفورماتيك) بوده است.

مهم‌ترين كاربرد گراف مدل‌سازي پديده‌هاي گوناگون و بررسي بر روي آنهاست. با گراف مي‌توان به راحتي يك نقشه بسيار بزرگ يا شبكه‌اي عظيم را در درون يك ماتريس به نام ماتريس وقوع گراف ذخيره كرد و يا الگوريتمهاي‌ مناسب مانند الگوريتم دايسترا يا الگوريتم كروسكال و ... را بر روي آن اعمال نمود.

يكي از قسمت‌هاي پركاربرد نظريهٔ گراف، گراف‌هاي مسطح است كه به بررسي گراف‌هايي مي‌پردازد كه مي‌توان آن‌ها را به نحوي روي صفحه كشيد كه يال‌ها جز در محل راس ها يكديگر را قطع نكنند. اين نوع گراف در ساخت جاده ها و حل مساله كلاسيك و قديمي سه خانه و سه چاه آب به كار مي رود.

نظريه گراف يكي از پركاربردترين نظريه ها در شاخه هاي مختلف علوم مهندسي (مانند عمران)، باستانشناسي(كشف محدوده يك تمدن) و ... است.

 انواع گراف

گراف ساده: هر گراف G زوج مرتبي مانند (V,E) است كه در آن V مجموعه اي متناهي و ناتهي است و E زيرمجموعه اي از تمام زيرمجموعه هاي دو عضوي V ميباشد. اعضاي V را رأسهاي G و اعضاي E را يالهاي G ميناميم. به بيان ساده تر بين دو رأس يك گراف ساده حداكثر يك يال وجود دارد.

گراف چندگانه: هرگاه بين دو رأس متمايز از يك گراف بيش از يك يال وجود داشته باشد، آن را يك گراف چند گانه مي گوييم.

گراف جهت دار: هر گراف G زوج مرتبي مانند (V,E) است كه در آن V مجموعه اي متناهي و ناتهي است و E زيرمجموعه اي از مجموعه ي تمام زوج مرتب هاي متشكل از اعضاي V است.

 خصوصيات گرافهاي خاص

·                     اگر تعداد يال ها و درجه راس ها در گراف ساده برابر باشد گراف موردنظر منتظم كامل است رابطه بين راسها و يالها اين چنين است.

 q=p(p-1)/2

كه در آن pتعداد راسها qتعداد يالها است.

·                     اگر گراف همبند باشد(يعني از هر نقطه بتوان به يك نقطه دلخواه ديگر رسيد) ولي دور نداشته باشد(يعني هيچ نقطه اي از دو راه به نقطه ي بعدي نرسد)مي گويند گراف درختي است. وفرمول آنهم اين چنين است.

 p=1+q

كه در آن pتعداد راسها qتعداد يالها است.

مرجع : كتاب آشنايي با نظريه گراف