ماکزیمم جریان در شبکه‌های متعادل

توضیحات

🟣 معرفی کلی کتاب و هدف آن

کتاب «ماکزیمم جریان در شبکه‌های متعادل» تألیف مرضیه فلاحت، اثری تخصصی در حوزه نظریه گراف، بهینه‌سازی شبکه‌ها و مدارهای الکتریکی و محاسباتی است که به بررسی ساختار، تحلیل و الگوریتم‌های یافتن بیشینه جریان در انواع شبکه‌های ارتباطی و انتقال با تأکید بر شبکه‌های متعادل و چندمسیری می‌پردازد.

هدف اصلی این کتاب، ارائه مبانی نظری و روش‌های الگوریتمی دقیق برای حل مسائل جریان شبکه و بهینه‌سازی ظرفیت‌هاست. اثر با تعریف مفاهیم بنیادین گراف، شبکه‌های جریان، برش‌ها و شبکه‌های مانده آغاز می‌شود و سپس مسائل پیشرفته‌تری نظیر ظرفیت پایانه‌ها در شبکه‌های بدون جهت، جریان‌های چندمسیری ($K$-مسیری) و جریان‌های متعادل کمانی و رأسی را با ارائه الگوریتم‌های تخصصی (همچون الگوریتم‌های مسیر افزایشی، روش مایدا، الگوریتم کیشی‌موتو، آگاروال و اورلین) و پیوست‌های کاربردی تحلیل می‌کند.

🟣 خلاصه

محتوای کتاب بر پایه فهرست مطالب در چهار فصل اصلی و دو پیوست ساختاریافته است:

• فصل اول: مفاهیم و تعاریف مقدماتی (ص. ۲)

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

• فصل دوم: ظرفیت پایانه در شبکه‌ی بدون جهت (ص. ۳۰)

  ماتریس ظرفیت پایانه، ارتباط ماتریس ظرفیت پایانه و ماتریس ظرفیت یالی، روش مایدا (Mayeda)، ماتریس ظرفیت پایانه مقدماتی، روش‌های ساخت شبکه‌ای با کمترین مجموع ظرفیت یال‌ها برای ماتریس ظرفیت پایانه و الگوریتم A.

• فصل سوم: شبکه‌ی جریان $K$-مسیری (ص. ۷۳)

  جریان ۲-مسیری در شبکه‌های بدون جهت، مفاهیم و تعاریف جریان $K$-مسیری، مسأله ماکزیمم جریان $K$-مسیری، تعمیم الگوریتم مسیر افزایشی برای جریان‌های $K$-مسیری و بررسی الگوریتم‌های تخصصی کیشی‌موتو (Kishimoto) و آگاروال–اورلین (Aggarwal & Orlin).

• فصل چهارم: شبکه‌ی جریان متعادل (ص. ۱۱۳)

  بررسی جریان $\delta$-معتبر کمانی و الگوریتم محاسبه ظرفیت $\delta$-معتبر کمانیِ یک برش، جریان $\delta$-معتبر رأسی و الگوریتم محاسبه ظرفیت آن در برش مخلوط، جریان $(\delta ,\eta )$-متعادل، الگوریتم محاسبه $(\delta ,\eta )$-ظرفیت از یک برش مخلوط و الگوریتم محاسبه ماکزیمم جریان $(\delta ,\eta )$-متعادل.

• پیوست‌ها و بخش‌های پایانی:

  • پیوست آ (ص. ۱۴۲): الگوریتم برچسب‌گذاری.
  • پیوست ب (ص. ۱۴۵): الگوریتم ساختن شبکه‌ای با کمترین مجموع ظرفیت یال‌ها برای یک ماتریس ظرفیت پایانه، $\beta$-افرازبندی و الگوریتم M.
  • مراجع (ص. ۱۶۳)، واژه‌نامه فارسی به انگلیسی (ص. ۱۶۵) و واژه‌نامه انگلیسی به فارسی (ص. ۱۶۷).