Элементы Комбинаторики

Шаг 2. Изучая i-ю и .j-ю строки матрицы весов, выбираем ребро минмального веса, инцидентное одной из двух вершин. Присоединяем выбранное ребро к остову и удаляем из матрицы весов. 
И так далее. Процесс повторяется до тех пор, пока в остов не будут включены все вершины графа.

Алгоритм Дейкстры 
Алгоритм Дейкстры позволяет, решить задачу о нахождении кратчайшего пути в графе. 
Особенностью алгоритма Дейкстры является то, что он позволяет найти кратчайшее расстояние от начальной вершины графа до всех остальных, что очень удобно, например, при моделировании сети дорог. 

Понятие потока в сети 
Примеры сетей и потоков в них: потоки автомобильного транспорта в сети автодорог, поток грузов по железнодорожной сети, поток телегр сообщений в сети связи и т.д. Все эти сети имеют огранич ресурс( поток ограничен сверху).  
Ориентир граф называется сетью, если он удовлетвор. след условиям: 

1. он связный граф без петель

2. существует ровно одна вершина, степень входа которой равна нулю(источник)

3. существует ровно одна вершина, степень выхода которой равна нулю(сток)

4. каждой дуге поставлено в соответствие неотриц. число, называемое пропускной способностью

Функция φ, определенная на множестве дуг сети, называется допустимым потоком, если: 
для любой дуги ei выполнено условие 0≤φ≤с(ei)

т.е. для любой дуги допустимый поток не превышает её пропускной способности. 
2.   для любой промежуточной величины выполнено условие баланса (условие сохранения потока): сумма потоков, втекающих в вершину, равна сумме вытекающих потоков, т.е. в промежуточных вершинах потоки не создаются и не исчезают. 
Величина  называется остаточной пропускной способностью дуги. 
Дуга ei  называется насыщенной, если  (если допустимый поток равен пропускной способностью)  
Суммарный поток, вытекающий из источника, равен суммарному потоку, втекающему в сток. Этот поток будем называть потоком в сети. 

Полный и максимальный потоки в сети 
Поток называется полным, если путь из источника в сток содержит хотя бы одну насыщенную дугу. 
Поток называется максимальным, если он принимает максимальное значение по сравнению с остальными потоками в сети.