نام کاربری و رمز عبور شما، شماره موبایل ارائه شده در زمان ثبت‌نام به همراه “0” اول شماره است.
لینک جلسات
تکالیف هفتهٔ اول
از راه‌حل‌های تشریحی خود عکس بگیرید و آنها را در بخش کامنت‌های همین صفحه آپلود کنید.
دانلود کتاب آشنایی با نظریه گراف
- یال‌های گراف کامل \(n\)رأسی رنگ شده‌اند به‌طوری که در هر مثلث حداقل دو یال همرنگ وجود دارد. حداکثر چند رنگ مختلف در این رنگ‌آمیزی به‌کار رفته است؟
- در یک گراف از مرتبهٔ \(n > 5\) در بین هر \(5\) رأس، رأسی وجود دارد که با \(4\) رأس دیگر مجاور است. به‌ازای چه \(n\)هایی می‌توان نتیجه گرفت رأسی از درجه \(n-1\) وجود دارد؟
- در یک گراف، درجهٔ یک رأس برابر \(50\) و درجهٔ بقیهٔ رئوس برابر \(100\) است. آیا ممکن است در این گراف هر سه رأس دقیقاً سه همسایه مشترک داشته باشند؟
- در گراف \(G\) از مرتبهٔ \(100\)، رأس تنها وجود ندارد و در بین هر \(4\) رأس، رأسی مجاور با حداقل دو رأس دیگر وجود دارد. ثابت کنید قطر \(G\) از \(3\) بیشتر نیست.
- فرض کنید \(G\) گرافی \(14\)-منتظم از مرتبه \(20\) باشد و \(G\) خوشه‌ای از مرتبهٔ \(10\) داشته باشد. ثابت کنید رأس‌های \(G\) را می‌توان به دو خوشه افراز کرد.
- در یک گراف از مرتبه \(30\) هر دو رأس حداقل دو همسایه مشترک دارند. ثابت کنید در این گراف رأسی از درجه حداقل \(9\) وجود دارد.
- در یک گراف از مرتبهٔ \(n\) هر زیرگراف القایی از مرتبه \(4\) مثلث دارد. ثابت کنید این گراف خوشه‌ای از مرتبه \(n-1\) دارد.
- یال‌های گراف کامل از مرتبه \(n\) آبی و قرمز شده‌اند. هر رأس از این گراف هم یال آبی دارد و هم یال قرمز. ثابت کنید \(4\) رأس \(a\)، \(b\)، \(c\)، و \(d\) وجود دارد به‌طوری که یال‌های \(ab\) و \(cd\) آبی باشند و یال‌های \(bc\) و \(da\) قرمز باشند.
- در گراف \(G\) از مرتبه \(90\) درجه هر رأس حداقل \(10\) است. ثابت کنید \(G\) دوری به طول \(4\) دارد.
- در گراف \(G\) از مرتبه \(n\)، درجه هیچ رأسی از \(11\) بیشتر نیست. ثابت کنید رأس‌های \(G\) را می‌توان با \(4\) رنگ، رنگ کرد به‌طوری که تعداد یال‌هایی از \(G\) که دو سر آنها همرنگ‌اند از \(n\) بیشتر نباشد.
