جریان های شبکه

بسیاری از مشکلات در علوم کامپیوتر را می توان با یک نمودار متشکل از گره ها و پیوندهای بین آنها نشان داد. به عنوان مثال مشکلات جریان شبکه ، که شامل حمل و نقل کالا یا مواد در سراسر یک شبکه، مانند یک سیستم راه آهن است.

شما می توانید یک جریان شبکه را با یک نمودار نشان دهید که گره های آن شهرها و قوس های آن خطوط ریلی بین آنها هستند. (آنها را جریان می نامند زیرا خواص آنها شبیه به آبی است که از طریق شبکه ای از لوله ها جریان می یابد.)

یک محدودیت کلیدی در جریان شبکه این است که هر قوس دارای ظرفیت است - حداکثر مقداری که می تواند در یک دوره زمانی ثابت در سراسر قوس منتقل شود.

مشکل حداکثر جریان ، تعیین حداکثر مقدار کل است که می تواند در تمام قوس های شبکه منتقل شود، با توجه به محدودیت های ظرفیت.

اولین کسی که این مسئله را بررسی کرد، ریاضیدان روسی آن. تولستوی در دهه 1930 بود. نقشه زیر شبکه راه آهن واقعی را نشان می دهد که او می خواست حداکثر جریان را برای آن پیدا کند.

OR-Tools چندین حل کننده برای مشکلات جریان شبکه در کتابخانه های گراف خود فراهم می کند.

بخش های زیر نمونه هایی از مشکلات جریان شبکه را ارائه می دهند و نحوه حل آنها را نشان می دهند:

• حداکثر جریان
• جریان های حداقل هزینه
• تخصیص به عنوان جریان حداقل هزینه
• تکلیف با تیم های کارگری