گراف نسر

در نظریه گراف گراف نسر (به انگلیسی: Kneser graph)،${\displaystyle KG_{n,k}}$، گرافی است که رأس‌های آن نظیر زیرمجموعه‌های k عضوی از یک مجموعه ی n عضوی است. بین دو رأس یک یال وجود دارد اگر و تنها اگر زیرمجموعه‌های نظیر رأس‌ها ناسازگار باشند (اشتراکشان تهی باشد). این گراف‌ها به نام مارتین نسرر نامگذاری شده‌اند که برای اولین بار آنها را در سال ۱۹۵۵ بررسی کرد.

گراف نسر
گراف ${\displaystyle KG_{5,2}}$ با گراف پترسن ایزومورف است.
Named after	Martin Kneser
راس	${\displaystyle \textstyle {\binom {n}{k}}}$
ضلع	${\displaystyle \textstyle {\binom {n}{k}}{\binom {n-k}{k}}/2}$
رنگ‌آمیزی گراف	${\displaystyle \left\{{\begin{array}{ll}n-2k+2&n\geq 2k\\1&{\text{otherwise}}\end{array}}\right.}$
ویژگی‌های	گراف منتظم arc-transitive
قراردادهای نوشتاری	KGn,k, K(n,k)