Задачу про потік найменшої вартості можна подати у

вигляді задачі лінійного програмування.  

Задачу про потік

найменшої вартості можна подати у вигляді задачі лінійного програмування. Для

кожної вершини записується обмеження, що задає баланс потоку, який проходить

через дану вершину:

Задача пошуку потоку

найменшої вартості в мережі з обмеженою пропускною здатністю узагальнює задачу

визначення максимального потоку за такими параметрами:

Припустимо, що потрібно знайти максимальний потік між

джерелом

Задати орієнтований граф за допомогою матриці суміжності.

Нехай задано неорієнтований граф.

Визначити:

Мережа автодоріг, що проходять через деяку область, може забезпечити пропускні здатності (тис. автомашин за годину), які

вказані на рисунку. Потрібно визначити максимальний потік у заданій мережі.

Дано граф

Знайти кістякові дерева цього графа.

Визначити, які з графів мають Ейлерів цикл, Ейлерів шлях, а які не мають ні  Ейлерового шляху, ні Ейлерового циклу.

Задати граф за допомогою матриці суміжності.