سوال؟

[s.h]

- فرض کنید یال e به تعداد دفعات فرد در یک گشت بسته آمده باشد و T یک گذر بسته نباشد . ثابت کنید که w شامل یک دور فرد است .
2- فرض کنید که T گذر ماکسیمالی در یک گراف باشد و T گذر بسته نباشد . ثابت کنید که نقاط پایانی T دارای درجه فرد اند .
3- ثابت کنید که یک گراف جهتدار متناهی دارای یک دور جهتدار است اگر هر راس حداقل یک یال به خارج داشته باشد .
4- فرض کنید G یک گراف ساده همبند است که هیچ زیرگراف القایی 4 راسی ندارد که یک مسیر یا یک دور باشد . ثابت کنید که G راسی دارد که با همه راسهای دیگر مجاور باشد . (راسی که درجه آن N-1 است ) (از اکسترمال استفاده کنید)
5- آیا درست است که یک گراف با دقیقا دو راس از درجه فرد باید شامل مسیری از یکی از آنها به دیگری باشد ؟ اثبات یا یک مثال نقض ارائه دهید .
6- در کلاسی با 9 دانشجو ، هر دانشجو برای 3 نفر دیگر کارت تبریک میفرستد . آیا ممکن است که هر دانشجو کارتهایی از همان سه دانشجویی که برایشان کارت فرستاده دریافت کند
7- ثابت کنید گراف G همبند است اگر و فقط اگر هر یال آن برشی باشد .
8- ثابت کنید گراف G همبند است اگر و فقط اگر با اضافه کردن هر یال به گراف، گراف شامل دور شود

لطفا اینها را حل کنید البته بعضیاش را نمی خواهد مثل 3 و2و8

 

[hc3]

پاسخ : سوال؟؟

rastesh man az in chiza sar dar namiyaram

 

[mehrdad-t]

پاسخ : سوال؟

۷ اشتباه هستش!!!
یه گراف کامل ۳ راسی , همبند هست ولی یال برشی نداره

 

[mehrdad-t]

پاسخ : سوال؟

سوال ۶!!
خیر!!!
اگرشما به هر کسی کارت بدهی,یه کارت ازش بگیری و این رابطه بده بستان(!) را یک یال بین این ۹ نفر در نظر بگیری!اون وقت ۹ راس داری با درجه ۳!!
که چنین چیزی مهال است
زیرا مجموع درجات فرد میشود

 

[mehrdad-t]

پاسخ : سوال؟

سوال ۵
از یکی‌ از راس‌ها با درجهٔ فرد(v۰) شروع کن،و به راس مجورش برو(چون درجه فرد دارد حتما یک همسایه مانند v۱ دارد)

اگر این راس(v۱) راس دیگر با درجه فرد بود که مساله حل شده

اگر نه به یکی‌ از همسایه‌های v۱ می‌رویم،فقط مواظب هستیم که از یال‌های تکراری به راس‌های دیگر نرویم(چون درجه و۱ زوج است حتما یک همسایه دیگر جز v۰, مانند v۲ دارد)

حل این روند را برای v۲,/v۳,... ادامه میدهیم!!چون تعداد یال‌های گراف متناهیست پس این عمل به زودی متوقف میشود،و دیگر نمی‌توان از راسی که در آن قرار داریم با یال غیر تکراری به راس مجاور آن برویم

راسی را که در آن متوقف شده ایم را Vf مینامیم!ادعا می‌کنیم Vf راسی با درجهٔ فرد است!چون از همهٔ یال‌های Vf قبلان گذر کرده ایم (در غیر این صورت در Vf متوقف نمی‌شدیم و از یال‌های باقی‌ مانده از آن بیرون می‌رفتیم)،پس مجموع تعداد ورود‌ها و تعداد خروج‌ها به Vf برابر درجه آن است!!!از طرفی‌ میدانیم Vf به ازای هر ورود به Vf, بلافاصله ،یک خروج از Vf داشته ایم،به جز ورود آخری که خروجی نداشته!!!

پس جمع تعداد ورود و خورج‌ها برای Vf فرد تاست!!!از طرفی‌ Vf همان V۰ نیست،چون V۰ در مرحلهٔ اول،یک خروج بدون ورود دارد(در ابتدا در V۰ قرار داریم) پس اگر Vf همان V۰ باشد،با توجه به ورود آخری که بدون خروج است،و خروج اولی‌ که بدون ورود است،درجهٔ V۰ زوج میشود،و این خلاف فرد بودن درجهٔ V۰ است!!

با این عمل یک گذر بین ۲ راس با درجهٔ فرد(v۰ و Vf که درجهٔ فرد داشتند) پیدا کردیم،پس از روی آن می‌شه یه مسیر بین آنها پیدا کرد