سلام. تطابق کامل معمولاً برای گرافهای دو بخشی که تعداد رئوس دو بخش برابره استفاده میشه؛ بطوری که هر راس دقیقاً به یک راس از طرف مقابل متصل بشه. توی این سوالات دو بخش مشخص نشدن. پس فقط به ازای ۲n راس باید تعداد n یال انتخاب کنیم که هر راس دقیقاً با یک راس مجاور باشه. یعنی درجه تمام رئوس ۱ بشه. توی سوال اول دنبال یه رابطه بازگشتی باشید. فکر کنم جواب ۳۴ باشه. سوال دوم هم یه گراف کوچیکه که اگه تقارن رو روش درنظر بگیرید جواب سریع بدست میاد. فکر کنم ۹ بشه.

(۱۷ مرداد ۱۳۹۲ ۰۴:۱۱ ب.ظ)Jooybari نوشته شده توسط:  سلام. تطابق کامل معمولاً برای گرافهای دو بخشی که تعداد رئوس دو بخش برابره استفاده میشه؛ بطوری که هر راس دقیقاً به یک راس از طرف مقابل متصل بشه. توی این سوالات دو بخش مشخص نشدن. پس فقط به ازای ۲n راس باید تعداد n یال انتخاب کنیم که هر راس دقیقاً با یک راس مجاور باشه. یعنی درجه تمام رئوس ۱ بشه. توی سوال اول دنبال یه رابطه بازگشتی باشید. فکر کنم جواب ۳۴ باشه. سوال دوم هم یه گراف کوچیکه که اگه تقارن رو روش درنظر بگیرید جواب سریع بدست میاد. فکر کنم ۹ بشه.

ممکنه لطفا راه حل این دو سوال را بگذارید

برای سوال اول جواب رو a8 درنظر بگیرید. یعنی جمله هشتم دنباله. قراره به یه شکل برسیم که درجه تمام رئوس ۱ باشه. راس بالایی سمت راست (شماره ۸ بالایی) میتونه به یکی از ۲ تا راس وصل بمونه. یعنی راس پایینی و راس سمت چپی (شماره ۷ بالایی). اگه به راس پایینی وصل باشه تعداد حالات برابر با a7 میشه. از روی شکل مشخصه. کافیه دو راس سمت راست رو از رئوس سمت چپ جداکنیم و تعداد حالات تطابق کامل سمت چپ رو حساب کنیم که برابر با a7 میشه.
اگه قرار باشه راس بالا سمت راست؛ راس سمت چپیش رو انتخاب کنه برای ایجاد تطابق کامل؛ راس پایین سمت راست هم باید راس سمت چپیش رو انتخاب کنه و این ۴ راس از ۱۲ راس دیگه جدا بشن. تعداد حالات برای این وضعیت برابر a میشه. پس رابطه بازگشتی میشه $a_n=a_{n-1} a_{n-2};n\geq 3$ و a1=1 و a2=2 که دنبالش مشابه فیبوناچی میشه. جمله هشتم برابر ۳۴ میشه.

سوال دوم هم هر راس سه راس برای انتخاب داریم. راس بالایی سمت راست شکل رو درنظر میگیرم. میتونه با راس مقابل، سمت چپی و یا پایینی وصل بشه. تعداد هرکدوم از این حالات باتوجه به تقارنشون برابره. پس کافیه تعداد یکیشونو حساب کرده و در ۳ ضرب کنیم. میتونید هرسه رو جداگانه محاسبه کنید و به جواب مشابه برسید. من حالتی که با راس مقابلش مجاوره رو درنظر میگیرم. ۶ راس باقی مونده باید با ۳ یال طوری بهم وصل بشن که درجه همشون ۱ بشه. ۳ حالت داریم: حالتی که هرسه یال موازی با یال اول باشن. حالتی که یال پایینی (سمت راست) موازی با یال اول و دو یال سمت چپ انتخابی هم عمودی باشن. و حالتی که یال بالایی (سمت چپ) موازی و دو یال پایینی افقی باشن. پس کل حالات میشه ۹ حالت.