گسترش، برش تنک، و نظریه طیفی گراف (پاییز ۹۵-۹۶)

توصیف درس: گسترش، برش تنک، و نظریه طیفی گراف

Islamic Diagram Pattern new

فرض کنید می‌خواهیم یک سری نامتناهی از گراف‌های G1, G2, … داشته باشیم که با اینکه درجه راس‌هایشان کم است، اما هم‌بندی بالایی دارند. مثلا فرض کنید می‌خواهیم درجهٔ راس‌ها عددی ثابت باشد، مثلا در Gn با اینکه nامین این گراف‌هاست و n عددی ثابت نیست، اما درجهٔ همهٔ این گراف‌ها یک عدد ثابت باشد. از طرفی دوست داریم مثلا گراف‌مان برش کمینه‌اش بزرگ باشد، یعنی این‌طوری نباشد که گراف قطعاتی داشته باشد که به دور از قطعات دیگر است. این گراف‌ها را گسترگراف می‌نامند.

بنابر تعبیر دیگری، گسترگراف‌ها گراف‌هایی هستند که هر مجموعهٔ نه خیلی بزرگی که از راس‌هایشان را بگیریم، همسایه‌های آن راس‌ها تقریبا همگی متفاوت هستند. مثلا در جامعه‌ای که روابط دوستی در آن به صورت گسترگراف باشد هر مجموعهٔ نه‌چندان‌بزرگی از افراد، تقریبا هیچ دوست مشترکی ندارند.

از طرف دیگر، یافتن برش تنک در گراف به معنای یافتن قسمت‌هایی از گراف است که شبیه گسترگراف‌ها نیستند. در این درس تلاش می‌کنیم با استفاده از نظریهٔ طیقی گراف به دنبال برش‌های تنک در گراف بگردیم. در طی این سفر، به گسترگراف‌ها هم سری می‌زنیم و روند تولید آن‌ها را مرور می‌کنیم.

برنامه کلاس‌ها

مباحث درس به صورت زیر است:

  1. مقدماتی در مورد نظریه جبری گراف‌ها
  2. تعریف‌های مربوط به مقدارهای ویژه و گسترشدر مورد مقادیر ویژهٔ ماتریس مجاورت گراف‌ها و ارتباط آن با خواص گراف صحبت می‌کنیم.
  3. ارتباط برش و گسترش گراف گسترش گراف یعنی تعداد همسایه‌های یک مجموعه از راس‌ها.
  4. روش توان یک الگوریتم جالب و بسیار شهودی برای یافتن مقدار و بردارهای ویژه بزرگ
  5. مقدارهای ویژه گراف‌های کایلی گراف‌های کایلی مثال‌های خوبی هستند برای تولید گسترگراف‌ها
  6. ساختن گسترگراف‌ها با اینکه گسترگراف‌ها گراف‌های جذابی بودند، اما تولید آن‌ها کار راحتی نبود. در این قسمت یک روش ساده برای تولید آن‌ها ارائه می‌کنیم.
  7. خواص گسترگراف‌ها و کاربردهای آن‌ها
  8. مسئله برش تنک غیریکنواختیک مسئلهٔ دیگر که با گسترگراف‌ها حل می‌شود.
  9. ارائه‌ها در این درس از دانش‌جویان انتظار می‌رود هر کدام پروژه‌ای داشته باشند و در قالب پروژه یک مبحث مربوط به گسترگراف‌ها را مطالعه کنند، ارائه‌ای انجام بدهند و متنی در مورد پروژهٔ خود تحویل بدهند.

کلا در این کلاس تلاش می‌کنیم به همراه اثبات‌ها همیشه نگاه شهودی‌مان به مطلب را حفظ کنیم.

پیش‌نیاز

آشنایی با الگوریتم‌ها، مباحث اولیه پیچیدگی محاسبات، و گراف برای این درس ضروری است.

منابع پیشنهادی

منبع اصلی: جزوهٔ درسی که برنامهٔ این درس خواهد بود به این آدرس. جزوهٔ دیگری نیز از یک کارگاهی که توسط آقای ترویسان ارائه شده موجود است که کمی با جزوهٔ قبلی متفاوت است.

منبع فرعی: درس نظریهٔ جبری گراف: درس آقای اسپیلمن در پاییز ۲۰۱۲ در مورد نظریهٔ جبری گراف خیلی نزدیک به مباحث این درس است.

کتابچه‌ای توسط آقای لواز در مورد مقدارهای ویژه.

کتاب نظریهٔ جبری گراف.

منبعی خوب برای مباحث جدیدتر: ارائه‌های موسسه سیمونز در برنامهٔ نظریهٔ طیفی گراف الگوریتمی. (با تشکر از خانم آقامولایی)

منابع پیشنهادی برای پروژه

  • مقاله آقایان لی، اویس‌قرن، و ترویسان. پیوند.
  • برنامهٔ نظریه طیفی گراف الگوریتمی از موسسه سیمونز. این برنامه شامل ۵ کارگاه است: ۱) مقدمه‌ای بر نظریه طیفی گراف، ۲) بهینه‌سازی نیمه معین و کاربردها، ۳) الگوریتم‌های طیفی: از نظر تا عمل، ۴) الگوریتم‌های سریع به وسیله روش‌های طیفی، ۵) بازنگری الگوریتم‌های طیفی گراف
  • ظاهرا فیلم‌های مختلف کارگاه‌های سیمونز در این پیوند در سایت دانشگاه هست (با تشکر از خانم آقاملایی).
  • نسخهٔ دیگری از درس آقای ترویسان هست که شامل مباحث پیشرفته‌تری نیز می‌شود مانند الگوریتم و روش گرد کردن ARV، الگوریتم تقریب سریع معادلهٔ لاپلاسین.
  • درس آقای اسپیل‌من نیز شامل مباحث جالبی است که قرار نیست در درس ارائه شود مانند: الگوریتم تقریب سریع معادلهٔ لاپلاسین، قدم‌زدن تصادفی و ربط آن به مقدارهای ویژه، تولید اعداد تصادفی توسط گسترگراف‌ها، محاسبهٔ سریع مقاوت معادل بین همهٔ راس‌ها، گراف‌های رامانویان و کاربردهای آن در اینجا، تنک‌سازی گراف.
  • درس آقای میلر نیز شامل برخی از مباحث بالاست و هم‌چنین در مورد تولید زیردرخت تصادفی
  • درس خانم کولا هم مانند درس‌های قبلی است.
  • درس آقای امین صابری نیز شامل همان مباحث و هم‌چنین الگوریتم‌های تقریبی جدیدی که ایشان به همراه آقای شایان اویس‌قرن برای مسئلهٔ فروشندهٔ دوره‌گرد ارائه کردند و راه حل‌شان برای مسئلهٔ کدیسون-سینگر را نیز شامل می‌شود. درس آقای اویس‌قرن نیز در همین موضوع‌هاست اما کمی مفصل‌تر.
  • درس آقای لپ چی لائو مانند درس‌های قبلی است کمی تمرکزش روی قدم‌زدن تصادفی بیشتر است و الگوریتم تقریبی برای شار بیشینه با روش به‌روزرسانی ضربی وزن‌ها را نیز شامل می‌شود.
  • بیست پروژه‌های پیشنهادی آقای ترویسان

جلسات درس

جلسه فصل از جزوه موضوع جزوه
۱ - معرفی درس جزوه ندارد
۲ ۱ تعریف تنکی برش و گسترش گراف جزوه تعاریف و جبرخطی
۳ ۱ جبر خطی و بردارهای ویژه جزوه تعاریف و جبرخطی
۴و ابتدای ۵ ۲ نامساوی چیگر جزوه نامساوی چیگر توسط خانم آقا ملایی
۵ ۳ رابطه مقدارویژه‌های دیگر و برش‌ها جزوه دیگر برش‌ها توسط خانم آقا ملایی
۶و۷ ۴ روش توان برای محاسبه‌ٔ سریع بردار ویژه دوم جزوه روش توان توسط آقای حاجی‌شفیعی‌ها (البته باید تایپ شود تا نهایی شود)
۸و۹و۱۰ ۵ گراف کایلی
۱۱و۱۲و۱۳ ۶ ساختن گسترگراف جزوه اول ساختن گسترگراف‌ها توسط خانم مرادی
۱۴ ۷ خواص گسترگراف‌ها
۱۵و۱۶و۱۷ ۸ مسئلهٔ برش تنک غیریکنواخت

جزوه‌نویسی
قالب برای جزوه‌ها. لطفا جزوه‌ها را به صورت خوبی توسط زیپرشین بنویسید. تمیز جزوه نوشتن و تمیز نوشتن آن به زبان تک نیز کار خیلی خوب و پسندیده‌ای است.

تمرین‌های درس

تمرین اول، در مورد لاپلاسین و محاسبهٔ لاپلاسین برای برخی گراف‌ها و در مورد نامساوی کوران-فیشر و مقدار رایلی. فقط در مورد این‌که هر کدام از مسئله‌ها در مورد خود لاپلاسین هستند یا در مورد لاپلاسین نرمال شده مطمئن نیستم. سعی کردم درست‌شان کنم، ولی ممکن است از زیر دستم در رفته باشد.

تمرین دوم در مورد روش توان.

فصل پنجم کتاب خودش تمرین‌های خوبی دارد.

موضوع ارائه‌ها

دانشجو موضوع منبع زمان
خانم فلکی موجک‌ها برروی گراف با یادگیری عمیق ۱ ۱۶ أذر
آقای سقایی ؟ ؟ ۲۱ آذر
آقای رحیمی اشتراک‌گذاری رمز با استفاده از گسترگراف‌ها ۱ ۲۱ آذر
آقای جیرآبادی قدم‌زدن تصادفی روی گسترگراف‌ها ۱ ۲۳ آذر
آقای کابلی حل معادلهٔ لاپلاسین ۱ ۲ ۳ ۴ ۲۳ آذر
خانم آقا ملایی قدم‌زدن تصادفی و مجموعه‌های تکاملی، هم‌گرایی سریع‌تر و محدودیت‌ها ۱ ۲۸ آذر
آقای بهنام‌نیا تنک‌سازی ۱ ۳۰ آذر
خانم محبی خوشه‌بندی گراف نیمه‌دیده‌شده ۱ ۳۰ آذر
خانم مرادی ؟ ؟ ۵ دی
آقای حاجی شفیعی‌ها کدهای تصحیح‌کنندهٔ خطا و کاهش خطای الگوریتم‌های احتمالاتی ۱ و ۲ (لینکش را پیدا نکردم) ۵ دی
آقای افرشته همیلتونی بودن و طیف گراف ۱ ۲ ۷ دی
آقای معصومی ؟ ؟ ۷ دی

پاسخ دهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *