دور همیلتونی‌ در گراف پریش

mahanmath · 1390/8/9

فرض کنید

$\pi , \sigma$

۲ جایگشت از اعداد

$\left \{ 1,2,...,n \right \}$

باشند ، میگوئیم جایگشت‌ های

$\pi , \sigma$

نسبت به هم پریش اند اگر در هیچ مولفه یکسان اعداد یکسان نداشته باشند .(

$\pi (k)\neq \sigma (k)$

)
گراف

$G_n$

شامل

$n!$

راس به نمایندگی تمامی‌ جایگشت‌های اعداد

$\left \{ 1,2,...,n \right \}$

است و در آن فقط راس‌هایی‌ که نسبت به هم پریش اند به هم وصلند ،
همه

$n$

هایی را بیابید که

$G_n$

دارای حداقل یک دور همیلتونی‌ (دوری که شامل همه راس ها است) باشد .