برگه تقلب (Cheat sheet)

هدف این کتاب از آموزش گراف، حفظ کردن تعاریف نیست. هر وقت که تعریفی را یادتان رفت می توانید به این صفحه مراجعه کنید و این کار اصلا معنی تقلب ندارد (عنوان صفحه صرفا یک اصطلاح است)

دقت کنید که این صفحه به منظور آموزش نیست و مطالب به طوری خلاصه شده اند که تنها کسی که قبلا با آن ها آشنا بوده می تواند آن را به خاطر بیاورد. برای آموزش، از درس نامه استفاده کنید

اعداد

  • عدد استقلال یا بزرگترین مجموعه مستقل (آلفا \(\alpha\) ): بیشترین تعداد راسی از گراف که به هم هیچ یالی ندارند.
  • بزرگ ترین تطابق (آلفا پریم \(\alpha^{\prime}\) ): بیشترین تعداد یال از گراف با راس های مجزا.
  • کوچک ترین پوشش راسی (بتا \(\beta\) ): کمترین تعداد راسی از گراف که هر یالی حداقل یک سرش در این راس ها باشد.
  • کوچک ترین پوشش یالی (بتا پریم \(\beta^{\prime}\) ): کمترین تعداد یال از گراف که هر راسی سر حداقل یکی از این یال ها باشد.
  • عدد رنگی (خی \(\chi\) ): کم ترین رنگی که می توان با آن رئوس گراف را رنگ آمیزی کرد به طوری که بین هیچ دو راس هم رنگی یال نباشد.
  • عدد رنگی یالی (خی پریم \(\chi^{\prime}\) ): کم ترین رنگی که می توان با آن یال های گراف را رنگ آمیزی کرد به طوری که هیچ دو یال هم رنگی سر مشترک نداشته باشند.
  • عدد همبندی (کاپا \(\kappa\)) حداقل تعداد رئوسی از گراف که با حذفشان گراف ناهمبند شود.
  • عدد همبندی یالی (کاپا پریم \(\kappa^{\prime}\)) حداقل تعداد یال هایی از گراف که با حذفشان گراف ناهمبند شود.
  • عدد خوشه ای (امگا \(\omega\) ): بیشترین تعداد راسی از گراف که دو به دو به هم یال دارند.
  • کمترین درجه (دلتای کوچک \(\delta\) ): تعداد یال های راسی که کمترین یال را دارد.
  • بیشترین درجه (دلتای بزرگ \(\Delta\) ): تعداد یال های راسی که بیشترین یال را دارد.