الگوریتم‌های گراف (پاییز ۹۵-۹۶)

توصیف درس: الگوریتم‌های کمی پیشرفته‌تر گراف

در این درس با الگوریتم‌های کمی پیشرفته‌تر در گراف آشنا می‌شویم. هدف این درس آشنایی الگوریتم‌هایی است در مورد همبندی در گراف‌ها.

graph-c

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

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

  1. شار بیشینه: الگوریتم سادهٔ Ford و Fulkerson برای شار بیشینه. الگوریتم سریع‌تر شار بیشینه برای گراف بدون وزن.
  2. استفاده از شار بیشینه برای مسئله‌های ترکیبیاتی: شامل مسئله بیشترین مسیر یال-مجزا. تطابق بیشینهٔ بدون وزن در گراف دوبخشی. قضیهٔ Dilworth.
  3. درجهٔ هم‌بندی گراف: گراف‌های k-همبند. الگوریتم یافتن مولفه‌های دو-همبندی.
  4. تولید شبکه‌های معادل: ساده‌سازی گراف به درخت با حفظ شار معادل: یعنی یک گراف را ساده کنیم به حدی که یک درخت به دست بیاید، ولی میزان شار بین هر دو راس تغییری نکند.
  5. مجموعه‌های اکسترمال راسی: یافتن کم‌ترین تعداد راس که حذف آن‌ها گراف را به چند k مولفه تقسیم کند.
  6. تنک‌سازی: یک گراف را ساده کنیم تا یال‌های آن کم شود ولی اندازهٔ همهٔ برش‌های آن تقریبا ثابت بماند.
  7. رنگ‌آمیزی: رنگ‌آمیزی گراف‌های ایده‌آل. رنگ‌آمیزی یالی گراف. قضیهٔ پنج-رنگ.

البته ممکن است برخی مباحث دیگر در مورد همبندی به درس اضافه شود.

پیش‌نیاز

قرار نیست این درس، درس تحلیل الگوریتم را مرور کند، در نتیجه فرض می‌کنیم مستمعین کاملا با الگوریتم‌های ابتدایی و الگوریتم‌های گراف که در درس الگوریتم ارائه می‌شوند آشنا هستند. برای مثال الگوریتم‌های جستجوی عمقی و جستجوی سطحی را باید کاملا بدانند. فصل‌های ۱، ۲، ۳، ۴، و ۶ (بخش‌های ۲۲ (به جز ۲۲.۵) و ۲۳ و ۲۴ و ۲۵) از کتاب Introduction to Algorithms (نوشته CLRS) نیز پیش‌نیازهای این بخش از درس هستند.

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

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

منبع اصلی: Jungnickel, Dieter. Graphs, networks and algorithms. Berlin: Springer, 2008.

منبع کمکی:
Nagamochi, Hiroshi, and Toshihide Ibaraki.Algorithmic aspects of graph connectivity. Vol. 123. New York: Cambridge University Press, 2008.

مطالب مربوط به درس

اثبات اینکه اگر مسیر افزایشی که اعمال می‌کنیم کوتاه‌ترین مسیر باشد، فاصلهٔ هیچ راسی از s کم‌تر نخواهد شد:

در آویز اولین مرحله‌ای را در نظر بگیرید که در آن راسی فاصله‌اش از s کم‌تر شده. و در بین این راس‌هایی که فاصله‌شان از s کم‌تر شده راسی را بگیرید که از همه فاصله‌اش از s کم‌تر است. آن راس را v بنامیم.

آویز در مرحلهٔ قبل را A و آویز در این مرحله را A’ بنامیم.

کوتاه‌ترین مسیر از s به v در A’ را در نظر بگیریم. راس‌های قبل از v در این مسیر همگی چون فاصله‌شان کمتر است از s نسبت به v پس همه فاصله‌شان در A کم‌تر مساوی بوده. آن‌ها فاصله‌شان کم نشده، باید از راسی بالاتر به خود v یال جدیدی اضافه شده باشد. اما این تنها در صورتی امکان دارد که مسیری که A را به A’ تبدیل کرده یالی برداشته باشد رو به بالا و بین v و یکی از سطوح حداقل دو واحد بالاتر از v. که با روش یافتن کوتاه‌ترین مسیر در تناقض است.

مختصری در مورد الگوریتم های شار بیشینه

جلسات

جلسه موضوع فصل کتاب تمرین
۲ مروری بر تعریف شار بیشینه و برش کمینه و الگوریتم فورد-فالکرسون کتاب G:۶.۱ و ۶.۲ ۶.۱.۱۰، ۶.۱.۱۱، ۶.۱.۱۵،
۲ الگوریتم شار بیشینه با کوتاه‌ترین مسیر کتاب G:۶.۳
۳ الگوریتم شار بیشینه انسدادی کتاب G:۶.۴
۳ الگوریتم شار بیشینه برای گراف‌های ۰-۱ کتاب G:۶.۵
۴ کاربردهای ترکیبیاتی شار بیشینه: مسیرهای مجزا کتاب G:۷.۱ و ۸.۱ ۷.۱.۹، ۷.۱.۱۰، ۸.۱.۳،
کاربردهای ترکیبیاتی شار بیشینه: قضیهٔ کونیگ کتاب G:۷.۲ ۷.۲.۲، ۷.۲.۷، ۷.۲.۸
کاربردهای ترکیبیاتی شار بیشینه: ترکیبیات ماتریس‌ها کتاب G:۷.۴ ۷.۴.۱۳، ۷.۴.۱۴، ۷.۴.۱۵، ۷.۴.۱۶، ۷.۴.۱۷
هم‌بندی یالی کتاب G:۸.۶ ۸.۶.۲،
سنتر شبکه و الگوریتم گوموری-هو کتاب G:۱۲.۱و G:۱۲.۲ و G:۱۲.۳
ترتیب MA کتاب C:۲.۱ و ۲.۱.۱ و ۲.۲ و ۲.۲.۱ و ۲.۲.۲
الگوریتم تقریبی برای برش کمینه کتاب C: ۲.۴
الگوریتم سریع‌تر شار بیشینه کتاب C:۲.۵.۱
چرخش کتاب G:۱۰.۱-۴
عرض درختی جزوه‌های و اسلایدهای آقای ولزلتمرین ۱ تمرین ۲

نمره‌بندی

موضوع نمره
کوئیز از مباحث کلاس ۲
کوئیز از تمرین‌ها ۵
میان‌ترم ۵
پایان‌ترم ۸

پاسخ دهید

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