ترکیبیات

ترکیبیات

ترکیبیات

ترکیبیات

۱۸آذر


سلام ؛ سلام ؛ خوبید؟ :دی

بعد از مدت ها برگشتم با کلی سوال خوب :دی

سوال برا سال اولی ها :

1)یه گراف دارم ؛ همبنده دور هم نداره :) تعداد یال هاش رو بر حسب راس ها پیدا کن :)

2)ثابت کنید هر تورنمنت شاه داره (تورنمنت : گراف جهتدار کامل ؛ شاه : راسی  که به همه ی راس ها مسیر یک یالی یا دو یالی داره :) )

سوال برا سال دومی ها :

1)یه مسابقه بوده تو "دور"(شهر فامیل و اینا) 200نفر شرکت کننده داره و 6سوال ؛ آقا فامیل میگه که هر سوال رو حداقل 120نفر حل کرده و هیچ دو نفری نیستند که روی هم همه ی سوال ها رو حل کرده باشند ؛ ثابت کنید آقا فامیل با این درد در بند در خواهد ماند!(یعنی ثابت کنید دروغ میگه)

2)فرض کنید n>1 باشد ؛ تعداد جایگشت های nتایی را بیابید که در گرافشون (گراف جایگشت) زوج تا دور دارند.

سوال برا سال سومی ها :

1)دو نفر دارن رو یه گراف دوبخشی بازی میکنن ؛ تو هر مرحله یه نفر یه راس رو میگیره میندازه تو جیبش :دی ؛ تو مرحله بعدی فرد باید یه راس و انتخاب کنه که همسایه باشه با راس قبلی انتخاب شده (بازیکن قبلیش) ؛ شرط لازم و کافی رو این گراف رو پیدا کنید که نفر اول ببیره :))

بعد نوشت : شاید واضح باشه اما تو سوال سومی ها کسی میبازه که نتونه راس برداره :)


رسا دهقانی
۰۸شهریور

1)

nنقطه در صفحه داریم ؛ فاصله ی بین هر دو نقطه از آن حداقل یک است.حداکثر 3nزوج از این نقاط فاصله ای دقیقا برابر 1 دارند.

2)

گراف G را این طور میسازیم:

برای هر جایگشت nتایی یک راس میگیریم و دو راس دو جاییگشتaوb را به هم وصل میکنیم اگر a با یک حرکت به bتبدیل شود.

تعریف یک حرکت :
یک حرکت در یک جایگشت مانند a1,a2,a3,...,an جای دو عضو مانند aiوajرا با هم عوض میکند.

ثابت کنید Gدو بخشی است.

3)

نشان دهید تعداد درخت های باینری (باینری:هر راس داخلی دو فرزند دارد)با nراس داخلی(داخلی:برگ نیست)برابر با n امین عدد کاتالان میباشد.

برای n=3 در زیر نشان داده شده است

رسا دهقانی
۰۷شهریور

یک گراف داریم:

1)مثلث ندارد و nراسی میباشد؛حداکثر چند یال دارد؟

2)دور چهار راسی ندارد و هشت راسی میباشد؛حداکثر چند یال دارد؟

3)دور زوج ندارد و nراسی میباشد؛ حداکثر چند یال دارد؟



رسا دهقانی