معکوس مساُلهُ برش k تایی مرتب کمینه

فرض کنید نشان دهندهُ مجموعهُ نقاط شدنی مسألهُ بهینه سازی باشد، همچنین فرض کنید ، و بیانگر بردار هزینهُ این مسأله باشد. معکوس مساُلهُ نسبت به جواب شدنی عبارت است از، پیدا کردن بردار هزینهُ بطوریکه نسبت به بردار هزینهُ یک جواب بهینه برای مساُلهُ باشد، بعلاوه مقدار نیز کمینه شود ( نشان دهندهُ نرم می باشد). در این تحقیق ابتدا چند نوع برش روی یک شبکهُ جهتدار تعریف می شود و در هر نوع برش، الگوریتمی جهت بدست آوردن برش کمینهُ مربوطه ارائه می گردد. در ادامه، مساُلهُ برش k تایی مرتب کمینه معرفی و حل می گردد، سپس معکوس آن تحت نرمهای و را بررسی می کنیم و نشان می دهیم حل این مسائل به حل تعداد چند جمله ایی مساُلهُ شبکهُ جریان تبدیل می گردند.تعریف مدل گراف همبند و جهت دار را در نظر بگیرید. برای هر کمان ظرفیت اختصاص دارد و قرار می دهیم . زیر مجموعهُ از مجموعه گره های که هم تولید کننده و هم مصرف کننده هستند را در نظر بگیرید . گره و زیر مجموعهُ سرهُ از را چنان در نظر می گیریم که . در اینصورت توسط مجموعهُ ، برش گره ای متناظر با گرهُ را که با نشان می دهیم می توان تعریف کرد، که برابر است با مجموعهُ کمانهایی که یک راُس از را به یک راُس از ، یا بر عکس وصل کنند. برای برش گره ای مجموعهُ کمانهای را مجموعهُ کمانهای پیشرو نامیده و با ، و مجموعهُ کمانهای را مجموعهُ کمانهای پسرو نامیده و با نشان می دهیم. ظرفیت برش گره ای را با نشان داده و بصورت = تعریف می کنیم. مساُلهُ برش گره ای کمینهُ متناظر با گره ُ ، عبارت است از پیدا کردن برش گره ای کمینه برای گرهُ . برای مجموعهُ ، برش k تایی متناظر با گرهُ را برابر اجتماع برشهای گره ای و و...و و و...و تعریف می کنیم. مجموعهُ کمانهای پیشرو و مجموعهُ کمانهای پسروی برش k تایی نظیر گرهُ را به ترتیب برابر با اجتماع مجموعهُ کمانهای پیشرو و پسروی برشهای گره ای تشکیل دهنده آن تعریف می کنیم