خوب، چند تا سوال دیگهی گسسته که من جواب دادم.
۷۵- کدام یک از گزینههای زیر صحیح است؟
۱) گرافی همبند با دنباله درجات (۳٫۳٫۳٫۲٫۱٫۱٫۱٫۱٫۱) موجود نمیباشد.
۲) گرافی غیرهمبند با دنباله درجات (۴٫۴٫۴٫۴٫۴٫۳٫۳٫۳٫۳) موجود نمیباشد.
۳) گرافی دوبخشی با دنباله درجات (۷٫۶٫۳٫۳٫۳٫۳٫۳٫۳٫۳) موجود نمیباشد.
۴) گرافی با دنباله درجات (۶٫۶٫۳٫۳٫۳٫۳٫۳) موجود میباشد.
من این رو گزینهی ۳ زدم. ولی حتی حال ندارم دوباره بررسی بکنمش. فقط اینکه آخری غلطه چون تعداد فرد رئوس با درجه فرد داره و برای گزینهی ۲ میشه از رابطهی [tex]\binom{n-1}{2}[/tex] که حداکثر تعداد یالهای ممکن در یک گراف ناهمبند رو مشخص میکنه استفاده کرد. گزینهی ۱ رو هم میشه به صورت همبند رسم کرد، من رسم کردم!
۷۶- فرض کنید G یک گراف بوده که روی یالهای آن اعداد صحیح گذاشتهایم به طوری که در هر راس مجموع مقادیر یالهای متصل به آن راس، برابر ۱ است. کدام گزینه صحیح است؟
۱) G دوبخشی است.
۲) تعداد رئوس G زوج است.
۳) تعداد رئوس G فرد است.
۴) G دارای تطابق کامل است.
یه چیزی شبیه این سوال رو تو کنکور دکترای علوم کامپیوتر امسال داده بودند که میخواست با ۱ و ۱- به یالها مقدار بدیم تا مجموع مقادیر یالهای متصل به هر راس ۱ بشود. من از همون تست یادم بود که گراف کامل [tex]K_4[/tex] این خاصیت رو داره و برای همین بلافاصه گزینه ۱ و ۳ رو حذف کردم. ولی الان هرچی فکر میکنم یادم نمیاد که بین ۲ و ۴ کدوم رو زدم
۷۷- فرض کنید G یک گراف n راسی بوده و A ماتریس مجاورت G باشد. اگر n تا درایه ۱ در A انتخاب کنیم که هیچ دوتایی در یک سطر و یک ستون مشترک نباشند، در این صورت این n تا ۱ در گراف متناظر با چیست؟
۱) یک تطابق کامل
۲) دوری همیلتونی
۳) اجتماعی از دورهای مجزا که رئوس را میپوشانند.
۴) یک زیرگراف فراگیر که هر مولفه همبندی اش دور یا مسیر یا دو راسی است.
من این رو هم زدم گزینهی ۳ (اجتماعی از دورهای مجزا).