واژه گراف در ریاضیات حداقل دارای دو معنی میباشد. در ریاضیات ابتدایی گراف به نمودار تابع اشاره دارد و در اصطلاح ریاضیدانان گراف مجموعهای از نقاط و خطوط متصل به هم هستند.
در واقع گراف مدلی ریاضی برای یک مجموعه گسسته است که اعضای آن به طریقی به هم مرتبط هستند. اعضای این مجموعه میتوانند انسان باشند و ارتباط آنها با هم دست دادن باشد. اعضا میتوانند اتمها در یک مولکول باشند و ارتباط آنها اتصالهای شیمیایی باشد یا اعضا میتوانند قسمتهای مختلف زمین و ارتباط بین آنها پلهایی باشد که آنها را به هم مرتبط میکند (همانند مسئله کونیگسبرگ).
نظریه گراف یکی از موضوعهای مهم در ریاضیات گسسته است که به مطالعهٔ گرافها و مدلبندی مسائل به وسیلهٔ آنها میپردازد. لئونارد اویلردر سال ۱۷۳۶ با حل مسئله پلهای کونیگسبرگ نظریهٔ گرافها را بنیان گذاشت. اما جیمز جوزف سیلوستر نخستین کسی بود که در سال ۱۸۷۸ از واژهٔ گراف برای نامیدن این مدلهای ریاضی استفاده کرد.
تعریفیک گراف از مجموعهای غیر خالی از اشیاء به نام رأس تشکیل شده، که آن را با نشان میدهیم، و مجموعهای شامل یالها، که رأسها را به هم وصل میکنند و با نمایش میدهیم. یک چنین گرافی را با نشان میدهیم. اگر یال دو رأس و را به هم وصل کند مینویسیم
اندازه گرافاندازه گراف تعداد یالهای یک گراف است و به صورت بیان میشود.
درجه راسهادر نظریه گرافها، درجه یک راس به تعداد یالهای متصل به آن راس گفته میشود. به عبارت دیگر، درجه یک راس تعداد همسایگی (مجاورت)های مستقیم یک راس را بیان میکند. از آنجا که هر یال در گراف دو راس را به هم وصل میکند، مجموع درجه راسهای یک گراف با دو برابر تعداد یالهای ان گراف برابر است.
فهرست مطالب:
مثالهایی ملموس از گراف
سنگ بنای نظریه ی گراف
پل کونیگسبرگ
معمای 1:ضیافت 6 نفره
معمای 2:مسأله 8 دایره
تعریف گراف
راس
یال
گراف جهتدار
مرتبه گراف
اندازه گراف
حلقه
راس منفرد
گراف بدون جهت
گراف ساده
نکات مربوط به گراف
مثال
گراف های معروف
زیرگراف ها
زیرگراف سره
زیرگراف فراگیر
زیرگراف القایی
معمای 3:جنون آنی
گراف تهی
یکریختی گراف ها
مسیرها و دورها
گشت بسته
گذر
گذر بسته
طول دور
گراف دو بخشی
درجه راس ها (گراف بدون جهت)
دنباله درجات رئوس
دنباله گرافیکی
تشخیص گرافیکی بودن یک دنباله
گراف کامل
گراف منتظم
درجه در گراف جهتدار
همبندی گراف
و...