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

نظریه گراف در قرن بیستم شاهد پیشرفت بی‌سابقه‌ای بوده است. یکی از بزرگترین دلایل این رشد قابلیت کاربردی نظریه گراف در بسیاری رشته‌ها مثل فیزیک، شیمی، روانشناسی و جامعه‌شناسی است. دلیل دیگر این است که مسائل علوم نظری کامپیوتر که با پیچیدگی محاسبه سروکار دارند را می‌توان به مسائل نظریه گراف تبدیل کرد.

هدف این کتاب، قضیه دیراک درباره گراف‌های K- همبند، قضیه هراری – ناش ویلیامز درباره همیلتونی بودن گراف‌های یالی، مشخصه‌سازی تویدا – مک‌کی از گراف‌های اویلری و ماتریس توته یک گراف را بررسی می‌کند و به اثبات فورنیر از قضیه کوراتسکی درباره گراف‌های مسطح، اثبات ناهمیلتونی بودن گراف توته روی ۶۴ رأس و یک کاربرد عملی از گراف‌های مثلثی شده می‌پردازد.

در این کتاب مراجع، نمایه و واژه‌نامه، فهرست نمادها و فهرست اسامی را نیز ارائه داده است.

این کتاب در ۲۹۹ صفحه و به‌قیمت ۲۹ هزار ریال برای دوره‌های کارشناسی و کارشناسی ارشد مورد استفاده است.

مقدمه................................................................................................................. ۱

۱- نتایج اساسی................................................................................................... ۱

۱,۰ مقدمه............................................................................................................ ۱

۱,۱ مفاهیم اساسی.............................................................................................. ۲

۱,۲ زیرگراف‌ها....................................................................................................... ۹

۱,۳ درجه‌ی رأس‌ها................................................................................................. ۱۱

۱,۴ مسیرها و همبندی........................................................................................... ۱۴

۱,۵ خودریختی گراف ساده....................................................................................... ۲۰

۱,۶ گراف‌های یالی................................................................................................. ۲۳

۱,۷ اعمال روی گراف‌ها............................................................................................ ۲۹

۱,۸ کاربردی در شیمی............................................................................................ ۳۵

۱,۹ تمرین‌های تکمیلی........................................................................................... ۳۶

۲- گراف‌های جهت‌دار.............................................................................................. ۳۹

۲,۰ مقدمه............................................................................................................ ۳۹

۲,۱ مفاهیم اساسی.............................................................................................. ۳۹

۲,۲ تورنمنت‌ها...................................................................................................... ۴۲

۲,۳ تورنمنت‌های k- بخشی..................................................................................... ۴۵

۳ – همبندی......................................................................................................... ۵۳

۳,۰ مقدمه............................................................................................................ ۵۳

۳,۱ رأس‌های برشی و یال‌های برشی........................................................................ ۵۴

۳,۲ همبندی و همبندی یالی................................................................................... ۵۸

۳,۳ بلوک‌ها.......................................................................................................... ۶۵

۳,۴ همبندی یالی دوری یک گراف.............................................................................. ۶۸

۳,۵ قضیه‌ی منگر.................................................................................................... ۶۸

۳,۶ چند تمرین...................................................................................................... ۷۹

۴ – درخت‌ها......................................................................................................... ۸۱

۴,۰ مقدمه............................................................................................................ ۸۱

۴,۱ تعریف، مشخصه‌سازی، و خواص ساده................................................................. ۸۱

۴,۲ مرکزها و مرکز ثقل‌ها......................................................................................... ۸۷

۴,۳ شمارش تعداد درخت‌های فرگیر........................................................................... ۹۱

۴,۴ فرمول کیلی.................................................................................................... ۹۴

۴,۵ خاصیت هلی................................................................................................... ۹۷

۵ – مجموعه‌های مستقل و جورسازی‌ها.................................................................... ۱۰۱

۵,۰ مقدمه............................................................................................................ ۱۰۱

۵,۱ مجموعه‌های مستقل راسی و پوشش‌ها راسی.................................................... ۱۰۱

۵,۲ مجموعه‌های مستقل یالی................................................................................ ۱۰۳

۵,۳ جورسازی‌ها و عامل‌ها...................................................................................... ۱۰۵

۵,۴ جورسازی در گراف‌های دوبخشی........................................................................ ۱۰۹

۵,۵ جورسازی‌های کامل و ماتریس توته...................................................................... ۱۲۰

۶ – گراف‌های اویلری و همیلتونی.............................................................................. ۱۲۳

۶,۰ مقدمه............................................................................................................ ۱۲۳

۶,۱ گراف‌های اویلری............................................................................................... ۱۲۳

۶,۲ گراف‌های همیلتونی......................................................................................... ۱۲۹

۶,۳ گراف‌های حامی دور.......................................................................................... ۱۳۹

۶,۴ دورهای همیلتونی در گراف‌های یالی................................................................... ۱۴۲

۶,۵ گراف‌های ۲- تجزیه‌پذیر....................................................................................... ۱۵۰

۶,۶ چند تمرین...................................................................................................... ۱۵۱

۷- رنگ‌آمیزی گراف‌ها.............................................................................................. ۱۵۵

۷,۰ مقدمه............................................................................................................ ۱۵۵

۷,۱ رنگ‌آمیزی راسی.............................................................................................. ۱۵۵

۷,۲ گراف‌های بحرانی.............................................................................................. ۱۵۹

۷,۳ گراف‌های آزاد – مثلث........................................................................................ ۱۶۵

۷,۴ رنگ‌آمیزی یالی گراف‌ها..................................................................................... ۱۶۷

۷,۵ اسنارک.......................................................................................................... ۱۷۵

۷,۶ مسأله‌ی دختران مدرسه‌ای کرکمن...................................................................... ۱۷۶

۷,۷ چندجمله‌ای‌های رنگی...................................................................................... ۱۷۹

۸ – تسطیح‌پذیری.................................................................................................. ۱۸۳

۸,۰ مقدمه............................................................................................................ ۱۸۳

۸,۱ گراف‌های مسطح و نامسطح.............................................................................. ۱۸۳

۸,۲ فرمول اویلر و نتایج آن........................................................................................ ۱۸۹

۸,۳ k۵ و K۳,۳ گراف‌های نامسطح هستند................................................................... ۱۹۴

۸,۴ دوگان یک گراف مسطح شده.............................................................................. ۱۹۶

۸,۵ قضیه‌ی چهار رنگ و قضیه‌ی پنج رنگ هیوود............................................................ ۲۰۰

۸,۶ قضیه‌ی کوراتسکی........................................................................................... ۲۰۳

۸,۷ گراف‌های مسطح شده‌ی همیلتونی.................................................................... ۲۱۲

۸,۸ رنگ‌آمیزی تایت................................................................................................ ۲۱۴

۹ – گراف‌های مثلثی شده....................................................................................... ۲۲۱

۹,۰ مقدمه............................................................................................................ ۲۲۱

۹,۱ گراف‌های تام................................................................................................... ۲۲۱

۹,۲ گراف‌های مثلثی شده....................................................................................... ۲۲۳

۹,۳ گراف‌های فاصله‌ای............................................................................................ ۲۲۷

۹,۴ گراف‌های دوبخشی (G)B از یک گراف Gو............................................................... ۲۳۰

۹,۵ گراف‌های کمان دایره‌ای...................................................................................... ۲۳۱

۹,۶ چند تمرین...................................................................................................... ۲۳۱

۹,۷ زمان‌بندی چراغ‌های راهنمایی در یک تقاطع.......................................................... ۲۳۳

۱۰ – کاربردها........................................................................................................ ۲۳۹

۱۰,۰ مقدمه.......................................................................................................... ۲۳۹

۱۰,۱ مسأله‌ی اتصال............................................................................................... ۲۳۹

۱۰,۲ الگوریتم کروسکال........................................................................................... ۲۴۰

۱۰,۳ الگوریتم پریم................................................................................................. ۲۴۲

۱۰,۴ مسأله‌ی کوتاه‌ترین مسیر................................................................................. ۲۴۳

۱۰,۵ مسأله‌ی زمان‌بندی......................................................................................... ۲۴۶

۱۰,۶ کاربرد در روانشناسی اجتماعی ....................................................................... ۲۴۹

۱۰,۷ چند تمرین..................................................................................................... ۲۵۲

مراجع.................................................................................................................. ۲۵۳

نمایه و واژه‌نامه...................................................................................................... ۲۶۷

فهرست نمادها...................................................................................................... ۲۸۵

فهرست اسامی.................................................................................................... ۲۸۹