واژه گراف در ریاضیات حداقل دارای دو معنی می‌باشد. در ریاضیات ابتدایی گراف به نمودار تابع اشاره دارد و در اصطلاح ریاضی‌دانان گراف مجموعه‌ای از نقاط و خطوط متصل به هم هستند.

در واقع گراف مدلی ریاضی برای یک مجموعه گسسته است که اعضای آن به طریقی به هم مرتبط هستند. اعضای این مجموعه می‌توانند انسان باشند و ارتباط آن‌ها با هم دست دادن باشد. اعضا می‌توانند اتم‌ها در یک مولکول باشند و ارتباط آن‌ها اتصال‌های شیمیایی باشد یا اعضا می‌توانند قسمت‌های مختلف زمین و ارتباط بین آن‌ها پل‌هایی باشد که آن‌ها را به هم مرتبط می‌کند (همانند مسئله کونیگسبرگ).

نظریه گراف یکی از موضوع‌های مهم در ریاضیات گسسته است که به مطالعهٔ گراف‌ها و مدل‌بندی مسائل به وسیلهٔ آن‌ها می‌پردازد. لئونارد اویلردر سال ۱۷۳۶ با حل مسئله پل‌های کونیگسبرگ نظریهٔ گراف‌ها را بنیان گذاشت. اما جیمز جوزف سیلوستر نخستین کسی بود که در سال ۱۸۷۸ از واژهٔ گراف برای نامیدن این مدل‌های ریاضی استفاده کرد.

از گراف‌ها برای حل مسایل زیادی در ریاضیات و علوم کامپیوتر استفاده می‌شود. ساختارهای زیادی را می‌توان به کمک گراف‌ها به نمایش درآورد. برای مثال برای نمایش چگونگی رابطه وب سایت‌ها به یکدیگر می‌توان از گراف جهت دار استفاده کرد. به این صورت که هر وب سایت را به یک راس در گراف تبدیل می‌کنیم و در صورتی‌که در این وب سایت لینکی به وب سایت دیگری بود، یک یال جهت دار از این راس به راسی که وب سایت دیگر را نمایش می‌دهد وصل می‌کنیم.

از گراف‌ها همچنین در شبکه‌ها، طراحی مدارهای الکتریکی، اصلاح هندسی خیابان‌ها برای حل مشکل ترافیک، و… استفاده می‌شود. مهم‌ترین کاربرد گراف مدل‌سازی پدیده‌های گوناگون و بررسی بر روی آنهاست. با گراف می‌توان به راحتی یک نقشه بسیار بزرگ یا شبکه‌ای عظیم را در درون یک ماتریس به نام ماتریس وقوع گراف ذخیره کرد یا الگوریتم‌های مناسب مانند الگوریتم دایسترا یا الگوریتم کروسکال و… را بر روی آن اعمال نمود. در این جا به بررسی گراف‌هایی می‌پردازد که می‌توان آن‌ها را به نحوی روی صفحه کشید که یال‌ها جز در محل رأس‌ها یکدیگر را قطع نکنند. این نوع گراف در ساخت جاده‌ها و حل مسئله کلاسیک و قدیمی سه خانه و سه چاه آب به کار می‌رود.

کاربرد گراف بازه‌ها از گراف‌ها برای حل مسایل زیادی در ریاضیات و علوم کامپیوتر استفاده می‌شود. ساختارهای زیادی را می‌توان به کمک گراف‌ها به نمایش درآورد.

درخت و ماتریس درخت در رشته‌های مختلفی مانند شیمی مهندسی برق و علم محاسبه کاربرد دارد. کیرشهف در سال ۱۸۴۷ میلادی هنگام حل دستگاه‌های معادلات خطی مربوط به شبکه‌های الکتریکی درخت‌ها را کشف و نظریه درخت‌ها را بارور کرد. کیلی در سال ۱۸۵۷ میلادی درخت‌ها را در ارتباط با شمارش ایزومرهای مختلف هیدروکربن‌ها کشف کرد وقتی مثلاً می‌گوییم در ایزومر مختلف c4h۱۰ وجود دارد منظورمان این است که دو درخت متفاوت با ۱۴ راس وجود دارند که درجه ۴ راس از این ۱۴ راس جهار و درجه هر یک از ۱۰ راس باقی‌مانده یک است. اگر هزینه کشیدن مثلاً راه‌آهن بین هر دو شهر ازp شهر مفروض مشخص باشد ارزانترین شبکه‌ای که این p شهر را به هم وصل می‌کند با مفهوم یک درخت از مرتبه p ارتباط نزدیک دارد. به جای مسئله مربوط به راه‌آهن می‌توان وضعیت مربوط به شبکه‌های برق‌رسانی و لوله‌کشی نفت و لوله‌کشی گاز و ایجاد کانال‌های آبرسانی را در نظر گرفت. برای تعیین یک شبکه با نازلترین هزینه از قاعده‌ای به نام الگوریتم صرفه جویی استفاده می‌شود که کاربردهای فراوان دارد.

 

فهرست مطالب:

فصل اول: مقدمه و تعریف گراف

گراف چيست؟

رقابتهاي تيمي

گرافهاي تهي و گرافهاي كامل

گرافهاي يكريخت

گرافهای هامنی

قضیه خم ژوردان

تعداد یالهای گراف

قضیه ها

گرافهای بازه ای

گرافهای افلاطونی

گرافهای دو بخشی

K – مکعب ها

اجتماع دو گراف

حذف و انقباض

گراف های مداری و چرخها

و...

فصل دوم: گراف های همبند

مولفه های همبند

گرافهای اویلری

قضیه ها

مدارهای همیلتنی

معماها و گرافها

و...

فصل سوم: درخت ها

درختها و جنگلها

مدارها و درختها

مسأله ارتباط دهی

درباره مساله فروشنده سیار

بست زنی شبكه ها

خیابانها و چهارراهها

و...

فصل چهارم: اثبات یک قضیه: قضیه جورسازی

اگر شرط تنوع برقرار باشد، می توان به هر متقاضی شغلی مناسب اختصاص داد

صورتهای دیگر مسئله جور سازی

مسابقه های دوره ای

و...

فصل پنجم: تسطیح و دوگانگی

گرافهای مسطح شده

قضایا

فرمول اویلر برای گرافهای مسطح

گرافهای روی سطوح دیگر

گرافهای دوگان

گرافهای نامتناهی

و...

فصل ششم: گراف های جهت دار

باز هم درباره مسابقه ها

سأله خيابانهاي يك طرفه

قضیه ها

درجه ها

گرافهاي ژنتيكي

تعيين كوتاه مدت ترين راه

و...

فصل هفتم: جور سازی، ازدواج و قضیه منجر

قضیه (ازدواج) هال

نظریه ترنسورسال

قضیه ها

ماتریسهای (1 و 0)

ترنسورسال مشترک

قضیه منجر

شارشهای شبکه

و...

فصل هشتم: نظریه متروید

درآمدی بر مترویدها

قضیه ها

مترویدهای بدیهی

مترویدهای گسسته

مترویدهای یکنواخت

مترویدهای گرافیکی

مترویدهای هم گرافیک

مترویدهای مسطح

مترویدهای نمایش پذیر

مترویدهای ترنسورسال

تحدید و انقباض

مترویدهای دو بخشی و اویلری

متروید فانو

مترویدها و نظریه گرافها

متروید ها و نظریه ترنسورسال

و...

به همراه اثبات تمام قضیه ها.