Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۳:گراف:سوال ۷

سوال ۷

فرض کنید G یک گراف دوبخشی باشد به طوری که هر بخش دقیقا n راس داشته باشد و دنباله‌ی درجه‌های راس‌های یک بخش r1,r2,,rn باشد. قضیه‌ برگمن بیان می‌دارد که تعداد تطابق‌های کامل این گراف کم‌تر یا مساوی است با

ni=1(ri!)1ri

(a) شما باید با استفاده از قضیه‌ی برگمن تعمیم زیر را اثبات کنید:

فرض کنید G یک گراف دوبخشی باشد به طوری که بخش X دقیقا m راس و بخش Y دقیقا nm راس داشته باشد. اگر دنباله‌ی درجه‌های راس‌های بخش X‌به صورت r1,r2,,rm باشد، آن‌گاه تعداد تطابق‌های با اندازه‌ی n‌کم‌تر یا مساوی است با:

n!nmn(nm)!ni=1(ri!)1ri

(b) فرض کنید S یک زیرمجموعه از خانه‌های یک مربع n×n باشد به طوری که دقیقا ri خانه در سطر iام و cj خانه در ستون j ام داشته باشد. با استفاده از قضیه‌ای که در قسمت قبل اثبات کردید ثابت کنید: تعداد مربع‌های لاتین جزیی که می‌توان در S قرار داد کم‌تر یا مساوی است با:

(ni=1(n!)nrin1(nri)!)(ni=1ci1j=0(nj)!1(nj)!)


ابزار صفحه