مقدمه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 قضیه‌ی منگر                                                                                                                     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