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

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

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

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

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

مقدمه................................................................................................................. 1

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

1.0 مقدمه............................................................................................................ 1

1.1 مفاهیم اساسی.............................................................................................. 2

1.2 زیرگراف‌ها....................................................................................................... 9

1.3 درجه‌ی رأس‌ها................................................................................................. 11

1.4 مسیرها و همبندی........................................................................................... 14

1.5 خودریختی گراف ساده....................................................................................... 20

1.6 گراف‌های یالی................................................................................................. 23

1.7 اعمال روی گراف‌ها............................................................................................ 29

1.8 کاربردی در شیمی............................................................................................ 35

1.9 تمرین‌های تکمیلی........................................................................................... 36

2- گراف‌های جهت‌دار.............................................................................................. 39

2.0 مقدمه............................................................................................................ 39

2.1 مفاهیم اساسی.............................................................................................. 39

2.2 تورنمنت‌ها...................................................................................................... 42

2.3 تورنمنت‌های k- بخشی..................................................................................... 45

3 – همبندی......................................................................................................... 53

3.0 مقدمه............................................................................................................ 53

3.1 رأس‌های برشی و یال‌های برشی........................................................................ 54

3.2 همبندی و همبندی یالی................................................................................... 58

3.3 بلوک‌ها.......................................................................................................... 65

3.4 همبندی یالی دوری یک گراف.............................................................................. 68

3.5 قضیه‌ی منگر.................................................................................................... 68

3.6 چند تمرین...................................................................................................... 79

4 – درخت‌ها......................................................................................................... 81

4.0 مقدمه............................................................................................................ 81

4.1 تعریف، مشخصه‌سازی، و خواص ساده................................................................. 81

4.2 مرکزها و مرکز ثقل‌ها......................................................................................... 87

4.3 شمارش تعداد درخت‌های فرگیر........................................................................... 91

4.4 فرمول کیلی.................................................................................................... 94

4.5 خاصیت هلی................................................................................................... 97

5 – مجموعه‌های مستقل و جورسازی‌ها.................................................................... 101

5.0 مقدمه............................................................................................................ 101

5.1 مجموعه‌های مستقل راسی و پوشش‌ها راسی.................................................... 101

5.2 مجموعه‌های مستقل یالی................................................................................ 103

5.3 جورسازی‌ها و عامل‌ها...................................................................................... 105

5.4 جورسازی در گراف‌های دوبخشی........................................................................ 109

5.5 جورسازی‌های کامل و ماتریس توته...................................................................... 120

6 – گراف‌های اویلری و همیلتونی.............................................................................. 123

6.0 مقدمه............................................................................................................ 123

6.1 گراف‌های اویلری............................................................................................... 123

6.2 گراف‌های همیلتونی......................................................................................... 129

6.3 گراف‌های حامی دور.......................................................................................... 139

6.4 دورهای همیلتونی در گراف‌های یالی................................................................... 142

6.5 گراف‌های 2- تجزیه‌پذیر....................................................................................... 150

6.6 چند تمرین...................................................................................................... 151

7- رنگ‌آمیزی گراف‌ها.............................................................................................. 155

7.0 مقدمه............................................................................................................ 155

7.1 رنگ‌آمیزی راسی.............................................................................................. 155

7.2 گراف‌های بحرانی.............................................................................................. 159

7.3 گراف‌های آزاد – مثلث........................................................................................ 165

7.4 رنگ‌آمیزی یالی گراف‌ها..................................................................................... 167

7.5 اسنارک.......................................................................................................... 175

7.6 مسأله‌ی دختران مدرسه‌ای کرکمن...................................................................... 176

7.7 چندجمله‌ای‌های رنگی...................................................................................... 179

8 – تسطیح‌پذیری.................................................................................................. 183

8.0 مقدمه............................................................................................................ 183

8.1 گراف‌های مسطح و نامسطح.............................................................................. 183

8.2 فرمول اویلر و نتایج آن........................................................................................ 189

8.3 k5 و K3,3 گراف‌های نامسطح هستند................................................................... 194

8.4 دوگان یک گراف مسطح شده.............................................................................. 196

8.5 قضیه‌ی چهار رنگ و قضیه‌ی پنج رنگ هیوود............................................................ 200

8.6 قضیه‌ی کوراتسکی........................................................................................... 203

8.7 گراف‌های مسطح شده‌ی همیلتونی.................................................................... 212

8.8 رنگ‌آمیزی تایت................................................................................................ 214

9 – گراف‌های مثلثی شده....................................................................................... 221

9.0 مقدمه............................................................................................................ 221

9.1 گراف‌های تام................................................................................................... 221

9.2 گراف‌های مثلثی شده....................................................................................... 223

9.3 گراف‌های فاصله‌ای............................................................................................ 227

9.4 گراف‌های دوبخشی (G)B از یک گراف Gو............................................................... 230

9.5 گراف‌های کمان دایره‌ای...................................................................................... 231

9.6 چند تمرین...................................................................................................... 231

9.7 زمان‌بندی چراغ‌های راهنمایی در یک تقاطع.......................................................... 233

10 – کاربردها........................................................................................................ 239

10.0 مقدمه.......................................................................................................... 239

10.1 مسأله‌ی اتصال............................................................................................... 239

10.2 الگوریتم کروسکال........................................................................................... 240

10.3 الگوریتم پریم................................................................................................. 242

10.4 مسأله‌ی کوتاه‌ترین مسیر................................................................................. 243

10.5 مسأله‌ی زمان‌بندی......................................................................................... 246

10.6 کاربرد در روانشناسی اجتماعی ....................................................................... 249

10.7 چند تمرین..................................................................................................... 252

مراجع.................................................................................................................. 253

نمایه و واژه‌نامه...................................................................................................... 267

فهرست نمادها...................................................................................................... 285

فهرست اسامی.................................................................................................... 289