حسن صالحی فتح آبادی - دانشگاه تهران
مهدی سلطانی فر - دانشگاه آزاد اسلامی واحد علوم و تحقیقات
علی ابراهیم نژاد

در شبکه های جریان تک کالایی، ظرفیت سیستم برابر ماکزیمم مقدار جریان ارسالی از منبع به مقصد تعریف می شود، بدیهی است که ظرفیت سیستم برای یک شبکه جریان قطعی، مقدار ثابتی است ولی برای یک شبکه جریان تصادفی (شبکه ای که در آن ظرفیت هر کمان، مقداری تصادفی است) متغیراست. از این رو لازم است اعتمادپذیری سیستم محاسبه گردد. این محاسبه از دو راه انجام می‌شود؛ احتمال اینکه ظرفیت سیستم از D بزرگتر شود و یا از D کمتر شود که D یک بردار سطح ظرفیت معین می‌باشد(لازم به ذکر است که در حالت تک کالایی، این دو راه مکمل یکدیگر می باشند و در حالت P کالایی (P≥2)، دو راه متفاوت می باشند). دو راه مذکور به ترتیب برحسب مسیرهای مینیمال و برشهای مینیمال محاسبه می‌شوند. در این مقاله پس از معرفی تخصیص جریان، با استفاده از خواص برش های مینیمال الگوریتم کارایی برای محاسبه اعتمادپذیری سیستم در حالت کلی، با P نوع کالا، پیشنهاد می‌گردد، به طور تجربی این الگوریتم نسبت به روش ها و الگوریتم های مشابه که از برشهای مینیمال استفاده نمی کنند، به مراتب بهتر است

شبکه‌های جریان تصادفی، مسیر مینیمال، برش مینیمال، اعتمادپذیری